TSP問(wèn)題的解決方案

1、算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告學(xué)號(hào)：日期：20161230姓名：得分:一、實(shí)驗(yàn)內(nèi)容：TSP問(wèn)題二、所用算法的基本思想及復(fù)雜度分析：1、蠻力法1）基本思想借助矩陣把問(wèn)題轉(zhuǎn)換為矩陣中點(diǎn)的求解。首先構(gòu)造距離矩陣，任意節(jié)點(diǎn)到自身節(jié)點(diǎn)的距離為無(wú)窮大。在第一行找到最小項(xiàng)a1j,從而跳轉(zhuǎn)到第j行，再找到最小值ajk,再到第k行進(jìn)行查找。然后構(gòu)造各行允許數(shù)組rown=1,1T,各列允許數(shù)組colablen=0,1,1,其中1表示允許訪問(wèn)，即該節(jié)點(diǎn)未被訪問(wèn)；0表示不允許訪問(wèn)，即該節(jié)點(diǎn)已經(jīng)被訪問(wèn)。如果改行或該列不允許訪問(wèn)，跳過(guò)該點(diǎn)訪問(wèn)下一節(jié)點(diǎn)。程序再發(fā)問(wèn)最后一個(gè)節(jié)點(diǎn)前，所訪問(wèn)的行中至少有1個(gè)允許訪問(wèn)的節(jié)點(diǎn)，依次訪問(wèn)這些節(jié)

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

3、合中，嘗試每如果V'不為空，那么就是對(duì)子問(wèn)題的最優(yōu)求解。你必須在個(gè)，并求出最優(yōu)解。d(i,V'尸minCik+d(k,V-k)注：Cik表示你選擇的城市和城市i的距離，d（k, V -k）是一個(gè)子問(wèn)題。綜上所述，TSP問(wèn)題的動(dòng)態(tài)規(guī)劃方程就出來(lái)了：卜2）復(fù)雜度分析和蠻力法相比，動(dòng)態(tài)規(guī)劃求解tsp問(wèn)題，把原來(lái)時(shí)間復(fù)雜性O(shè)（n!）的排列轉(zhuǎn)化為組合問(wèn)題，從而降低了時(shí)間復(fù)雜度，但仍需要指數(shù)時(shí)間。3、回溯法1）基本思想確定了解空間的組織結(jié)構(gòu)后，回溯法從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)

4、新結(jié)點(diǎn)即成為新的活結(jié)點(diǎn)，并為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)時(shí)為止。回溯法求解TSP問(wèn)題，首先把所有的頂點(diǎn)的訪問(wèn)標(biāo)志初始化為0,然后在解空間樹中從根節(jié)點(diǎn)出發(fā)開始搜索，如果從根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)一個(gè)部分解，即滿足上述約束條件，則在當(dāng)前結(jié)點(diǎn)處選擇第一棵子樹繼續(xù)搜索，否則，對(duì)當(dāng)前子樹的兄弟結(jié)點(diǎn)進(jìn)行搜索，如果當(dāng)前結(jié)點(diǎn)的所有子樹都已嘗試過(guò)并且發(fā)生沖突，則回溯到當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)。采用鄰接矩陣mp

5、nn存儲(chǔ)頂點(diǎn)之間邊的情況，為避免在函數(shù)間傳遞參數(shù)，將數(shù)組mp設(shè)置為全局變量，設(shè)數(shù)組xn表示哈密頓回路經(jīng)過(guò)的頂點(diǎn)。2）復(fù)雜度分析在哈密頓回路的可能解中，考慮到約束條件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í)，算法停止。根據(jù)遞歸條件不同時(shí)間復(fù)雜度也會(huì)不同，這里為O（n?。?。4、分支限界法1）基本思想分支界限法以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)勢(shì)的方式搜索問(wèn)題的解空間樹。問(wèn)題的解空間樹是表示問(wèn)題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問(wèn)題的解空

