第9章_分支限界法

1、教學(xué)重點(diǎn)教學(xué)重點(diǎn)分支限界法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的限界函數(shù)分支限界法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的限界函數(shù)教學(xué)難點(diǎn)教學(xué)難點(diǎn)各種經(jīng)典問(wèn)題的限界函數(shù)以及限界算法各種經(jīng)典問(wèn)題的限界函數(shù)以及限界算法教學(xué)內(nèi)容及目教學(xué)內(nèi)容及目標(biāo)標(biāo)知識(shí)點(diǎn)知識(shí)點(diǎn)教學(xué)要求教學(xué)要求了解了解理解理解掌握掌握熟練掌握熟練掌握分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的時(shí)空性能分支限界法的時(shí)空性能TSP問(wèn)題問(wèn)題多段圖的最短路徑問(wèn)題多段圖的最短路徑問(wèn)題0/1背包問(wèn)題背包問(wèn)題任務(wù)分配問(wèn)題任務(wù)分配問(wèn)題批處理作業(yè)調(diào)度問(wèn)題批處理作業(yè)調(diào)度問(wèn)題)()(11iiwvwWvub分支限界法的一般過(guò)程分支限界法的一般過(guò)程 1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的

2、根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的 down，up； 2將待處理結(jié)點(diǎn)表將待處理結(jié)點(diǎn)表PT 初始化為空；初始化為空； 3. 對(duì)根結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)對(duì)根結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作執(zhí)行下列操作 3.1 估算結(jié)點(diǎn)估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值value; 3.2 若（若（value=down）,則將結(jié)點(diǎn)則將結(jié)點(diǎn)x加入表加入表PT中；中； 4循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大中最大4.1 i=表表PT中值最大的結(jié)點(diǎn)；中值最大的結(jié)點(diǎn)；4.2 對(duì)結(jié)點(diǎn)對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作執(zhí)行下列操作4.2.1 估算結(jié)點(diǎn)估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值的目標(biāo)

3、函數(shù)值value；4.2.2 若若(value=down)，則將結(jié)點(diǎn)，則將結(jié)點(diǎn)x加入表加入表PT中；中；4.2.3 若（結(jié)點(diǎn)若（結(jié)點(diǎn)x是葉子結(jié)點(diǎn)且是葉子結(jié)點(diǎn)且value值在表值在表PT中最大），則將結(jié)點(diǎn)中最大），則將結(jié)點(diǎn)x對(duì)對(duì)應(yīng)的解輸出，算法結(jié)束；應(yīng)的解輸出，算法結(jié)束；4.2.4 若若(結(jié)點(diǎn)結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但是葉子結(jié)點(diǎn)但value值在表值在表PT中不是最大中不是最大),則令則令down=value，并且將表，并且將表PT中所有小于中所有小于value的結(jié)點(diǎn)刪除；的結(jié)點(diǎn)刪除；UrUrjikiiiijrrrrclb2/ )2(111行最小的兩個(gè)元素素行不在路徑上的最小元i=1,k1111,(2 )

4、/ 2jkiiijiikrUlbc rrrr行不在路徑上的最小元素行最小的兩個(gè)元素n處理結(jié)點(diǎn)處理結(jié)點(diǎn)11的孩子。結(jié)點(diǎn)的孩子。結(jié)點(diǎn)12，C1C3C5C2 ，路徑長(zhǎng)度為1+2+9，目標(biāo)函數(shù)值:lb=(2*12+(3+3)+(3+4)/2=19 超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)12丟棄n在結(jié)點(diǎn)在結(jié)點(diǎn)13， C1C3 C5C4 ，路徑長(zhǎng)度為1+2+3 目標(biāo)函數(shù)值：lb=(2*6+(3+4)+(3+6)/2=14,將結(jié)點(diǎn)13加入表PT中n處理結(jié)點(diǎn)處理結(jié)點(diǎn)13的孩子。結(jié)點(diǎn)的孩子。結(jié)點(diǎn)14， C1C3 C5C4C2 ，路徑長(zhǎng)度為1+2+3+7，目標(biāo)函數(shù)值:lb=(2*13+(3+3)/2=16由于結(jié)點(diǎn)14為葉子結(jié)點(diǎn)，得到一個(gè)可行解其路徑長(zhǎng)度為16已確定的已確定的路徑長(zhǎng)度路徑長(zhǎng)度ri+1出發(fā)的出發(fā)的最短邊最短邊ri+2后面每段后面每段的最短邊和的最短邊和nikkvlb1行的最小值第nikkvlb1行的最小值第上界：41min3121kiknjjittt23,maxsum1k,sum2k-1min ijj k j Mi Mlbtt23