TSP問題的解決方案

頁腳內(nèi)容頁腳內(nèi)容《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報告一學(xué)號：日期：20161230一、實(shí)驗(yàn)內(nèi)容：問題二、所用算法的根本思想及復(fù)雜度分析：1、蠻力法根本思想

姓名：得分：借助矩陣把問題轉(zhuǎn)換為矩陣中點(diǎn)的求解。首先構(gòu)造距離矩陣，任意節(jié)點(diǎn)k造各行允許數(shù)組row[n]={1,1…1，各列允許數(shù)組1表示允許訪問，即該節(jié)點(diǎn)未被訪問；0表示不允許訪問，即該節(jié)點(diǎn)已經(jīng)被訪問。假若改行或該列不允許訪問，跳過該點(diǎn)訪問下一節(jié)點(diǎn)。程序再發(fā)問最后一個節(jié)點(diǎn)前，所訪問的k=0，即實(shí)現(xiàn)訪問源節(jié)點(diǎn)，得出一條簡單回路。復(fù)雜度分析根本語句是訪問下一個行列中最小的點(diǎn)，主要操作是求平方，假設(shè)有n。2、動態(tài)規(guī)劃法根本思想sd(i,V’)表示從頂點(diǎn)i動身經(jīng)過V’(是一個點(diǎn)的集合)中各個頂s的最短路徑長度。推導(dǎo)：(分情況來辯論)①V’d(i,V’)is了，如上圖的城市3->0(0為起點(diǎn)城市)d(i,V’)=Cis(就是城市i到城市s的距離)、②假若V’不為空，那么就是對子問題的最優(yōu)求解。你必需在V’這個城市集合中，嘗試每一個，并求出最優(yōu)解。d(i,V’)=min{Cik+d(k,V’-{k})}注：Cik表示你選擇的城市和城市i的距離，d(k,V’-{k})是一個子問題。綜上所述，TSP問題的動態(tài)規(guī)劃方程就出來了：復(fù)雜度分析p問題，把原來時間復(fù)雜性（）排列轉(zhuǎn)化為組合問題，從而降低了時間復(fù)雜度，但仍需要指數(shù)時間。3、回溯法根本思想（根結(jié)點(diǎn)）動身，以要求的解或解空間中已無活結(jié)點(diǎn)時為止。0，頁腳內(nèi)容頁腳內(nèi)容點(diǎn)的所有子樹都已嘗試過并且發(fā)生沖突，則回溯到當(dāng)前結(jié)點(diǎn)的父節(jié)mpx[n]表示哈密頓回路經(jīng)過的頂點(diǎn)。復(fù)雜度分析在哈密頓回路的可能解中，考慮到約束條件則可能解應(yīng)該是（1,2,…,n）的一n!個葉子結(jié)點(diǎn)，每個葉子結(jié)點(diǎn)代（。4、分支限界法根本思想（最大效益優(yōu)勢的方式搜索問值是優(yōu)先隊(duì)列的優(yōu)先級。minout記錄。minout作算法初始化。復(fù)雜度分析（限界函數(shù)b2倍，加上第二部分離著路徑首尾節(jié)點(diǎn)最近的距離相加（不在已知路徑上的，加上第三部分除了路徑上節(jié)點(diǎn)，矩陣中兩個最短2便是每個節(jié)（智力特定指出。三、源程序及注釋：1、蠻力法intmain(){inti,j,s=0;int**a;printf("輸入節(jié)點(diǎn)個數(shù)：\n");scanf("%d",&n);\n",n);colable[0]=0;for(i=1;i<n;i++){colable[i]=1;}row=(int*)malloc((sizeof(int))*n);for(i=0;i<n;i++){row[i]=1;}a=(int**)malloc((sizeof(int*))*n);for(i=0;i<n;i++){a[i]=(int*)malloc((sizeof(int*))*n);}for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&a[i][j])'}}i=0;while(row[i]==1){j=min(a[i]);row[i]=0;printf("訪問路徑：\n");s=s+a[i][j];i=j;}printf("最短總距離為：%d\n",s);}intmin(int*a){intj=0,m=a[0],k=0;{j++;m=a[j];}//求最短距離{if(colable[j]==1&&row[j]==1)//節(jié)點(diǎn)沒有被訪問{if(m>=a[j]){始終保持最短距離k=j;}}}returnk;}2、動態(tài)規(guī)劃法intintinit(){inti;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",&g[i][j]);}}memset(con,-1,sizeof(con));for(i=0;i<n;i++){bit[i]=1<<i;}t=1;for(i=1;i<n;i++){con[t<<(i-1)][i]=g[0][i];}return1;}intgetcon(ints,intk){intt,tt;inti;intmin=INF;if(con[s][k]!=-1)returncon[s][k];t=s&(~bit[k-1]);for(i=1;i<n;i++){tt=t&bit[i-1];if(tt>0){if(getcon(t,i)+g[i][k]<min){min=getcon(t,i)+g[i][k];}}}con[s][k]=min;returncon[s][k];}回溯法voidbacktrack(inti){if(i>n){if(graph[road[n]][1]!=INF&&(ans+graph[road[n]][1])<bestans){bestans=ans+graph[road[n]][1];for(intj=1;j<=n;j++)bestroad[j]=road[j];}}else{for(intj=1;j<=n;j++){if(graph[road[i-1]][j]!=INF&&ans+graph[road[i-1]][j]<bestans&&!vis[j]){road[i]=j;ans+=graph[road[i-1]][j];vis[j]=1;backtrack(i+1);//改回輔助的全局變量ans-=graph[road[i-1]][j];vis[j]=0;}}}}intmain(){memset(graph,INF,sizeof(graph));cin>>n>>m;for(inti=1;i<=m;i++){inta,b;cin>>a>>b;cin>>graph[a][b];graph[b][a]=graph[a][b];}vis[1]=1;road[1]=1;//1開頭backtrack(2);cout<<bestans<<endl;for(inti=1;i<=n;i++)cout<<bestroad[i]<<"";cout<<1<<endl;}分支限界法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;//走過的點(diǎn)數(shù)intsumv;//經(jīng)過路徑的距離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)連出來的邊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++){/*經(jīng)過排序求兩個最小值*/intmin1=INF,min2=INF;inttmpA[22];for(intj=1;j<=n;j++){tmpA[j]=mp[i][j];}sort(tmpA+1,tmpA+1+n);//對臨時的數(shù)組進(jìn)行排序low+=tmpA[1];}}intsolve(){/*貪心法確定上界*/get_up();/*取每行最小的邊之和作為下界*/get_low();/*設(shè)置初始點(diǎn),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){/*找最后一個沒有走的點(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)先級隊(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];/*更新最后一個點(diǎn)*/next.ed=i;/*更新頂點(diǎn)數(shù)*/next.k=tmp.k+1;/*更新經(jīng)過的頂點(diǎn)*/for(intj=1;j<=n;