6、間樹時(shí)，分支界限法與回溯法的主要區(qū)別在于他們對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所采用的擴(kuò)展方式不同。在分支界限法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解得兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。算法開始時(shí)創(chuàng)建一個(gè)最小堆，用于表示活結(jié)點(diǎn)優(yōu)先隊(duì)列。堆中每個(gè)結(jié)點(diǎn)的子樹費(fèi)用的下界lcost值是優(yōu)先隊(duì)列的優(yōu)先級(jí)。接著算法計(jì)算出圖中每個(gè)頂點(diǎn)的最小費(fèi)用出邊并用minout記錄。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路，算法即告結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的minout作算法初始化。2）復(fù)雜度分析目標(biāo)

7、函數(shù)（限界函數(shù)），lb分為三部分，第一部分是經(jīng)過(guò)路徑的長(zhǎng)度相加的2倍，加上第二部分離著路徑首尾節(jié)點(diǎn)最近的距離相加（不在已知路徑上的），加上第三部分除了路徑上節(jié)點(diǎn)，矩陣中兩個(gè)最短的距離相加，最后這三部分和相加，得到的結(jié)果除以2便是每個(gè)節(jié)點(diǎn)的限界值。由于限界函數(shù)的不同，下界為O（n）,上界為O（2M）,智力特定指出。三、源程序及注釋：1、蠻力法intmain（）int*a;printf("輸入節(jié)點(diǎn)個(gè)數(shù)：n");scanf("%d",&n);printf("輸入%d維對(duì)稱矩陣：n",n);colable=(int*)malloc(s

8、izeof(int)*n);colable0=0;/對(duì)各列允許矩陣進(jìn)行賦值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=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)'while(rowi=1)j=min(ai);ro

9、wi=0;colablej=0;printf("訪問(wèn)路徑：n");printf("t%d->%dn",i,j);s=s+aij;i=j;printf("最短總距離為：%dn",s);intmin(int*a)intj=0,m=a0,k=0;while(colablej=0|rowj=0)j+;m=aj;/求最短距離for(;j<n;j+)if(colablej=1&&rowj=1)/節(jié)點(diǎn)沒(méi)有被訪問(wèn)if(m>=aj)m=aj;/m始終保持最短距離k=j;returnk;2、動(dòng)態(tài)規(guī)劃法intinit()i

10、nti;intj;intt;if(scanf("%d",&n尸EOF)return-1;for(i=0;i<n;i+)for(j=0;j<n;j+)if(i=j)continue;scanf("%d",&gij);)memset(con,-1,sizeof(con);for(i=0;i<n;i+)biti=1<<i;)t=1;for(i=1;i<n;i+)cont<<(i-1)i=g0i;return1;intgetcon(ints,intk)intt,tt;inti;intmin=INF;

11、if(consk!=-1)returnconsk;t=s&(bitk-1);for(i=1;i<n;i+)tt=t&biti-1;if(tt>0)if(getcon(t,i)+gik<min)min=getcon(t,i)+gik;consk=min;returnconsk;3 .回溯法voidbacktrack(inti)if(i>n)if(graphroadn1!=INF&&(ans+graphroadn1)<bestans)bestans=ans+graphroadn1;for(intj=1;j<=n;j+)bestro

12、adj=roadj;elsefor(intj=1;j<=n;j+)if(graphroadi-1j!=INF&&ans+graphroadi-1加卜bestans&&!visj)roadi=j;ans+=graphroadi-1皿；visj=1；backtrack(i+1);/改回輔助的全局變量ans-=graphroadi-1皿；visj=0；intmain()memset(graph,INF,sizeof(graph);cin>>n>>m;for(inti=1;i<=m;i+)inta,b;cin>>a>

13、>b;cin>>graphab;graphba=graphab;vis1=1;road1=1;/假設(shè)是從1開始backtrack(2);cout<<bestans<<endl;for(inti=1;i<=n;i+)cout<<bestroadi<<""cout<<1<<endl;4 .分支限界法voidin()5scanf("%d",&n);for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)if(i=j)mpij=

