算法程序與計算系統(tǒng)之靈魂最全課件

算法程序與計算系統(tǒng)之靈魂算法程序與計算系統(tǒng)之靈魂基本目標:

理解算法類問題求解框架內(nèi)容提要基本目標:理解算法類問題求解框架內(nèi)容提要算法：程序與計算系統(tǒng)之靈魂1.算法與算法類問題求解算法與算法類問題求解----什么是算法----算法類問題及求解概述算法：程序與計算系統(tǒng)之靈魂算法與算法類問題求解算法算法---計算學科和計算機器的靈魂?！八惴ā?Algorithm)一詞源于數(shù)學家的名字：公元825年，阿拉伯數(shù)學家阿科瓦里茨米(AlKhowarizmi)寫了著名的《波斯教科書》(PersianTextbook)，書中概括了進行四則算術(shù)運算的計算規(guī)則。算法是一個有窮規(guī)則的集合，它用規(guī)則規(guī)定了解決某一特定類型問題的運算序列，或者規(guī)定了任務(wù)執(zhí)行或問題求解的一系列步驟。1.算法與算法類問題求解1.1什么是算法?如音樂樂譜、太極拳譜等都可看作廣義的算法算法算法---計算學科和計算機器的靈魂?！八惴ā?Algor算法解決問題的步驟程序計算機能夠理解與執(zhí)行的解決問題的步驟計算機語言步驟書寫的規(guī)范、語法規(guī)則、標準的集合是人和計算機都能理解的語言算法、語言與計算機程序1.算法與算法類問題求解1.2為什么算法很重要呢?“是否會編程序”，本質(zhì)上是“能否想出求解問題的算法”，其次才是將算法用計算機可以識別的形式書寫出來算法解決問題程序計算機能夠理解與計算機語言步驟書寫的規(guī)范、語歐幾里德算法：求解兩個數(shù)的最大公約數(shù)的算法(公元前300年)表述了最大公約數(shù)的求解過程表述了一個判定過程，即判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公約數(shù)）命題的真假。該算法體現(xiàn)了輸入、輸出、有窮規(guī)則、確定性和能行性等算法的基本特征。尋找兩個正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N)算法步驟：Step1.

M除以N,記余數(shù)為RStep2.如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。算法示例1.算法與算法類問題求解1.3什么是計算學科中的算法?歐幾里德算法：求解兩個數(shù)的最大公約數(shù)的算法(公元前300年)有窮性：一個算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。確定性：算法的每一個步驟必須要確切地定義，不得有歧義性。輸入：算法有零個或多個的輸入。輸出：算法有一個或多個的輸出/結(jié)果，即與輸入有某個特定關(guān)系的量。能行性：算法中有待執(zhí)行的運算和操作必須是相當基本的(可以由機器自動完成)。并能在有限時間內(nèi)完成。算法的基本特征1.算法與算法類問題求解1.4具備什么特征才能被認為是算法?基本運算：除法、賦值、邏輯判斷典型的“重復/循環(huán)”與“迭代”尋找兩個正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N)算法步驟：Step1.

