算法設(shè)計(jì)與分析分支限界法02

第第頁(yè)算法設(shè)計(jì)與分析分支限界法02哈工程

智能信息處理討論中心(RCIIP)

P

第6章

分支限界法a潘海為

n1

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，P其中集裝箱i的重量為wi,且

裝載問(wèn)題a確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。假如有，找出一種裝載方案。簡(jiǎn)單證明，假如一個(gè)給定裝載問(wèn)題有解，那么采納下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿(mǎn)；n(2)將剩余的集裝箱裝上第二艘輪船。25

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題隊(duì)列式分支限界法P

在算法的while循環(huán)中，首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。假如是那么將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中(右兒子結(jié)a點(diǎn)肯定是可行結(jié)點(diǎn))。2個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄。

n26

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題隊(duì)列式分支限界法while(true){//檢查左兒子結(jié)點(diǎn)if(Ew+w[i]=c)//*[i]=1EnQueue(Q,Ew+w[i],bestw,i,n);//右兒子結(jié)點(diǎn)總是可行的EnQueue(Q,Ew,bestw,i,n);//*[i]=0Q.Delete(Ew);//取下一擴(kuò)展結(jié)點(diǎn)

P

a

n27

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題算法的改進(jìn)P

節(jié)點(diǎn)的左子樹(shù)表示將此集裝箱裝上船，右子樹(shù)表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量。那么當(dāng)ew+rbestw時(shí)，可將其a右子樹(shù)剪去，由于此時(shí)假設(shè)要船裝最多集裝箱，就應(yīng)當(dāng)把此箱裝上船。另外，為了確保右子樹(shù)勝利剪枝，應(yīng)當(dāng)在算法每一次進(jìn)入左子樹(shù)的時(shí)候更新bestw的值。n

28

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題算法的改進(jìn)//檢查左兒子結(jié)點(diǎn)Typewt=Ew+w[i];if(wt=c){

P//左兒子結(jié)點(diǎn)的重量//可行結(jié)點(diǎn)提前更新

if(wtbestw)bestw=wt;//加入活結(jié)點(diǎn)隊(duì)列if(in)Q.Add(wt);}

bestw

a右兒子剪枝

//檢查右兒子結(jié)點(diǎn)if(Ew+rbestwin)Q.Add(Ew);Q.Delete(Ew);

n

//可能含最優(yōu)解//取下一擴(kuò)展結(jié)點(diǎn)29

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題構(gòu)造最優(yōu)解P

為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法需要存儲(chǔ)相應(yīng)子集樹(shù)中從活結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)a點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)識(shí)。找到最優(yōu)值后，可以依據(jù)parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解。

n30

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題優(yōu)先隊(duì)列式分支限界法P

解裝載問(wèn)題的優(yōu)先隊(duì)列式分支限界法用最大優(yōu)先隊(duì)列存儲(chǔ)活結(jié)點(diǎn)表?；罱Y(jié)點(diǎn)*在優(yōu)先隊(duì)列

中的優(yōu)先級(jí)定義為從根結(jié)點(diǎn)到結(jié)點(diǎn)*的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。a優(yōu)先隊(duì)列中優(yōu)先級(jí)最大的活結(jié)點(diǎn)成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。以結(jié)點(diǎn)*為根的子樹(shù)中全部結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過(guò)它的優(yōu)先級(jí)。在優(yōu)先隊(duì)列式分支限界法中，一旦有一個(gè)葉結(jié)點(diǎn)成為n當(dāng)前擴(kuò)展結(jié)點(diǎn)，那么可以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。此時(shí)可終止算法。31

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題問(wèn)題描述P

給定n個(gè)頂點(diǎn)的帶權(quán)圖G=(V,E),圖中各邊的權(quán)為正數(shù)，圖中的一條周游路徑是包括V中的每個(gè)頂點(diǎn)在內(nèi)的一條回路，一條周游路徑的費(fèi)用是這條路徑上全部邊的權(quán)之和。a旅行商問(wèn)題(TravelingSalesperson)是要在圖G中找出一條有最小費(fèi)用的周游路徑。此問(wèn)題是NP完全問(wèn)題。

n

32

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——FIFO隊(duì)列式A123

1

3054

2104

P63

B32

442

20BC,D,E

a

C

4

D

E

3

F4

G3

H4

I2

263

JP

K2

n

F,G,H,I,J,KL,M,N,P,Q33

L59

M66

N25

O

Q

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——優(yōu)先隊(duì)列式(1)A12

1

3054

2104

P63

B32

442

20BE,D,C

a

C4

D

E

3

HN25

I

J

K

n

,CD,J,KH,J,K,I,C

J,K,N,I,CK,N,I,CN,I,C34

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——優(yōu)先隊(duì)列式(2)A12

1

3054

2104

P63

B32

442

20E

a

C4

D

3

HN25

I3

JP25

K

n35

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——?dú)w約矩陣法-10-2-2-3-4行約數(shù)=21

P

-1-0-3-0-0

列約數(shù)||4

a

矩陣約數(shù)r=行約數(shù)+列約數(shù)=25最小代價(jià)函數(shù)C’(1)=25

n36

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——?dú)w約矩陣法130543204210

P6

a

n37

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題P41

a

n38

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題P4132

a

n39

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題P413213

a31204-25

n1

0340

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題31210034-25

P

41321324

a

周游路徑：13241最小耗費(fèi)：25

n41

哈工程

