TSP問(wèn)題分析動(dòng)態(tài)規(guī)劃,分支界限法,蠻力法

③inq[i]表示頂點(diǎn)i已經(jīng)走過(guò)了。算法描述首先通過(guò)貪心法求解的值作為上界,把每個(gè)點(diǎn)最近的兩條邊之和的1/2作為下界。分支限界法通過(guò)設(shè)定目標(biāo)函數(shù),每次從優(yōu)先級(jí)隊(duì)列中取目標(biāo)函數(shù)的值最小的節(jié)點(diǎn)。先判斷是否已經(jīng)經(jīng)過(guò)了n-1個(gè)點(diǎn),如果已經(jīng)經(jīng)過(guò)了n-1個(gè)點(diǎn),那么可直接求出最短路徑和,并與在隊(duì)列里的其他節(jié)點(diǎn)的目標(biāo)函數(shù)值比較,如果該路徑和比其他所有在隊(duì)列里的節(jié)點(diǎn)的目標(biāo)函數(shù)值都小,那么改路徑和就是問(wèn)題的解。否則,繼續(xù)計(jì)算優(yōu)先級(jí)隊(duì)列里面的其他節(jié)點(diǎn)。源程序及注釋：這里默認(rèn)頂點(diǎn)的個(gè)數(shù)小于22。 1、動(dòng)態(tài)規(guī)劃法#include<iostream>#include<cstdio>#defineINF9999usingnamespacestd;intmp[22][22];intn;voidin<>{scanf<"%d",&n>;for<inti=0;i<n;i++>{for<intj=0;j<n;j++>{if<i==j>{mp[i][j]=INF;continue;}scanf<"%d",&mp[i][j]>;}}}intdp[22][1<<22];intsolve<>{ints=<1<<<n-1>>;dp[0][0]=0;for<inti=1;i<n;i++>{dp[i][0]=mp[i][0];}dp[0][<s-1>]=INF;for<intj=1;j<<s-1>;j++>//總共有n-1個(gè)點(diǎn),但不能全部取{for<inti=1;i<n;i++>//把1~<n-1>這n-1個(gè)點(diǎn),映射為集合對(duì)應(yīng)的二進(jìn)制數(shù)中的0~<n-2>位{if<<j&<1<<<i-1>>>==0>//i不在集合中{intm=INF;for<intk=1;k<n;k++>{if<<j&<1<<<k-1>>>>0>//k在集合中{inttmp=dp[k][<j-<1<<<k-1>>>]+mp[i][k];if<m>tmp>m=tmp;}}dp[i][j]=m;}}}dp[0][s-1]=INF;for<inti=1;i<n;i++>{dp[0][s-1]=min<dp[0][s-1],mp[0][i]+dp[i][<s-1>-<1<<<i-1>>]>;}returndp[0][s-1];}intmain<>{in<>;printf<"%d\n",solve<>>;return0;} 2、貪心法#include<iostream>#include<cstdio>#defineINF9999usingnamespacestd;intn;intmp[22][22];intinq[22];voidin<>{scanf<"%d",&n>;for<inti=1;i<=n;i++>{for<intj=1;j<=n;j++>{if<i==j>{mp[i][j]=INF;continue;}scanf<"%d",&mp[i][j]>;}}}intdfs<intu,intk,intl>{if<k==n>returnl+mp[u][1];intminlen=INF,p;for<inti=1;i<=n;i++>{if<inq[i]==0&&minlen>mp[u][i]>/*取與所有點(diǎn)的連邊中最小的邊*/{minlen=mp[u][i];p=i;}}inq[p]=1;returndfs<p,k+1,l+minlen>;}intmain<>{in<>;inq[1]=1;printf<"%d\n",dfs<1,1,0>>;return0;} 3、分支限界法//分支限界法#include<iostream>#include<algorithm>#include<cstdio>#include<queue>#defineINF100000usingnamespacestd;/*n*n的一個(gè)矩陣*/intn;intmp[22][22];//最少3個(gè)點(diǎn),最多15個(gè)點(diǎn)/*輸入距離矩陣*/voidin<>{scanf<"%d",&n>;for<inti=1;i<=n;i++>{for<intj=1;j<=n;j++>{if<i==j>{mp[i][j]=INF;continue;}scanf<"%d",&mp[i][j]>;}}}structnode{intvisp[22];//標(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>const{returnlb>p.lb;}};priority_queue<node>q;intlow,up;intinq[22];//確定上界intdfs<intu,intk,intl>{if<k==n>returnl+mp[u][1];intminlen=INF,p;for<inti=1;i<=n;i++>{if<inq[i]==0&&minlen>mp[u][i]>/*取與所有點(diǎn)的連邊中最小的邊*/{minlen=mp[u][i];p=i;}}inq[p]=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.visp[i]==0&&min1>mp[i][p.st]>{min1=mp[i][p.st];}}ret+=min1;for<inti=1;i<=n;i++>{if<p.visp[i]==0&&min2>mp[p.ed][i]>{min2=mp[p.ed][i];}}ret+=min2;for<inti=1;i<=n;i++>{if<p.visp[i]==0>{min1=min2=INF;for<intj=1;j<=n;j++>{if<min1>mp[i][j]>min1=mp[i][j];}for<intj=1;j<=n;j++>{if<min2>mp[j][i]>min2=mp[j][i];}ret+=min1+min2;}}returnret%2==0?<ret/2>:<ret/2+1>;}voidget_up<>{inq[1]=1;up=dfs<1,1,0>;}voidget_low<>{low=0;for<inti=1;i<=n;i++>{/*通過(guò)排序求兩個(gè)最小值*/intmin1=INF,min2=INF;inttmpA[22];for<intj=1;j<=n;j++>{tmpA[j]=mp[i][j];}sort<tmpA+1,tmpA+1+n>;//對(duì)臨時(shí)的數(shù)組進(jìn)行排序low+=tmpA[1];}}intsolve<>{/*貪心法確定上界*/get_up<>;/*取每行最小的邊之和作為下界*/get_low<>;/*設(shè)置初始點(diǎn),默認(rèn)從1開(kāi)始*/nodestar;star.st=1;star.ed=1;star.k=1;for<inti=1;i<=n;i++>star.visp[i]=0;star.visp[1]=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.visp[i]==0>{p=i;break;}}intans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p];nodejudge=q.top<>;/*如果當(dāng)前的路徑和比所有的目標(biāo)函數(shù)值都小則跳出*/if<ans<=judge.lb>{ret=min<ans,ret>;break;}/*否則繼續(xù)求其他可能的路徑和,并更新上界*/else{up=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.visp[i]==0>{next.st=tmp.st;/*更新路徑和*/next.sumv=tmp.sumv+mp[tmp.ed][i];/*更新最后一個(gè)點(diǎn)*/next.ed=i;/*更新頂點(diǎn)數(shù)*/next.k=tmp.k+1;/*更新經(jīng)過(guò)的頂點(diǎn)*/for<intj=1;j<=n;j++>next.visp[j]=tmp.visp[j];next.visp[i]=1;/*求目標(biāo)函數(shù)*/next.lb=get_lb<next>;/*如果大于上界就不加入隊(duì)列*/if<next.lb>up>continue;q.push<next>;}}}returnret;}intmain<>{in<>;printf<"%d\n",solve<>>;return0;}四、運(yùn)行輸出結(jié)果： 〔貼出程序運(yùn)行完成時(shí)的屏幕截圖或者輸出文件的內(nèi)容這里采用相同的兩組數(shù)據(jù)進(jìn)行測(cè)試。1、動(dòng)態(tài)規(guī)劃法樣例1：樣例2：2、貪心法樣例1：樣例2：貪心法只能求局部最優(yōu)解,局部最優(yōu)解不一定是全局最優(yōu)解。 3、分支限界法樣例1：樣例2：五、調(diào)試和運(yùn)行程序過(guò)程中產(chǎn)生的問(wèn)題及采取的措施： 1、動(dòng)態(tài)規(guī)劃法中輸出錯(cuò)誤,通過(guò)測(cè)試數(shù)據(jù)進(jìn)行反復(fù)驗(yàn)證,并分塊輸出局部結(jié)果,從而發(fā)現(xiàn)問(wèn)題并解決。2、貪心法對(duì)第二組樣例的解不正確,因?yàn)榫植孔顑?yōu)解不一定是全局最優(yōu)解。3、分支限界法對(duì)于測(cè)試樣例輸出隨機(jī)值,solve<>函數(shù)在每次返回的時(shí)候結(jié)果不一致。通過(guò)反復(fù)觀察代碼,發(fā)現(xiàn)循環(huán)跳出的條件有問(wèn)題,應(yīng)該是當(dāng)前的解小于或等于隊(duì)列中的目標(biāo)函數(shù)值才跳出。六、對(duì)算法的程序的討論、分析,改進(jìn)設(shè)想,其它經(jīng)驗(yàn)教訓(xùn)： 1、動(dòng)態(tài)規(guī)劃法算法時(shí)間復(fù)雜度為O<>,在oj上的測(cè)試時(shí)間如下：〔oj上的測(cè)試樣例n最大值為15 2、貪心法只能求局部最優(yōu)解,不一定是全局最優(yōu)解。所以第二組樣例的解不正確。 3、分支限界法的復(fù)雜度是根據(jù)數(shù)據(jù)的不同而不同,搜索的節(jié)點(diǎn)越少,復(fù)雜度越低,跟目標(biāo)函數(shù)的選擇有很大關(guān)系。目標(biāo)函數(shù)值的計(jì)算也會(huì)需要一定時(shí)間,比如此文章中的目標(biāo)函數(shù)值求解的復(fù)雜度是O<>。在oj上的測(cè)試時(shí)間如下：在設(shè)置節(jié)點(diǎn)的時(shí)候,用數(shù)組標(biāo)記經(jīng)過(guò)的頂點(diǎn),visp[i]=1,則說(shuō)明i點(diǎn)已經(jīng)經(jīng)過(guò)了,由于是靜態(tài)分配空間,所以每次創(chuàng)建新的節(jié)點(diǎn),都會(huì)增加空間。所以可以考慮動(dòng)態(tài)分配空間,把不用的節(jié)點(diǎn)的空間釋放掉。對(duì)于頂點(diǎn)少的TSP問(wèn)題,還可以采用蠻力法。時(shí)間復(fù)雜度為O<n!>,但實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單,這里使用了stl中生成全全排列的函數(shù)next_permutation<>。在oj上的測(cè)試時(shí)間如下：〔測(cè)試時(shí)限為5000ms下面給出蠻力法的代碼：#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;intmp[22][22],n;#defineINF99999voidin<>{scanf<"%d",&n>;for<inti=1;i<=n;i++>{