M除以N,記余數(shù)為RStep2.如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。有窮性：一個算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。算法的基本特征算法(類)問題：尋找一個(唯一的)方法(算法)以解決同一類型的無窮多個單個問題系列的問題。典型問題：哥尼斯堡七橋問題：“尋找走遍這7座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”“對給定的任意一個河道圖與任意多座橋判定可能不可能每座橋恰好走過一次?”。梵天塔問題：有三根柱子，梵天將64個直徑大小不一的金盤子按照從大到小的順序依次套放在第一根柱子上形成一座金塔，要求每次只能移動一個盤子，盤子只能在三根柱子上來回移動不能放在他處，在移動過程中三根柱子上的盤子必須始終保持大盤在下小盤在上。其他如：背包問題，丟番圖方程可解性問題；……1.算法與算法類問題求解1.5你知道一些典型的算法類問題嗎?算法類問題：由一個算法可以解決的問題算法(類)問題：尋找一個(唯一的)方法(算法)以解決同一類型TSP問題(TravelingSalesmanProblem，旅行商問題)，威廉哈密爾頓爵士和英國數(shù)學家克克曼于19世紀初提出TSP問題．TSP問題：有若干個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費用最少。TSP是最有代表性的組合優(yōu)化問題之一，在半導體制造(線路規(guī)劃)、物流運輸(路徑規(guī)劃)等行業(yè)有著廣泛的應(yīng)用。城市之間的距離1.算法與算法類問題求解1.6你知道TSP問題嗎?算法類問題示例TSP問題(TravelingSalesmanProbl問題抽象及數(shù)學建模：將問題抽象為一個數(shù)學問題，并給出求解該數(shù)學問題的算法模型。算法策略設(shè)計算法的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)設(shè)計：將數(shù)學模型轉(zhuǎn)換為可由計算機自動計算的算法。算法的實現(xiàn)：用程序設(shè)計語言編寫算法實現(xiàn)的程序。算法的分析：分析算法的正確性和復雜性，判斷能行性！1.算法與算法類問題求解1.7你知道算法類問題求解的一般步驟嗎?算法類問題求解框架問題抽象及數(shù)學建模：將問題抽象為一個數(shù)學問題，并給出求解該數(shù)算法：程序與計算系統(tǒng)之靈魂2.數(shù)學建模與算法策略設(shè)計---算法思想數(shù)學建模與算法策略設(shè)計---算法思想----數(shù)學建模----有不同的算法求解策略算法：程序與計算系統(tǒng)之靈魂數(shù)學建模與算法策略設(shè)計---算法思算法類問題求解的第一步就是要數(shù)學建模。數(shù)學建模：是一種數(shù)學的思考方法，是運用數(shù)學的語言和方法，通過抽象、簡化建立對問題進行精確描述和定義的數(shù)學模型。簡單而言，數(shù)學建模是用數(shù)學語言描述實際現(xiàn)象的過程，即建立數(shù)學模型的過程。數(shù)學模型是對實際問題的一種數(shù)學表述，是關(guān)于部分現(xiàn)實世界為某種目的的一個抽象的簡化的數(shù)學結(jié)構(gòu)。2.數(shù)學建模與算法策略設(shè)計---算法思想2.1為什么說數(shù)學建模對于算法很重要?將現(xiàn)實世界的問題抽象成數(shù)學模型，就可能發(fā)現(xiàn)問題的本質(zhì)及其能否求解，甚至找到求解該問題的方法和算法。算法類問題求解的第一步就是要數(shù)學建模。2.數(shù)學建模與算法策略哥尼斯堡七橋問題被抽象成一個“圖(Graph)”--由節(jié)點和邊所構(gòu)成的一種結(jié)構(gòu)，--依據(jù)“圖”，可發(fā)現(xiàn)該問題所蘊含的許多性質(zhì)：“回路---從一個節(jié)點出發(fā)最后又回到該節(jié)點的一條路徑”“連通----兩個節(jié)點間有路徑相連接”“可達----從一個節(jié)點出發(fā)能夠到達另一個節(jié)點”“經(jīng)過圖中每邊一次且僅一次的回路”“經(jīng)過圖中每個節(jié)點一次且僅一次的回路”

