數(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)和運(yùn)算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實際問題。二、設(shè)計要求 在本課程設(shè)計過程中要求學(xué)生：（1）重視課程設(shè)計環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；（2）按照課程設(shè)計的題目要求，獨(dú)立地完成各項任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實驗報告或源程序雷同，涉及的全部人員皆以零分計入本

2、課程設(shè)計成績。（3）學(xué)生在接受設(shè)計任務(wù)后，根據(jù)要求認(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è)計思想對于TSP問題，一種最容易想到的也肯定能得到最佳解的算法是窮舉法，即考慮所有可能的旅行路線，從中選擇最佳的一條。但是

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

4、v=最后一個被訪問的頂點； 2.2在頂點v的鄰接點中查找距離頂點v最近的未被訪問的鄰接點j； 2.2訪問頂點j； 3.從最后一個訪問的頂點直接回到出發(fā)點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個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑

5、的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。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是所有城市之間連接的成本度量（一般為城市之間的距離）；如果crs = csr, 那么該TSP問

6、題為對稱的，否則為非對稱的。一個TSP問題可以表達(dá)為：求解遍歷圖G = (V, E, C)，所有的節(jié)點一次并且回到起始節(jié)點，使得連接這些節(jié)點的路徑成本最低。二、貪心算法貪心算法，又名貪婪算法，是一種常用的求解最優(yōu)化問題的簡單、迅速的算法。貪心算法總是做出在當(dāng)前看來最好的選擇，它所做的每一個在當(dāng)前狀態(tài)下某種意義上是最好的選擇即貪心選擇，并希望通過每次所作的貪心選擇導(dǎo)致最終得到問題最優(yōu)解。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。1、貪心算法的基本思路從問題的某一個初始解觸發(fā)逐步逼近給定的目標(biāo)，

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

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

9、市的距離是2（2號城市），由于不能返回，所以從2號城市繼續(xù)尋找與之最近的城市（1號城市除外）的距離是4（3號城市），以此類推，最終在返回起始城1。補(bǔ)充：上面的最短距離要記錄下來，求和，則得到最短路徑。如果城市數(shù)目增加，則重復(fù)第一個城市到第二個城市這個步驟。在計算機(jī)中實現(xiàn)這個程序，則要記住每個最優(yōu)城市的標(biāo)號。存放數(shù)組中，再輸出最優(yōu)路徑。四、程序流程圖：五、核心源程序清單和執(zhí)行結(jié)果package twl;import java.io.BufferedReader;import java.io.FileInputStream;import java.io.IOException;import jav

10、a.io.InputStreamReader;public class TxTsp private int cityNum; / 城市數(shù)量private int distance; / 距離矩陣private int col;/代表列，也表示是否走過，走過置0private int row;/代表行，選過置0public TxTsp(int n) cityNum = n;private void init(String filename) throws IOException / 讀取數(shù)據(jù)int x;int y;String strbuff;BufferedReader data = new

11、BufferedReader(new InputStreamReader(new FileInputStream(filename);distance = new intcityNumcityNum;x = new intcityNum;y = new intcityNum;for (int i = 0; i cityNum; i+) / 讀取一行數(shù)據(jù)，數(shù)據(jù)格式1 6734 1453strbuff = data.readLine();/ 字符分割String str = strbuff.split( );xi = Integer.valueOf(str1);/ x坐標(biāo)yi = Integer.

12、valueOf(str2);/ y坐標(biāo)data.close();/ 計算距離矩陣/ ，針對具體問題，距離計算方法也不一樣，此處用的是TSPlib上的att48作為案例，它有48個城市，距離計算方法為偽歐氏距離(最優(yōu)值為10628)for (int i = 0; i cityNum - 1; i+) distanceii = 0; / 對角線為0for (int j = i + 1; j cityNum; j+) double rij = Math.sqrt(xi - xj) * (xi - xj) + (yi - yj)* (yi - yj) / 10.0);/ 四舍五入，取整/int tij

13、 = (int) Math.round(rij);/if (tij rij) /distanceij = tij + 1;/distanceji = distanceij;/ else /distanceij = tij;/distanceji = distanceij;/distanceij = (int)rij + 1;distanceji = distanceij;/矩陣對稱distancecityNum - 1cityNum - 1 = 0;/矩陣右下角col = new intcityNum;col0 = 0;for (int i = 1; i cityNum; i+) coli =

14、 1;row = new intcityNum;for (int i = 0; i cityNum; i+) rowi = 1;public void solve()int temp = new intcityNum;String path=0;int s=0;/計算距離int i=0;/當(dāng)前節(jié)點int j=0;/下一個節(jié)點/默認(rèn)從0開始while(rowi=1)/復(fù)制距離矩陣一行for (int k = 0; k + j;/System.out.println(i + - + j);/System.out.println(distanceij);s = s + distanceij;i =

15、j;/當(dāng)前節(jié)點指向下一節(jié)點System.out.println(路徑: + path);System.out.println(總距離為: + s);public int selectmin(int p)int j = 0, m = p0, k = 0;/尋找第一個可用節(jié)點，注意最后一次尋找，沒有可用節(jié)點while (colj = 0) j+;/System.out.print(j+ );if(j=cityNum)/沒有可用節(jié)點，說明已結(jié)束，最后一次為 *-0m = p0;break;/或者直接return 0;elsem = pj;/從可用節(jié)點J開始往后掃描，找出距離最小節(jié)點for (; j = pj) m = pj;k = j;return k;public void printinit() System.out.println(print begin.);for (int i = 0; i cityNum; i+) for (int j = 0; j 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-4