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

1、TSP問題算法實驗報告指導(dǎo)教師： 季曉慧 姓 名： 辛瑞乾 學(xué) 號： 1004131114 提交日期： 2015年11月 目錄總述2動態(tài)規(guī)劃法2算法問題分析2算法設(shè)計2實現(xiàn)代碼2輸入輸出截圖5OJ提交截圖5算法優(yōu)化分析5回溯法5算法問題分析5算法設(shè)計6實現(xiàn)代碼6輸入輸出截圖8OJ提交截圖8算法優(yōu)化分析9分支限界法9算法問題分析9算法設(shè)計9實現(xiàn)代碼9輸入輸出截圖14OJ提交截圖14算法優(yōu)化分析14總結(jié)15總述TSP問題又稱為旅行商問題，是指一個旅行商要歷經(jīng)所有城市一次最后又回到原來的城市，求最短路程或最小花費，解決TSP可以用好多算法，比如蠻力法，動態(tài)規(guī)劃法具體的時間復(fù)雜的也各有差異，本次實驗報

2、告包含動態(tài)規(guī)劃法，回溯法以及分支限界法。動態(tài)規(guī)劃法算法問題分析假設(shè)n個頂點分別用0n-1的數(shù)字編號，頂點之間的代價存放在數(shù)組mpnn中，下面考慮從頂點0出發(fā)求解TSP問題的填表形式。首先，按個數(shù)為1、2、n-1的順序生成1n-1個元素的子集存放在數(shù)組x2n-1中，例如當(dāng)n=4時，x1=1,x2=2,x3=3,x4=1,2,x5=1,3,x6=2,3,x7=1,2,3。設(shè)數(shù)組dpn2n-1存放迭代結(jié)果，其中dpij表示從頂點i經(jīng)過子集xj中的頂點一次且一次，最后回到出發(fā)點0的最短路徑長度，動態(tài)規(guī)劃法求解TSP問題的算法如下。算法設(shè)計輸入：圖的代價矩陣mpnn輸出：從頂點0出發(fā)經(jīng)過所有頂點一次且僅

3、一次再回到頂點0的最短路徑長度1. 初始化第0列（動態(tài)規(guī)劃的邊界問題）for(i=1;in;i+)dpi0=mpi02. 依次處理每個子集數(shù)組x2n-1for(i=1;in;i+)if（子集xj中不包含i）對xj中的每個元素k，計算dij=minmpik+dpkj-1;3. 輸出最短路徑長度。實現(xiàn)代碼#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #incl

4、ude #include #include #include #include #define debug output for debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f3f#define ll long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;const int mod = 1000000007;const int Max = 100005;int n,mp2020,dp

