單源最短路徑問題_第1頁
單源最短路徑問題_第2頁
單源最短路徑問題_第3頁
單源最短路徑問題_第4頁
單源最短路徑問題_第5頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、實驗四 單源最短路徑問題一、實驗目的:1、 理解分支限界法的剪枝搜索策略;2、 掌握分支限界法的算法柜架;3、 掌握分支限界法的算法步驟;4、 通過應用范例學習動態(tài)規(guī)劃算法的設計技巧與策略;二、 實驗內(nèi)容及要求:1、使用分支限界法解決單源最短路徑問題。2、通過上機實驗進行算法實現(xiàn)。3、保存和打印出程序的運行結果,并結合程序進行分析,上交實驗報告。三、實驗原理:分支限界法的基本思想:1、分支限界法與回溯法的不同:1)求解目標:回溯法的求解目標是找出解空間樹中滿足約束條件的所有解,而分支限界法的求解目標則是找出滿足約束條件的一個解,或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。2)搜索方式的不

2、同:回溯法以深度優(yōu)先的方式搜索解空間樹,而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。 2、分支限界法基本思想:分支限界法常以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中,每一個活結點只有一次機會成為擴展結點?;罱Y點一旦成為擴展結點,就一次性產(chǎn)生其所有兒子結點。在這些兒子結點中,導致不可行解或導致非最優(yōu)解的兒子結點被舍棄,其余兒子結點被加入活結點表中。 此后,從活結點表中取下一結點成為當前擴展結點,并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。 3、常見的兩種分支限界法:1)隊列式(FIFO)分支限界法 按照隊列先進先

3、出(FIFO)原則選取下一個節(jié)點為擴展節(jié)點。 2)優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。四、程序代碼#include using namespace std;int matrix100100; / 鄰接矩陣bool visited100; / 標記數(shù)組int dist100; / 源點到頂點i的最短距離int path100; / 記錄最短路的路徑int source; / 源點int vertex_num; / 頂點數(shù)int edge_num; / 邊數(shù)int destination;/ 終結點 void Dijkstra(int source

4、)memset(visited, 0, sizeof(visited); / 初始化標記數(shù)組visitedsource = true;for (int i = 0; i vertex_num; i+)disti = matrixsourcei;pathi = source;int min_cost; / 權值最小int min_cost_index; / 權值最小的下標for (int i = 1; i vertex_num; i+) / 找到源點到另外 vertex_num-1 個點的最短路徑min_cost = INT_MAX;for (int j = 0; j vertex_num; j

5、+)if (visitedj = false & distj min_cost) / 找到權值最小min_cost = distj;min_cost_index = j;visitedmin_cost_index = true; / 該點已找到,進行標記for (int j = 0; j vertex_num; j+) / 更新 dist 數(shù)組if (visitedj = false &matrixmin_cost_indexj != INT_MAX & / 確保兩點之間有邊matrixmin_cost_indexj + min_cost distj)distj = matrixmin_cos

6、t_indexj + min_cost;pathj = min_cost_index;int main()cout 請輸入圖的頂點數(shù)( vertex_num;cout edge_num;for (int i = 0; i vertex_num; i+)for (int j = 0; j vertex_num; j+)matrixij = (i != j) ? INT_MAX : 0; / 初始化 matrix 數(shù)組cout 請輸入邊的信息:n;int u, v, w;for (int i = 0; i edge_num; i+)cout 請輸入第 i + 1 u v w;matrixuv =

7、matrixvu = w;cout 請輸入源點( vertex_num source;Dijkstra(source);cout 請輸入終結點( vertex_num destination;cout source 到 destination 最短距離是: distdestination ,路徑是: destination;int t = pathdestination;while (t != source)cout - t;t = patht;cout - source endl;return 0;五、結果運行與分析本例用使迪杰斯特拉算法來求單源最短路徑,也即采用優(yōu)先隊列式分支限界法,按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。選定源節(jié)點后,從源節(jié)點開始擴展,并將其子節(jié)點按路徑長度大小依次存于棧中,每次從棧頂彈出節(jié)點作為擴展節(jié)點,利用限界來剪去相應的節(jié)點。6、 心得與體會通過這次實驗,對迪杰斯

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論