動態(tài)規(guī)劃法回溯法分支限界法求解TSP問題實驗報告

TSP問題算法實驗報告指導教師：季曉慧姓名：辛瑞乾學號：提交日期：2015年11月目錄總述......................................................................動向規(guī)劃法................................................................算法問題解析............................................................算法設計................................................................實現(xiàn)代碼................................................................輸入輸出截圖............................................................OJ提交截圖..............................................................算法優(yōu)化解析............................................................回溯法....................................................................算法問題解析............................................................算法設計................................................................實現(xiàn)代碼................................................................輸入輸出截圖............................................................OJ提交截圖..............................................................算法優(yōu)化解析............................................................分支限界法................................................................算法問題解析............................................................算法設計................................................................實現(xiàn)代碼................................................................輸入輸出截圖............................................................OJ提交截圖..............................................................算法優(yōu)化解析............................................................總結(jié)......................................................................總述TSP問題又稱為旅行商問題，是指一個旅行商要歷經(jīng)所有城市一次最后又回到原來的城市，求最短行程或最小開銷，解決TSP可以用很多算法，比方蠻力法，動向規(guī)劃法?詳盡的時間復雜的也各有差異，本次實驗報告包含動態(tài)規(guī)劃法，回溯法以及分支限界法。動向規(guī)劃法算法問題解析假設n個極點分別用0~n-1的數(shù)字編號，極點之間的代價存放在數(shù)組mp[n][n]中，下面考慮從極點0出發(fā)求解TSP問題的填表形式。第一，按個數(shù)為1、2、?、n-1的序次生成1~n-1個元素的子集存放在數(shù)組x[2^n-1]中，比如當n=4時，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}

。設數(shù)組

dp[n][2^n-1]

存放迭代結(jié)果，其中

dp[i][j]

表示從極點

i經(jīng)過子集

x[j]

中的極點一次且一次，最后回到出發(fā)點

0的最短路徑長度，動態(tài)規(guī)劃法求解