智能信息處理討論中心(RCIIP)

批處理作業(yè)調(diào)度問(wèn)題問(wèn)題的描述給定n個(gè)作業(yè)的集合{J1,J2,…,Jn}。

P

每個(gè)作業(yè)需要先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時(shí)間為tji。a對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。全部作業(yè)在機(jī)器2上完成處理的時(shí)間和稱(chēng)為該作業(yè)調(diào)

度的完成時(shí)間和。批處理作業(yè)調(diào)度問(wèn)題n對(duì)于給定的n個(gè)作業(yè)，制定最正確作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。42

哈工程

智能信息處理討論中心(RCIIP)

P

第6章

分支限界法a潘海為

n1

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，P其中集裝箱i的重量為wi,且

裝載問(wèn)題a確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。假如有，找出一種裝載方案。簡(jiǎn)單證明，假如一個(gè)給定裝載問(wèn)題有解，那么采納下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿(mǎn)；n(2)將剩余的集裝箱裝上第二艘輪船。25

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題隊(duì)列式分支限界法P

在算法的while循環(huán)中，首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。假如是那么將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中(右兒子結(jié)a點(diǎn)肯定是可行結(jié)點(diǎn))。2個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄。

n26

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題隊(duì)列式分支限界法while(true){//檢查左兒子結(jié)點(diǎn)if(Ew+w[i]=c)//*[i]=1EnQueue(Q,Ew+w[i],bestw,i,n);//右兒子結(jié)點(diǎn)總是可行的EnQueue(Q,Ew,bestw,i,n);//*[i]=0Q.Delete(Ew);//取下一擴(kuò)展結(jié)點(diǎn)

P

a

n27

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題算法的改進(jìn)P

節(jié)點(diǎn)的左子樹(shù)表示將此集裝箱裝上船，右子樹(shù)表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量。那么當(dāng)ew+rbestw時(shí)，可將其a右子樹(shù)剪去，由于此時(shí)假設(shè)要船裝最多集裝箱，就應(yīng)當(dāng)把此箱裝上船。另外，為了確保右子樹(shù)勝利剪枝，應(yīng)當(dāng)在算法每一次進(jìn)入左子樹(shù)的時(shí)候更新bestw的值。n

28

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題算法的改進(jìn)//檢查左兒子結(jié)點(diǎn)Typewt=Ew+w[i];if(wt=c){

P//左兒子結(jié)點(diǎn)的重量//可行結(jié)點(diǎn)提前更新

if(wtbestw)bestw=wt;//加入活結(jié)點(diǎn)隊(duì)列if(in)Q.Add(wt);}

bestw

a右兒子剪枝

//檢查右兒子結(jié)點(diǎn)if(Ew+rbestwin)Q.Add(Ew);Q.Delete(Ew);

n

//可能含最優(yōu)解//取下一擴(kuò)展結(jié)點(diǎn)29

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題構(gòu)造最優(yōu)解P

為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法需要存儲(chǔ)相應(yīng)子集樹(shù)中從活結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)a點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)識(shí)。找到最優(yōu)值后，可以依據(jù)parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解。

n30

哈工程

智能信息處理討論中心(RCIIP)

裝載問(wèn)題優(yōu)先隊(duì)列式分支限界法P

解裝載問(wèn)題的優(yōu)先隊(duì)列式分支限界法用最大優(yōu)先隊(duì)列存儲(chǔ)活結(jié)點(diǎn)表?；罱Y(jié)點(diǎn)*在優(yōu)先隊(duì)列

中的優(yōu)先級(jí)定義為從根結(jié)點(diǎn)到結(jié)點(diǎn)*的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。a優(yōu)先隊(duì)列中優(yōu)先級(jí)最大的活結(jié)點(diǎn)成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。以結(jié)點(diǎn)*為根的子樹(shù)中全部結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過(guò)它的優(yōu)先級(jí)。在優(yōu)先隊(duì)列式分支限界法中，一旦有一個(gè)葉結(jié)點(diǎn)成為n當(dāng)前擴(kuò)展結(jié)點(diǎn)，那么可以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。此時(shí)可終止算法。31

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題問(wèn)題描述P

給定n個(gè)頂點(diǎn)的帶權(quán)圖G=(V,E),圖中各邊的權(quán)為正數(shù)，圖中的一條周游路徑是包括V中的每個(gè)頂點(diǎn)在內(nèi)的一條回路，一條周游路徑的費(fèi)用是這條路徑上全部邊的權(quán)之和。a旅行商問(wèn)題(TravelingSalesperson)是要在圖G中找出一條有最小費(fèi)用的周游路徑。此問(wèn)題是NP完全問(wèn)題。

n

32

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——FIFO隊(duì)列式A123

1

3054

2104

P63

B32

442

20BC,D,E

a

C

4

D

E

3

F4

G3

H4

I2

263

JP

K2

n

F,G,H,I,J,KL,M,N,P,Q33

L59

M66

N25

O

Q

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——優(yōu)先隊(duì)列式(1)A12

1

3054

2104

P63

B32

442

20BE,D,C

a

C4

D

E

3

HN25

I

J

K

n

,CD,J,KH,J,K,I,C

J,K,N,I,CK,N,I,CN,I,C34

哈工程

智能信息處理討論中心(RCIIP)

旅行售貨員問(wèn)題實(shí)例——優(yōu)先隊(duì)列式(2)A12

1

3054

2104

P63

B32

442

20E