算法分析與分析

算法設(shè)計與分析

分支限界法

分支限界法:?

?分支限界法

?與回溯法類似，都是在問題的解空間樹上搜索問題

解的算法；

?求解目標(biāo)：找出滿足約束條件的解

?可行解或最優(yōu)解

?搜索策略_

根據(jù)限界函數(shù)值，剔除那些導(dǎo)致不可行解或非曼優(yōu)解的

子結(jié)點，使搜索過程僅限制在剩余的分支內(nèi)進行；

提綱

?分支限界法的基本思想

?實例分析

?本章小結(jié)

提綱

?分支限界法的基本思想

?實例分析

?本章小結(jié)

分支限界法Vs回溯法

分支限界法的主要分類

實例說明

分支限界法Vs回溯法

分支限界法的主要分類

實例說明

分支限界法Vs回溯法：：

?相同點：

?兩者在進行問題求解前，都需要完成解空間的定義

和組織；

?都是通過在解空間搜索來尋找問題的解；

分支限界法Vs回溯法

?不同點：

?搜索方式

回溯法：深度優(yōu)先；

分支限界法：廣度優(yōu)先；

?搜索策略

回溯法：根據(jù)剪枝函數(shù)，選擇下一個擴展接點并按深度優(yōu)先

方式進行搜索；

分支限界法：在擴展結(jié)點處，先產(chǎn)生其所有的子結(jié)點（分

支），然后根據(jù)限界函數(shù)，確定哪些子結(jié)點將導(dǎo)致不可行解

或非最優(yōu)解，將這些子結(jié)點剔除，用剩下的子結(jié)點構(gòu)造當(dāng)前

的活結(jié)點表，然后從該表中取一個結(jié)點作為當(dāng)前擴展結(jié)點，

并重復(fù)上述過程；

分支限界法Vs回溯法

分支限界法的主要分類

實例說明

分支限界法的主要分類

?分支限界法的主要分類

?根據(jù)從活結(jié)點表中選擇下一個擴展結(jié)點的方式

?隊列式FIFO分支限界法

優(yōu)先隊列式分支限界法

隊列式FIFO分支限界法

?隊列式FIFO分支限界法

?算法思想：將活結(jié)點表組織成一個隊列，并按

隊列的先進先出FIFO原則選取下一個結(jié)點作為

當(dāng)前擴展結(jié)點；

優(yōu)先隊列式分支限界法::

?優(yōu)先隊列式分支限界法

?算法思想：將活結(jié)點表組織成一個優(yōu)先隊列，并按

優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級，選取剩余隊列中優(yōu)

先級最高的下一個結(jié)點作為當(dāng)前擴展結(jié)點；

分支限界法Vs回溯法

分支限界法的主要分類

實例說明

實例說明

?實例說明

?0-1背包問題

?TSP問題

實例說明

?實例說明

?0」背包問題

?TSP問題

實例說明——0?1背包問題

?n=3的0」背包問題

?w=[16,15,15]

?p=[45,25,25]

?c=30

解空間為：

{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}

活結(jié)點&當(dāng)前

擴展結(jié)點

活結(jié)點

死結(jié)點

n=3的0」背包問題的解空間樹

利用隊列式FIFO分支限界法

利用優(yōu)先隊列式分支限界法

???

活結(jié)點隊列

（初始為空）活結(jié)點隊列

兩個子結(jié)點，但D是不可行結(jié)

A將結(jié)點加入到活結(jié)

點(因為超過背包容量)，所■E

以將D舍去。E是可行結(jié)點。點隊列中

活結(jié)點隊列活結(jié)點隊列

-Cc)00—CE)Cc)

—國

兩個子結(jié)點

:尸點。F.、G都是可

iz3</1

