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

算法設(shè)計(jì)與分析分支限界法第六章第一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/121計(jì)算機(jī)算法設(shè)計(jì)與分析樹搜索的一般形式SearchTree(SpaceT){ok=0;L=T.initial;while(!ok||L≠){a=L.first;if(aisgoal)unfinish=falseelseControl-put-in(L,Sons(a));}三種搜索方法的不同就在于存放待考察的結(jié)點(diǎn)的表L的控制方式不同：DFS(回溯法)是棧；WFS是隊(duì)列；BFS是隊(duì)列中的元素排序。第二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/122計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法基本思想分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先)的搜索法。其基本思想是：將要待考察的結(jié)點(diǎn)按其優(yōu)劣排序，優(yōu)先搜索好結(jié)點(diǎn)。于是便有了兩個(gè)問(wèn)題：(1)如何知道結(jié)點(diǎn)的優(yōu)劣？(2)在回溯法中，表L中結(jié)點(diǎn)的層次分明，因而路徑也分明。但是這里排序會(huì)打亂表L中結(jié)點(diǎn)的層次，那又如何找回解的路徑呢？第三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/123計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法基本思想分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先)的搜索法。其基本思想是：將要待考察的結(jié)點(diǎn)按其優(yōu)劣排序，優(yōu)先搜索好結(jié)點(diǎn)。于是便有了兩個(gè)要點(diǎn)：(1)需要構(gòu)造評(píng)價(jià)結(jié)點(diǎn)優(yōu)劣的評(píng)價(jià)函數(shù)。(2)需要能夠重新構(gòu)造解的路徑，也就是搜索的路徑。第四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/124計(jì)算機(jī)算法設(shè)計(jì)與分析評(píng)價(jià)函數(shù)的構(gòu)造評(píng)價(jià)函數(shù)要能夠提供一個(gè)評(píng)定候選擴(kuò)展結(jié)點(diǎn)的方法，以便確定哪個(gè)結(jié)點(diǎn)最有可能在通往目標(biāo)的最佳路徑上。一個(gè)評(píng)價(jià)函數(shù)f(d)通常由兩個(gè)部分構(gòu)成：⑴從開始結(jié)點(diǎn)到d的已有耗損值g(d)，和⑵再?gòu)膁到達(dá)目標(biāo)的期望耗損值h(d)。即：f(d)=g(d)+h(d)。通常g(d)的構(gòu)造較易，h(d)的構(gòu)造較難。第五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/125計(jì)算機(jī)算法設(shè)計(jì)與分析搜索路徑的構(gòu)造在回溯法中，每次僅考察一條路徑，因而只需要構(gòu)造這一條路徑即可：前進(jìn)時(shí)記下相應(yīng)結(jié)點(diǎn)，回溯時(shí)刪去最末尾結(jié)點(diǎn)的記錄。這比較容易實(shí)現(xiàn)。在分支限界法中，是同時(shí)考察若干條路徑，那么又該如何構(gòu)造搜索的路徑呢？往前看，前程無(wú)數(shù)！往回看，來(lái)路一條。每個(gè)結(jié)點(diǎn)只要記住其前驅(qū)結(jié)點(diǎn)就行了！第六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/126計(jì)算機(jī)算法設(shè)計(jì)與分析搜索路徑的構(gòu)造為此，只需要對(duì)每一個(gè)擴(kuò)展的結(jié)點(diǎn)d，建立三個(gè)信息：(1)該結(jié)點(diǎn)的名稱d；(2)它的評(píng)價(jià)函數(shù)值f(d)；(3)指向其前驅(qū)的指針p；即表示為[d,f(d),p]。這樣一旦找到目標(biāo)，即可以很方便地逆向構(gòu)造出該路徑。第七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/127計(jì)算機(jī)算法設(shè)計(jì)與分析Open表與Closed表搜索中，表L用來(lái)保存準(zhǔn)備擴(kuò)展的結(jié)點(diǎn)，即下一步的結(jié)點(diǎn)。把表L稱為Open表。此外，為了構(gòu)造解的路徑，還需要一個(gè)表來(lái)保存已經(jīng)搜索過(guò)的結(jié)點(diǎn)，即已經(jīng)走過(guò)的結(jié)點(diǎn)。此表被稱為Closed表。故任意結(jié)點(diǎn)d必是：①dOpen&&dClosed；②dClosed||dOpen。結(jié)點(diǎn)d尚未被考察。結(jié)點(diǎn)d已經(jīng)被考察。第八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/128計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴初始化：計(jì)算起點(diǎn)s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷if(f(p)<U){將[p,f(p),x]放入Closed;⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d有二種情況：①dOpen&&dClosed；②dClosed||dOpen。若結(jié)點(diǎn)d尚未被考察，則將[d,f(d),p]插入到Open中。若f(p)≥U，則剪去該路徑。第九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/129計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴初始化：計(jì)算起點(diǎn)s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷if(f(p)<U){將[p,f(p),x]放入Closed;⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d有二種情況：①dOpen&&dClosed；②dClosed||dOpen。若結(jié)點(diǎn)d已被考察，則說(shuō)明這次是通過(guò)另一條路徑到達(dá)到d。設(shè)d原來(lái)評(píng)價(jià)為f(d)’，將其與新的評(píng)價(jià)f(d)比較。若新評(píng)價(jià)更好，則刪去舊的，將新的插入到Open中；否則丟棄。第十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1210計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴初始化：計(jì)算起點(diǎn)s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷if(f(p)<U){將[p,f(p),x]放入Closed;⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}第十一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1211計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求單源最短路徑單源最短路徑問(wèn)題的評(píng)價(jià)函數(shù)的構(gòu)造：g(d)定義為從源s到結(jié)點(diǎn)d所走的路徑長(zhǎng)度：g(d)=g(p)+C[p][d]，這里p為d的前驅(qū)結(jié)點(diǎn)，C[p][d]為p到d的距離。h(d)定義為0。于是f(d)=g(d)。源s的評(píng)價(jià)函數(shù)f(s)=0。評(píng)價(jià)函數(shù)的下界為0；上界初始時(shí)為∞，以后不斷用取得的更短路徑的長(zhǎng)度來(lái)替代。第十二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1212計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求最短路徑舉例12543102050100301060賦權(quán)圖G初始時(shí)，將源[1,0,0]放入Open，Closed為空。Open表[1,0,0]Closed表取出[1,0,0]放入Closed；生成其后繼[2,10,1]、[4,30,1]和[5,100,1]，并依序放入Open。[1,0,0][5,100,1][4,30,1][2,10,1]取出[2,10,1]放入Closed；生成其后繼[3,60,2]，并依序插入Open。[2,10,1][3,60,2][4,30,1]取出[4,30,1]放入Closed；生成其后繼[3,50,4]和[5,90,4]，修訂Open中已有的兩個(gè)結(jié)點(diǎn)并依序排列。[4,30,1][5,90,4][3,50,4]取出[3,50,4]放入Closed；生成其后繼[2,100,3]和[5,60,3]，前者因劣于Closed中的[2,10,1]而被拋棄，后者修訂了Open中的[5,90,4]。[3,50,4][5,60,3]取出[5,60,3]，因其已經(jīng)是目標(biāo)結(jié)點(diǎn)，算法成功并終止。依據(jù)逆向指針可得最短路徑為1→4→3→5。第十三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1213計(jì)算機(jī)算法設(shè)計(jì)與分析界限(Bounding)評(píng)價(jià)函數(shù)f(d)關(guān)系著算法的效率乃至成敗。因?yàn)樵诖蠖鄶?shù)問(wèn)題中f(d)只是個(gè)估計(jì)值，所以單靠f(d)是不夠的。通常還要設(shè)計(jì)它的上下界函數(shù)U(d)和L(d)。L(d)≤f(d)≤U(d)。所謂分支限界法就是通過(guò)評(píng)價(jià)函數(shù)及其上下界函數(shù)的計(jì)算，將狀態(tài)空間中不可能產(chǎn)生最佳解的子樹剪去，減少搜索的范圍，提高效率。因而更準(zhǔn)確的稱呼應(yīng)是“界限剪支法”第十四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1214計(jì)算機(jī)算法設(shè)計(jì)與分析用分支限界法求TSPTSP是求排列的問(wèn)題，不是僅找一條路徑而已。因而需要對(duì)分支限界法的一般算法作些修改：(1)待擴(kuò)展結(jié)點(diǎn)若已在本路徑上，則不再擴(kuò)展，但若是在其他路徑上出現(xiàn)過(guò)，則仍需要擴(kuò)展。為此，用一個(gè)表L來(lái)存儲(chǔ)該路徑出現(xiàn)的結(jié)點(diǎn)，即將[d,f(d),p]改為[d,f(d),*L]。該結(jié)點(diǎn)是否已經(jīng)出現(xiàn)過(guò)，可查Closed表或者Open表。但是要查它出現(xiàn)在哪條路徑上，就頗費(fèi)周章了。這個(gè)L該怎么做？第十五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1215計(jì)算機(jī)算法設(shè)計(jì)與分析用分支限界法求TSPTSP是求排列的問(wèn)題，不是僅找一條路徑而已。因而需要對(duì)分支限界法的一般算法作些修改：(1)待擴(kuò)展結(jié)點(diǎn)若在本路徑上已經(jīng)出現(xiàn)，則不再擴(kuò)展，但若是在其他路徑上出現(xiàn)過(guò)，則仍需要擴(kuò)展。為此，用一個(gè)表L來(lái)存儲(chǔ)該路徑出現(xiàn)的結(jié)點(diǎn)。(2)新結(jié)點(diǎn)，無(wú)論其優(yōu)劣，既不影響其它路徑上的結(jié)點(diǎn)，也不受其它路徑上的結(jié)點(diǎn)的影響。(3)若考察結(jié)點(diǎn)的評(píng)價(jià)值超過(guò)上界值，則可以剪去。這實(shí)際上是剪去了這一支。L可設(shè)計(jì)為數(shù)組L[n]，初始值都為n；每加入新結(jié)點(diǎn)i，則L[i]