什么情況下有解，什么情況下無解？注：《離散數(shù)學》或者《集合論與圖論》課程將介紹圖的有關(guān)性質(zhì)和方法。2.數(shù)學建模與算法策略設(shè)計---算法思想2.1為什么說數(shù)學建模對于算法很重要?如果能抽象成數(shù)學模型，則可將一個具體問題的求解，推廣為一類問題的求解！哥尼斯堡七橋問題被抽象成一個“圖(Graph)”2.數(shù)學建模TSP問題的數(shù)學模型2.數(shù)學建模與算法策略設(shè)計---算法思想2.2數(shù)學建模要做到怎樣?TSP問題的數(shù)學模型2.數(shù)學建模與算法策略設(shè)計---算法思想算法策略設(shè)計---算法思想當數(shù)學建模完成后，就要設(shè)計算法的策略或者說問題求解的策略。TSP問題的基本求解策略遍歷：列出每一條可供選擇的路線，計算出每條路線的總里程，最后從中選出一條最短的路線。出現(xiàn)的問題是：組合爆炸路徑組合數(shù)目：(n-1)!20個城市，遍歷總數(shù)1.216×1017計算機以每秒檢索1000萬條路線的計算速度，需386年。所有路徑組合及其長度城市之間的距離2.數(shù)學建模與算法策略設(shè)計---算法思想2.3算法思想或者算法策略對問題求解有什么影響?算法策略設(shè)計---算法思想當數(shù)學建模完成后，就要設(shè)計算法的策TSP問題的難解性：隨著城市數(shù)量的上升，TSP問題的“遍歷”方法計算量劇增，計算資源將難以承受。2001年解決了德國15112個城市的TSP問題，使用了美國Rice大學和普林斯頓大學之間互連的、速度為500MHz

的CompaqEV6Alpha處理器組成的110臺計算機，所有計算機花費的時間之和為22.6年。AnoptimalTSPtourthroughGermany’s15largestcities.Itistheshortestamong43589145600possibletoursvisitingeachcityexactlyonce.2.數(shù)學建模與算法策略設(shè)計---算法思想2.3算法思想或者算法策略對問題求解有什么影響?TSP問題的難解性：隨著城市數(shù)量的上升，TSP問題的“遍歷”TSP問題，有沒有其他求解算法呢？最優(yōu)解

