動(dòng)態(tài)規(guī)劃法,回溯法,分支限界法求解TSP問(wèn)題實(shí)驗(yàn)報(bào)告

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

2、告包含動(dòng)態(tài)規(guī)劃法，回溯法以及分支限界法。動(dòng)態(tài)規(guī)劃法算法問(wèn)題分析假設(shè)n個(gè)頂點(diǎn)分別用0n-1的數(shù)字編號(hào)，頂點(diǎn)之間的代價(jià)存放在數(shù)組mpnn中，下面考慮從頂點(diǎn)0出發(fā)求解TSP問(wèn)題的填表形式。首先，按個(gè)數(shù)為1、2、n-1的順序生成1n-1個(gè)元素的子集存放在數(shù)組x2n-1中，例如當(dāng)n=4時(shí)，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表示從頂點(diǎn)i經(jīng)過(guò)子集xj中的頂點(diǎn)一次且一次，最后回到出發(fā)點(diǎn)0的最短路徑長(zhǎng)度，動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題的算法如下。算法設(shè)計(jì)輸入：圖的代價(jià)矩陣mpnn輸出：從頂點(diǎn)0出發(fā)經(jīng)過(guò)所有頂點(diǎn)一次且僅

3、一次再回到頂點(diǎn)0的最短路徑長(zhǎng)度1. 初始化第0列（動(dòng)態(tài)規(guī)劃的邊界問(wèn)題）for(i=1;in;i+)dpi0=mpi02. 依次處理每個(gè)子集數(shù)組x2n-1for(i=1;in;i+)if（子集xj中不包含i）對(duì)xj中的每個(gè)元素k，計(jì)算dij=minmpik+dpkj-1;3. 輸出最短路徑長(zhǎng)度。實(shí)現(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，搜索下一個(gè)頂點(diǎn)。3.2、若n個(gè)頂點(diǎn)沒(méi)有被窮舉完，則執(zhí)行下列操作3.2.1、若頂點(diǎn)xk不在湖密頓回路上并且(xk-1,xk)E，轉(zhuǎn)步驟3.3；3.2.2、否則，xk=xk+1,搜索下一個(gè)頂點(diǎn)。3.3、若數(shù)組xn已經(jīng)形成哈密頓路徑，則輸出數(shù)

7、組xn，算法結(jié)束；3.4、若數(shù)組xn構(gòu)成哈密頓路徑的部分解，則k=k+1，轉(zhuǎn)步驟3；3.5、否則，取消頂點(diǎn)xk的訪問(wèn)標(biāo)志，重置xk,k=k-1，轉(zhuǎn)步驟3。實(shí)現(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）的一個(gè)排列，對(duì)應(yīng)的解空間樹(shù)種至少有n!個(gè)葉子結(jié)點(diǎn)，每個(gè)葉子結(jié)點(diǎn)代表一種可能解。當(dāng)找到可行的最優(yōu)解時(shí)，算法停止。分支限界法算法問(wèn)題分析分支限界法解決TSP問(wèn)題首先確定目標(biāo)函數(shù)的界down,up，可以

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

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

13、分量。實(shí)現(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;