TSP問題的解決方案

1、算法設計與分析實驗報告學號：日期：20161230姓名：得 分：一、實驗內容：TSP問題二、所用算法的基本思想及復雜度分析：1、蠻力法1) 基本思想借助矩陣把問題轉換為矩陣中點的求解。首先構造距離矩陣，任意節(jié)點 到自身節(jié)點的距離為無窮大。在第一行找到最小項a1j，從而跳轉到第j行，再找到最小值ajk，再到第k行進行查找。然后構造各行允 許數組rown=1,11，各列允許數組 colablen=0,1,1.1，其中1 表示允許訪問，即該節(jié)點未被訪問；0表示不允許訪問，即該節(jié)點已經 被訪問。如果改行或該列不允許訪問，跳過該點訪問下一節(jié)點。程序再 發(fā)問最后一個節(jié)點前，所訪問的行中至少有1個允許訪問的

2、節(jié)點，依次訪問這些節(jié)點找到最小的即可；在訪問最后一個節(jié)點后，再次訪問，會 返回k=0，即實現訪問源節(jié)點，得出一條簡單回路。2) 復雜度分析基本語句是訪問下一個行列中最小的點，主要操作是求平方，假設有n個點，則計算的次數為 nA2-n。T(n)=n*(n-1)=O(nT)。2、動態(tài)規(guī)劃法1)基本思想假設從頂點s岀發(fā)，令d(i, V ')從頂點i岀發(fā)經過 V是一個點的集合)中各個頂點一次且 僅一次，最后回到岀發(fā)點s的最短路徑長度。推導：(分情況來討論) 當V為空集，那么d(i, V ；表示從i不經過任何點就回到 s 了，如上圖的 城市3-城 市0(0為起點城市)。此時d(i, V '

3、; )=Ci就是城市i到城市s的距離)、如果V不為空，那么就是對子問題的最優(yōu)求解。你必須在V這個城市集合中，嘗試每一個，并求出最優(yōu)解。d（i, V ' ）=minCik +d（k, V -'）注：Cik表示你選擇的城市和城市 i的距離，d（k, V -k）是一個子問題。綜上所述，TSP問題的動態(tài)規(guī)劃方程就岀來了：班匚刃）=丘帆乞4/（上尸-（幻） 2$2）復雜度分析和蠻力法相比，動態(tài)規(guī)劃求解tsp問題，把原來時間復雜性 O （n!）的 排列轉化為組合問題，從而降低了時間復雜度，但仍需要指數時間。3、回溯法1）基本思想確定了解空間的組織結構后，回溯法從開始結點（根結點）出發(fā)，以

4、深度優(yōu)先方式搜索整個解空間。這個開始結點成為活結點，同時也成 為當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點 即成為新的活結點，并為當前擴展結點。如果在當前的擴展結點處不 能再向縱深方向移動，則當前擴展結點就成為死結點。 此時，應往回 移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴 展結點。回溯法以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結點時為止?；厮莘ㄇ蠼釺SP問題，首先把所有的頂點的訪問標志初始化為 0，然 后在解空間樹中從根節(jié)點出發(fā)開始搜索，如果從根節(jié)點到當前結點對 應一個部分解，即滿足上述約束條件，則在當前結點處選擇第一棵子 樹

5、繼續(xù)搜索，否則，對當前子樹的兄弟結點進行搜索， 如果當前結點 的所有子樹都已嘗試過并且發(fā)生沖突，貝U回溯到當前結點的父節(jié)點。 采用鄰接矩陣mpnn存儲頂點之間邊的情況，為避免在函數間傳遞 參數，將數組mp設置為全局變量，設數組xn表示哈密頓回路經過 的頂點。2）復雜度分析在哈密頓回路的可能解中，考慮到約束條件xi!=xj（1<=l,jv=n,i!=j）,則可能解應該是（1,2,n）的一個排列，對應的解空間樹種至少有n!個葉子結點，每個葉子結點代表一種可能解。 當找到可行的最優(yōu)解時， 算法停止。根據遞歸條件不同時間復雜度也會不同，這里為 O（n！）。4、分支限界法1 ）基本思想分支界限法以

