圖的搜索算法(已修改)
2025-08-06 03:44 本頁面
【正文】 第五章 圖的搜索算法 分支限界法 分枝搜索算法 分枝 限界搜索算法 算法框架 圖的搜索算法小結(jié) 分枝搜索算法 1．基本思想 分支搜索法也是一種在問題解空間上進行嘗試搜索算法。所謂 “ 分支 ” 是采用廣度優(yōu)先的策略，依次生成 E結(jié)點所有分支，也就是所有的兒子結(jié)點。和回溯法一樣，在生成的節(jié)點中，拋棄那些不滿足約束條件（或者說不可能導(dǎo)出最優(yōu)可行解）的結(jié)點，其余節(jié)點加入活節(jié)點表。然后從表中選擇一個節(jié)點作為下一個 E節(jié)點。選擇下一個 E節(jié)點的方式不同導(dǎo)致幾種不同的分支搜索方式： 1． FIFO搜索 2． LIFO搜索 3．優(yōu)先隊列式搜索 上一頁 下一頁 返回首頁 分枝 限界搜索算法 【 例 2】 有兩艘船， n 個貨箱。第一艘船的載重量是 c1，第二艘船的載重量是 c2， wi 是貨箱 i 的重量 ,且 w 1+w2+…… +wn≤c1+c2 。 我們希望確定是否有一種可將所有 n 個貨箱全部裝船的方法。若有的話，找出該方法 FIFO限界搜索算法 優(yōu)先隊列式分支限界法 上一頁 下一頁 返回首頁 MaxLoading(c1)。 if (s bestw =c2)。 {print(“The first ship loading”, bestw ，“ chose：” )。 for(i=1。i=n。i++) if(bestx[i]=1) print(i，“，” )。 print(“ 換行符 The second ship loading”, s bestw,“chose”)。 for(i=1。i=n。i++) if(bestx[i]=1) print(i,”,”)。 } else print(“no solution”)。 } 1）結(jié)點擴展方式：無論那種分支限界法，都需要有一張活結(jié)點表。優(yōu)先隊列的分支限界法將活結(jié)點組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。 2）結(jié)點優(yōu)先級確定：優(yōu)先隊列中結(jié)點優(yōu)先級常規(guī)定為一個與該結(jié)點相關(guān)的數(shù)值 p，它一般表示其接近最優(yōu)解的程度，本例題就以當前結(jié)點的所在分支的裝載上界為優(yōu)先值。 3）優(yōu)先隊列組織：結(jié)點優(yōu)先級確定后，簡單地按結(jié)點優(yōu)先級進行排序，就生成了優(yōu)先隊列。排序算法的時間復(fù)雜度較高，考慮到搜索算法每次只擴展一個結(jié)點，回憶數(shù)據(jù)結(jié)構(gòu)中堆排序，適合這一特點且比較交換的次數(shù)最少。此題應(yīng)該采用最大堆來實現(xiàn)優(yōu)先隊列。 數(shù)據(jù)結(jié)構(gòu)設(shè)計： 1）要輸出解的方案，在搜索過程中仍需要生成解結(jié)構(gòu)樹，其結(jié)點信息包括指向父結(jié)點的指針和標識物品取舍（或是父結(jié)點的左、右孩子）。 2）堆結(jié)點首先應(yīng)該包括結(jié)點優(yōu)先級信息：結(jié)點的所在分支的裝載上界 uweight；堆中無法體現(xiàn)結(jié)點的層次信息（ level），只能存儲在結(jié)點中； AddLiveNode用于把 bbnode類型的活節(jié)點加到子樹中 ， 并把HeapNode類型的活節(jié)點插入最大堆 。 3）不同與算法 2，由于擴展結(jié)點不是按層進行的計算結(jié)點的所在分支的裝載上界時，要用數(shù)組變量 r記錄當前層以下的最大重量，這樣可以隨時方便使用各層結(jié)點的裝載上界。 小結(jié)討論： FIFO搜索或 LIFO搜索也可以通過加入 “ 限界 ” 策略加速搜索嗎？ 那與優(yōu)先隊列式分支限界法 ——LC—檢索的區(qū)別在哪兒呢？ 答案：由于 FIFO搜索或 LIFO搜索是盲目擴展地結(jié)點，當前最優(yōu)解距真正的最優(yōu)解距離較大，作為 “ 界 ” 所起到的剪枝作用很有限，不能有效提高搜索速度。其實看了下面的例子大家會發(fā)現(xiàn)，優(yōu)先隊列式擴展結(jié)點的過程，一開始實際是在進行類似 “ 深度優(yōu)先 ” 的搜索。 例如： W={10， 30， 50}， C1=60， 所構(gòu)成的子集樹如下圖所表示： 上一頁 下一頁 返回首頁 FIFO限界搜索過程為： 上一頁
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1