數(shù)據(jù)結(jié)構(gòu)課設(shè)TSP貪婪算法

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書題目TSP問題貪心算法起止日期：2014年 11月 10 日 至2014 年 11月17日學(xué)生姓名滕 文 亮班 級113301 班成 績指導(dǎo)教師(簽字)運算機(jī)科學(xué)與工程學(xué)院2014年11月9日課程設(shè)計任務(wù)書一、設(shè)計目的熟悉各類數(shù)據(jù)結(jié)構(gòu)和運算，會利用數(shù)據(jù)結(jié)構(gòu)的大體操作解決一些實際問題。二、設(shè)計要求在本課程設(shè)計進(jìn)程中要求學(xué)生：（1）重視課程設(shè)計環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；（2）依照課程設(shè)計的題目要求， 獨立地完成各項任務(wù)， 嚴(yán)禁剽竊；凡發(fā)覺剽竊，剽竊者與被剽竊者皆以零分計入本課程設(shè)計成績。凡發(fā)覺實驗報告或源程序類似，涉及的全數(shù)人員皆以零分計

2、入本課程設(shè)計成績。（3）學(xué)生在同意設(shè)計任務(wù)后，依照要求認(rèn)真完成。（4）認(rèn)真編寫課程設(shè)計報告。三、設(shè)計內(nèi)容TSP問題（貪婪法求解）1) 問題描述所謂 TSP問題是指旅行家要旅行 n個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。2) 大體要求(1) 上網(wǎng)查找 TSP問題的應(yīng)用實例；(2) 分析求 TSP問題的全局最優(yōu)解的時刻復(fù)雜度；(3) 設(shè)計一個求近似解的算法；(4) 分析算法的時刻復(fù)雜度。3) 設(shè)計思想關(guān)于 TSP問題，一種最容易想到的也確信能取得最正確解的算法是窮舉法，即考慮所有可能的旅行線路，從當(dāng)選擇

3、最正確的一條。可是用窮舉法求解TSP問題的時刻復(fù)雜度為 (n!)，當(dāng) n大到必然程度后是不可解的。4）設(shè)計思想關(guān)于 TSP 問題，一種最容易想到的也確信能取得最正確解的算法是窮舉法，即考慮所有可能的旅行線路，從當(dāng)選擇最正確的一條。可是用窮舉法求解TSP 問題的時刻復(fù)雜度為( n !) ，當(dāng) n 大到必然程度后是不可解的。本實驗只要求近似解，能夠采納貪婪法求解：任意選擇某個城市作為起點，然后前去最近的未訪問的城市，直到所有的城市都被訪問而且僅被訪問一次，最后返回到起點。為便于查找離某極點最近的鄰接點，能夠采納鄰接矩陣存儲該圖。算法用偽代碼描述如下：1. 任意選擇某個極點 v 作為起點；2. 執(zhí)行

4、下述進(jìn)程，直到所有極點都被訪問：v= 最后一個被訪問的極點；在極點 v 的鄰接點中查找距離極點v 最近的未被訪問的鄰接點j ；訪問極點j ；3. 從最后一個訪問的極點直接回到起點v；四、參考文獻(xiàn)1. 王紅梅，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社；2. 王紅梅，數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實驗指導(dǎo)，清華大學(xué)出版社；3. 王曉東，運算機(jī)算法設(shè)計與分析，電子工業(yè)出版社。一、 TSP 問題TSP問題（ Travelling Salesman Problem）即旅行商問題，又譯為旅行推銷員問題、貨郎擔(dān)問題， 是數(shù)學(xué)領(lǐng)域中聞名問題之一。假設(shè)有一個旅行商人要造訪n個城市， 他必需選擇所要走的途徑，途徑的限制是每一個城市只能造訪一

5、次，而且最后要回到原先動身的城市。途徑的選擇目標(biāo)是要求得的途徑路程為所有途徑當(dāng)中的最小值。TSP問題是一個組合優(yōu)化問題。該問題能夠被證明具有NPC計算復(fù)雜性。 TSP問題能夠分為兩類，一類是對稱TSP問題（Symmetric TSP），另一類是非對稱問題（Asymmetric TSP）。所有的TSP問題都能夠用一個圖（Graph）來描述：V=c1, c2, , ci, , cn， i = 1,2, , n，是所有城市的集合.ci表示第 i個城市，n為城市的數(shù)量；E=(r, s): r,s V 是所有城市之間連接的集合；C = crs: r,s V 是所有城市之間連接的本錢氣宇（一樣為城市之間的