=p，這里p是i的前驅(qū)結(jié)點(diǎn)。若L[i]

≠n，則i已在此路徑中。這樣結(jié)點(diǎn)i的插入時(shí)間和判定時(shí)間都為常量。第十六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1216計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴初始化：計(jì)算起點(diǎn)s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷if(f(p)<U){將[p,f(p),x]放入Closed;⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}不失一般性，令0為起點(diǎn)，U為上界值：

Initialization：{

U=∞;Open=Closed=;計(jì)算f(0)；產(chǎn)生空表L；//L0=[0,n,……,n]Put-ordered-in(Open,[0,f(0),*L]);//把[0,f(0),*L)按序放入Open表中。//}第十七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1217計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),x](f(p)為最小);⑷if(f(p)<U){將[p,f(p),x]放入Closed;⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}*L此處改為表L。第十八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1218計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),*L](f(p)為最小);⑷if(f(p)<U){將[p,f(p),x]放入Closed;⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}此句可以不要了。因?yàn)槊織l通路上考察過(guò)的結(jié)點(diǎn)放在表L中了。Closed表L不再需要了。第十九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1219計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),*L](f(p)為最小);⑷if(f(p)<U){⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}如何知道p是目標(biāo)？如果L中已有n個(gè)結(jié)點(diǎn)了，則p是目標(biāo)。那又如何知道L中已有n個(gè)結(jié)點(diǎn)了？第二十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1220計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),*L](f(p)為最小);⑷if(f(p)<U){⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}L中存放的是每個(gè)結(jié)點(diǎn)的前驅(qū)，故可用L[0]作計(jì)數(shù)器。初始化時(shí)L[0]=1；之后每加入一個(gè)結(jié)點(diǎn)，L[0]++。當(dāng)L[0]=n，則已達(dá)目標(biāo)。第二十一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1221計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),*L](f(p)為最小);⑷if(f(p)<U){⑸if(p是目標(biāo)){成功返回}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}所以，這里應(yīng)改為：

if(L[0]==n){S=[p,f(p),*Lp];U=f(p)]}else//這里變量S用于存放解。//第二十二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1222計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),*L](f(p)為最小);⑷if(f(p)<U){⑸if(L[0]==n){S=[p,f(p),*Lp];U=f(p)]}else⑹{產(chǎn)生p的后繼d并計(jì)算f(d)；對(duì)每個(gè)后繼d⑺{(lán)if(dClosed&&dOpen){將[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){刪去舊結(jié)點(diǎn)并將[d,f(d),p]重新插入到Open中。}}}因?yàn)門SP要考察每一條通路，只要這條通路沒(méi)走完，就要繼續(xù)考察。⑹

