0033算法筆記——【分支限界法】分支限界法與單源最短路徑問(wèn)題.doc

《0033算法筆記——【分支限界法】分支限界法與單源最短路徑問(wèn)題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1、分支限界法???(1)描述：采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹(shù)的結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱為分枝限界法。???所謂“分支”是采用廣度優(yōu)先的策略，依次生成擴(kuò)展結(jié)點(diǎn)的所有分支（即：兒子結(jié)點(diǎn)）。???所謂“限界”是在結(jié)點(diǎn)擴(kuò)展過(guò)程中，計(jì)算結(jié)點(diǎn)的上界（或下界），邊搜索邊減掉搜索樹(shù)的某些分支，從而提高搜索效率。???(2)原理：按照廣度優(yōu)先的原則，一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)（E-結(jié)點(diǎn)）R后，算法將依次生成它的全部孩子結(jié)點(diǎn)，將那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點(diǎn)表中。然后，從活結(jié)點(diǎn)表中取出一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程，直至找到問(wèn)題的解或判定無(wú)解為止。???(3)分支限

2、界法與回溯法???1)求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹(shù)中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。????2)搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。??(4)常見(jiàn)的分支限界法???1)FIFO分支限界法(隊(duì)列式分支限界法)???基本思想：按照隊(duì)列先進(jìn)先出(FIFO)原則選取下一個(gè)活結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。???搜索策略：一開(kāi)始，根結(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根結(jié)點(diǎn)入隊(duì)。從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的

3、所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子加入活結(jié)點(diǎn)隊(duì)列中。再?gòu)幕罱Y(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)（隊(duì)中最先進(jìn)來(lái)的結(jié)點(diǎn)）為當(dāng)前擴(kuò)展結(jié)點(diǎn)，……，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。??2)LC(leastcost)分支限界法(優(yōu)先隊(duì)列式分支限界法)??基本思想：為了加速搜索的進(jìn)程，應(yīng)采用有效地方式選擇活結(jié)點(diǎn)進(jìn)行擴(kuò)展。按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。??搜索策略：對(duì)每一活結(jié)點(diǎn)計(jì)算一個(gè)優(yōu)先級(jí)（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級(jí)；從當(dāng)前活結(jié)點(diǎn)表中優(yōu)先選擇一個(gè)優(yōu)先級(jí)最高（最有利）的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。再?gòu)幕罱Y(jié)點(diǎn)

4、表中下一個(gè)優(yōu)先級(jí)別最高的結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)，……，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。???(5)分支限界法搜索應(yīng)用舉例????1)0-1背包問(wèn)題，當(dāng)n=3時(shí)，w={16,15,15},p={45,25,25},c=30???隊(duì)列式分支限界法(處理法則:先進(jìn)先出)：{}—>{A}—>{B,C}—>{C,D,E}(D是不可行解，舍棄)—>{C,E}—>{E,F,G}—>{F,G,J,K}(J是不可行解，舍棄)—>{F,G,K}—>{G,K,L,M}—>{K,L,M,N,O}—>{}???優(yōu)先隊(duì)列式分支限界法(處理法則:價(jià)值大者優(yōu)先)：{}—>{A}—>{B,C}—>{C，D，E}—>{C，E}—

5、>{C，J，K}—>{C}—>{F，G}—>{G，L，M}—>{G，M}—>{G}—>{N，O}—>{O}—>{}???2)旅行員售貨問(wèn)題???隊(duì)列式分支限界法(節(jié)點(diǎn)B開(kāi)始)：{}—{B}—{C，D，E}—{D，E，F(xiàn)，G}—{E，F(xiàn)，G，H，I}—{F，G，H，I，J，K}—{G，H，I，J，K，L}—{H，I，J，K，L，M}—{I，J，K，L，M，N}—{J，K，L，M，N，O}—{K，L，M，N，O，P}—{L，M，N，O，P，Q}—{M，N，O，P，Q}—{N，O，P，Q}—{O，P，Q}—{P，Q}—{Q}—{}???優(yōu)先隊(duì)列式分支限界法：優(yōu)先級(jí)是結(jié)點(diǎn)的當(dāng)前費(fèi)用：{}—{B}—{C

6、，D，E}—{C，D，J，K}—{C，J，K，H，I}—{C，J，K，I，N}—{C，K，I，N，P}—{C，I，N，P，Q}—{C，N，P，Q，O}—{C，P，Q，O}—{C，Q，O}—{Q，O，F(xiàn)，G}—{Q，O，G，L}—{Q，O，L，M}—{O，L，M}—{O，M}—{M}—{}???2、單源最短路徑問(wèn)題???問(wèn)題描述???在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。???下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問(wèn)題產(chǎn)生的解空間樹(shù)。其中，每一個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。??????算法設(shè)計(jì)???算法從圖G的

7、源頂點(diǎn)s和空優(yōu)先隊(duì)列開(kāi)始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過(guò)程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。??在算法擴(kuò)展結(jié)點(diǎn)的