




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、TSP問(wèn)題算法實(shí)驗(yàn)報(bào)告指導(dǎo)教師: 季曉慧 姓 名: 辛瑞乾 學(xué) 號(hào): 1004131114 提交日期: 2015年11月 目錄總述2動(dòng)態(tài)規(guī)劃法2算法問(wèn)題分析2算法設(shè)計(jì)2實(shí)現(xiàn)代碼2輸入輸出截圖5OJ提交截圖5算法優(yōu)化分析5回溯法5算法問(wèn)題分析5算法設(shè)計(jì)6實(shí)現(xiàn)代碼6輸入輸出截圖8OJ提交截圖8算法優(yōu)化分析9分支限界法9算法問(wèn)題分析9算法設(shè)計(jì)9實(shí)現(xiàn)代碼9輸入輸出截圖14OJ提交截圖14算法優(yōu)化分析14總結(jié)15總述TSP問(wèn)題又稱為旅行商問(wèn)題,是指一個(gè)旅行商要?dú)v經(jīng)所有城市一次最后又回到原來(lái)的城市,求最短路程或最小花費(fèi),解決TSP可以用好多算法,比如蠻力法,動(dòng)態(tài)規(guī)劃法具體的時(shí)間復(fù)雜的也各有差異,本次實(shí)驗(yàn)報(bào)
2、告包含動(dòng)態(tài)規(guī)劃法,回溯法以及分支限界法。動(dòng)態(tài)規(guī)劃法算法問(wèn)題分析假設(shè)n個(gè)頂點(diǎn)分別用0n-1的數(shù)字編號(hào),頂點(diǎn)之間的代價(jià)存放在數(shù)組mpnn中,下面考慮從頂點(diǎn)0出發(fā)求解TSP問(wèn)題的填表形式。首先,按個(gè)數(shù)為1、2、n-1的順序生成1n-1個(gè)元素的子集存放在數(shù)組x2n-1中,例如當(dāng)n=4時(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)過(guò)子集xj中的頂點(diǎn)一次且一次,最后回到出發(fā)點(diǎn)0的最短路徑長(zhǎng)度,動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題的算法如下。算法設(shè)計(jì)輸入:圖的代價(jià)矩陣mpnn輸出:從頂點(diǎn)0出發(fā)經(jīng)過(guò)所有頂點(diǎn)一次且僅
3、一次再回到頂點(diǎn)0的最短路徑長(zhǎng)度1. 初始化第0列(動(dòng)態(tài)規(guī)劃的邊界問(wèn)題)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. 輸出最短路徑長(zhǎng)度。實(shí)現(xiàn)代碼#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #incl
4、ude #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 = 1000000007;const int Max = 100005;int n,mp2020,dp
5、2040000;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; 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
6、&(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+dpi(mx-1)-(1=1)3.1、xk=xk+1,搜索下一個(gè)頂點(diǎn)。3.2、若n個(gè)頂點(diǎn)沒(méi)有被窮舉完,則執(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ù)
7、組xn,算法結(jié)束;3.4、若數(shù)組xn構(gòu)成哈密頓路徑的部分解,則k=k+1,轉(zhuǎn)步驟3;3.5、否則,取消頂點(diǎn)xk的訪問(wèn)標(biāo)志,重置xk,k=k-1,轉(zhuǎn)步驟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 debug
8、n#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;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
9、=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=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)
10、 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)化分析在哈密頓回路的可能解中,考慮到約束條件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í),算法停止。分支限界法算法問(wèn)題分析分支限界法解決TSP問(wèn)題首先確定目標(biāo)函數(shù)的界down,up,可以
11、采用貪心法確定TSP問(wèn)題的一個(gè)上界。如何求得TSP問(wèn)題的一個(gè)合理的下界呢?對(duì)于無(wú)向圖的代價(jià)矩陣,吧矩陣中每一行最小的元素想家,可以得到一個(gè)簡(jiǎn)單的下界,但是還有一個(gè)信息量更大的下界:考慮一個(gè)TSP問(wèn)題的完整解,在每條路徑上,每個(gè)城市都有兩條鄰接邊,一條是進(jìn)入這個(gè)城市的,另一條是離開這個(gè)城市的,那么,如果把矩陣中每一行最小的兩個(gè)元素相加在除以2,假設(shè)圖中所有的代價(jià)都是整數(shù),再對(duì)這個(gè)結(jié)果向上取整,就得到一個(gè)合理的下界。需要強(qiáng)調(diào)的是,這個(gè)解可能不是一個(gè)可行解(可能沒(méi)有構(gòu)成哈密頓回路),但給出了一個(gè)參考下界。一般情況下,假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,rk),即路徑上已確定了k個(gè)頂點(diǎn),此時(shí),該部
12、分解的目標(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、 循環(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è)
13、分量。實(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#define ll
14、long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;const int mod = 1000000007;const int Max = 100005;/*/vectorMp20;vector:iterator 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
15、; ;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() int 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,t
16、2=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+=*it; 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.emp
17、ty() 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=tmp.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) tm
18、p.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 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;
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國(guó)自動(dòng)貼標(biāo)行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 旅游景區(qū)管理操作規(guī)程及流程
- 國(guó)內(nèi)外光儲(chǔ)充一體化停車場(chǎng)發(fā)展對(duì)比研究
- 2025至2030中國(guó)胃鏡市場(chǎng)應(yīng)用趨勢(shì)預(yù)測(cè)及發(fā)展?jié)摿υu(píng)估報(bào)告
- 2025至2030中國(guó)聚醋酸乙烯乳液行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國(guó)聚乙烯(PE)隔離膜行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)耐熱鋼型材行業(yè)供需趨勢(shì)及投資風(fēng)險(xiǎn)報(bào)告
- 2025至2030中國(guó)美法侖注射液行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)網(wǎng)絡(luò)直播行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 五語(yǔ)上冊(cè)第七單元班級(jí)管理教學(xué)計(jì)劃
- 倉(cāng)庫(kù)與生產(chǎn)線的有效對(duì)接計(jì)劃
- 《心律失?;颊叩淖o(hù)理》課件
- 2025江蘇省惠隆資產(chǎn)管理限公司招聘30人易考易錯(cuò)模擬試題(共500題)試卷后附參考答案
- (人教2024版)英語(yǔ)七年級(jí)上冊(cè)單詞默寫清單(新教材)
- 空腸管置管方法及護(hù)理
- 2025-2030中國(guó)清酒行業(yè)市場(chǎng)運(yùn)行分析及競(jìng)爭(zhēng)形勢(shì)與投資前景研究報(bào)告
- 武功縣人民醫(yī)院傳染病麻疹應(yīng)急演練方案
- 夏季軍營(yíng)安全教育
- 超藥品說(shuō)明書用藥目錄(兒科2024年版)
- 2025年廣東省中山市沙溪隆都醫(yī)院第二期招聘合同制工作人員11人歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- 成都鐵路局招聘2025屆高校畢業(yè)生663人高頻重點(diǎn)提升(共500題)附帶答案詳解
評(píng)論
0/150
提交評(píng)論