TSP問題的算法以下。算法設計輸入：圖的代價矩陣mp[n][n]輸出：從極點0出發(fā)經(jīng)過所有極點一次且僅一次再回到極點0的最短路徑長度初始化第0列（動向規(guī)劃的界線問題）for(i=1;i<n;i++)dp[i][0]=mp[i][0]依次辦理每個子集數(shù)組x[2^n-1]for(i=1;i<n;i++)if（子集x[j]中不包含i）x[j]中的每個元素k，計算d[i][j]=min{mp[i][k]+dp[k][j-1]};輸出最短路徑長度。實現(xiàn)代碼#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<ctime>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<deque>#include<list>#include<set>#include<map>#include<stack>#include<queue>#include<cctype>#include<numeric>#include<iomanip>#include<bitset>#include<sstream>#include<fstream>#definedebug"outputfordebug\n"#definepi(acos)#defineeps(1e-8)#defineinf0x3f3f3f3f#definelllonglongint#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;constintMax=100005;intn,mp[20][20],dp[20][40000];intmain(){while(~scanf("%d",&n)){intans=inf;memset(mp,0,sizeofmp);for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(i==j){mp[i][j]=inf;continue;}inttmp;scanf("%d",&tmp);mp[i][j]=tmp;}}intmx=(1<<(n-1));dp[0][0]=0;for(inti=1;i<n;i++){dp[i][0]=mp[i][0];}dp[0][mx-1]=inf;for(intj=1;j<(mx-1);j++){for(inti=1;i<n;i++){if((j&(1<<(i-1)))==0){intx,y=inf;for(intk=1;k<n;k++){if((j&(1<<(k-1)))>0){x=dp[k][(j-(1<<(k-1)))]+mp[i][k];y=min(y,x);}}dp[i][j]=y;}}}dp[0][mx-1]=inf;for(inti=1;i<n;i++)dp[0][mx-1]=min(dp[0][mx-1],mp[0][i]+dp[i][(mx-1)-(1<<(i-1))]);printf("%d\n",dp[0][mx-1]);}return0;}輸入輸出截圖OJ提交截圖算法優(yōu)化解析該算法需要對極點會集{1，2，?，n-1}的每一個子集進行操作，因此時間復雜度為O(2^n)。和蠻力法對照，動向規(guī)劃法求解TSP問題，把原來的時間復雜度是O(n!)的排列問題，轉(zhuǎn)變成組合問題，從而降低了算法的時間復雜度，但仍需要指數(shù)時間?；厮莘ㄋ惴▎栴}解析回溯法求解TSP問題，第一把所有的極點的接見標志初始化為0，爾后在解空間樹中從根節(jié)點出發(fā)開始找尋，若是從根節(jié)點到當前結(jié)點對應一個部分解，即滿足上述拘束條件，則在當前結(jié)點處選擇第一棵子樹連續(xù)找尋，否則，對當前子樹的兄弟結(jié)點進行找尋，若是當前結(jié)點的所有子樹都已試一試過并且發(fā)生矛盾，則回溯到當前結(jié)點的父節(jié)點。采用毗鄰矩陣mp[n][n]儲藏極點之間邊的情況，為防備在函數(shù)間傳達參數(shù)，將數(shù)組mp設置為全局變量，設數(shù)組x[n]表示哈密頓回路經(jīng)過的極點。算法設計輸入:無向圖G=(V,E)輸出：哈密頓回路1、將極點數(shù)組x[n]初始化為0，標志數(shù)組vis[n]初始化為0；2、從極點0出發(fā)構(gòu)造哈密頓回路：vis[0]=1;x[0]=1;k=1;3、While(k>=1)x[k]=x[k]+1，找尋下一個極點。、若n個極點沒有被窮舉完，則執(zhí)行以下操作∈E，轉(zhuǎn)步驟；、若數(shù)組x[n]已經(jīng)形成哈密頓路徑，則輸出數(shù)組x[n]，算法結(jié)束；、若數(shù)組x[n]構(gòu)成哈密頓路徑的部分解，則k=k+1，轉(zhuǎn)步驟3；、否則，取悲觀點x[k]的接見標志，重置x[k],k=k-1，轉(zhuǎn)步驟3。實現(xiàn)代碼#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<ctime>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<deque>#include<list>#include<set>#include<map>#include<stack>#include<queue>#include<cctype>#include<numeric>#include<iomanip>#include<bitset>#include<sstream>#include<fstream>#definedebug"outputfordebug\n"#definepi(acos)#defineeps(1e-8)#defineinf0x3f3f3f3f#definelllonglongint#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;intmp[20][20];intx[30],vis[30];intn,k,cur,ans;voidinit(){for(inti=0;i<n;i++)for(intj=0;j<n;j++)mp[i][j]=-1;ans=-1;cur=0;for(inti=1;i<=n;i++)x[i]=i;}voiddfs(intt){if(t==n){if(mp[x[n-1]][x[n]]!=-1&&(mp[x[n]][1]!=-1)&&(cur+mp[x[n-1]][x[n]]+mp[x[n]][1]<ans||ans==-1)){for(inti=1;i<=n;i++)vis[i]=x[i];ans=cur+mp[x[n-1]][x[n]]+mp[x[n]][1];}}else{for(inti=t;i<=n;i++){if(mp[x[t-1]][x[i]]!=-1&&(cur+mp[x[t-1]][x[i]]<ans||ans==-1)){swap(x[t],x[i]);cur+=mp[x[t-1]][x[t]];dfs(t+1);cur-=mp[x[t-1]][x[t]];swap(x[t],x[i]);}}}}intmain(){while(~scanf("%d",&n)){init();for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i==j)continue;scanf("%d",&mp[i][j]);}}egin();sum+=*it;it++;sum+=*it;}returnsum/2;}intgao(nodes){intres=*2;intt1=inf,t2=inf;for(inti=1;i<=n;i++){if(![i]){t1=min(t1,mp[i][]);t2=min(t2,mp[][i]);}}res+=t1;res+=t2;inttmp;for(inti=1;i<=n;i++){tmp=inf;if(![i]){it=Mp[i].begin();res+=*it;for(intj=1;j<=n;j++)tmp=min(tmp,mp[j][i]);res+=tmp;}}return!(res%2)?(res/2):(res/2+1);}voidbfs(nodes){(s);while(!()){nodehead=();();if==n-1){intp;for(inti=1;i<=n;i++){if(![i]){p=i;break;}}intcnt=+mp[p][]+mp[][p];nodetmp=();if(cnt<={ans=min(ans,cnt);return;}else{up=min(up,cnt);ans=min(ans,cnt);continue;}}nodetmp;for(inti=1;i<=n;i++){if(![i]){=;=+mp[][i];=i;=+1;for(intj=1;j<=n;j++)[j]=[j];[i]=1;=gao(tmp);if<=up)(tmp);}}}}intmain(){while(~scanf("%d",&n)){for(inti=0;i<=n;i++)Mp[i].clear();for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i!=j){scanf("%d",&mp[i][j]);Mp[i].push_ba