《算法設(shè)計與分析》第07講.ppt

《《算法設(shè)計與分析》第07講.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第7講分支限界法上海海洋大學(xué)信息學(xué)院2009-12-27.1概述7.2復(fù)雜的有限作業(yè)調(diào)度問題7.3貨郎擔(dān)問題的分支限界法7.1概述上海海洋大學(xué)信息學(xué)院2009-12-2分枝限界法概述采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱為分枝限界法。按照廣度優(yōu)先的原則，一個活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)（E-結(jié)點(diǎn)）R后，算法將依次生成它的全部孩子結(jié)點(diǎn)，并將它們一一加入活結(jié)點(diǎn)表，此時R自身成為死結(jié)點(diǎn)。算法從活結(jié)點(diǎn)表中另選一個活結(jié)點(diǎn)作為E-結(jié)點(diǎn)。上海海洋大學(xué)信息學(xué)院2009-12-2不同的活結(jié)點(diǎn)表形成不同的分枝限界法，分為：FIFO分枝限界法、LIFO分枝限界法和LC（leastcos

2、t）分枝限界法。三種不同的活結(jié)點(diǎn)表，規(guī)定了從活結(jié)點(diǎn)表中選取下一個E-結(jié)點(diǎn)的不同次序。FIFO分枝限界法的活結(jié)點(diǎn)表是先進(jìn)先出隊列LIFO分枝限界法的活結(jié)點(diǎn)表是堆棧；LC分枝限界法的活結(jié)點(diǎn)表是優(yōu)先權(quán)隊列，LC分枝限界法將選取具有最高優(yōu)先級的活結(jié)點(diǎn)出隊列，成為新的E-結(jié)點(diǎn)。例(4-皇后問題)FIFO分枝限界法求解分枝限界算法templatestructNode{Tcost;Node*parent;}templatevoidBranchBound(Node*t){LiveList*>lst(mSize);Node*x,*E=

3、t;do{for(對結(jié)點(diǎn)E的每個不受限的孩子){x=newNode;x->parent=E;if(x是一個答案結(jié)點(diǎn)){輸出從x到t的一條路徑；return;}lst.Append(x);}if(lst.IsEmpty()){cout<<“沒有答案結(jié)點(diǎn)”；return；}lst.Serve(E);//從lst輸出一個活結(jié)點(diǎn)為E-結(jié)點(diǎn)}while（1）；}LC分枝限界法代價函數(shù)c(·)若X是答案結(jié)點(diǎn)，則c(X)是從根結(jié)點(diǎn)到X的搜索代價；若X不是答案結(jié)點(diǎn)且子樹X上不含任何答案結(jié)點(diǎn)，則c(X)=?；若X不是答案結(jié)點(diǎn)但子樹X上包含答案結(jié)點(diǎn)，則c(X)等于子樹X上具有最小搜索代價的答案結(jié)

4、點(diǎn)的代價。上海海洋大學(xué)信息學(xué)院2009-12-2相對代價函數(shù)g(·)衡量一個結(jié)點(diǎn)X的相對代價一般有兩種標(biāo)準(zhǔn)：①在生成一個答案結(jié)點(diǎn)之前，子樹X上需要生成的結(jié)點(diǎn)數(shù)目；②在子樹X上，離X最近的答案結(jié)點(diǎn)到X的路徑長度。容易看出，如果采用標(biāo)準(zhǔn)①，總是生成最小數(shù)目的結(jié)點(diǎn)；如果采用標(biāo)準(zhǔn)②，則要成為E-結(jié)點(diǎn)的結(jié)點(diǎn)只是由根到最近的那個答案結(jié)點(diǎn)路徑上的那些結(jié)點(diǎn)。假設(shè)狀態(tài)空間樹上含A、B、C三個答案結(jié)點(diǎn)，且搜索代價為A

5、,則:g(X)=4,g(Y)=3,g(Z)=2若按標(biāo)準(zhǔn)(2),則:g(X)=1,g(Y)=g(Z)=2相對代價估計函數(shù)?(.)?(X)作為g(X)的估計值，用于估計結(jié)點(diǎn)X的相對代價，它是由X到達(dá)一個答案結(jié)點(diǎn)所需代價的估計函數(shù)。一般地，假定?(X)滿足如下特性：如果Y是X的孩子，則有?(Y)≤?(X)。代價估計函數(shù)?(.)?(X)是代價估計函數(shù)，它由兩部分組成：從根到X的代價f(X)和從X到答案結(jié)點(diǎn)的估計代價?(X)，即?(X)=f(X)+?(X)。一般而言，可令f(X)等于X在樹中的層次。7.2復(fù)雜的有限作業(yè)調(diào)度問題問題描述對于單處理機(jī)的帶時限作業(yè)排序問題，如果每個作業(yè)具有相

6、同的處理時間，則可以用貪心法求解。如果每個作業(yè)的處理時間允許不同，帶時限的作業(yè)排序問題可描述為：設(shè)有n個作業(yè)和一臺處理機(jī)，每個作業(yè)所需的處理時間、要求的時限和收益可用三元組（ti,di,pi），0≤i＜n表示，其中，作業(yè)i的所需時間為ti，如果作業(yè)i能夠在時限di內(nèi)完成，將可收益pi，求使得總收益最大的作業(yè)子集J。例:設(shè)有帶時限的作業(yè)排序?qū)嵗簄=4，(p1,t1,d1)=(5,1,1)，(p2,t2,d2)=(10,2,3)，(p3,t3,d3)=(6,1,2)和(p4,t4,d4)=(3,1,1)，求使得總收益最大的作業(yè)子集J。分枝限界法求解可變大小元組（x0,x1,…,

7、xk）表示解，xi為作業(yè)編號。問題的顯式約束為：xi?{0,1,…,n?1}且xi＜xi+1(0≤i＜n?1)，隱式約束為：對于選入子集J的作業(yè)（x0,x1,…,xk），存在一種作業(yè)排列使J中作業(yè)均能如期完成。問題的目標(biāo)函數(shù)是作業(yè)子集J中所有作業(yè)所獲取的收益之和，使得總收益最大的作業(yè)子集是問題的最優(yōu)解。如果希望以最小值為最優(yōu)解，則可以適當(dāng)改變目標(biāo)函數(shù)，將其改為未入選子集J的作業(yè)所導(dǎo)致的損失，即為：?(X)u(X)?(X)?c(X)?u(X)可變大小元組狀態(tài)空間樹7.3貨郎擔(dān)問題的分支限界法上海海洋大學(xué)信