單源最短路徑問(wèn)題

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

2、同：回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。 2、分支限界法基本思想：分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。 3、常見(jiàn)的兩種分支限界法：1）隊(duì)列式(FIFO)分支限界法 按照隊(duì)列先進(jìn)先

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

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

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

6、t_indexj + min_cost;pathj = min_cost_index;int main()cout 請(qǐng)輸入圖的頂點(diǎn)數(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 請(qǐng)輸入邊的信息：n;int u, v, w;for (int i = 0; i edge_num; i+)cout 請(qǐng)輸入第 i + 1 u v w;matrixuv =

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