?f(G>將結(jié)點F、G

1Ho1X。按從左到右

/V.JZ的順序加入

9W09(2)到活結(jié)點隊

?o??c列中

活結(jié)點隊列活結(jié)點隊列

??01」->000-?

兩個子結(jié)點都是葉結(jié)點，其

中J是不可行解，而K是可行

解（價值為45）

0

活結(jié)點隊列活結(jié)點隊列

-BCD00

兩個子結(jié)點都是葉結(jié)點，而

且都分別對應(yīng)一個可行解，

其中L對應(yīng)的解的價值50,

而M對應(yīng)的解的價值25

A/I

1

活結(jié)點隊列

最優(yōu)解為：：?：'

???1

(0,1,1),對應(yīng)的價值為50

o兩個子結(jié)點都是葉結(jié)點，而

、且都分別對應(yīng)一個可行解，

其中N對應(yīng)的解的價值25,

而。對應(yīng)的解的價值0

活結(jié)點隊列活結(jié)點隊列

利用隊列式FIFO分支限界法

利用優(yōu)先隊列式分支限界法

當(dāng)前唯一的活結(jié)點，也

是當(dāng)前的擴展結(jié)點

A

0兩個可行的子結(jié)點，由于結(jié)點

B獲得的當(dāng)前價值為40,而結(jié)

點C的當(dāng)前價值為0。

BC

00

將B、C放入極

DEG大堆，而且結(jié)點

10000B是當(dāng)前堆中的

取大兀素。

HMNO

極大堆

C極大堆

（初始為空）

兩個子結(jié)點，但D是不可行結(jié)

點（因為超過背包容量），所

以將D舍去。E是可行結(jié)點。

0

L忘我價值為40,大于結(jié)點

（C）（的價值，所以成為當(dāng)前堆）

中的最大元素J

兩個子結(jié)點都是葉結(jié)點，其

中J是不可行解，而K是可行

解（價值為45）

0

0兩個子結(jié)點F、G都是可

、行結(jié)點。F的價值為25,

而G的價值為0。

/1

Pf"(GVZ將結(jié)點F、G加入

Ko1ZXo到極大堆中，結(jié)

XX'點F成為當(dāng)前堆中

(M)(N)(。)的最大元素。

極大堆

0兩個子結(jié)點F、G都是可行結(jié)

點，都是可行解。L的價值

c為50,而G的價值為25。

1

F

>0

M

極大堆

最優(yōu)解為：

(0,1,1),對應(yīng)的價值為50

、兩個子結(jié)點N、。都是

可行結(jié)點，都是可行

,Vx解。N的價值為25,而

O的價值為0。

"M/

(M^<O5

極大堆

實例說明

?實例說明

?0-1背包問題

?TSP問題

實例說明——TSP問題

4頂點的無向帶權(quán)圖

n=4的TSP問題的解空間樹（排列樹）

利用隊列式FIFO分支限界法

利用優(yōu)先隊列式分支限界法

活結(jié)點隊列

（初始為空）活結(jié)點隊列

A

兩個可行的子結(jié)點，按從左1

到右的順序?qū)⑦@兩個子結(jié)點

加入活結(jié)點隊列。4

活結(jié)點隊列活結(jié)點隊列

A

兩個可行的子結(jié)點，按從左1

到右的順序?qū)⑦@兩個子結(jié)點

加入活結(jié)點隊列。/4

/3

活結(jié)點隊列活結(jié)點隊列

^TTFTTE

\兩個可行的子結(jié)點，按從

CIDL/左到右的順序?qū)⑦@兩個子

及二結(jié)點加入活結(jié)點隊列。

活結(jié)點隊列活結(jié)點隊列

當(dāng)前擴展結(jié)點的子結(jié)

點是葉結(jié)點，表明找

B

到一條TSP回路，費4

用為59。3

CD

242當(dāng)前最優(yōu)解為12341

HIJ費用：59

423

NP

活結(jié)點隊列活結(jié)點隊列

當(dāng)前擴展結(jié)點的子結(jié)