vs.可行解不同的算法設(shè)計策略：遍歷、搜索算法分治算法貪心算法動態(tài)規(guī)劃算法……可選取一種合適的策略來求解TSP問題可行解最優(yōu)解TSP問題的可行解與最優(yōu)解示意2.數(shù)學建模與算法策略設(shè)計---算法思想2.4有哪些算法策略?算法策略設(shè)計---算法思想TSP問題，有沒有其他求解算法呢？可行解最優(yōu)解TSP問題的可貪心算法是一種算法策略，或者說問題求解的策略?；舅枷搿敖癯芯平癯怼?。一定要做當前情況下的最好選擇，否則將來可能會后悔，故名“貪心”。TSP問題的貪心算法求解思想從某一個城市開始，每次選擇一個城市，直到所有城市都被走完。每次在選擇下一個城市的時候，只考慮當前情況，保證迄今為止經(jīng)過的路徑總距離最短。城市之間的距離2.數(shù)學建模與算法策略設(shè)計---算法思想2.5為什么稱為“貪心算法”?貪心算法貪心算法是一種算法策略，或者說問題求解的策略?；舅枷搿敖癯惴ǎ撼绦蚺c計算系統(tǒng)之靈魂3.算法設(shè)計---算法思想的精確表達算法設(shè)計---算法思想的精確表達(I)----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計----算法的控制結(jié)構(gòu)設(shè)計及其表達方法----TSP算法解讀算法：程序與計算系統(tǒng)之靈魂算法設(shè)計---3.算法設(shè)計---算法思想的精確表達3.1算法設(shè)計包括什么?算法設(shè)計算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計---問題或算法相關(guān)的數(shù)據(jù)之間的邏輯關(guān)系及存儲關(guān)系的設(shè)計算法的控制結(jié)構(gòu)設(shè)計---算法的計算規(guī)則或計算步驟設(shè)計如何構(gòu)造和表達處理的規(guī)則，以便能夠按規(guī)則逐步計算出結(jié)果?如何將數(shù)學模型中的數(shù)據(jù)轉(zhuǎn)為計算機可以存儲和處理的數(shù)據(jù)？3.算法設(shè)計---算法思想的精確表達算法設(shè)計算法的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)如何組織、記憶、改變和操作數(shù)據(jù)的集合呢？數(shù)據(jù)存在什么結(jié)構(gòu)呢？數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的關(guān)系；數(shù)學模型中反映的通常是數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)：在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在存儲器中的存儲方式。典型的有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。面向數(shù)據(jù)存儲結(jié)構(gòu)的基本運算：(1)建立數(shù)據(jù)結(jié)構(gòu)；(2)清除數(shù)據(jù)結(jié)構(gòu)；(3)插入數(shù)據(jù)元素；(4)刪除數(shù)據(jù)元素；(5)更新數(shù)據(jù)元素；(6)查找數(shù)據(jù)元素；(7)按序重新排列；(8)判定某個數(shù)據(jù)結(jié)構(gòu)是否為空，或是否已達到最大允許的容量；(9)統(tǒng)計數(shù)據(jù)元素的個數(shù)等。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其操作的總稱，它提供了問題求解/算法的數(shù)據(jù)操縱機制。3.算法設(shè)計---算法思想的精確表達3.2什么是數(shù)據(jù)結(jié)構(gòu)?數(shù)據(jù)結(jié)構(gòu)3.算法設(shè)計---算法思想的精確表達3.算法設(shè)計---算法思想的精確表達3.2什么是數(shù)據(jù)結(jié)構(gòu)?典型的數(shù)據(jù)結(jié)構(gòu)---“樹”示例存儲結(jié)構(gòu)中,用一個指針表達數(shù)據(jù)之間的邏輯關(guān)系150120160數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)503070100數(shù)據(jù)元素對應(yīng)數(shù)據(jù)元素的指針—指向該元素的父元素數(shù)據(jù)結(jié)構(gòu)的設(shè)計3.算法設(shè)計---算法思想的精確表達典型的數(shù)據(jù)結(jié)構(gòu)---150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)通過指針的變化,不改變數(shù)據(jù)的存儲,但卻改變了數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)結(jié)構(gòu)的設(shè)計3.算法設(shè)計---算法思想的精確表達3.2什么是數(shù)據(jù)結(jié)構(gòu)?150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲150120160503070100數(shù)據(jù)元素對應(yīng)數(shù)據(jù)元素的左指針—指向該元素的左側(cè)子結(jié)點對應(yīng)數(shù)據(jù)元素的右指針—指向該元素的右側(cè)子結(jié)點3.算法設(shè)計---算法思想的精確表達3.3同樣的邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)嗎?數(shù)據(jù)結(jié)構(gòu)的設(shè)計典型的數(shù)據(jù)結(jié)構(gòu)---“樹”示例另一種存儲結(jié)構(gòu),用兩個指針表達數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)不同，數(shù)據(jù)之間的操作方法也是不同的150120160503070100數(shù)據(jù)元素對應(yīng)數(shù)據(jù)元素的左1501201605030701003.算法設(shè)計---算法思想的精確表達3.3同樣的邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)嗎?數(shù)據(jù)結(jié)構(gòu)的設(shè)計典型的數(shù)據(jù)結(jié)構(gòu)---“樹”示例另一種存儲結(jié)構(gòu),用兩個指針(左指針和右指針)表達數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)110Null動手練習一下1501201605030701003.算法設(shè)計---算法向量或列表或數(shù)組。矩陣或表向量實例n=4;Sum=0; ForJ=0tonStep1

{

Sum=Sum+mark[J]; }

NextJ

Avg=Sum/n;

多元素變量及其程序處理(前講介紹的)3.算法設(shè)計---算法思想的精確表達3.4多元素變量結(jié)構(gòu)是怎樣的?112522254539844212801003483751612341234行列M[2,3]表實例Sum=0; ForI=1to4Step1{ForJ=1to4Step1{Sum=Sum+M[I][J];}NextJ

}NextI

