【正文】 str = getSubString(k,j)。 j ++) for(int i = 1 。 ()。 } //主函數(shù) public static void main(String[] args) { TSPDynamic TSP = new TSPDynamic()。 i ++){ shortestPath += path[i]。 } } public void tspGreedNode(){ Scanner in = new Scanner( )。amp。 }}/*99999 3 3 2 63 99999 7 3 23 7 99999 2 52 3 2 99999 36 2 5 3 99999*/(1)(2)(3)(4)畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。這期間凝聚了很多人的心血，在此我表示由衷的感謝。最后，我要特別感謝我的導(dǎo)師劉望蜀老師、和研究生助教吳子儀老師。感謝老師四年來對我孜孜不倦的教誨，對我成長的關(guān)心和愛護(hù)。首先非常感謝學(xué)校開設(shè)這個課題，為本人日后從事計算機(jī)方面的工作提供了經(jīng)驗(yàn)，奠定了基礎(chǔ)。 } (總路程為： + shortestPath)。 for(int j = 0 。 j N 。//出發(fā)城市編號 static int IFINITE = 99999。 i = 0 。 i N 。//初始化第一個元素，即為出發(fā)城市頂點(diǎn) //(d[i][0] + )。 //stringEqual(str)表示返回與上面獲得的字符串相同的V中元素的下標(biāo)，即找上一個子集 path[i][j] = path[v][stringEqual(str)] + i。//如果子集中只有一個元素，則返回空串 else{ if(k == 0) return V[j].substring(1,V[j].length())。 while(i = 0 amp。//輸入錯誤，結(jié)束！ } (請輸入城市相鄰城市間距離（城市從0開始編號，且出發(fā)城市為第0個城市?。?)。4建議當(dāng)城市個數(shù)較少時，用動態(tài)規(guī)劃法求出最優(yōu)解；當(dāng)城市個數(shù)較多并且各邊的代價值分布比較均勻時，貪心法可以給出較好的近似解。3結(jié)論本文主要重點(diǎn)討論了動態(tài)規(guī)劃法和貪心法求解TSP問題算法，并附錄給出了相應(yīng)程序。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。
動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計算。關(guān)于TSP的完全有效的算法目前尚未找到，這促使人們長期以來不斷地探索并積累了大量的算法。2正文蠻力法所依賴的基本技術(shù)是掃描技術(shù)，即采用一定的策略將待求解問題的所有元素一次處理一次，從而找出問題的解。 j 1。
2．V=V{u0}。在求解最佳路徑所經(jīng)過城市順序時，本文是通過邊查找d[i][j]邊記錄路徑的，這樣可以省掉很多麻煩，另，路徑也是采用字符串形式的數(shù)組，數(shù)組規(guī)模與存儲城市間距離的c[][]數(shù)組相同，由于很多元素均不需賦值，這樣做可能會浪費(fèi)內(nèi)存空間，但是目前還沒找到更好地求解方法。//頂點(diǎn)間距離 int[][] d。 j N 。//用于表示下一個即將加入子集的數(shù)字 if(i == 0)ch = 0。 while(i ){ if(V[i].equals(str)) return i。 if(min c[i][v] + d[v][stringEqual(str)]){ min = c[i][v] + d[v][stringEqual(str)]。 i N 。 } for(int i = 0 。 ()。 } return shortestPath。 (請輸入出發(fā)城市編號（注意城市從0開始編號，請按照輸入城市間距離即初始化c[][]時順序計算）：)。 c[V[k 1]][i] min){ min = c[V[k 1]][i]。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。沒有他們的幫助，我將無法順利完成這次設(shè)計。是他們在我畢業(yè)的最后關(guān)頭給了我們巨大的幫助與鼓勵，給了我很多解決問題的思路，在此表示衷心的感激?；厥姿哪?，取得了些許成績，生活中有快樂也有艱辛。作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日致 謝時間飛逝，大學(xué)的學(xué)習(xí)生活很快就要過去，在這四年的學(xué)習(xí)生活中，收獲了很多，而這些成績的取得是和一直關(guān)心幫助我的人分不開的。 shortestPath += path[i]。 i ++){ int mark = 0。 i ++) for(int j = 0 。//表示最短路徑 int u0。 for(int i = () 2 。 for(int i = 0 。 path[i][0] = 0 + i。//先把最小的距離賦值給從V[j]中第一個頂點(diǎn)出發(fā)的距離 //(min)。 } //獲得子集V[j]中除指定元素k外的元素，用字符串形式表示 public String getSubString(int k , int j){ if(V[j].length()