


版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、算法設計與分析實驗報告學號:日期:20161230姓名:得 分:一、實驗內容:TSP問題二、所用算法的基本思想及復雜度分析:1、蠻力法1) 基本思想借助矩陣把問題轉換為矩陣中點的求解。首先構造距離矩陣,任意節(jié)點 到自身節(jié)點的距離為無窮大。在第一行找到最小項a1j,從而跳轉到第j行,再找到最小值ajk,再到第k行進行查找。然后構造各行允 許數組rown=1,11,各列允許數組 colablen=0,1,1.1,其中1 表示允許訪問,即該節(jié)點未被訪問;0表示不允許訪問,即該節(jié)點已經 被訪問。如果改行或該列不允許訪問,跳過該點訪問下一節(jié)點。程序再 發(fā)問最后一個節(jié)點前,所訪問的行中至少有1個允許訪問的
2、節(jié)點,依次訪問這些節(jié)點找到最小的即可;在訪問最后一個節(jié)點后,再次訪問,會 返回k=0,即實現訪問源節(jié)點,得出一條簡單回路。2) 復雜度分析基本語句是訪問下一個行列中最小的點,主要操作是求平方,假設有n個點,則計算的次數為 nA2-n。T(n)=n*(n-1)=O(nT)。2、動態(tài)規(guī)劃法1)基本思想假設從頂點s岀發(fā),令d(i, V ')從頂點i岀發(fā)經過 V是一個點的集合)中各個頂點一次且 僅一次,最后回到岀發(fā)點s的最短路徑長度。推導:(分情況來討論) 當V為空集,那么d(i, V ;表示從i不經過任何點就回到 s 了,如上圖的 城市3-城 市0(0為起點城市)。此時d(i, V '
3、; )=Ci就是城市i到城市s的距離)、如果V不為空,那么就是對子問題的最優(yōu)求解。你必須在V這個城市集合中,嘗試每一個,并求出最優(yōu)解。d(i, V ' )=minCik +d(k, V -')注:Cik表示你選擇的城市和城市 i的距離,d(k, V -k)是一個子問題。綜上所述,TSP問題的動態(tài)規(guī)劃方程就岀來了:班匚刃)=丘帆乞4/(上尸-(幻) 2$2)復雜度分析和蠻力法相比,動態(tài)規(guī)劃求解tsp問題,把原來時間復雜性 O (n!)的 排列轉化為組合問題,從而降低了時間復雜度,但仍需要指數時間。3、回溯法1)基本思想確定了解空間的組織結構后,回溯法從開始結點(根結點)出發(fā),以
4、深度優(yōu)先方式搜索整個解空間。這個開始結點成為活結點,同時也成 為當前的擴展結點處,搜索向縱深方向移至一個新結點。這個新結點 即成為新的活結點,并為當前擴展結點。如果在當前的擴展結點處不 能再向縱深方向移動,則當前擴展結點就成為死結點。 此時,應往回 移動(回溯)至最近的一個活結點處,并使這個活結點成為當前的擴 展結點。回溯法以這種工作方式遞歸地在解空間中搜索,直至找到所要求的解或解空間中已無活結點時為止?;厮莘ㄇ蠼釺SP問題,首先把所有的頂點的訪問標志初始化為 0,然 后在解空間樹中從根節(jié)點出發(fā)開始搜索,如果從根節(jié)點到當前結點對 應一個部分解,即滿足上述約束條件,則在當前結點處選擇第一棵子 樹
5、繼續(xù)搜索,否則,對當前子樹的兄弟結點進行搜索, 如果當前結點 的所有子樹都已嘗試過并且發(fā)生沖突,貝U回溯到當前結點的父節(jié)點。 采用鄰接矩陣mpnn存儲頂點之間邊的情況,為避免在函數間傳遞 參數,將數組mp設置為全局變量,設數組xn表示哈密頓回路經過 的頂點。2)復雜度分析在哈密頓回路的可能解中,考慮到約束條件xi!=xj(1<=l,jv=n,i!=j),則可能解應該是(1,2,n)的一個排列,對應的解空間樹種至少有n!個葉子結點,每個葉子結點代表一種可能解。 當找到可行的最優(yōu)解時, 算法停止。根據遞歸條件不同時間復雜度也會不同,這里為 O(n!)。4、分支限界法1 )基本思想分支界限法以
6、廣度優(yōu)先或以最小耗費 (最大效益) 優(yōu)勢的方式搜索問 題的解空間樹。 問題的解空間樹是表示問題解空間的一棵有序樹, 常 見的有子集樹和排列樹。 在搜索問題的解空間樹時, 分支界限法與回 溯法的主要區(qū)別在于他們對當前擴展結點所采用的擴展方式不同。 在 分支界限法中, 每一個活結點只有一次機會成為擴展結點。 活結點一 旦成為擴展結點,就一次性產生其所有兒子結點。 在這些兒子結點中, 導致不可行解或導致非最優(yōu)解得兒子結點被舍棄, 其余兒子結點被加 入活結點表中。 算法開始時創(chuàng)建一個最小堆, 用于表示活結點優(yōu)先隊 列。堆中每個結點的子樹費用的下界 lcost 值是優(yōu)先隊列的優(yōu)先級。 接著算法計算出圖中
7、每個頂點的最小費用出邊并用 minout 記錄。如 果所給的有向圖中某個頂點沒有出邊, 則該圖不可能有回路, 算法即 告結束。如果每個頂點都有出邊,則根據計算出的 minout 作算法初 始化。2)復雜度分析目標函數(限界函數) , lb 分為三部分,第一部分是經過路徑的長度 相加的 2 倍,加上第二部分離著路徑首尾節(jié)點最近的距離相加 (不在 已知路徑上的),加上第三部分除了路徑上節(jié)點,矩陣中兩個最短的 距離相加, 最后這三部分和相加, 得到的結果除以 2便是每個節(jié)點的 限界值。由于限界函數的不同,下界為 O (n),上界為0 (25),智 力特定指出。三、源程序及注釋:1 、 蠻力法int
8、main()int i,j,s=0;int *a;printf(" 輸入節(jié)點個數 : n");scanf("%d",&n);printf(”輸入%d維對稱矩陣:n",n);colable=(int*)malloc(sizeof(int)*n);colable0=0;/對各列允 許矩陣進行賦值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=
9、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)'i=0;while(rowi=1)j=min(ai);rowi=0;colablej=0;printf(" 訪問 路徑: n");printf("t%d->%dn",i,j);s=s+aij;i=j;printf(" 最短 總距離 為: %dn",s);int min(int *a)int j=0,m
10、=a0,k=0;while(colablej=0|rowj=0)j+;m=aj;/ 求最短距離for(;j<n;j+)if(colablej=1&&rowj=1)/ 節(jié)點沒有被 訪問if(m>=aj)m=aj;/m 始 終保持最短距離k=j;return k;2、動態(tài)規(guī)劃法int init()int i;int j;int t;if(sca nf("%d", &n )=EOF) return -1;for(i=0; i<n; i+)for(j=0; j< n; j+)if(i=j)con ti nue;scan f("
11、;%d", &gij);memset(c on ,-1,sizeof(c on);for(i=0; i<n; i+)biti=1<<i;t=1;for(i=1; i<n; i+)return 1;int getc on (i nt s,i nt k)int t,tt;int i;int mi n=INF;if(con sk!=-1)return con sk;t=s&(bitk-1);for(i=1; i<n; i+)tt=t&biti-1;if(tt>0)if(getc on( t,i)+gik< min)min=g
12、etc on( t,i)+gik;con sk=mi n;return con sk;3.回溯法 void backtrack(i nt i)if(i> n)if(graphroad n1!=INF&&(a ns+graphroad n 1)<besta ns)besta ns=a ns+graphroad n1;for(i nt j=1;j<=n ;j+) bestroadj=roadj;elsefor(i nt j=1;j<=n ;j+)if(graphroadi-1j!=INF &&an s+graphroadi-1j<bes
13、ta ns&& !visj)roadi=j;an s+=graphroadi-1j;visj=1;backtrack(i+1);/改回輔助的全局變量an s-=graphroadi-1j;visj=0;int mai n()memset(graph,INF,sizeof(graph);cin»n»m;for(i nt i=1;i<=m;i+)int a,b;cin> >a»b;cin> >graphab;graphb a=graphab;vis1=1;road1=1;/假設是從1開始backtrack(2);cout&
14、lt;<besta ns<<e ndl;for(i nt i=1;i<=n ;i+) cout<<bestroadi<<"" cout<<1<<e ndl;4.分支限界法void in()scan f("%d", &n);for(i nt i=1; i<=n; i+)for(i nt j=1; j<=n; j+)if(i=j)mpij=INF;con ti nue;scan f("%d", &mpij);struct nodein t
15、visp22;標記哪些點走了int st;/起點int st_p;起點的鄰接點int ed;終點int ed_p;終點的鄰接點int k; 走過的點數int sumv;/經過路徑的距離int lb;/目標函數的值bool operator <(c onst node &p )constreturn lb>p .lb;priority_queue <no de> q;in t low,up;int in q22;/確定上界int dfs(i nt u,i nt k,i nt I)if(k=n) return l+mpu1;int minlen=INF , p;fo
16、r(i nt i=1; i<=n; i+)if(i nqi=0&&mi nle n>mpui)/*取與所有點的連邊中最小的邊*/p=i;in qp=1;return dfs(p,k+1,l+mi nle n);int get_lb( node p)int ret=p.sumv*2;路徑上的點的距離int mi n仁INF,mi n2=INF;起點和終點連出來的邊for(i nt i=1; i<=n; i+)if(p.vispi=0&&min 1>mpip.st)mi n1=mpip.st;ret+=mi n1;for(i nt i=1;
17、i<=n; i+)if(p.vispi=0&&mi n2>mpp.edi)mi n2=mpp.edi;ret+=mi n2;for(i nt i=1; i<=n; i+)if(p.vispi=O)mi n仁min 2=INF;for(i nt j=1; j<=n; j+)if(mi n1>mpij)mi n1=mpij;for(i nt j=1; j<=n; j+)if(mi n2>mpji)mi n2=mpji;ret+=min 1+m in2;return ret%2=0?(ret/2):(ret/2+1);void get_up(
18、)in q1=1;up=dfs(1,1,O);void get_low()low=0;for(i nt i=1; i<=n; i+)/*通過排序求兩個最小值*/in t min 1=INF,mi n2=INF;int tmpA22;for(i nt j=1; j<=n; j+)tmpAj=mpij;sort(tmpA+1,tmpA+1+ n);對臨時的數組進行排序low+=tmpA1;int solve()/*貪心法確定上界*/get_up();/*取每行最小的邊之和作為下界*/get_low();/*設置初始點,默認從1開始*/node star;star.st=1;star.e
19、d=1;star.k=1;for(i nt i=1; i<=n; i+) star.vispi=O;star.visp1=1;star.sumv=0;starb=low;/*ret 為問題的解*/int ret=INF;q.push(star);while(!q.empty()node tmp=q.top();q.pop();if(tmp.k=n-1)/*找最后一個沒有走的點*/in t p;for(i nt i=1; i<=n; i+)if(tmp.vispi=O)p=i;break;int an s=tmp.sumv+mpptmp.st+mptmp.edp;node judge
20、 = q.top();/*如果當前的路徑和比所有的目標函數值都小則跳出*/if(ans <= judge .lb)ret=mi n(an s,ret);break;/*否則繼續(xù)求其他可能的路徑和,并更新上界*/elseup = min( up,a ns);ret=mi n( ret,a ns);con ti nue;/*當前點可以向下擴展的點入優(yōu)先級隊列*/node n ext;for(i nt i=1; i<=n; i+)if(tmp.vispi=O)n ext.st=tmp.st;/*更新路徑和*/n ext.sumv=tmp.sumv+mptmp.edi;/*更新最后一個點*/n ext.ed=i;/*更新頂點數*/n ext.k=tmp.k+1;/*更新經過的頂點*/for(i nt j=1; j<=n; j+) n
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- DB14-T 3359-2025 黃花菜采收技術規(guī)程
- 科技園區(qū)參觀交流合作協議
- 鏟車駕駛員職業(yè)保險聘用協議書
- 出租車公司股權轉讓及新能源充電樁建設合同
- 項目六 浪潮可視化大數據工具應用 自學自測答案
- 2025年海洋科學專業(yè)入學考試試卷及答案
- 2025年國際文化與藝術管理研究生入學考試試卷及答案
- 2025年翻譯專業(yè)英語技能考核試題及答案
- 2025年財政與稅務專業(yè)入學考試試題及答案
- 河北省秦皇島市山海關區(qū)第一中學2025屆高三下學期沖刺預測模擬數學試卷【含答案】
- 2025年農村集體土地上房屋買賣合同模板
- 1999年普通高等學校招生全國統一考試.文科數學試題及答案
- 結核傳染病試題及答案
- 河南省洛陽市伊川縣2024-2025學年七年級下學期期中生物試題(含答案)
- 健康活動:快樂生活的源泉
- 產后出血的觀察及護理
- 2025-2030中國蘆筍行業(yè)市場發(fā)展趨勢與前景展望戰(zhàn)略研究報告
- 港口安全AI大模型自主研發(fā)的關鍵技術與應用研究
- QGDW11882-2018預制艙式10kV~35kV一二次組合設備技術規(guī)范
- 循證口腔醫(yī)學試題及答案
- 陜西省西安市西北工業(yè)大學2025屆高考物理押題試卷含解析
評論
0/150
提交評論