14、INF;continue;scanf("%d",&mpij);structnodeintvisp22;標(biāo)記哪些點(diǎn)走了intst;/起點(diǎn)intst_p;/起點(diǎn)的鄰接點(diǎn)inted;/終點(diǎn)inted_p;/終點(diǎn)的鄰接點(diǎn)intk;走過(guò)的點(diǎn)數(shù)intsumv;經(jīng)過(guò)路徑的距離intlb;/目標(biāo)函數(shù)的值booloperator<(constnode&p)constreturnlb>p.lb;；priority_queue<node>q;intlow,up;intinq22;/確定上界intdfs(intu,intk,intl)if(k=n)retur

15、nl+mpu1;intminlen=INF,p;for(inti=1;i<=n;i+)if(inqi=0&&minlen>mpui)/*取與所有點(diǎn)的連邊中最小的邊*/minlen=mpui;p=i；inqp=1；returndfs(p,k+1,l+minlen);intget_lb(nodep)intret=p.sumv*2;路徑上的點(diǎn)的距離intmin1=INF,min2=INF;起點(diǎn)和終點(diǎn)連出來(lái)的邊f(xié)or(inti=1;i<=n;i+)if(p.vispi=0&&min1>mpip.st)min1=mpip.st;ret+=min1;

16、for(inti=1;i<=n;i+)if(p.vispi=0&&min2>mpp.edi)min2=mpp.edi;ret+=min2;for(inti=1;i<=n;i+)if(p.vispi=0)min1=min2=INF;for(intj=1;j<=n;j+)if(min1>mpij)min1=mpij;for(intj=1;j<=n;j+)if(min2>mp皿i)min2=mpji;ret+=min1+min2;returnret%2=0?(ret/2):(ret/2+1);voidget_up()inq1=1;up=dfs

17、(1,1,0);voidget_low()low=0;for(inti=1;i<=n;i+)/*通過(guò)排序求兩個(gè)最小值*/intmin1=INF,min2=INF;inttmpA22;for(intj=1;j<=n;j+)tmpAj=mpij;sort(tmpA+1,tmpA+1+n);/對(duì)臨時(shí)的數(shù)組進(jìn)行排序low+=tmpA1;intsolve()/*貪心法確定上界*/get_up()；/*取每行最小的邊之和作為下界*/get_low();/*設(shè)置初始點(diǎn)，默認(rèn)從1開始*/nodestar;star.st=1;star.ed=1;star.k=1;for(inti=1;i<=n

18、;i+)star.vispi=0;star.visp1=1;star.sumv=0;star.lb=low;/*ret為問(wèn)題的解*/intret=INF;q.push(star);while(!q.empty()nodetmp=q.top();q.pop();if(tmp.k=n-1)/*找最后一個(gè)沒(méi)有走的點(diǎn)*/intp；for(inti=1;i<=n;i+)if(tmp.vispi=0)p=i；break;intans=tmp.sumv+mpptmp.st+mptmp.edp;nodejudge=q.top();/*如果當(dāng)前的路徑和比所有的目標(biāo)函數(shù)值都小則跳出*/if(ans<=judge.lb)ret=min(ans,ret);break;/*否則繼續(xù)求其他可能的路徑和，并更新上界*/elseup=min(up,ans);ret=min(ret,ans);continue;/*當(dāng)前點(diǎn)可以向下擴(kuò)展的點(diǎn)入優(yōu)先級(jí)隊(duì)列*/nodenext;for(inti=1;i<=n;i+)if(tmp.vispi=0)next.st=tmp.st;/*更新路徑和*/next.sumv=tmp.sumv+mptmp.edi;/*更新最后一個(gè)點(diǎn)*/next.ed=i;/*