算法設計與分析 課件 第七章 分支限界 7.2.1 分支限界方式

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

①出隊結(jié)點保存為node。

②ifnode結(jié)點對應更優(yōu)的解then更新當前最優(yōu)解best_score的值。③fornode的每一個子結(jié)點child：a.計算child結(jié)點的目標函數(shù)限界值。b.ifchild滿足解的約束條件且耗費函數(shù)值不超過

目標函數(shù)的當前限界thenc.將child加入