算法設(shè)計(jì)大作業(yè)—求解Tsps問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上基于貪心算法求解TSP問題 一、TSP問題TSP問題（Travelling Salesman Problem）即旅行商問題，又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問題是一個(gè)組合優(yōu)化問題。該問題可以被證明具有NPC計(jì)算復(fù)雜性。TSP問題可以分為兩類，一類是對(duì)稱TSP問題（Symmetric TSP），另一類是非對(duì)稱問題（Asymmetric TSP）。所有的TSP問題

2、都可以用一個(gè)圖（Graph）來描述：V=c1, c2, , ci, , cn，i = 1,2, , n，是所有城市的集合.ci表示第i個(gè)城市，n為城市的數(shù)目；E=(r, s): r,s V是所有城市之間連接的集合；C = crs: r,s V是所有城市之間連接的成本度量（一般為城市之間的距離）；如果crs = csr, 那么該TSP問題為對(duì)稱的，否則為非對(duì)稱的。一個(gè)TSP問題可以表達(dá)為：求解遍歷圖G = (V, E, C)，所有的節(jié)點(diǎn)一次并且回到起始節(jié)點(diǎn)，使得連接這些節(jié)點(diǎn)的路徑成本最低。二、貪心算法貪心算法，又名貪婪算法，是一種常用的求解最優(yōu)化問題的簡單、迅速的算法。貪心算法總是做出在當(dāng)前看來

3、最好的選擇，它所做的每一個(gè)在當(dāng)前狀態(tài)下某種意義上是最好的選擇即貪心選擇，并希望通過每次所作的貪心選擇導(dǎo)致最終得到問題最優(yōu)解。必須注意的是，貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。1、貪心算法的基本思路從問題的某一個(gè)初始解觸發(fā)逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。大致步驟如下：1）建立數(shù)學(xué)模型來描述問題；2）把求解的問題分成若干個(gè)子問題3）對(duì)每一個(gè)子問題求解，得到子問題的局部最優(yōu)解4）把子問題的局部最優(yōu)解合成原問題的一個(gè)解2、貪心算法的實(shí)現(xiàn)框架貪心

4、算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇，而貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。    從問題的某一初始解出發(fā)；    while （能朝給定總目標(biāo)前進(jìn)一步）              利用可行的決策，求出可行解的一個(gè)解元素；        由所有解元素組合成問題的一個(gè)可行解；3、貪心算法存在的問題1）不能保證求得的最后解是

5、最佳的；2）不能用來求最大最小解問題；3）只能在某些特定條件約束的情況下使用，例如貪心策略必須具備無后效性等。4、典型的貪心算法使用領(lǐng)域馬踏棋盤、背包、裝箱等三、貪心算法求解TSP問題貪心策略：在當(dāng)前節(jié)點(diǎn)下遍歷所有能到達(dá)的下一節(jié)點(diǎn)，選擇距離最近的節(jié)點(diǎn)作為下一節(jié)點(diǎn)?；舅悸肥?，從一節(jié)點(diǎn)出發(fā)遍歷所有能到達(dá)的下一節(jié)點(diǎn)，選擇距離最近的節(jié)點(diǎn)作為下一節(jié)點(diǎn)，然后把當(dāng)前節(jié)點(diǎn)標(biāo)記已走過，下一節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，重復(fù)貪心策略，以此類推直至所有節(jié)點(diǎn)都標(biāo)記為已走節(jié)點(diǎn)結(jié)束。貪心法的方法是在每個(gè)節(jié)點(diǎn)中找到與其他節(jié)點(diǎn)的最小距離，并且有順序，比如從第1節(jié)點(diǎn)出發(fā)，到其他節(jié)點(diǎn)的最小節(jié)點(diǎn)為3，在從第3節(jié)點(diǎn)到不包含節(jié)點(diǎn)1的最小節(jié)點(diǎn)距離

6、為節(jié)點(diǎn)5，以此繼續(xù)下去，找到路線1-3-5-4-2-1回路。四、C+算法如下：#include <iostream.h>#define N 5void copy(int ANN,int BNN)for(int i=0;i<N;i+)for(int j=0;j<N;j+) Aij=Bij;int main()int a55=1000,3,1,5,8,3,1000,6,7,9,1,6,1000,4,2,5,7,4,1000,3,8,9,2,3,1000;int ANN;copy(A,a);/int a55=1000,3,1,5,8,3,1000,6,17,9,1,6,100

7、0,4,2,5,17,4,1000,3,8,9,2,3,1000;int b5=0;int n=sizeof(b)/sizeof(int);int i=1,j,k;while(i<n)int visit=0;int min=1000;for(j=0;j<n;j+)ajbi-1=-1;for(j=0;j<n;j+)if(min>abi-1j&&abi-1j>0)visit=j;min=abi-1j;abi-1j=-1;bi+=visit;for(j=0;j<n;j+)for(k=0;k<n;k+)cout<<ajk<<"t"cout<<endl;cout<<endl;cout<<"貪心法路線為："<<endl;for(i=0;i<n;i+)cout<<bi+1<<" ->"<<"t"cout<<b0+1<<endl;cout<<"貪心法路線長度為："int sum=0;for(