6、距離）；若是 crs = csr,那么該 TSP問題為對稱的，不然為非對稱的。一個 TSP問題能夠表達(dá)為：求解遍歷圖 G = (V, E, C)，所有的節(jié)點一次而且回到起始節(jié)點，使得連接這些節(jié)點的途徑本錢最低。二、貪婪算法貪婪算法，又名貪婪算法，是一種經(jīng)常使用的求解最優(yōu)化問題的簡單、迅速的算法。貪婪算法老是做出在當(dāng)前看來最好的選擇，它所做的每一個在當(dāng)前狀態(tài)下某種意義上是最好的選擇即貪婪選擇，并希望通過每次所作的貪婪選擇致使最終取得問題最優(yōu)解。必需注意的是，貪婪算法不是對所有問題都能取得整體最優(yōu)解，選擇的貪婪策略必需具有無后效性，即某個狀態(tài)以后的進(jìn)程可不能阻礙以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。一、貪

7、婪算法的大體思路從問題的某一個初始解觸發(fā)慢慢逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時，算法停止。大致步驟如下：1）成立數(shù)學(xué)模型來描述問題；2）把求解的問題分成若干個子問題3）對每一個子問題求解，得到子問題的局部最優(yōu)解4）把子問題的局部最優(yōu)解合成原問題的一個解二、貪婪算法的實現(xiàn)框架貪婪算法沒有固定的算法框架，算法設(shè)計的關(guān)鍵是貪婪策略的選擇，而貪婪策略適用的前提是：局部最優(yōu)策略能致使產(chǎn)生全局最優(yōu)解。從問題的某一初始解動身；while（能朝給定總目標(biāo)前進(jìn)一步）利用可行的決策，求出可行解的一個解元素；由所有解元素組合成問題的一個可行解；3、貪婪算法存在的問題1）

8、不能保證求得的最后解是最正確的；2）不能用來求最大最小解問題；3）只能在某些特定條件約束的情況下使用，例如貪心策略必須具備無后效性等。4、典型的貪婪算法利用領(lǐng)域馬踏棋盤、背包、裝箱等。三、問題求解：TSP問題，要求先畫一個旅行的線路圖的圖示，然后假設(shè)有個人，遍歷所有的旅行的城市，考慮所有可能的旅行線路，從當(dāng)選擇最正確的一條。突出其頂用到的中間數(shù)據(jù)是：數(shù)組形式，初始數(shù)據(jù)是各個城市間的距離。假設(shè)咱們進(jìn)行咱們的旅行打算，共五個城市，然后前去最近的未訪問的城市，直到所有的城市都被訪問而且僅被訪問一次，最后返回到起點。要求這時遍歷各城市的距離為最短距離。當(dāng)咱們要求整體的最優(yōu)解時，能夠從它的局部最優(yōu)解求的

9、，抱著如此的思想咱們從起始城市1動身比較與之最近的城市的距離是2（2號城市），由于不能返回，因此從 2號城市繼續(xù)尋覓與之最近的城市（1號城市除外）的距離是4（ 3號城市），以此類推，最終在返回起始城1。補(bǔ)充：上面的最短距離要記錄下來，求和，那么取得最短途徑。若是城市數(shù)量增加，那么重復(fù)第一個城市到第二個城市那個步驟。在運算機(jī)中實現(xiàn)那個程序，那么要記住每一個最優(yōu)城市的標(biāo)號。寄存數(shù)組中，再輸出最優(yōu)途徑。城市 1城市5城市4城市24城市3四、程序流程圖：開始輸入城市數(shù)與城市間距遍歷樹并另第一條可行回路的解和值為當(dāng)前最優(yōu)解和最優(yōu)值繼續(xù)遍歷并與當(dāng)前最優(yōu)解和最優(yōu)值比較最優(yōu)則替換到達(dá)結(jié)束點NY輸出最優(yōu)值和最優(yōu)

10、解結(jié)束五、核心源程序清單和執(zhí)行結(jié)果package twl;importclass TxTsp private int cityNum; qrt(xi - xj) * (xi - xj) + (yi - yj)* (yi - yj) / ;.");for (int i = 0; i < cityNum; i+) for (int j = 0; j < cityNum; j+) +"");"print end.");public static void main(String args) throws IOException "

11、;Start.");TxTsp ts = new TxTsp(48);("." + "");.路徑 :0->8->37->30->43->17->6->27->35->29->5->36->18->26->42->16->45->32->14->11->10->22->13->24->12->20->46->19->39->2->21->15->40->33->28->4->47->38->31->23->9->41->25->3->34->44->1->7->0總距離為 :12842五、總結(jié)單從求解結(jié)果來看，我個人其實仍是能同意那個解，但認(rèn)真想一想，事實上那個求解結(jié)果有太多運氣成份在里面，