算法設(shè)計(jì)與分析 課件 第七章 分支限界 7.2.1 分支限界方式

計(jì)算機(jī)算法設(shè)計(jì)與分析第7章分支限界法7.2.1分支限界方式分支限界法根據(jù)從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的方式，可分為隊(duì)列式分支限界和優(yōu)先隊(duì)列式分支限界。（1）隊(duì)列式分支限界法隊(duì)列式（FIFO）式分支限界法的基本思想：（1）首先將初始狀態(tài)節(jié)點(diǎn)放入活結(jié)點(diǎn)隊(duì)列中。（2）若隊(duì)列非空，則重復(fù)下列步驟：①出隊(duì)，將出隊(duì)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。②判斷當(dāng)前擴(kuò)展結(jié)點(diǎn)是否為目標(biāo)結(jié)點(diǎn)，若是目標(biāo)結(jié)點(diǎn)，則搜索到一個(gè)可行解而結(jié)束。③對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)進(jìn)行擴(kuò)展。在擴(kuò)展節(jié)點(diǎn)時(shí)，一次性產(chǎn)生它的所有子結(jié)點(diǎn)，并利用剪枝函數(shù)檢測(cè)，把滿足約束和限界條件的的子結(jié)點(diǎn)依次加入活結(jié)點(diǎn)隊(duì)列。（3）重復(fù)（2），直到隊(duì)列為空，則搜索失敗結(jié)束。（2）優(yōu)先隊(duì)列式分支限界法將活結(jié)點(diǎn)表組成一個(gè)優(yōu)先隊(duì)列，按照優(yōu)先隊(duì)列中指定的結(jié)點(diǎn)優(yōu)先級(jí)，選取優(yōu)先級(jí)最高的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，以優(yōu)先隊(duì)列儲(chǔ)存活結(jié)點(diǎn)。結(jié)點(diǎn)的優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的限界函數(shù)值來(lái)表示。也稱為最小耗費(fèi)優(yōu)先分支限界法(LC)該策略與隊(duì)列式分支限界法的主要區(qū)別是：優(yōu)先隊(duì)列式分支限界法的活結(jié)點(diǎn)表組成一個(gè)優(yōu)先隊(duì)列，每個(gè)活結(jié)點(diǎn)入隊(duì)時(shí)會(huì)計(jì)算其優(yōu)先級(jí)，優(yōu)先級(jí)最高的活結(jié)點(diǎn)位于隊(duì)首位置。（2）優(yōu)先隊(duì)列式分支限界法優(yōu)先隊(duì)列通常采用堆數(shù)據(jù)結(jié)構(gòu)來(lái)組織，通過(guò)維護(hù)堆屬性，可以保證優(yōu)先隊(duì)列的入隊(duì)操作時(shí)按結(jié)點(diǎn)元素優(yōu)先級(jí)重新排序，也即隊(duì)列中優(yōu)先級(jí)最高的結(jié)點(diǎn)元素始終位于隊(duì)列首部位置。每次出隊(duì)的隊(duì)首結(jié)點(diǎn)總是當(dāng)前隊(duì)列中具有優(yōu)先級(jí)最高（最有利）的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)有最優(yōu)解的分支方向快速推進(jìn)，以便快速找到問(wèn)題的最優(yōu)解。優(yōu)先隊(duì)列式分支限界法基本思想（1）確定合理的限界函數(shù)，并根據(jù)限界函數(shù)確定問(wèn)題的目標(biāo)函數(shù)的上（下）界，又稱耗費(fèi)函數(shù)值或代價(jià)值。（2）初始化一個(gè)空的優(yōu)先隊(duì)列H，并將初始狀態(tài)加入隊(duì)列。初始化一個(gè)變量best_score用于保存當(dāng)前找到的最優(yōu)解（初值=無(wú)窮大）。（3）當(dāng)隊(duì)列H不為空時(shí)，執(zhí)行以下步驟：優(yōu)先隊(duì)列式分支限界法基本思想

①出隊(duì)結(jié)點(diǎn)保存為node。

②ifnode結(jié)點(diǎn)對(duì)應(yīng)更優(yōu)的解then更新當(dāng)前最優(yōu)解best_score的值。③fornode的每一個(gè)子結(jié)點(diǎn)child：a.計(jì)算child結(jié)點(diǎn)的目標(biāo)函數(shù)限界值。b.ifchild滿足解的約束條件且耗費(fèi)函數(shù)值不超過(guò)

目標(biāo)函數(shù)的當(dāng)前限界thenc.將child加入