4

E

42;當(dāng)前最優(yōu)解為12341

Q費用：59

IJ

23

P

活結(jié)點隊列

A

當(dāng)前擴展結(jié)點的子結(jié)1

點是葉結(jié)點，表明找

到一條TSP回路，費4

用為25。3?

C，DE

34742;當(dāng)前最優(yōu)解為13241

Q費用：

HIJ25

\423

P

活結(jié)點隊列活結(jié)點隊列

A

1由于從根結(jié)點到當(dāng)前結(jié)

點的費用〉當(dāng)前最優(yōu)費

4用，所以結(jié)點I被舍棄。

4黑42;當(dāng)前最優(yōu)解為13241

Q費用：25

HIJ

423

活結(jié)點隊列

A

由于從根結(jié)點到當(dāng)前結(jié)

點的費用＞當(dāng)前最優(yōu)費用，*

4所以結(jié)點5被舍棄。

4黑42\3/當(dāng)前最優(yōu)解為13241

HIJ費用：25

423

活結(jié)點隊列活結(jié)點隊列

利用隊列式FIFO分支限界法

利用優(yōu)先隊列式分支限界法

1當(dāng)前擴展結(jié)點

B

4一三個可行的子結(jié)點，被加入到

3三:，極小堆中。由于E是當(dāng)前堆中

CDE具有最小費用的結(jié)點（費用為

424234）,所以處于堆頂，向下依次

是D和C。

GHIJK

434232

LMIN

極小堆極小堆

C

CID兩個可行的子結(jié)點，被加

入到極小堆中。其中J的

費用為14,K的費用為24。

——D在當(dāng)前堆中費用最

小，所以處于堆頂

極小堆

兩個可行的子結(jié)點，被加

入到極小堆中。其中H的

費用為11,K的費用為26。

——H在當(dāng)前堆中費用最

小，所以處于堆頂

極小堆

A

當(dāng)前擴展結(jié)點的子結(jié)1

點是葉結(jié)點，表明找

到一條TSP回路,費4

用為25。3i

CZDE

34黑當(dāng)前最優(yōu)解為13241

H費用：25

\4

極小堆

A

4

4黑42最優(yōu)解為13241

HIJ費用：25

423

極小堆

以此類推

提綱

?分支限界法的基本思想

?實例分析

?本章小結(jié)

實例分析

?單源最短路徑問題1

?裝載問題,

?布線問題J

?0-1背包問題

?最大團問題

?TSP問題

?電路板排列問題

?批處理作業(yè)調(diào)度,

單源最短路徑

算法思想

?算法思想

?采用優(yōu)先隊列式分支限界法

以當(dāng)前結(jié)點所對應(yīng)的路徑長度為參考標(biāo)準(zhǔn)（路徑長度越短,

優(yōu)先級越高）

?限界函數(shù)設(shè)計

利用已經(jīng)獲得的當(dāng)前最短路徑長度Lmin為基準(zhǔn)，對那些

結(jié)點所對應(yīng)路徑長度大于Lmin的情況，剪去以該結(jié)點為

根的子樹；

利用結(jié)點間的控制關(guān)系進行剪枝

?對于通過不同路徑到達同一頂點的兩條路徑，路徑長度短的結(jié)

點（控制結(jié)點）控制路徑長度長的結(jié)點（被控制結(jié)點）

分將被控制結(jié)點所對應(yīng)的子樹剪去

實例分析

找從頂點“1”到

頂點“5”的最短

路徑

一個帶權(quán)有向圖

一個帶權(quán)有向圖有向圖G的單源最短路

徑問題的解空間樹

A、B是兩個可行的子結(jié)點，被加入

到極小堆中。由于A是當(dāng)前堆中具

有最小路徑長度的結(jié)點（路徑長度

為10）,所以處于堆頂。

C為葉結(jié)點，表示得到一條從“1”

到“5”的路徑，路徑長度為100