Avg=Sum/16;向量或列表或數(shù)組。向量實例n=4;多元素數(shù)據(jù)結(jié)構(gòu)設(shè)計就是針對選定的算法策略，設(shè)計其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及其運算規(guī)則。不同的算法可能有不同的數(shù)據(jù)結(jié)構(gòu)及其運算規(guī)則！城市映射為編號:A---1,B---2,C---3,D---4城市間距離關(guān)系:表或二維數(shù)組D，用D[i][j]或D[i,j]來確定欲處理的每一個元素訪問路徑/解:一維數(shù)組S，用S[j]來確定每一個元素1432{A->D->C->B->A}SS[1]S[2]S[3]S[4]DD[2][3]3.算法設(shè)計---算法思想的精確表達3.5一個問題中應(yīng)該設(shè)計哪些數(shù)據(jù)結(jié)構(gòu)?TSP問題的數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計就是針對選定的算法策略，設(shè)計其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及其算法：程序與計算系統(tǒng)之靈魂3.算法設(shè)計---算法思想的精確表達算法設(shè)計---算法思想的精確表達(II)----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計----算法的控制結(jié)構(gòu)設(shè)計及其表達方法----TSP算法解讀算法：程序與計算系統(tǒng)之靈魂算法設(shè)計---順序結(jié)構(gòu)：“執(zhí)行A，然后執(zhí)行B”，是按順序執(zhí)行一條條規(guī)則的一種結(jié)構(gòu)。分支結(jié)構(gòu)：“如果Q成立，那么執(zhí)行A，否則執(zhí)行B”，Q是某些邏輯條件，即按條件判斷結(jié)果決定執(zhí)行哪些規(guī)則的一種結(jié)構(gòu)。循環(huán)結(jié)構(gòu)：控制指令或規(guī)則的多次執(zhí)行的一種結(jié)構(gòu)---迭代(iteration)循環(huán)結(jié)構(gòu)又分為有界循環(huán)結(jié)構(gòu)和條件循環(huán)結(jié)構(gòu)。有界循環(huán)：“執(zhí)行A指令N次”，其中N是一個整數(shù)。條件循環(huán)：某些時候稱為無界循環(huán)，“重復執(zhí)行A直到條件Q成立”或“當Q成立時反復執(zhí)行A”，其中Q是條件。算法與程序的基本控制結(jié)構(gòu)3.算法設(shè)計---算法思想的精確表達3.6怎樣表達算法的步驟呢?順序結(jié)構(gòu)：“執(zhí)行A，然后執(zhí)行B”，是按順序執(zhí)行一條條規(guī)則的一流程圖的基本表示符號

矩形框：表示一組順序執(zhí)行的規(guī)則或者程序語句。菱形框：表示條件判斷，并根據(jù)判斷結(jié)果執(zhí)行不同的分支。圓形框：表示算法或程序的開始或結(jié)束。箭頭線：表示算法或程序的走向。算法與程序構(gòu)造的表達方法：程序流程圖3.算法設(shè)計---算法思想的精確表達3.7怎樣繪制流程圖?流程圖的基本表示符號算法與程序構(gòu)造的表達方法：程序流程圖3三種控制結(jié)構(gòu)的流程圖表示方法示意開始第1條規(guī)則或語句第n條規(guī)則或語句結(jié)束順序結(jié)構(gòu)的流程圖開始條件成立否？是否條件成立時執(zhí)行的規(guī)則或語句結(jié)束條件不成立時執(zhí)行的規(guī)則或語句分支結(jié)構(gòu)的流程圖循環(huán)結(jié)構(gòu)的流程圖初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句。即：循環(huán)體結(jié)束是否循環(huán)結(jié)束3.算法設(shè)計---算法思想的精確表達3.7怎樣繪制流程圖?算法與程序構(gòu)造的表達方法：程序流程圖三種控制結(jié)構(gòu)的流程圖表示方法示意開始第1條規(guī)則或語句第n條規(guī)循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示方法示意初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句結(jié)束是否循環(huán)結(jié)束有界循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)確定)初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句結(jié)束否循環(huán)未結(jié)束是條件循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)不確定)3.算法設(shè)計---算法思想的精確表達3.7怎樣繪制流程圖?算法與程序構(gòu)造的表達方法：程序流程圖循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示方法示意初始化部分開始循環(huán)控制算法思想及算法流程圖表示示例歐幾里德算法流程圖3.算法設(shè)計---算法思想的精確表達3.7怎樣繪制流程圖?算法與程序構(gòu)造的表達方法：程序流程圖算法思想及算法流程圖表示示例3.算法設(shè)計---算法思想的精步驟描述法，即用人們?nèi)粘Ｊ褂玫恼Z言和數(shù)學語言描述算法的步驟。

