【正文】 葉結(jié)點(diǎn)。此時(shí)該葉結(jié)點(diǎn)所相應(yīng)的回路的費(fèi)用等于 cc和 lcost的值。剩余的活結(jié)點(diǎn)的1cost值不小于己找到的回路的費(fèi)用。它們都不可能導(dǎo)致費(fèi)用更小的回路。因此已找到的葉結(jié)點(diǎn)所相應(yīng)的回路是一個(gè)最小費(fèi)用旅行售貨員回路，算法可以結(jié)束 . 2021年 11月 12日 67 算法的 while循環(huán)體完成對(duì)排列樹內(nèi)部結(jié)點(diǎn)的擴(kuò)展。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)，算法分兩種情況進(jìn)行處理。 首先；考慮 s＝ n— 2的情形。此時(shí)當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)相應(yīng)一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中，否則舍去該葉結(jié)點(diǎn)。 當(dāng) s＜ n2時(shí)，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)。由于當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的路徑是 x[0:s]，其可行兒子結(jié)。點(diǎn)是從剩余頂點(diǎn) x[s+1:n1]中選取的頂點(diǎn) xIj]，且 (x[ s]，x[i])是所給有向圖 G中的一條邊。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn)，計(jì)算出其前綴 (x[0:s]， x[i])的費(fèi)用 cc和相應(yīng)的下界 Lcost。當(dāng) lcost＜ bestc時(shí)，將這個(gè)可 行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。 2021年 11月 12日 68 試寫出 0/1 背包問(wèn)題的優(yōu)先隊(duì)列式分枝限界算法程序，并找一個(gè)物品件數(shù)為 16 的例子檢驗(yàn)程序的運(yùn)行情況。 上機(jī) 2021年 11月 12日 69 回溯法與分支限界法的用法取向探討 回溯法的基本思想 : 首先確定解空間的組織結(jié)構(gòu) , 接著就從開始結(jié)點(diǎn) (根結(jié)點(diǎn) ) 出發(fā) , 以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn) , 同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處 , 搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn) , 并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng) , 則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說(shuō) , 這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí) , 應(yīng)往回移動(dòng) (回溯 ) 至最近的一個(gè)活結(jié)點(diǎn)處 , 并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法即以這種工作方式遞歸地在解空間中搜索 , 直至找到所要求的解或解空間中已沒(méi)有活結(jié)點(diǎn)時(shí)為止。 2021年 11月 12日 70 分支限界法的基本思想 : 確定解空間的組織結(jié)構(gòu) , 以廣度優(yōu)先或以最小耗費(fèi) (最大效益 ) 優(yōu)先的方式搜索問(wèn)題的解空間樹。在搜索問(wèn)題的解空間樹時(shí) , 分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中 , 每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn) , 就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中 , 那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄 , 其余兒子結(jié)點(diǎn)被子加入活結(jié)點(diǎn)表中。此后 , 從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn) , 并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止。 2021年 11月 12日 71 用法比較 分支限界法類似于回溯法 , 也是一種在問(wèn)題的解空間樹 T上搜索問(wèn)題解的算法。但在一般情況下 , 分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出 T中滿足約束條件的所有解 , 而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解 , 或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解 , 即在某種意義下的最優(yōu)解。 2021年 11月 12日 72 由于求解目標(biāo)不同 , 導(dǎo)致分支限界法與回溯法在解空間樹 T上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹 T, 而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹 T。分支限界法的搜索策略是 : 在擴(kuò)展結(jié)點(diǎn)處 , 先生成其所有的兒子結(jié)點(diǎn) (分支 ) , 然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn) , 以加速搜索的進(jìn)程 ,在每一活結(jié)點(diǎn)處 , 計(jì)算一個(gè)函數(shù)值(限界 ) , 并根據(jù)這些已計(jì)算出的函數(shù)值 , 從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn) , 使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn) , 以便盡快地找出一個(gè)最優(yōu)解。 2021年 11月 12日 73 分支限界法常以廣度優(yōu)先或以最小耗費(fèi) (最大效益 ) 優(yōu)先的方式搜索問(wèn)題的解空間樹。問(wèn)題的解空間樹是表示問(wèn)題解空間的一棵有序樹 , 常見(jiàn)的有子集樹和排列樹。在搜索問(wèn)題的解空間樹時(shí) , 分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中 , 每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn) , 就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中 , 那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄 , 其余兒子結(jié)點(diǎn)被子加入活結(jié)點(diǎn)表中。此后 , 從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn) , 并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止。 2021年 11月 12日 74 方法 空間樹的搜索方式 存儲(chǔ)結(jié)點(diǎn)的常用數(shù)據(jù)結(jié)構(gòu) 結(jié)點(diǎn)存儲(chǔ)特性 常用應(yīng)用 回溯法 深度優(yōu)先搜索 深度優(yōu)先搜索堆棧 活結(jié)點(diǎn)的所有可行子結(jié)點(diǎn)被遍歷后才被從棧中彈出 找出滿足約束條件的所有解 分支限界法 廣度優(yōu)先或最小消耗優(yōu)先搜索 隊(duì)列、優(yōu)先隊(duì)列 每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì) 找出滿足約束條件的一個(gè)解或特定意義下的最優(yōu)解 2021年 11月 12日 75 用法舉例 (1)一個(gè)比較適合采用回溯法解決的問(wèn)題 n后問(wèn)題。 (2)一個(gè)既可以采用回溯法也可以采用分支限界法解決的問(wèn)題 ——— 0 1背包問(wèn)題。 2021年 11月 12日 76 n后問(wèn)題的解空間樹是一棵排列樹 , 一旦一種組合是一種解 , 則解與解之間不存在優(yōu)劣的分別。直到搜索到葉節(jié)點(diǎn)時(shí)才能確定出一組解。這時(shí)我們用回溯法可以系統(tǒng)地搜索問(wèn)題的全部解 , 而且由于解空間樹是排列樹的特性 , 在最壞的情況下 ,堆棧的深度不會(huì)超過(guò) n。如果采取分支限界法 , 在解空間樹的第一層就會(huì)產(chǎn)生 n個(gè)活結(jié)點(diǎn) , 如果不考慮剪枝 , 將在第二層產(chǎn)生 n* ( n 1) 個(gè)活節(jié)點(diǎn) , 如此下去對(duì)隊(duì)列空間的要求太高。 n后問(wèn)題不適合使用分支限界法處理的根源是它需要找處所 有解的組合 , 而不是某種最優(yōu)解 (事實(shí)上也沒(méi)有最優(yōu)解可言 ) 。 2021年 11月 12日 77 0 1背包問(wèn)題的解空間樹是一棵子集樹 , 所要求的解具有最優(yōu)性質(zhì)。 如果采用回溯法解決這個(gè)問(wèn)題 , 可采用如下的搜索策略 : 只要一個(gè)結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)就搜索其左子樹 。 而對(duì)于右子樹 , 需要用貪心算法構(gòu)造一個(gè)上界函數(shù) ,這個(gè)函數(shù)表明這個(gè)結(jié)點(diǎn)的子樹所能達(dá)到的可能的最大容量 (因?yàn)橹挥袑?0 1背包問(wèn)題改變?yōu)楸嘲鼏?wèn)題才可能利用貪心算法 , 因此這個(gè)上界函數(shù)在絕大多數(shù)情況下不會(huì)是上確界函數(shù) ) , 只在這個(gè)上界函數(shù)的值超過(guò)當(dāng)前最優(yōu)解時(shí)才進(jìn)入搜索。隨著搜索進(jìn)程的推進(jìn) ,最優(yōu)解不斷得到加強(qiáng) , 對(duì)搜索的限制就越來(lái)越嚴(yán)格。 2021年 11月 12日 78 如果采用分支限界法解決這個(gè)問(wèn)題 , 同樣需要用到貪心算法構(gòu)造的上界函數(shù)。所不同的是 ,這個(gè)上界函數(shù)的作用不在于判斷是否進(jìn)入一個(gè)結(jié)點(diǎn)的子樹繼續(xù)搜索 , 因?yàn)樵谒阉鞯竭_(dá)葉節(jié)點(diǎn)之前 ,大家也無(wú)法知道已經(jīng)得到的最優(yōu)解是什么。在這里 , 可用一個(gè)最大堆來(lái)實(shí)現(xiàn)活結(jié)點(diǎn)的優(yōu)先隊(duì)列 ,上界函數(shù)的值將作為優(yōu)先級(jí) , 這樣一旦有一個(gè)葉結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn) , 就表明已經(jīng)找到了最優(yōu)解。 2021年 11月 12日 79 可以看出 , 用兩種方法處理 0 1背包問(wèn)題都有一定的可行性。相比之下回溯法的思路容易理解一些 , 但是這是一個(gè)尋找最優(yōu)解的問(wèn)題。由于采用了優(yōu)先隊(duì)列處理 , 不同的結(jié)點(diǎn)不再像 n后問(wèn)題那樣沒(méi)有相互之間的牽制和聯(lián)系 , 用分支限界法處理效果一樣很好。 2021年 11月 12日 80 回溯和分支限界都是以構(gòu)造一顆狀態(tài)空間樹為基礎(chǔ)的 , 樹的節(jié)點(diǎn)反映了對(duì)一個(gè)部分解所作的特定選擇。如果可以保證 , 節(jié)點(diǎn)子孫所對(duì)應(yīng)的選擇不可能得出問(wèn)題的一個(gè)解 , 兩種技術(shù)都會(huì)立即停止處理這個(gè)節(jié)點(diǎn)。兩種技術(shù)的區(qū)別在于它們能夠處理的問(wèn)題類型不同。分支限界法只能應(yīng)用于最優(yōu)問(wèn)題 , 因?yàn)樗卺槍?duì)一個(gè)問(wèn)題的目標(biāo)函數(shù) , 計(jì)算其可能值的邊界。掌握這點(diǎn) , 正確選擇這兩種算法 , 求解問(wèn)題將取到事半功倍的效率。