5、2040000;int main() while(scanf(%d,&n) int ans=inf; memset(mp,0,sizeof mp); for(int i=0; in; i+) for(int j=0; jn; j+) if(i=j) mpij=inf; continue; int tmp; scanf(%d,&tmp); mpij=tmp; int mx=(1(n-1); dp00=0; for(int i=1; in; i+) dpi0=mpi0; dp0mx-1=inf; for(int j=1; j(mx-1); j+) for(int i=1; in; i+) if(j

6、&(1(i-1)=0) int x,y=inf; for(int k=1; kn; k+) if(j&(10) x=dpk(j-(1(k-1)+mpik; y=min(y,x); dpij=y; dp0mx-1=inf; for(int i=1;in;i+) dp0mx-1=min(dp0mx-1,mp0i+dpi(mx-1)-(1=1)3.1、xk=xk+1，搜索下一個頂點。3.2、若n個頂點沒有被窮舉完，則執(zhí)行下列操作3.2.1、若頂點xk不在湖密頓回路上并且(xk-1,xk)E，轉(zhuǎn)步驟3.3；3.2.2、否則，xk=xk+1,搜索下一個頂點。3.3、若數(shù)組xn已經(jīng)形成哈密頓路徑，則輸出數(shù)

7、組xn，算法結(jié)束；3.4、若數(shù)組xn構(gòu)成哈密頓路徑的部分解，則k=k+1，轉(zhuǎn)步驟3；3.5、否則，取消頂點xk的訪問標(biāo)志，重置xk,k=k-1，轉(zhuǎn)步驟3。實現(xiàn)代碼#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug output for debug

8、n#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f3f#define ll long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;int mp2020;int x30,vis30;int n,k,cur,ans;void init() for(int i=0;in;i+) for(int j=0;jn;j+) mpij=-1; ans=-1;cur=0; for(int i=1;i=n;i+)xi

9、=i;void dfs(int t) if(t=n) if(mpxn-1xn!=-1&(mpxn1!=-1)&(cur+mpxn-1xn+mpxn1ans|ans=-1) for(int i=1;i=n;i+) visi=xi; ans=cur+mpxn-1xn+mpxn1; else for(int i=t;i=n;i+) if(mpxt-1xi!=-1&(cur+mpxt-1xians|ans=-1) swap(xt,xi); cur+=mpxt-1xt; dfs(t+1); cur-=mpxt-1xt; swap(xt,xi); int main() while(scanf(%d,&n)

10、 init(); for(int i=1; i=n; i+) for(int j=1; j=n; j+) if(i=j) continue; scanf(%d,&mpij); /puts(YES); dfs(2); coutansendl; return 0;輸入輸出截圖OJ提交截圖算法優(yōu)化分析在哈密頓回路的可能解中，考慮到約束條件xi!=xj(1=I,j=n,i!=j),則可能解應(yīng)該是（1,2,n）的一個排列，對應(yīng)的解空間樹種至少有n!個葉子結(jié)點，每個葉子結(jié)點代表一種可能解。當(dāng)找到可行的最優(yōu)解時，算法停止。分支限界法算法問題分析分支限界法解決TSP問題首先確定目標(biāo)函數(shù)的界down,up，可以

11、采用貪心法確定TSP問題的一個上界。如何求得TSP問題的一個合理的下界呢？對于無向圖的代價矩陣，吧矩陣中每一行最小的元素想家，可以得到一個簡單的下界，但是還有一個信息量更大的下界：考慮一個TSP問題的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條是進(jìn)入這個城市的，另一條是離開這個城市的，那么，如果把矩陣中每一行最小的兩個元素相加在除以2，假設(shè)圖中所有的代價都是整數(shù)，再對這個結(jié)果向上取整，就得到一個合理的下界。需要強(qiáng)調(diào)的是，這個解可能不是一個可行解（可能沒有構(gòu)成哈密頓回路），但給出了一個參考下界。一般情況下，假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,rk),即路徑上已確定了k個頂點，此時，該部

12、分解的目標(biāo)函數(shù)值的計算方法（限界函數(shù)）如下：Lb=（2crir(i+1)+ri行不在路徑上的最小元素+ri行最小的兩個元素）/2算法設(shè)計輸入：圖G=(V,E)輸出：最短哈密頓回路1、 根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up；2、 計算根節(jié)點的目標(biāo)函數(shù)值并加入待處理結(jié)點表PT；3、 循環(huán)知道某個葉子結(jié)點的目標(biāo)函數(shù)值在表PT中取得極小值3.1、i=表PT中具有最小值的結(jié)點；3.2、對結(jié)點i的每個孩子幾點x執(zhí)行下列操作：3.2.1估算結(jié)點x的目標(biāo)函數(shù)值lb；3.2.2若（lb=up），則將結(jié)點x加入表PT中；否則丟棄該結(jié)點；4、將葉子結(jié)點對應(yīng)的最優(yōu)解輸出，回溯求得最優(yōu)解的各個

13、分量。實現(xiàn)代碼#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug output for debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f3f#define ll

14、long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;const int mod = 1000000007;const int Max = 100005;/*/vectorMp20;vector:iterator it;int mp2020;int vis20;int up,low,n,ans;struct node int x20,st,ed,dis,val,num; bool operator(const node &p)const return valp.val

15、; ;priority_queueq;int getup(int u,int v,int w) if(v=n) return w+mpu1; int sum=inf,p; for(int i=1; impui) sum=mpui; p=i; visp=1; return getup(p,v+1,w+sum);int getlow() int sum=0; for(int i=1; i=n; i+) it=Mpi.begin(); sum+=*it; it+; sum+=*it; return sum/2;int gao(node s) int res=s.dis*2; int t1=inf,t

16、2=inf; for(int i=1; i=n; i+) if(!s.xi) t1=min(t1,mpis.st); t2=min(t2,mps.edi); res+=t1; res+=t2; int tmp; for(int i=1; i=n; i+) tmp=inf; if(!s.xi) it=Mpi.begin(); res+=*it; for(int j=1; j=n; j+) tmp=min(tmp,mpji); res+=tmp; return !(res%2) ? (res/2):(res/2+1);void bfs(node s) q.push(s); while(!q.emp

17、ty() node head=q.top(); q.pop(); if(head.num=n-1) int p; for(int i=1; i=n; i+) if(!head.xi) p=i; break; int cnt=head.dis+mpphead.st+mphead.edp; node tmp=q.top(); if(cnt=tmp.val) ans=min(ans,cnt); return; else up=min(up,cnt); ans=min(ans,cnt); continue; node tmp; for(int i=1; i=n; i+) if(!head.xi) tm

18、p.st=head.st; tmp.dis=head.dis+mphead.edi; tmp.ed=i; tmp.num=head.num+1; for(int j=1; j=n; j+) tmp.xj=head.xj; tmp.xi=1; tmp.val=gao(tmp); if(tmp.val=up) q.push(tmp); int main() while(scanf(%d,&n) for(int i=0; i=n; i+) Mpi.clear(); for(int i=1; i=n; i+) for(int j=1; j=n; j+) if(i!=j) scanf(%d,&mpij); Mpi.push_back(mpij); else mpij=inf; sort(Mpi.begin(),Mpi.end(); memset(vis,0,sizeof vis); vis1=1;