數(shù)據(jù)結(jié)構(gòu)程序設(shè)計TSPn城市旅行問題

學(xué)號數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書TSP起止日期：20XX年12月12日至20XX年12學(xué)生姓名班級成績指導(dǎo)教師(簽字)電子與信息工程系20XX年12月16日

天津城市建設(shè)學(xué)院課程設(shè)計任務(wù)書20XX—20XX學(xué)年第1學(xué)期電子與信息工程系軟件工程專業(yè)班級課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目：Tsp完成期限：自20XX年12月12日至20XX年12月16日共1周設(shè)計依據(jù)、要求及主要內(nèi)容（可另加附頁）：一、設(shè)計目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實際問題。二、設(shè)計要求（1）重視課程設(shè)計環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；（2）按照課程設(shè)計的題目要求，獨立地完成各項任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實驗報告或源程序雷同，涉及的全部人員皆以零分計入本課程設(shè)計成績；（3）學(xué)生在接受設(shè)計任務(wù)后，首先要按設(shè)計任務(wù)書的要求編寫設(shè)計進(jìn)程表；（4）認(rèn)真編寫課程設(shè)計報告。三、設(shè)計內(nèi)容6．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問題，一種最容易想到的也肯定能得到最佳解的算法是窮舉法，即考慮所有可能的旅行路線，從中選擇最佳的一條。但是用窮舉法求解TSP問題的時間復(fù)雜度為Ο(n!)，當(dāng)n大到一定程度后是不可解的。本實驗只要求近似解，可以采用貪心法求解：任意選擇某個城市作為出發(fā)點，然后前往最近的未訪問的城市，直到所有的城市都被訪問并且僅被訪問一次，最后返回到出發(fā)點。為便于查找離某頂點最近的鄰接點，可以采用鄰接矩陣存儲該圖。算法用偽代碼描述如下：1.任意選擇某個頂點v作為出發(fā)點；2.執(zhí)行下述過程，直到所有頂點都被訪問：2.1v=最后一個被訪問的頂點；2.2在頂點v的鄰接點中查找距離頂點v最近的未被訪問的鄰接點j；2.2訪問頂點j；3.從最后一個訪問的頂點直接回到出發(fā)點v；【思考題】上網(wǎng)查找TSP問題的應(yīng)用實例，寫一篇綜述報告。四、參考文獻(xiàn)1．王紅梅．?dāng)?shù)據(jù)結(jié)構(gòu)．清華大學(xué)出版社2．王紅梅．?dāng)?shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實驗指導(dǎo)．清華大學(xué)出版社3．嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）．清華大學(xué)出版社一、需求分析(程序的功能、輸入輸出的要求)任意選擇某個城市作為出發(fā)點，然后前往最近的未訪問的城市，直到所有的城市都被訪問并且僅被訪問一次，最后返回到出發(fā)點。要求這時遍歷各城市的距離為最短距離。輸入城市間的距離，把本城市到本城市距離輸入為99999。要求輸入的為整數(shù)。結(jié)果為輸出最短路徑和遍歷的最短距離，要求為整數(shù)。二、問題求解TSP問題，要求先畫一個旅行的線路圖的圖示，然后假設(shè)有個人，遍歷所有的旅行的城市，考慮所有可能的旅行路線，從中選擇最佳的一條。突出其中用到的中間數(shù)據(jù)是：數(shù)組形式，初始數(shù)據(jù)是各個城市間的距離。假設(shè)我們進(jìn)行我們的旅游計劃，共五個城市，然后前往最近的未訪問的城市，直到所有的城市都被訪問并且僅被訪問一次，最后返回到出發(fā)點。要求這時遍歷各城市的距離為最短距離。當(dāng)我們要求整體的最優(yōu)解時，可以從它的局部最優(yōu)解求的，抱著這樣的思想我們從起始城市1出發(fā)比較與之最近的城市的距離是2（2號城市），由于不能返回，所以從2號城市繼續(xù)尋找與之最近的城市（1號城市除外）的距離是4（3號城市），以此類推，最終在返回起始城1。補(bǔ)充：上面的最短距離要記錄下來，求和，則得到最短路徑。如果城市數(shù)目增加，則重復(fù)第一個城市到第二個城市這個步驟。在計算機(jī)中實現(xiàn)這個程序，則要記住每個最優(yōu)城市的標(biāo)號。存放數(shù)組中，再輸出最優(yōu)路徑。城市1城市1城市567城市5城市4城市452893城市2城市35城市2城市34三、總體設(shè)計程序設(shè)計組成框圖:TSPTSP循環(huán)遍歷找到與起始城市最近的城市序號。用flag[]保存，用min[]保存最短路徑。用sum+=min[]求出最短路徑輸出flag[],得到最佳路徑輸入各城市間的距離循環(huán)遍歷找到與起始城市最近的城市序號。用flag[]保存，用min[]保存最短路徑。用sum+=min[]求出最短路徑輸出flag[],得到最佳路徑輸入各城市間的距離流程圖開始開始輸入城市的個數(shù)cityNum和城市間的距離輸入城市的個數(shù)cityNum和城市間的距離mmin[i]>=d[][j]?J++J++yesMMin[i]=d[][j]FFlag[i]=jSum=0Sum=0Sum+=min[i]i<cityNum?輸出最短路徑Flag[i]輸出最短距離sumyesYes輸出最短路徑Flag[i]輸出最短距離sum四、詳細(xì)設(shè)計publicvoidinitDistance()作用：該方法是存儲個城市間的距離，及城市的數(shù)目。publicvoidsum()作用：該方法是求各個城市間的最短路徑和，并且記錄下最佳的旅行路徑。補(bǔ)充說明：每次都要起初的最小距離min[i]=99999;去和臨近的城市去比較距離min[i]>=distance[flag[k]][j]，這樣min[i]肯定會被覆蓋，此時在根據(jù)for（j++）循環(huán)逐次比較，得出最小的min[i]，用flag[k+1]去記下這個城市的編號。再用for循環(huán)，輸出最佳路徑flag[]。publicstaticvoidmain(String[]args){}作用：主函數(shù)，在主函數(shù)中調(diào)用各種方法。例如：sum()方法，initDistance()方法。五、調(diào)試與測試測設(shè)過程中for(inti=0;i<cityNum-1;i++){ min[i]=99999;for(intj=0;j<cityNum;j++){ if(min[i]>=distance[flag[k]][j]){ min[i]=distance[flag[k]][j]; flag[k+1]=j; }Min[i]我把第二個for循環(huán)的i寫成了j，沒有錯誤，但是結(jié)果不對，導(dǎo)致我改了一下午。細(xì)心很重要啊。六、關(guān)鍵源程序清單和執(zhí)行結(jié)果代碼： importjava.util.Scanner;publicclassTsp{ intcityNum; int[][]distance=newint[10][10]; intmin[]=newint[10]; intflag[]=newint[10]; publicvoidinitDistance(){ System.out.println("請輸入城市的數(shù)目"); Scannerinput=newScanner(System.in); cityNum=input.nextInt(); /* *for(inti=0;i<cityNum;i++){//為了輸入的更快當(dāng)

i=j時自動的賦值為0 *distance[i][i]=0;} */ for(inti=0;i<cityNum;i++){//由于二維數(shù)組的存儲

是對稱的可以用壓縮存儲的方法初始化 for(intj=0;j<cityNum;j++){ System.out.println("請輸入第"+i+"城市

到第"+j+"城市之間的距離"); distance[i][j]=input.nextInt(); } } intcount=0; for(inti=0;i<cityNum;i++){ for(intj=0;j<cityNum;j++){ System.out.print(distance[i][j]); count++; if(count%cityNum==0){ System.out.println(); } } } } publicvoidsum(){ intk=0; intx=0; flag[0]=0; for(inti=0;i<cityNum-1;i++){ min[i]=99999; for(intj=0;j<cityNum;j++){ if(min[i]>=distance[flag[k]][j]){ min[i]=distance[flag[k]][j]; flag[k+1]=j; } } k++; x=0; //對稱的點變成99999，防止往回遍歷。 while((k-x)!=0){ distance[flag[k]][flag[k-x-1]]=99999;

x++; } } System.out.println("最優(yōu)路徑："); for(inti=0;i<cityNum;i++){ System.out.print(flag[i]); } System.out.println(flag[0]); intsum=0; for(intm=0;m<cityNum-1;m++){ sum=sum+min[m]; } sum=sum+distance[flag[0]][flag[cityNum-1]]; System.out.println("最優(yōu)路徑長度為："+sum); } publicstaticvoidmain