例如：sum=1+2+3+4+…+n求和問題的算法描述

Startofthealgorithm(算法開始)(1)輸入N的值；(2)設(shè)i的值為1；sum的值為0；(3)如果i<=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(7)步執(zhí)行；(4)計算sum+i，并將結(jié)果賦給sum；(5)計算i+1，并將結(jié)果賦給i;(6)返回到第3步繼續(xù)執(zhí)行；(7)輸出sum的結(jié)果。Endofthealgorithm(算法結(jié)束)

3.算法設(shè)計---算法思想的精確表達3.8自然語言表述算法有什么問題?算法與程序構(gòu)造的表達方法：步驟描述法自然語言表示的算法容易出現(xiàn)二義性、不確定性等問題步驟描述法，即用人們?nèi)粘Ｊ褂玫恼Z言和數(shù)學語言描述算法的步驟。算法：程序與計算系統(tǒng)之靈魂3.算法設(shè)計---算法思想的精確表達算法設(shè)計---算法思想的精確表達(III)----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計----算法的控制結(jié)構(gòu)設(shè)計及其表達方法----TSP算法解讀算法：程序與計算系統(tǒng)之靈魂算法設(shè)計---求解TSP問題的遍歷算法遍歷所有的組合路徑；累加一條路徑的距離之和；判斷某條路徑的距離是不是比當前最短路徑距離短；如果是，則用新路徑取代當前最短路徑，并記錄其距離；直到所有路徑比較完畢；……當前最短路徑設(shè)為空，當前最短距離設(shè)為最大值開始所有路徑組合完畢否？結(jié)束否是組合一條新路徑并計算該路徑的距離比當前最短距離小嗎？將該路徑記錄為當前最短路徑，并用其距離值更新當前最短距離輸出當前最短路徑及當前最短距離是否3.算法設(shè)計---算法思想的精確表達3.9算法的控制結(jié)構(gòu)如何設(shè)計?將思想/策略轉(zhuǎn)變?yōu)椤安襟E”求解TSP問題的遍歷算法當前最短路徑設(shè)為空，當前最短距離設(shè)為步驟描述法表示的求解TSP問題的貪心算法城市用數(shù)字編號來表示,1,2…,N任何兩個城市的距離記錄在數(shù)組D[i,j]中依次訪問過的城市編號被記錄在S[1],S[2],…,S[N}中,即第i次訪問的城市記錄在S[i]中。Step(1)：從第1個城市開始訪問起，將城市編號1賦值給S[1]。Step(6)：第I次訪問的城市為城市j，其距第I-1次訪問城市的距離最短。3.算法設(shè)計---算法思想的精確表達3.9算法的控制結(jié)構(gòu)如何設(shè)計?StartoftheAlgorithm(1)S[1]=1;(2)Sum=0;(3)初始化距離數(shù)組D[N,N];(4)I=2;(5)從所有未訪問過的城市中查找距離S[I-1]最近的城市j;(6)S[I]=j;(7)I=I+1;(8)Sum=Sum+Dtemp;(9)如果I<=N，轉(zhuǎn)步驟(5)，否則，轉(zhuǎn)步驟(10);(11)Sum=Sum+D[1,j]；(12)逐個輸出S[N]中的全部元素;(13)輸出Sum。EndoftheAlgorithm步驟描述法表示的求解TSP問題的貪心算法3.算法設(shè)計---步驟描述法表示的求解TSP問題的貪心算法(Cont.)前述第5步“從所有未訪問過的城市中查找距離S[I-1]最近的城市j”還是不夠明確，需要進一步細化3.算法設(shè)計---算法思想的精確表達3.9算法的控制結(jié)構(gòu)如何設(shè)計?(5.1)K=2;(5.2)將Dtemp設(shè)為一個大數(shù)(比所有兩個城市之間的距離都大)(5.3)L=1；(5.4)如果S[L]==K，轉(zhuǎn)步驟5.8；//該城市已出現(xiàn)過，跳過(5.5)L=L+1；(5.6)如果L<I，轉(zhuǎn)5.4；(5.7)如果D[K,S[I-1]]<Dtemp;j=K;Dtemp＝D[K,S[I-1]]；(5.8)K=K+1;(5.9)如果K<=N，轉(zhuǎn)步驟5.3。步驟描述法表示的求解TSP問題的貪心算法(Cont.)3.數(shù)學建模與算法策略設(shè)計---算法思想徑大小不一的金盤子按照從大到小的順序依次套放將現(xiàn)實世界的問題抽象成數(shù)學模型，就可能發(fā)現(xiàn)問題的本質(zhì)及其能否求解，甚至找到求解該問題的方法和算法。如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。如果實例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計方法對若干問題實例的算法結(jié)果與最優(yōu)解進行對比分析，即可對其進行效果評價；數(shù)學建模：是一種數(shù)學的思考方法，是運用數(shù)學的語言和方法，通過抽象、簡化建立對問題進行精確描述和定義的數(shù)學模型。TSP問題的貪心算法求解思想條件不成立時執(zhí)行的規(guī)則或語句2什么是數(shù)據(jù)結(jié)構(gòu)?分支結(jié)構(gòu)：“如果Q成立，那么執(zhí)行A，否則執(zhí)行B”，Q是某些邏輯條件，即按條件判斷結(jié)果決定執(zhí)行哪些規(guī)則的一種結(jié)構(gòu)。S[1]S[2]S[3]S[4]算法設(shè)計---算法思想的精確表達TSP問題貪心算法程序?qū)嵗?12)逐個輸出S[N]中的全部元素;算法與程序構(gòu)造的表達方法：步驟描述法NextJ(5)計算i+1，并將結(jié)果賦給i;程序設(shè)計過程：一般經(jīng)過編輯源程序編譯鏈接執(zhí)行。流程圖表示的求解TSP問題的貪心算法3.算法設(shè)計---算法思想的精確表達3.9算法的控制結(jié)構(gòu)如何設(shè)計?數(shù)學建模與算法策略設(shè)計---算法思想流程圖表示的求解TSP問算法思想解讀計算學科的學生不僅能夠設(shè)計算法，而且會描述和表達算法，更要能讀懂算法。外層循環(huán)，I從2至N循環(huán)；I-1個城市已訪問過，正在找與第I-1個城市最近距離的城市；已訪問過的城市號存儲在S[]中。中層循環(huán),K從第2個城市至第N個城市循環(huán),判斷D[K,S[I-1]]是否是最小值，j記錄了最小距離的城市號K。內(nèi)層循環(huán)，L從1至I-1,循環(huán)判斷第K個城市是否是已訪問過的城市，如是則不參加最小距離的比較；3.算法設(shè)計---算法思想的精確表達3.10你能夠讀懂流程圖嗎?算法思想解讀外層循環(huán)，I從2至N循環(huán)；I-1個城市已訪問過，算法：程序與計算系統(tǒng)之靈魂4.算法實現(xiàn)---程序設(shè)計算法實現(xiàn)---程序設(shè)計算法：程序與計算系統(tǒng)之靈魂算法實現(xiàn)---程序設(shè)計一個盤子，盤子只能在三根柱子上來回移動不能放數(shù)學建模與算法策略設(shè)計---算法思想算法設(shè)計---算法思想的精確表達列出每一條可供選擇的路線，計算出每條路線的總里程，最后從中選出一條最短的路線----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計TSP問題貪心算法程序?qū)嵗齌SP問題貪心算法的效果評價：循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示方法示意算法設(shè)計---算法思想的精確表達訪問路徑/解:一維數(shù)組S，用S[j]來確定每一個元素算法的實現(xiàn)程序是算法的一種機器相容(Compatible)的表示，是利用計算機程序設(shè)計語言對算法描述的結(jié)果，是可以在計算機上執(zhí)行的算法。計算機語言是書寫算法步驟地規(guī)范、標準、語法規(guī)則等，以便使人和計算機能夠理解用計算機語言編寫出的程序(注：更重要的是使計算機能夠理解)。4.算法實現(xiàn)---程序設(shè)計4.1算法實現(xiàn)要選定計算機語言，你知道嗎?一個盤子，盤子只能在三根柱子上來回移動不能放算法的實現(xiàn)程序是程序設(shè)計過程：一般經(jīng)過編輯源程序