極小堆極小堆

,一個可行的子結(jié)點，被加入到

極小堆中。由于D結(jié)點所對應(yīng)

路徑長度為60,所以被加入到

B結(jié)點之后，B是當(dāng)前堆中具有

最小路徑長度的結(jié)點（路徑長

度為30）,處于堆頂

極小堆

E為可行的子結(jié)點，被加入到極小堆??

中。由于E結(jié)點所對應(yīng)路徑長度為50

/，'（小于D結(jié)點所對應(yīng)的路徑長度），

'而且D、E在圖G中對應(yīng)同一個頂點3

分結(jié)點D被結(jié)點E控制，剪去以D結(jié)

點為根的子樹；

F結(jié)點為葉結(jié)點，且對應(yīng)的

從“1“到”5”的路徑長度為90,小于

已知的最短路徑長度

少用該路徑最為當(dāng)前已知的最優(yōu)解

因此，當(dāng)前極小堆中只剩下E

極小堆

到達葉結(jié)點處，由于H結(jié)點所對應(yīng)

路徑長度為60（小于F結(jié)點所對應(yīng)

的路徑長度）

少用該路徑取代已知的最短路徑，

作為當(dāng)前已知的最優(yōu)解

極小堆極小堆

最優(yōu)解

一個帶權(quán)有向圖有向圖G的單源最短路

徑問題的解空間樹

裝載問題

問題描述

裝載問題

有一批共n個集裝箱要裝上兩艘載重量分別為C1和。2的船,

n

其中集裝箱，的重量為明，且?的。+。

II12

Z=1

現(xiàn)要求確定是否有一個合理的裝載方案，可將這〃個集裝箱

裝上這兩艘輪船。如果有請給出裝載方案。

裝載問題是NP難問題。

求解出發(fā)點

?容易證明，如果一個給定的裝載問題有解，

則采用以下策略可以得到最優(yōu)裝載方案：

1.首先將第一艘船盡可能裝滿；

等價于選取全體集裝箱的一個子集，使該子集中集裝

箱重量之和最接近C1

2.將剩余的集裝箱裝上第二艘船;

算法思想

?算法思想

?解空間樹

?子集樹

?分支限界法

?隊列式

優(yōu)先隊列式

隊列式

?隊列式

?算法實現(xiàn)：檢查當(dāng)前結(jié)點的深度

?i=n

?表示當(dāng)前活結(jié)點為葉結(jié)點，不需要加入到活結(jié)點隊列中，只要

檢查該結(jié)點表示的可行解是否優(yōu)于當(dāng)前最優(yōu)解，并適時更新當(dāng)

前最優(yōu)解

i<n

■表示當(dāng)前結(jié)點為內(nèi)部結(jié)點，應(yīng)加入到活結(jié)點隊列中

限界函數(shù)設(shè)計：

?限界函數(shù)

?是否超過船的負(fù)荷限制

?根據(jù)當(dāng)前已知的最優(yōu)解bestw來進行剪枝

?當(dāng)前擴展結(jié)點所對應(yīng)的重量ew；

?剩余集裝箱的重量r；

如果ew+rv=bestw,則進行剪枝（剪去右子樹，因

為右子樹為0,表示下一個集裝箱沒有被選中）

——提早更新bestw（在每次進入左子樹時更新）

優(yōu)先隊列式

?優(yōu)先隊列式

?思路：根據(jù)活結(jié)點X在優(yōu)先隊列中的優(yōu)先級

?優(yōu)先級定義

從根結(jié)點到結(jié)點x的路徑所對應(yīng)的載重量+剩余集裝箱的重量

?優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴展結(jié)點

一旦有一個葉結(jié)點成為當(dāng)前擴展結(jié)點，則該葉結(jié)點所對應(yīng)

的解就是最優(yōu)解

優(yōu)先級策略的實現(xiàn)方式

