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