編譯

鏈接

執(zhí)行。所謂編輯源程序是利用程序編輯器，按照計算機語言的規(guī)范書寫程序的過程；所謂編譯是將編制好的源程序翻譯成機器可以執(zhí)行的機器代碼程序(又稱為目標代碼)的過程。所謂鏈接是將目標代碼與公用函數(shù)庫中的函數(shù)實現(xiàn)代碼集成起來形成最終可執(zhí)行程序的過程。所謂執(zhí)行就是程序的運行過程。計算機語言程序設(shè)計環(huán)境通常由一套書寫程序的語法規(guī)則、一個編譯程序、一個鏈接程序和一組編譯好的公用函數(shù)庫構(gòu)成。有些計算機語言同時也提供了相應(yīng)的編程環(huán)境、調(diào)試環(huán)境及集成開發(fā)環(huán)境等。算法的實現(xiàn)4.算法實現(xiàn)---程序設(shè)計4.1算法實現(xiàn)要選定計算機語言，你知道嗎?程序設(shè)計過程：一般經(jīng)過編輯源程序編譯鏈接執(zhí)行。所謂編輯TSP問題貪心算法程序?qū)嵗惴ǖ膶崿F(xiàn)4.算法實現(xiàn)---程序設(shè)計4.2你能用某一種計算機語言書寫出TSP問題貪心算法的程序嗎?TSP問題貪心算法程序?qū)嵗惴ǖ膶崿F(xiàn)4.算法實現(xiàn)---程序算法：程序與計算系統(tǒng)之靈魂5.高級問題初探:算法分析與計算復雜性高級問題初探:算法分析與計算復雜性算法：程序與計算系統(tǒng)之靈魂高級問題初探:算法分析與計算復雜性算法的模擬與分析算法的正確性問題：問題求解的過程、方法——算法是正確的嗎？算法的輸出是問題的解嗎？20世紀60年代，美國一架發(fā)往金星的航天飛機由于控制程序出錯而永久丟失在太空中算法的效果評價：算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？兩種評價方法：證明方法：利用數(shù)學方法證明；仿真分析方法：產(chǎn)生或選取大量的、具有代表性的問題實例，利用該算法對這些問題實例進行求解，并對算法產(chǎn)生的結(jié)果進行統(tǒng)計分析。5.高級問題初探:算法分析與計算復雜性5.1算法是正確的嗎?算法是正確的嗎?算法獲得的解是最優(yōu)的嗎?算法分析與計算復雜性算法的模擬與分析5.高級問題初探:算法算法分析示例：TSP問題貪心算法的模擬與分析TSP問題貪心算法的正確性評價：直觀上只需檢查算法的輸出結(jié)果中，每個城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問題的可行解，說明算法正確地求解了這些問題實例TSP問題貪心算法的效果評價：如果實例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計方法對若干問題實例的算法結(jié)果與最優(yōu)解進行對比分析，即可對其進行效果評價；對于較大規(guī)模的問題實例，其最優(yōu)解往往是未知的，因此，算法的效果評價只能借助于與前人算法結(jié)果的比較。5.高級問題初探:算法分析與計算復雜性5.1算法是正確的嗎?算法分析與計算復雜性算法分析示例：TSP問題貪心算法的模擬與分析5.高級問題初探另一個問題：算法是能夠執(zhí)行的嗎？算法的復雜性分析算法的效率：時間效率和空間效率時間復雜性:如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數(shù)，T(n)稱為這一算法的“時間復雜性”?！按驩記法”：基本參數(shù)n——問題實例的規(guī)模把復雜性或運行時間表達為n的函數(shù)。“O”表示量級(order)，允許使用“=”代替“≈”，如n2+n+1=Ο(n2)。算法的空間復雜度：算法在執(zhí)行過程中所占存儲空間的大小。5.高級問題初探:算法分析與計算復雜性5.2算法的計算