圖的搜索算法-文庫吧資料
2024-08-07 03:44本頁面
【正文】 下一頁 leaf=x。 初始化隊； ADDQ（ T）； //根結(jié)點入隊 parent（ E） =0； //記錄擴展路徑，當前結(jié)點的父結(jié)點 while （隊不空） {DELETEQ(E) //隊首結(jié)點出隊為新的 E結(jié)點； for （ E的每個兒子 X） if (s（ X） u) //當是可能的最優(yōu)解時入隊 {ADD Q（ X） ； parent （ X ） =E。 search（ T） //為找出最小成本答案結(jié)點檢索 T。 下一頁 返回首頁 算法框架如下： 上一頁 u為當前的最優(yōu)解 ， 初值為一個較大的數(shù) 。 算法框架 上一小節(jié)的例子是求最大值的最優(yōu)化問題 ， 下面我們以求找最小成本的最優(yōu)化問題 ， 給出 FIFO分支搜索算法框架 。 返回首頁 上一頁 7） 結(jié)點 J變?yōu)?E結(jié)點，擴展的層次為 4算法結(jié)束。 5） 結(jié)點 C變?yōu)?E結(jié)點擴充 F入堆， bestw仍為 40； 結(jié)點 G的裝載上界為 50 bestw，也入堆；此時堆中 E上界為 60為優(yōu)先隊列首。 3） 結(jié)點 B變?yōu)?E結(jié)點擴充 D入堆， bestw=40； 結(jié)點 E的裝載上界為 60 bestw，也入堆；此時堆中 D上界為 90為優(yōu)先隊列首。 1） 初始隊列中只有結(jié)點 A； 2） 結(jié)點 A變?yōu)?E結(jié)點擴充 B入隊， bestw=10； 結(jié)點 C的裝載上界為 30+50=80 bestw，也入隊； 3） 結(jié)點 B變?yōu)?E結(jié)點擴充 D入隊， bestw=40； 結(jié)點 E的裝載上界為 60 bestw，也入隊； 4） 結(jié)點 C變?yōu)?E結(jié)點擴充 F入隊， bestw仍為 40； 結(jié)點 G的裝載上界為 50 bestw，也入隊； 5） 結(jié)點 D變?yōu)?E結(jié)點，葉結(jié)點 H超過容量， 葉結(jié)點 I的裝載為 40， bestw仍為 40； 6） 結(jié)點 E變?yōu)?E結(jié)點，葉結(jié)點 J裝載量為 60， bestw為 60； 葉結(jié)點 K被剪掉； 7） 結(jié)點 F變?yōu)?E結(jié)點，葉結(jié)點 L超過容量， bestw為 60； 葉結(jié)點 M被剪掉； 8） 結(jié)點 G變?yōu)?E結(jié)點，葉結(jié)點 N、 O都被剪掉； 此時隊列空算法結(jié)束。 返回首頁 FIFO限界搜索過程為： 上一頁 下一頁 其實看了下面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列式擴展結(jié)點的過程，一開始實際是在進行類似 “ 深度優(yōu)先 ” 的搜索。 3）不同與算法 2，由于擴展結(jié)點不是按層進行的計算結(jié)點的所在分支的裝載上界時，要用數(shù)組變量 r記錄當前層以下的最大重量，這樣可以隨時方便使用各層結(jié)點的裝載上界。 數(shù)據(jù)結(jié)構(gòu)設(shè)計： 1）要輸出解的方案，在搜索過程中仍需要生成解結(jié)構(gòu)樹，其結(jié)點信息包括指向父結(jié)點的指針和標識物品取舍（或是父結(jié)點的左、右孩子）。排序算法的時間復(fù)雜度較高，考慮到搜索算法每次只擴展一個結(jié)點，回憶數(shù)據(jù)結(jié)構(gòu)中堆排序，適合這一特點且比較交換的次數(shù)最少。 2）結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級常規(guī)定為一個與該結(jié)點相關(guān)的數(shù)值 p，它一般表示其接近最優(yōu)解的程度，本例題就以當前結(jié)點的所在分支的裝載上界為優(yōu)先值。 } 1）結(jié)點擴展方式：無論那種分支限界法，都需要有一張活結(jié)點表。i++) if(bestx[i]=1) print(i,”,”)。 for(i=1。i++) if(bestx[i]=1) print(i，“，” )。 for(i=1。 if (s bestw =c2)。 返回首頁 若有的話，找出該方法 FIFO限界搜索算法 優(yōu)先隊列式分支限界法 上一頁 第一艘船的載重量是 c1，第二艘船的載重量是 c2， wi 是貨箱 i 的重量 ,且 w 1+w2+…… +wn≤c1+c2 。 返回首頁 選擇下一個 E節(jié)點的
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1