圖的搜索算法(已改無錯(cuò)字)
2022-08-22 03:44:26 本頁面
【正文】 標(biāo)函數(shù)值為 lb=2+8+5+3=18，將結(jié)點(diǎn) 9加入表 PT中； （ 7）在表 PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn) 5優(yōu)先進(jìn)行搜索； （ 8）在結(jié)點(diǎn) 10，第 3段選擇邊 5, 7，可直接確定第 4段的邊7, 9，目標(biāo)函數(shù)值為 lb=3+4+8+7=22，為一個(gè)可行解但超出目標(biāo)函數(shù)的界，將其丟棄；在結(jié)點(diǎn) 11，第 3段選擇邊 5, 8，可直接確定第 4段的邊 8, 9，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個(gè)較好的可行解。由于結(jié)點(diǎn) 11是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是表 PT中最小的，所以，結(jié)點(diǎn) 11代表的解即是問題的最優(yōu)解，搜索過程結(jié)束。 6 4 0→ 1 lb=20 2 3 1 start lb=18 0→ 2 lb=16 0→ 3 lb=15 分支限界法求解多段圖的最短路徑問題示例 ( 表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序 ) 7 2→ 4 lb=16 8 2→ 5 lb=18 9 2→ 6 lb=18 5 3→ 5 lb=16 3→ 6 lb=18 11 10 5→ 7 lb=22 5→ 8 lb=16 為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個(gè)表 ST，在表 PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲到表ST中，表 PT和表 ST的數(shù)據(jù)結(jié)構(gòu)為 (第 i段， 第 i段頂點(diǎn) , 第 i+1段頂點(diǎn) lb)，在搜索過程中表 PT和表 ST的狀態(tài)如下： (b) 擴(kuò)展結(jié)點(diǎn) 3后的狀態(tài) (d) 擴(kuò)展結(jié)點(diǎn) 5后的狀態(tài) ， 最優(yōu)解為 0→ 3→ 5→ 8→ 9 多段圖的最短路徑問題最優(yōu)解的確定 (1,0,216) (1,0,315) (1,0,216) (2,2,416) (2,2,518) (2,2,618) (1,0,315) (2,2,416) (2,2,518) (2,2,618) (2,3,516) (2,3,618) (1,0,315) (1,0,216) (2,2,416) (2,2,518) (2,2,618) (2,3,618) (3,5,816) (1,0,315) (1,0,216) (2,3,516) (a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) PT ST ST PT (c) 擴(kuò)展結(jié)點(diǎn) 4后的狀態(tài) ST ST 回溯過程是： (3,5, 816)→( 2,3, 516)→( 1,0, 315)。 算法 ——多段圖的最短路徑問題 1． 根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界 down；采用貪心法得到上界 up； 2． 將待處理結(jié)點(diǎn)表 PT初始化為空； 3． for (i=1。 i=k。 i++) x[i]=0。 4． i=1。 u=0。 //求解第 i段 5． while (i=1) 對頂點(diǎn) u的所有鄰接點(diǎn) v 根據(jù)式 lb。 若 lb=up， 則將 i,u,v,lb存儲在表 PT中； 如果 i= =k1且葉子結(jié)點(diǎn)的 lb值在表 PT中最小 ， 則輸出該葉子結(jié)點(diǎn)對應(yīng)的最優(yōu)解； 否則 ， 如果 i= =k1且表 PT中的葉子結(jié)點(diǎn)的 lb值不是最小 ， 則 up=表 PT中的葉子結(jié)點(diǎn)最小的 lb值 。 將表 PT中目標(biāo)函數(shù)值超出 up的結(jié)點(diǎn)刪除； u=表 PT中 lb最小的結(jié)點(diǎn)的 v值； i=表 PT中 lb最小的結(jié)點(diǎn)的 i值； i++。 圖的搜索算法小結(jié) 1．深度優(yōu)先搜索與廣度優(yōu)先搜索算法有何區(qū)別 通常深度優(yōu)先搜索法不全部保留結(jié)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)存儲結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲的結(jié)點(diǎn)數(shù)就是解空間樹的深度，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1