旅行商問題的求解方法動態(tài)規(guī)劃法和貪心法算法論文-預(yù)覽頁
【正文】 == V[ 1]k。貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個(gè)選擇都不會改變。本文僅重點(diǎn)討論最近鄰點(diǎn)策略及其求解過程。 u=u0。 //從頂點(diǎn)v出發(fā)繼續(xù)求解但需注意，用最近鄰點(diǎn)貪心策略求解TSP問題所得的結(jié)果不一定是最優(yōu)解。對這個(gè)孩子結(jié)點(diǎn)分別估算可能取得的目標(biāo)函數(shù)值，其含義是以該孩子結(jié)點(diǎn)為根的子樹所可能取得的目標(biāo)函數(shù)值不大于，也就是部分解應(yīng)滿足：
本文本欲詳細(xì)討論該算法，但無奈在編程問題中，尚有問題有待解決，時(shí)間所限，不得已放棄。因?yàn)楹竺嬖貍€(gè)數(shù)較多的子集與前面比其元素個(gè)數(shù)少1的子集間有一定對應(yīng)關(guān)系，所以用遞歸方式，可以簡便很多。貪心法中，由于貪心法相對動態(tài)規(guī)劃法要簡單很多，每次在查找最近城市時(shí)所得的頂點(diǎn)均為最后該法最佳路徑所經(jīng)過的城市編號，規(guī)模相對較小，容易確定，操作相對簡單，所以本文用數(shù)組V[]存放最佳路徑所經(jīng)過的城市編號順序相對來說方便很多。另外，動態(tài)規(guī)劃法有一個(gè)明顯的缺點(diǎn)，就是出發(fā)城市只能是第0個(gè)城市（城市從0開始編號），若出發(fā)城市改變，則必須以該城市為第0個(gè)城市順序給其他城市編號，輸入城市間距離。另外，程序中有詳細(xì)注釋，程序中變量取名都是根據(jù)變量的性質(zhì)和所代表的含義命名的，也相應(yīng)提高了程序的可讀性。import 。//存放迭代結(jié)果 int N。 initialV1()。 if(N = 1){ (不符合要求，請認(rèn)真核對！)。//為c分配空間 for(int i = 0 。 j ++){ c[i][j] = ()。//為V分配空間 initialV(0,0)。 if(m == 0)V[m ++] = 。 V[i].length() == len)//找與最后一個(gè)初始化的V[m1]子集內(nèi)元素個(gè)數(shù)相同的集合，把指針i指向滿足條件的集合 i 。//如果i指向V中第一個(gè)元素 else{ String chStr = + V[i].charAt(V[i].length() 1)。//對已存在的自己逐個(gè)掃描添加 } } initialV(m,V[m 1].length())。//如若存在，則返回false else return true。//如果k是最后一個(gè)元素，則返回其前面的元素 else return (V[j].substring(0, k) + V[j].substring(k+1, V[j].length()))。 i ++。//銘記V[j].charAt(k)得到的是字符型，轉(zhuǎn)換成整形后是字母對應(yīng)的ASC碼?。。?！ int v = (vStr)。 int min = c[i][v] + d[v][stringEqual(str)]。 //尋找最小距離 while(k V[j].length()){ vStr = + V[j].charAt(k)。 path[i][j] = path[v][stringEqual(str)] + i。//返回最小值 } //處理函數(shù) public void dynamic(){ d = new int[N][(int)(2,N1)]。 i ++){//初始化第一列 d[i][0] = c[i][0]。 for( 。 i ++){ if(exclude(i,j))//判斷V子集中是否包含當(dāng)前頂點(diǎn)，即V[j]中是否包含i { //(done！ + i + + j)。 i (int)(2,N1) 。 ) ()。 j N 。 i N 。 ()。 ((() 1))。 } (會有最短路徑)。//求最短路徑 //()。public class TSPGreedNode { int[] V。//城市個(gè)數(shù) int shortestPath。 } //得到最短路徑 public int getShortestPath(){ for(int i = 0 。 } //初始化數(shù)組c[]，即頂點(diǎn)間距離 public void initialC(){ Scanner in = new Scanner( )。 (0)。 i N 。 //輸入時(shí)，按城市編號從小到大，如若兩城市間沒有公路相連，則距離為無窮大。 u0 = ()。 V[k] = u0。 i N 。 j ++) if(V[j] == i) mark = 1。 V[k] = i。 } //輸出最短路徑下所經(jīng)城市，兩城市間距離和最短路徑 public void print(){ shortestPath = 0。 i ++){ (從 + V[i] + + V[i + 1] + ,所經(jīng)路程為： + path[i])。 ()。對本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。對本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。涉密論文按學(xué)校規(guī)定處理。本次畢業(yè)設(shè)計(jì)是對我大學(xué)四年學(xué)習(xí)下來最好的檢驗(yàn)。首先，我要特別感謝我的知道郭謙功老師對我的悉心指導(dǎo)，在我的論文書寫及設(shè)計(jì)過程中給了我大量的幫助和指導(dǎo)，為我理清了設(shè)計(jì)思路和操作方法，并對我所做的課題提出了有效的改進(jìn)方案。其次，我要感謝大學(xué)四年中所有的任課老師和輔導(dǎo)員在學(xué)習(xí)期間對我的嚴(yán)格要求，感謝他們對我學(xué)習(xí)上和生活上的幫助，使我了解了許多專業(yè)知識和為人的道理，能夠在今后的生活道路上有繼續(xù)奮斗的力量。從這里走出，對我的人生來說，將是踏上一個(gè)新的征程，要把所學(xué)的知識應(yīng)用到實(shí)際工作中去。四年的風(fēng)風(fēng)雨雨，我們一同走過，充滿著關(guān)愛，給我留下了值得珍藏的最美好的記憶。老師們認(rèn)真負(fù)責(zé)的工作態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1