[10]分支限界法策略

1、1分支限界法分支限界法2內(nèi)內(nèi) 容容1.寬度優(yōu)先搜索2.代價(jià)樹搜索3.啟發(fā)函數(shù)與估價(jià)函數(shù)4.應(yīng)用例子背包問題任務(wù)調(diào)度問題TSP問題3引言引言分枝限界法的基本思想代價(jià)樹搜索 + 剪枝策略分枝限界法求解的問題類型以優(yōu)化問題為主4分支限界算法的基本要素解空間的樹形表示0/1背包問題：子集樹旅行商問題：排列樹n皇后問題：滿n叉樹剪枝操作約束剪枝，優(yōu)化目標(biāo)函數(shù)剪枝節(jié)點(diǎn)評估函數(shù)定義及計(jì)算（即定義結(jié)點(diǎn)的優(yōu)先級別）決定挑下一個(gè)處理節(jié)點(diǎn)的優(yōu)先級5設(shè)計(jì)分枝限界法的基本步驟1. 將解空間表示成一棵樹T（解空間樹）求解問題轉(zhuǎn)化為在樹T中搜索解對應(yīng)的樹結(jié)點(diǎn)2. 定義剪枝操作考慮約束條件和目標(biāo)值優(yōu)化兩方面3. 定義每個(gè)節(jié)點(diǎn)

2、成本函數(shù)4.搜索算法寬度優(yōu)先搜索代價(jià)樹搜索最佳優(yōu)先搜索（best-first search）61.寬度優(yōu)先搜索寬度優(yōu)先搜索寬度優(yōu)先搜索結(jié)果ABCDEFGHIJK 算法框架？7算法: 寬度優(yōu)先搜索 function width_first( x0 ) open= x0 /根節(jié)點(diǎn)放在open表中 while( openNULL) x=GetFromHead(open) VisitFun(x) /處理節(jié)點(diǎn)x CA=Expand(x) /擴(kuò)展節(jié)點(diǎn)x，CA是節(jié)點(diǎn)x的子節(jié)點(diǎn)集合 if(CA=NULL) /CA為空，表示節(jié)點(diǎn)x不可擴(kuò)展 countinue end if InsertToTail(open,C

3、A) end whileend function82.代價(jià)樹（圖）搜索代價(jià)樹（圖）搜索代價(jià)樹概念代價(jià)數(shù)：在一棵樹中，父節(jié)點(diǎn)到子節(jié)點(diǎn)之間有一個(gè)數(shù)值，這個(gè)數(shù)值，對不同的問題，表示不同的涵義。9代價(jià)的表示：用g(x)表示從根節(jié)點(diǎn)到任意節(jié)點(diǎn)“x”的代價(jià)C(x1,x2)表示從節(jié)點(diǎn)x1到x2的代價(jià)（邊代價(jià)）則 x2的總代價(jià)為： g(x2)=g(x1)+C(x1,x2)例如對右圖： g(1)=0 g(2)=g(1)+c(1,2)=5 g(3)=g(2)+c(2,3)=5+3=8 g(6)=g(2)+c(2,6)=5+4=9723210function cost_width_first( x0 ) open=

4、 x0 while( openNULL) x=SelecFromHead（open）/從open頭部選擇一個(gè)節(jié)點(diǎn)x，并從open表中刪除該節(jié)點(diǎn) closed=closed x /將節(jié)點(diǎn)x插入集合closed中 CA=expand(x) /擴(kuò)展節(jié)點(diǎn)x，CA是節(jié)點(diǎn)x的子節(jié)點(diǎn)集合 if(CA=NULL) /A為空，表示節(jié)點(diǎn)x不可擴(kuò)展 countinue end if foreach (n in CA) n.parent=x; / 或者 n.prev=x ,配置集合A中每個(gè)節(jié)點(diǎn)的指針 end for CA= CA-closed /從A中刪除在closed表中已經(jīng)出現(xiàn)過的節(jié)點(diǎn) CA=calculateC

5、ost(CA) /計(jì)算A中每個(gè)節(jié)點(diǎn)的代價(jià)函數(shù)值 CI= CA open for(n in CI) s=find(open,n) if(s.costn.cost) s.cost=n.cost end for CA=CA-CI open=Insert(open,CA) /將子集合A插入open表中 open=sort(open) /對open表中每個(gè)節(jié)點(diǎn)按代價(jià)值進(jìn)行升序排序 end whileend function113.啟發(fā)式搜索啟發(fā)式搜索啟發(fā)式搜索：利用問題本身的特征信息，指導(dǎo)搜索朝著最有希望的進(jìn)行搜索過程的關(guān)鍵：如何確定下一個(gè)要考察的節(jié)點(diǎn)！確定節(jié)點(diǎn)方法不同：形成不同的搜索策略在確定節(jié)點(diǎn)時(shí)充