6、廣度優(yōu)先或以最小耗費 （最大效益） 優(yōu)勢的方式搜索問 題的解空間樹。 問題的解空間樹是表示問題解空間的一棵有序樹， 常 見的有子集樹和排列樹。 在搜索問題的解空間樹時， 分支界限法與回 溯法的主要區(qū)別在于他們對當前擴展結點所采用的擴展方式不同。 在 分支界限法中， 每一個活結點只有一次機會成為擴展結點。 活結點一 旦成為擴展結點，就一次性產生其所有兒子結點。 在這些兒子結點中， 導致不可行解或導致非最優(yōu)解得兒子結點被舍棄， 其余兒子結點被加 入活結點表中。 算法開始時創(chuàng)建一個最小堆， 用于表示活結點優(yōu)先隊 列。堆中每個結點的子樹費用的下界 lcost 值是優(yōu)先隊列的優(yōu)先級。 接著算法計算出圖中

7、每個頂點的最小費用出邊并用 minout 記錄。如 果所給的有向圖中某個頂點沒有出邊， 則該圖不可能有回路， 算法即 告結束。如果每個頂點都有出邊，則根據計算出的 minout 作算法初 始化。2）復雜度分析目標函數（限界函數） ， lb 分為三部分，第一部分是經過路徑的長度 相加的 2 倍，加上第二部分離著路徑首尾節(jié)點最近的距離相加 （不在 已知路徑上的），加上第三部分除了路徑上節(jié)點，矩陣中兩個最短的 距離相加， 最后這三部分和相加， 得到的結果除以 2便是每個節(jié)點的 限界值。由于限界函數的不同，下界為 O （n）,上界為0 （25）,智 力特定指出。三、源程序及注釋：1 、 蠻力法int

8、main（）int i,j,s=0;int *a;printf(" 輸入節(jié)點個數 ： n");scanf("%d",&n);printf(”輸入%d維對稱矩陣：n",n);colable=(int*)malloc(sizeof(int)*n);colable0=0;/對各列允 許矩陣進行賦值for(i=1;i<n;i+)colablei=1;row=(int *)malloc(sizeof(int)*n);for(i=0;i<n;i+)rowi=1;a=(int *)malloc(sizeof(int*)*n);for(i=

9、0;i<n;i+)ai=(int *)malloc(sizeof(int*)*n);for(i=0;i<n;i+)for(j=0;j<n;j+)scanf("%d",&aij)'i=0;while(rowi=1)j=min(ai);rowi=0;colablej=0;printf(" 訪問 路徑： n");printf("t%d->%dn",i,j);s=s+aij;i=j;printf(" 最短 總距離 為： %dn",s);int min(int *a)int j=0,m

