TSP問題分析動態(tài)規(guī)劃,分支界限法,蠻力法

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