{擴(kuò)展結(jié)點(diǎn)p：對(duì)p的每個(gè)后繼結(jié)點(diǎn)d，若d不在L中，則{計(jì)算f(d);若f(d)<U,則生成[d,f(d),*Ld]并將其按序放入Open表中;}}}第二十三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1223計(jì)算機(jī)算法設(shè)計(jì)與分析擴(kuò)展結(jié)點(diǎn)p擴(kuò)展結(jié)點(diǎn)p需要做的事情有：對(duì)p的每個(gè)后繼結(jié)點(diǎn)d，若d不在L中，則{計(jì)算f(d)；若f(d)<U，則生成[d,f(d),*Ld]并將其按序放入Open表中。什么樣的結(jié)點(diǎn)是p的后繼結(jié)點(diǎn)？令代價(jià)矩陣為C[n][n]。若C[p][d]<∞，則d是p的后繼結(jié)點(diǎn)。即：for(d=1,d<n,d++){if(C[p][d]<∞)…。0是起點(diǎn)，無(wú)需考慮。if(L[d]=n)then把這兩個(gè)if寫在一起。第二十四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1224計(jì)算機(jī)算法設(shè)計(jì)與分析擴(kuò)展結(jié)點(diǎn)p擴(kuò)展結(jié)點(diǎn)p需要做的事情有：對(duì)p的每個(gè)后繼結(jié)點(diǎn)d，若d不在L中，則{計(jì)算f(d)；若f(d)<U，則生成[d,f(d),*L]并將其按序放入Open表中。for(d=1,d<n,d++){if(L(d)=n&&C[p][d]<∞)then{

V=f(d);//調(diào)用評(píng)價(jià)函數(shù)計(jì)算f(d)//

if(V<U){生成Ld;

Ld=L∪d;

Put-ordered-in(Open,[d,f(d),*Ld])}}需要為d生成一個(gè)其自有的路徑表Ld。將p的路徑表L插入p的后繼結(jié)點(diǎn)d之后再賦值給Ld。最后將新擴(kuò)展結(jié)點(diǎn)d按序放入Open表中。第二十五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1225計(jì)算機(jī)算法設(shè)計(jì)與分析擴(kuò)展結(jié)點(diǎn)pDevelop([p,f(p),*L]){for(d=1,d<n,d++){if(L(d)=n&&C[p][d]<∞)then{V=f(d);//調(diào)用評(píng)價(jià)函數(shù)計(jì)算f(d)//if(V<U){

生成Ld;Ld=L∪d;

Put-ordered-in(Open,[d,f(d),*Ld])}}第二十六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1226計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法的一般算法Branch-bounding-for-TSP(n,*C[][]){⑴Initialization；⑵while(Open≠){⑶從Open中取出[p,f(p),*L](f(p)為最小);⑷if(f(p)<U){⑸if(L[0]==n){S=[p,f(p),*Lp];U=f(p)]}else⑹Develop([p,f(p),*Lp];}}}第二十七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1227計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求TSP舉例設(shè)有向圖G=(V,E)的邊的代價(jià)矩陣為C=[cij]。若沒(méi)有有向邊<i,j>∈E，則定義cij=∞且規(guī)定cii=∞。不失一般性，設(shè)周游路線均以頂點(diǎn)1為起點(diǎn)。左下為一個(gè)有向圖G的代價(jià)矩陣C?！?54031275∞1730251915∞6195024∞6228710∞評(píng)價(jià)函數(shù)f(d)為1到d的代價(jià)減去已經(jīng)過(guò)的邊數(shù)。初始時(shí)f(1)=0;f(d)=f(p)+cpd–1，這里p是d的前驅(qū)。第二十八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1228計(jì)算機(jī)算法設(shè)計(jì)與分析分支限界法求TSP的搜索∞254031275∞1730251915∞6195024∞6228710∞102243394305262340453548523333243542793535453246437234946242843584286找到了一條周游路線1→5→3→4→2→1，其長(zhǎng)度為95。這不是最短周游路線，需要修改上界后繼續(xù)搜索。第二十九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1229計(jì)算機(jī)算法設(shè)計(jì)與分析評(píng)價(jià)函數(shù)影響搜索效率前面的搜索的效率不高，幾乎要搜索全部的狀態(tài)空間。其原因是評(píng)價(jià)函數(shù)性能不好以及上下界的估計(jì)太低。要提高搜索效率，就必須要提高評(píng)價(jià)函數(shù)的性能，并精確上界的估計(jì)值。為了設(shè)計(jì)求解TSP問(wèn)題的更好的評(píng)價(jià)函數(shù)，先定義其代價(jià)矩陣的歸約矩陣和約數(shù)。第三十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1230計(jì)算機(jī)算法設(shè)計(jì)與分析歸約矩陣以及約數(shù)給定代價(jià)矩陣C，從C的任何行i(或列i)的各元素中減去此行(或此列)的最小元素的值r(i)(或r’(i))，稱為對(duì)i行(或i列)的歸約。將C的各行和各列都?xì)w約后的矩陣稱為C的歸約矩陣。數(shù)r=∑i≤nr(i)+∑i≤nr’(i)，即各行最小元素的值之和加上各列最小元素之和，稱為C的約數(shù)。第三十一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1231計(jì)算機(jī)算法設(shè)計(jì)與分析例子中的歸約矩陣和約數(shù)計(jì)算前面例子中的歸約矩陣及其約數(shù)如下：∞254031275∞1730251915∞6195024∞6228710∞先做行歸約：∞254031275∞1730251915∞6195024∞6228710∞r(nóng)(1)=25∞01562r(2)=5

0∞122520r(3)=11814∞50r(4)=6

34421∞0r(5)=715103∞第三十二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1232計(jì)算機(jī)算法設(shè)計(jì)與分析例子中的歸約矩陣和約數(shù)計(jì)算前面例子中的歸約矩陣及其約數(shù)如下：∞254031275∞1730251915∞6195024∞6228710∞再做列歸約：∞254031275∞1730251915∞6195024∞6228710∞r(nóng)(1)=25∞01562r(2)=5

0∞122520r(3)=11814∞50r(4)=6

34421∞0r(5)=715103∞r(nóng)’(1)=r’(2)=r’(3)=r’(5)=0r’(4)=

3322∞047約數(shù)r=47。歸約矩陣這個(gè)約數(shù)r是什么呢？第三十三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1233計(jì)算機(jī)算法設(shè)計(jì)與分析約數(shù)是周游路線代價(jià)的下界定理：設(shè)C是圖G的代價(jià)矩陣，P是周游路線，則P的代價(jià)，即∑<i,j>∈Pcij=r+∑<i,j>∈Pcij’，式中C’=[cij’]是C的歸約矩陣，r為約數(shù)。證明：由歸約矩陣的構(gòu)造可知：cij’=cij–r(i)–r’(j)，即cij=cij’+r(i)+r’(j)。任何周游路線包含n條邊并且對(duì)應(yīng)在C中的每行每列有且僅有一條邊。于是∑<i,j>∈Pcij=∑<i,j>∈P(cij’+r(i)+r’(j))=r+∑<i,j>∈Pcij’。原來(lái)約數(shù)r是圖G的任何一條周游路線的代價(jià)的下界!第三十四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1234計(jì)算機(jī)算法設(shè)計(jì)與分析用約數(shù)定義期望函數(shù)h(d)既然約數(shù)是周游路線長(zhǎng)度的下界，可以考慮用約數(shù)來(lái)定義期望函數(shù)h(d)：對(duì)開始結(jié)點(diǎn)1，令g(1)=0，h(1)=r，f(1)=r。若從結(jié)點(diǎn)1選擇了一條邊，不妨設(shè)邊<1,2>，則令g(2)=f(1)+從1到2的距離l

，顯然l應(yīng)該是c’12，而不應(yīng)該再是c12了。那么h(2)=？自然可以想到h(2)是從2開始的路線的下界r2。是否可用類似求r一樣去求新的約數(shù)r2呢？第三十五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1235計(jì)算機(jī)算法設(shè)計(jì)與分析求新的約數(shù)r2可以。要先將邊<1,2>和所有邊<1,k>和邊<k,2>都刪去，即置c12’、c1k’和ck2’為∞。設(shè)Cp’為路線上點(diǎn)p的歸約矩陣。從p選擇邊<p,d>所得點(diǎn)d的歸約矩陣Cd’和約數(shù)rd為：⑴先將Cp’中的cpd’，cpk’和ckd’都置為∞，這里1≤k≤n，即刪去這些邊；⑵依照求歸約矩陣C’的方法對(duì)C’p進(jìn)行行歸約和列歸約，便得到了Cd’和rd。因?yàn)檫?lt;1,2>已走過(guò)，所以不可能再走邊<1,k>和邊<k,2>了。第三十六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1236計(jì)算機(jī)算法設(shè)計(jì)與分析新的評(píng)價(jià)函數(shù)f(d)不失一般性，將圖G中結(jié)點(diǎn)標(biāo)記為1~n，并設(shè)0為起點(diǎn)。將圖G的代價(jià)矩陣C的約數(shù)r和歸約矩陣C’分別為起點(diǎn)0的約數(shù)r1和歸約矩陣C1’。對(duì)任意路線上結(jié)點(diǎn)d，定義其評(píng)價(jià)函數(shù)為：f(d)=g(d)+h(d)，其中：⑴g(d)=f(p)+Cp’[p][d]，這里p為d的前驅(qū)結(jié)點(diǎn)，并規(guī)定g(1)=0；⑵h(d)=rd。兩點(diǎn)在p的歸約矩陣中的代價(jià)第三十七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1237計(jì)算機(jī)算法設(shè)計(jì)與分析用新的評(píng)價(jià)函數(shù)求TSP下面用新的評(píng)價(jià)函數(shù)求前面的例子，我們已經(jīng)求得了它的歸約矩陣C’和約數(shù)r=47。∞015320∞1222201814∞2034418∞015100∞1472g(2)=47+0=47∞∞∞∞∞∞∞∞010801512h(2)=12+3=15f(2)=47+15=62623∞015320∞1222201814∞2034418∞015100∞g(3)=47+15=62

∞∞∞∞∞∞∞∞04313h(3)=1f(3)=63634類似地可求出f(4)=51。515類似地可求出f(5)=50。50下面優(yōu)先擴(kuò)展的是結(jié)點(diǎn)5。2此時(shí)C’2是在C’5的基礎(chǔ)上進(jìn)行。右邊就是C’5?！蕖蕖蕖蕖?∞1222∞1814∞2∞34418∞∞

∞000∞g(2)=50+0=50∞∞∞∞∞01601503h(2)=17f(2)=67673類似地計(jì)算出f(3)=68684類似地計(jì)算出f(4)=8181下面擴(kuò)展f(4)=51的結(jié)點(diǎn)4。并用同樣方法計(jì)算它們的評(píng)價(jià)函數(shù)值。2121369464154下面要擴(kuò)展的結(jié)點(diǎn)是f(2)=62的結(jié)點(diǎn)2。右邊是其對(duì)應(yīng)的歸約矩陣C’2。2∞∞∞∞∞∞∞010815∞∞200∞18∞012∞00∞3g(3)=62+0=62；對(duì)C’2進(jìn)行歸約，∞∞∞∞∞得h(3)=0；于是f(3)=62。62對(duì)結(jié)點(diǎn)2的另外兩個(gè)兒子進(jìn)行同樣的計(jì)算，得：f(4)=84，f(5)=72。484572下面對(duì)f(3)=62的結(jié)點(diǎn)3進(jìn)行擴(kuò)展。它有兩個(gè)后繼結(jié)點(diǎn)。345對(duì)結(jié)點(diǎn)4，g(4)=62+2=64。∞∞∞∞0h(4)=12，于是f(4)=64+12=7676對(duì)結(jié)點(diǎn)5，g(5)=62+0=62?！蕖蕖蕖蕖蕖蕖蕖蕖蕖?5∞∞200∞∞∞012∞∞0∞∞∞∞∞∞h(5)=0，于是f(5)=62+0=6262對(duì)結(jié)點(diǎn)5(f(5)=62)再進(jìn)行擴(kuò)展。54g(4)=62+0=62，∞∞h(4)=0，f(4)=62。62結(jié)點(diǎn)4是目標(biāo)結(jié)點(diǎn)，找到了第一條路線。4這條路線的長(zhǎng)度為62，以其為上界。其余未擴(kuò)展的結(jié)點(diǎn)的評(píng)價(jià)函數(shù)值均超過(guò)上界，因而不再需要擴(kuò)展了。××××××××××于是找到了一條最短的周游路線：1→2→3→5→4→1。C1’C2’C1’r3的計(jì)算仍然要用C1’，故恢復(fù)為C1’。下面與此相類似，不再演示。

第三十八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2023/6/1238計(jì)算機(jī)算法設(shè)計(jì)與分析評(píng)價(jià)函數(shù)的程序設(shè)計(jì)對(duì)任意路線上結(jié)點(diǎn)d，定義其評(píng)價(jià)函數(shù)為：f(d)=g(d)+h(d)，其中：⑴g(d)=f(p)+Cp’[p][d]，這里p為d的前驅(qū)結(jié)點(diǎn)，并規(guī)定g(1)=0；⑵h(d)=rd。其中用到了d的前驅(qū)結(jié)點(diǎn)p的歸約矩陣Cp’。因此，評(píng)