10、=a0,k=0;while(colablej=0|rowj=0)j+;m=aj;/ 求最短距離for(;j<n;j+)if(colablej=1&&rowj=1)/ 節(jié)點沒有被 訪問if(m>=aj)m=aj;/m 始 終保持最短距離k=j;return k;2、動態(tài)規(guī)劃法int init()int i;int j;int t;if(sca nf("%d", &n )=EOF) return -1;for(i=0; i<n; i+)for(j=0; j< n; j+)if(i=j)con ti nue;scan f("

11、;%d", &gij);memset(c on ,-1,sizeof(c on);for(i=0; i<n; i+)biti=1<<i;t=1;for(i=1; i<n; i+)return 1;int getc on (i nt s,i nt k)int t,tt;int i;int mi n=INF;if(con sk!=-1)return con sk;t=s&(bitk-1);for(i=1; i<n; i+)tt=t&biti-1;if(tt>0)if(getc on( t,i)+gik< min)min=g

12、etc on( t,i)+gik;con sk=mi n;return con sk;3.回溯法 void backtrack(i nt i)if(i> n)if(graphroad n1!=INF&&(a ns+graphroad n 1)<besta ns)besta ns=a ns+graphroad n1;for(i nt j=1;j<=n ;j+) bestroadj=roadj;elsefor(i nt j=1;j<=n ;j+)if(graphroadi-1j!=INF &&an s+graphroadi-1j<bes

13、ta ns&& !visj)roadi=j;an s+=graphroadi-1j;visj=1;backtrack(i+1);/改回輔助的全局變量an s-=graphroadi-1j;visj=0;int mai n()memset(graph,INF,sizeof(graph);cin»n»m;for(i nt i=1;i<=m;i+)int a,b;cin> >a»b;cin> >graphab;graphb a=graphab;vis1=1;road1=1;/假設是從1開始backtrack(2);cout&

14、lt;<besta ns<<e ndl;for(i nt i=1;i<=n ;i+) cout<<bestroadi<<"" cout<<1<<e ndl;4.分支限界法void in()scan f("%d", &n);for(i nt i=1; i<=n; i+)for(i nt j=1; j<=n; j+)if(i=j)mpij=INF;con ti nue;scan f("%d", &mpij);struct nodein t

15、visp22;標記哪些點走了int st;/起點int st_p;起點的鄰接點int ed;終點int ed_p;終點的鄰接點int k; 走過的點數int sumv;/經過路徑的距離int lb;/目標函數的值bool operator <(c onst node &p )constreturn lb>p .lb;priority_queue <no de> q;in t low,up;int in q22;/確定上界int dfs(i nt u,i nt k,i nt I)if(k=n) return l+mpu1;int minlen=INF , p;fo

16、r(i nt i=1; i<=n; i+)if(i nqi=0&&mi nle n>mpui)/*取與所有點的連邊中最小的邊*/p=i；in qp=1；return dfs(p,k+1,l+mi nle n);int get_lb( node p)int ret=p.sumv*2;路徑上的點的距離int mi n仁INF,mi n2=INF;起點和終點連出來的邊for(i nt i=1; i<=n; i+)if(p.vispi=0&&min 1>mpip.st)mi n1=mpip.st;ret+=mi n1;for(i nt i=1;

17、i<=n; i+)if(p.vispi=0&&mi n2>mpp.edi)mi n2=mpp.edi;ret+=mi n2;for(i nt i=1; i<=n; i+)if(p.vispi=O)mi n仁min 2=INF;for(i nt j=1; j<=n; j+)if(mi n1>mpij)mi n1=mpij;for(i nt j=1; j<=n; j+)if(mi n2>mpji)mi n2=mpji;ret+=min 1+m in2;return ret%2=0?(ret/2):(ret/2+1);void get_up(

18、)in q1=1;up=dfs(1,1,O);void get_low()low=0;for(i nt i=1; i<=n; i+)/*通過排序求兩個最小值*/in t min 1=INF,mi n2=INF;int tmpA22;for(i nt j=1; j<=n; j+)tmpAj=mpij;sort(tmpA+1,tmpA+1+ n);對臨時的數組進行排序low+=tmpA1;int solve()/*貪心法確定上界*/get_up();/*取每行最小的邊之和作為下界*/get_low();/*設置初始點，默認從1開始*/node star;star.st=1;star.e

19、d=1;star.k=1;for(i nt i=1; i<=n; i+) star.vispi=O;star.visp1=1;star.sumv=0;starb=low;/*ret 為問題的解*/int ret=INF;q.push(star);while(!q.empty()node tmp=q.top();q.pop()；if(tmp.k=n-1)/*找最后一個沒有走的點*/in t p;for(i nt i=1; i<=n; i+)if(tmp.vispi=O)p=i;break;int an s=tmp.sumv+mpptmp.st+mptmp.edp;node judge

20、 = q.top();/*如果當前的路徑和比所有的目標函數值都小則跳出*/if(ans <= judge .lb)ret=mi n(an s,ret);break;/*否則繼續(xù)求其他可能的路徑和，并更新上界*/elseup = min( up,a ns);ret=mi n( ret,a ns);con ti nue;/*當前點可以向下擴展的點入優(yōu)先級隊列*/node n ext;for(i nt i=1; i<=n; i+)if(tmp.vispi=O)n ext.st=tmp.st;/*更新路徑和*/n ext.sumv=tmp.sumv+mptmp.edi;/*更新最后一個點*/n ext.ed=i;/*更新頂點數*/n ext.k=tmp.k+1;/*更新經過的頂點*/for(i nt j=1; j<=n; j+) n