6、分利用與問題有關(guān)的特性信息估計(jì)出節(jié)點(diǎn)的重要性；在搜索時(shí)選擇重要性高有節(jié)點(diǎn)；這樣有利于求得最優(yōu)解。 12啟發(fā)性信息 指與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息。一般有三種：用于決定要擴(kuò)展的下一節(jié)點(diǎn)，避免盲目擴(kuò)展，去擴(kuò)展最有希望的節(jié)點(diǎn)；在擴(kuò)展一個(gè)節(jié)點(diǎn)的過程中，用于決定要生成哪一個(gè)或那幾個(gè)后繼節(jié)點(diǎn)，以免盲目同時(shí)生成所有可能的節(jié)點(diǎn)。常常用來決定應(yīng)采用哪一個(gè)操作施加于給定的節(jié)點(diǎn)；用于決定某些應(yīng)該從搜索樹中拋棄或修剪得節(jié)點(diǎn)。剪枝技術(shù)。 13估價(jià)函數(shù) 估價(jià)函數(shù)的任務(wù)就是估計(jì)狀態(tài)空間樹中各節(jié)點(diǎn)的重要程度。 估價(jià)函數(shù)f（x）的定義為初始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的所有路徑中最小路徑

7、代價(jià)的估計(jì)值。一般形式為：f(x)=g(x)+h(x) g(x) : 代價(jià)函數(shù),是從初始節(jié)點(diǎn)S0到當(dāng)前節(jié)點(diǎn)x的實(shí)際代價(jià)，h(x): 啟發(fā)函數(shù),是從當(dāng)前節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)sg的估計(jì)代價(jià)；這里的估價(jià)函數(shù)實(shí)際上也就是界限函數(shù)。這里的估價(jià)函數(shù)實(shí)際上也就是界限函數(shù) 14分支界限法主要用于求最優(yōu)解，求最優(yōu)解可分成兩種情況：求最小解（對應(yīng)代價(jià)樹），求最大解（對應(yīng)利益樹）。對于最小化問題，其估價(jià)函數(shù)我們稱為下界函數(shù)，對于最大化問題，其估價(jià)函數(shù)我們稱為上界函數(shù)。后面我們以求最小值為主要討論內(nèi)容。 對于求最小值問題，假定問題的解有n個(gè)分量，解可以分逐步構(gòu)造。 那么估價(jià)函數(shù)之間應(yīng)該有下面的關(guān)系。)k1 ( ,1211

8、21nxxxxfxxxfkkk也就是說，第k-1層節(jié)點(diǎn)的估價(jià)函數(shù)值不可能大于第k層節(jié)點(diǎn)估價(jià)函數(shù)值。 15例例1：任務(wù)分配問題：任務(wù)分配問題把n項(xiàng)工作分配給n個(gè)人，每個(gè)人完成不同的工作有不同的代價(jià)，如下圖所示的代介矩陣，要求每個(gè)分配一項(xiàng)任務(wù)，使得總的代價(jià)最小。16下面我們研究估價(jià)函數(shù)(界限函數(shù))的定義如圖所示定義狀態(tài)空間樹，每個(gè)節(jié)點(diǎn)表示給一個(gè)人的任務(wù)分配g(xk):(從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)k的代價(jià)之和，實(shí)際表示的是從第1個(gè)人到當(dāng)前第k個(gè)所分配任務(wù)的總代價(jià))。h(xk):（從第k到第n個(gè)人從剩余n-k項(xiàng)任務(wù)中每人按最小代價(jià)分配時(shí)的代價(jià)之和）例如：初始情況k=0,即還沒有給任何人分配任務(wù) g(0)=0;

9、 h(0)=2+3+1+4=10則：lb(0)=g(0)+h(0)=10;Lb(x)=f(x)=g(x)+h(x)17假定已經(jīng)給A和B兩個(gè)人分配了任務(wù)，假定A分配的任務(wù)是2，B分配的任務(wù)是3（對應(yīng)節(jié)點(diǎn)6），那么： g(6)=2+3=5;(A分配2的代價(jià)為2，B分配3的代價(jià)為3) h(6)=5+4=9；（C分配任務(wù)1代價(jià)最小，為5，D分配任務(wù)4，代價(jià)為4）所以，lb(6)=g(6)+h(6)=14lb(6)=g(6)+h(6)=14 1819例例2：背包問題：背包問題給定n個(gè)重量為wi,價(jià)值為vi的物品（i=1,2,3,.,n）,以及一個(gè)承重量為T的背包，找出能裝入背包中的最有價(jià)值的物品集?？紤]

10、下面一個(gè)問題實(shí)例：物品重量(wi)價(jià)值(vi)價(jià)值/重量(pi=vi/wi)144010274263525543124背包承重量T1020分析：這個(gè)問題是一個(gè)求最大值問題，其“代價(jià)”函數(shù)對應(yīng)于利益，當(dāng)然是越大越好。g(x)=(已選擇裝入背包物品的價(jià)值之和)h(x)=(背包的剩余承重量)*(剩余物品的最大單位位價(jià)值)路徑上所選徑上所選物x根節(jié)節(jié)點(diǎn)到當(dāng)前節(jié) w(x)()(T()(11iiwvxwxh求最大值時(shí)，評估函數(shù)是上界函數(shù)=f(x)=g(x)+h(x)2122例例3：TSP問題問題TSP問題是指旅行家要旅行問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。所走的路程最短。23分析：求極小值問題定義啟發(fā)函數(shù)（下界函數(shù)）lb(x)=g(x)+h(x)g(x)-從起