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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上TSP問題算法實(shí)驗(yàn)報(bào)告指導(dǎo)教師： 季曉慧 姓 名： 辛瑞乾 學(xué) 號(hào)： 提交日期： 2015年11月 目錄總述TSP問題又稱為旅行商問題，是指一個(gè)旅行商要?dú)v經(jīng)所有城市一次最后又回到原來的城市，求最短路程或最小花費(fèi)，解決TSP可以用好多算法，比如蠻力法，動(dòng)態(tài)規(guī)劃法具體的時(shí)間復(fù)雜的也各有差異，本次實(shí)驗(yàn)報(bào)告包含動(dòng)態(tài)規(guī)劃法，回溯法以及分支限界法。動(dòng)態(tài)規(guī)劃法算法問題分析假設(shè)n個(gè)頂點(diǎn)分別用0n-1的數(shù)字編號(hào)，頂點(diǎn)之間的代價(jià)存放在數(shù)組mpnn中，下面考慮從頂點(diǎn)0出發(fā)求解TSP問題的填表形式。首先，按個(gè)數(shù)為1、2、n-1的順序生成1n-1個(gè)元素的子集存放在數(shù)組x2n-1中，例如當(dāng)n=4

2、時(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)過子集xj中的頂點(diǎn)一次且一次，最后回到出發(fā)點(diǎn)0的最短路徑長度，動(dòng)態(tài)規(guī)劃法求解TSP問題的算法如下。算法設(shè)計(jì)輸入：圖的代價(jià)矩陣mpnn輸出：從頂點(diǎn)0出發(fā)經(jīng)過所有頂點(diǎn)一次且僅一次再回到頂點(diǎn)0的最短路徑長度1. 初始化第0列（動(dòng)態(tài)規(guī)劃的邊界問題）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.

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 debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f3f#defi

4、ne ll long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;const int mod = ;const int Max = ;int n,mp2020,dp2040000;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;

5、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&(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

6、+dpi(mx-1)-(1=1)3.1、xk=xk+1，搜索下一個(gè)頂點(diǎn)。3.2、若n個(gè)頂點(diǎn)沒有被窮舉完，則執(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ù)組xn，算法結(jié)束；3.4、若數(shù)組xn構(gòu)成哈密頓路徑的部分解，則k=k+1，轉(zhuǎn)步驟3；3.5、否則，取消頂點(diǎn)xk的訪問標(biāo)志，重置xk,k=k-1，轉(zhuǎn)步驟3。實(shí)現(xiàn)代碼#include #include #include #include #include #include #include #include #

7、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 long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using nam

8、espace 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=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=

9、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) 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)化分析在哈密頓回路

10、的可能解中，考慮到約束條件xi!=xj(1=I,j=n,i!=j),則可能解應(yīng)該是（1,2,n）的一個(gè)排列，對(duì)應(yīng)的解空間樹種至少有n!個(gè)葉子結(jié)點(diǎn)，每個(gè)葉子結(jié)點(diǎn)代表一種可能解。當(dāng)找到可行的最優(yōu)解時(shí)，算法停止。分支限界法算法問題分析分支限界法解決TSP問題首先確定目標(biāo)函數(shù)的界down,up，可以采用貪心法確定TSP問題的一個(gè)上界。如何求得TSP問題的一個(gè)合理的下界呢？對(duì)于無向圖的代價(jià)矩陣，吧矩陣中每一行最小的元素想家，可以得到一個(gè)簡單的下界，但是還有一個(gè)信息量更大的下界：考慮一個(gè)TSP問題的完整解，在每條路徑上，每個(gè)城市都有兩條鄰接邊，一條是進(jìn)入這個(gè)城市的，另一條是離開這個(gè)城市的，那么，如果把矩陣

11、中每一行最小的兩個(gè)元素相加在除以2，假設(shè)圖中所有的代價(jià)都是整數(shù)，再對(duì)這個(gè)結(jié)果向上取整，就得到一個(gè)合理的下界。需要強(qiáng)調(diào)的是，這個(gè)解可能不是一個(gè)可行解（可能沒有構(gòu)成哈密頓回路），但給出了一個(gè)參考下界。一般情況下，假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,rk),即路徑上已確定了k個(gè)頂點(diǎn)，此時(shí)，該部分解的目標(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、 循

12、環(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è)分量。實(shí)現(xiàn)代碼#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #in

13、clude #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 = ;const int Max = ;/*/vectorMp20;vector:iterator

14、 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; ;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() in

15、t 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,t2=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+=*i

16、t; 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.empty() 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=t

17、mp.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) tmp.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

18、 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; up=0; up+=getup(1,1,up); low=getlow(); node fir; fir.st=1; fir.ed=1; fir.num=1; for(int i=1; i=n; i+) fir.xi=0; fir.x1=1; fir.dis=0; fir.val=low; ans=inf; bfs(fir); printf(%dn,ans); return 0;輸入輸出截圖OJ提交截圖算法優(yōu)化分析分支限界法的復(fù)雜度是根據(jù)數(shù)據(jù)的不同而不同，搜索的節(jié)點(diǎn)越少，復(fù)雜度越低，跟目標(biāo)函數(shù)的選擇有很大關(guān)系。目標(biāo)函數(shù)值的計(jì)算也會(huì)需要一定時(shí)間，比如此文章中的目標(biāo)函數(shù)值求解的復(fù)雜度是O(n2 )。當(dāng)然此算法仍然有可以優(yōu)化的地方，比如在記