分支限界法的基本思想

分支限界法解決單源最短路徑1.分支限界法基本思想2.問(wèn)題描述3.算法思路分支限界法的基本思想分支限界法以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜尋解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其全部?jī)鹤咏Y(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í)為止。 給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到全部其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。

單源最短路徑STa2b3k3f9e2d7c4l5h2g2n5i5m1j3o5p2u3從s點(diǎn)動(dòng)身到t點(diǎn)，如何找到最短路徑?單源最短路徑qr2字母旁邊的數(shù)字為路長(zhǎng)解題思路：優(yōu)先隊(duì)列式分支限界法 依據(jù)優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 在本例中，優(yōu)先級(jí)即為各節(jié)點(diǎn)的當(dāng)前路長(zhǎng)，當(dāng)前路長(zhǎng)小的節(jié)點(diǎn)優(yōu)先單源最短路徑剪枝條件：在算法擴(kuò)展過(guò)程中，一旦發(fā)覺(jué)一個(gè)結(jié)點(diǎn)的路徑不小于當(dāng)前找到的最短路徑，則減去以該結(jié)點(diǎn)為根的子樹(shù)shfgdeucba2546125943單源路徑問(wèn)題的解空間樹(shù)

節(jié)點(diǎn)旁數(shù)字為當(dāng)前路長(zhǎng)算法從源節(jié)點(diǎn)S起先S被擴(kuò)展，3個(gè)子節(jié)點(diǎn)被插入堆中計(jì)算當(dāng)前最短路徑為2將當(dāng)前路徑最短的節(jié)點(diǎn)擴(kuò)展，即走au,ae,ad計(jì)算當(dāng)前最短路徑為3，將其擴(kuò)展，走bg,bf計(jì)算當(dāng)前最短路徑為4，由先進(jìn)先出原則，走ch.單源最短路徑sqhfgdeucbalmk254612594310675當(dāng)前最短路程為4，將其擴(kuò)展即走aeq,aek;計(jì)算最短路程為5，留意：當(dāng)前結(jié)點(diǎn)不小于已找到的最短路程，剪枝：不再擴(kuò)展接著，最短路程為5，將其擴(kuò)展，即bgm,bgl；計(jì)算最短路徑為5.滿足剪枝條件，剪枝。單源最短路徑sqhfgdeucbalmkrp25461259431067588計(jì)算當(dāng)前最短路程6滿足剪枝條件，剪枝計(jì)算當(dāng)前最短路程為6走bgmr，bgmp路徑。當(dāng)前最短路徑為7，擴(kuò)展得aeko.當(dāng)前最短路徑為8.算法結(jié)束單源最短路徑12總結(jié)：分支限界法，通過(guò)目標(biāo)函數(shù)和約束條件削減無(wú)效操作，盡早發(fā)覺(jué)剪枝點(diǎn)。適用于解決滿足約束條