資源描述：
《0033算法筆記——【分支限界法】分支限界法與單源最短路徑問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、1、分支限界法???(1)描述：采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結(jié)點，并使用剪枝函數(shù)的方法稱為分枝限界法。???所謂“分支”是采用廣度優(yōu)先的策略，依次生成擴展結(jié)點的所有分支（即：兒子結(jié)點）。???所謂“限界”是在結(jié)點擴展過程中，計算結(jié)點的上界（或下界），邊搜索邊減掉搜索樹的某些分支，從而提高搜索效率。???(2)原理：按照廣度優(yōu)先的原則，一個活結(jié)點一旦成為擴展結(jié)點（E-結(jié)點）R后，算法將依次生成它的全部孩子結(jié)點，將那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點表中。然后，從活結(jié)點表中取出一個結(jié)點作為當(dāng)前擴展結(jié)點。重復(fù)上述結(jié)點擴展過程，直至找到問題的解或判定無解為止。???(3)分支限
2、界法與回溯法???1)求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。????2)搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。??(4)常見的分支限界法???1)FIFO分支限界法(隊列式分支限界法)???基本思想：按照隊列先進先出(FIFO)原則選取下一個活結(jié)點為擴展結(jié)點。???搜索策略：一開始，根結(jié)點是唯一的活結(jié)點，根結(jié)點入隊。從活結(jié)點隊中取出根結(jié)點后，作為當(dāng)前擴展結(jié)點。對當(dāng)前擴展結(jié)點，先從左到右地產(chǎn)生它的
3、所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子加入活結(jié)點隊列中。再從活結(jié)點表中取出隊首結(jié)點（隊中最先進來的結(jié)點）為當(dāng)前擴展結(jié)點，……，直到找到一個解或活結(jié)點隊列為空為止。??2)LC(leastcost)分支限界法(優(yōu)先隊列式分支限界法)??基本思想：為了加速搜索的進程，應(yīng)采用有效地方式選擇活結(jié)點進行擴展。按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的結(jié)點成為當(dāng)前擴展結(jié)點。??搜索策略：對每一活結(jié)點計算一個優(yōu)先級（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級；從當(dāng)前活結(jié)點表中優(yōu)先選擇一個優(yōu)先級最高（最有利）的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。再從活結(jié)點
4、表中下一個優(yōu)先級別最高的結(jié)點為當(dāng)前擴展結(jié)點，……，直到找到一個解或活結(jié)點隊列為空為止。???(5)分支限界法搜索應(yīng)用舉例????1)0-1背包問題，當(dāng)n=3時，w={16,15,15},p={45,25,25},c=30???隊列式分支限界法(處理法則:先進先出)：{}—>{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)先隊列式分支限界法(處理法則:價值大者優(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)旅行員售貨問題???隊列式分支限界法(節(jié)點B開始)：{}—{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)先隊列式分支限界法：優(yōu)先級是結(jié)點的當(dāng)前費用：{}—{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、單源最短路徑問題???問題描述???在下圖所給的有向圖G中，每一邊都有一個非負(fù)邊權(quán)。要求圖G的從源頂點s到目標(biāo)頂點t之間的最短路徑。???下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。??????算法設(shè)計???算法從圖G的
7、源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴展后，它的兒子結(jié)點被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴展結(jié)點，并依次檢查與當(dāng)前擴展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴展結(jié)點i到頂點j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當(dāng)前最優(yōu)路徑長度，則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。這個結(jié)點的擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止。??在算法擴展結(jié)點的