?優(yōu)先級策略的實現(xiàn)方式

?第一種，在結(jié)點優(yōu)先隊列的每一個活結(jié)點中保存從

解空間樹的根結(jié)點到該結(jié)點的路徑；

在到達最優(yōu)值的葉結(jié)點時，在該結(jié)點處同時得到相應(yīng)的

最優(yōu)解；

?第二種，在算法的搜索過程中保存當(dāng)前已構(gòu)造出的

部分解空間樹。

當(dāng)達到最優(yōu)值的葉結(jié)點時，可以在解空間樹中從該葉結(jié)

點開始向根結(jié)點回溯，從而構(gòu)造出最優(yōu)解。

?教材中所選用的方案

布線問題

布線問題

?布線問題

?問題描述：確定連接方

格a的中點到方格b的

中點的最短布線路徑。

布線時，電路只能沿直

線或直角布線X

其他線路不允許穿過已b

布線的方格

d

算法設(shè)計思想::

?算法設(shè)計思想

?解空間：圖

?搜索策略：隊列式分支限界法

從起始位置a開始，將其作為第一個擴展結(jié)點。與該擴

展結(jié)點相鄰并且可達的方格（有相鄰邊且未被標(biāo)記）作

為可行結(jié)點被加入到活動結(jié)點隊列中，并且將這些方格

標(biāo)記為1（即從起始方格a到這些方格的距離為1）。

然后，算法從活結(jié)點隊列中取出隊首結(jié)點作為下一個擴

展結(jié)點，并將與當(dāng)前擴展結(jié)點相鄰且可達的方格標(biāo)記為

2,并存入活結(jié)點隊列。

該過程一直持續(xù)，直到算法搜索到目標(biāo)方格b或活結(jié)點

隊列為空時停止。

相鄰可達的概念

>滿足相鄰可達條件

―?不滿足相鄰可達條件

qoo

算法實現(xiàn)&復(fù)雜性分析

?算法實現(xiàn)

?參看教材216

?注意移動方向的設(shè)置以及布線長度的設(shè)置

?算法復(fù)雜性分析

?擴展每個結(jié)點需0(1)時間，算法共需耗時0(mn)。

構(gòu)造相應(yīng)的最短距離需要0(L)時間

-L是最短布線路徑長度

實際的電路布線問題

?實際的電路布線問題

?參看提供的參考文獻

從“…/算法分析/參考資料”處下載

批處理作業(yè)調(diào)度

問題描述

給定及個作業(yè)的集合/={4，4，每個作業(yè)人都有兩項任務(wù)

要分別在兩臺機器上完成。每個作業(yè)必須先在機器1上處理，

然后再由機器2處理。

作業(yè)《需要機器J的處理時間為/..,/=1,2,...,/I；7=1,2.

對于一個確定的作業(yè)調(diào)度，設(shè)廠,是作業(yè)，在機器/上完成處理的時間,

n

則所有作業(yè)在機器2上完成處理的時間和/=Z

稱為該作業(yè)調(diào)度的完成時間和。

批處理作業(yè)調(diào)度問題要求對于給定的〃個作業(yè)，制定最佳作業(yè)調(diào)度方案,

使其完成時間和達到最小。

對于批處理作業(yè)調(diào)度問題，可以證明存在最佳作業(yè)調(diào)度使得在機器1和

機器2上作業(yè)以相同次序完成。

舉例???

品機器1機器2

作業(yè)121

作業(yè)231

作業(yè)323

上述3個作業(yè)有6種不同的調(diào)度方案

1-2-3：19機器1完成的時間機器2完成印$間|

1-3-2：18?—最優(yōu)作業(yè)122+5：|

■■

2-1-3：20作業(yè)

1I32+2=44+3T17?

2-3-1：211作業(yè)24+3=77+七

3-1-2：19

11

3-2-1：21

13+7+8=18

算法設(shè)計思想

?