分支限界法實(shí)現(xiàn)單源最短路徑

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告分支限界法實(shí)現(xiàn)單源最短路徑班級(jí)： 11計(jì)算機(jī)1 姓名： 金李揚(yáng) 日期： 5.22 1.問(wèn)題描述以分支限界法實(shí)現(xiàn)單源最短路徑1.以分支限界實(shí)現(xiàn)優(yōu)先隊(duì)列2.再以分支限界法的優(yōu)先隊(duì)列實(shí)現(xiàn)單元最短路徑以該圖為算法測(cè)試數(shù)據(jù)，獲得鏈接矩陣如下：以-1代表無(wú)法到達(dá)的點(diǎn)-1 2 3 4 -1 -1 -1 -1 -1 -1 -1-1 -1 3 -1 7 2 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 9 2 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 3 3 -1 -1-1 -1 -1 -1 -

2、1 -1 1 -1 3 -1 -1-1 -1 -1 -1 -1 -1 -1 -1 5 1 -1-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -12.算法思想分支限界法基本思想：分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)

3、解的兒子結(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í)為止。算法步驟1.用一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表，其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。2.算法從圖G的源頂點(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ò)

4、程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。剪枝函數(shù)1.在算法擴(kuò)展結(jié)點(diǎn)的過(guò)程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹(shù)。2.在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長(zhǎng)不同，因此可以將路長(zhǎng)長(zhǎng)的路徑所對(duì)應(yīng)的樹(shù)中的結(jié)點(diǎn)為根的子樹(shù)剪去。3.算法設(shè)計(jì)1.定義HEAPNODE結(jié)構(gòu)體：typedef struct HeapNode int left, right; int weight; bool friend operator < (const HeapNode &a, const HeapNod

5、e &b) return a.weight > b.weight; int i,length; HeapNode() HeapNode(int ii,int l) i=ii; length=l; ;2.以堆實(shí)現(xiàn)優(yōu)先隊(duì)列類(lèi)：#define MAXN 25500class priority_queue private : HeapNode rMAXN; int length; void heap_adjust(int s, int m) HeapNode rc = rs; for (int j = s << 1; j <= m; j <<= 1) if

6、(j < m && rj < rj+1) j+; if (!(rc < rj) break; rs = rj; s = j; rs = rc; public : priority_queue() length = 0; /*=下面是堆操作部分，建堆，堆排等=*/ void creat_heap() for (int i = length >> 1; i > 0; i-) heap_adjust(i, length); void set_size(int length) this->length = length; void set_va

7、lue(int id, HeapNode value) rid = value; void heap_sort() for (int i = length; i > 1; i-) HeapNode tmp = r1; r1 = ri; ri = tmp; heap_adjust(1, i - 1); bool is_heap() int len = length >> 1 - 1, j; if (len < 1) if (length = 1 | (!(r1 < rlength) && !(r1 < rlength - 1) return t

8、rue; return false; for (int i = 1; i <= len; i+) j = i << 1; if (rj < rj + 1) j+; if (ri < rj) return false; return true; /* 用堆實(shí)現(xiàn)的priority_queue */ void push(HeapNode rc) +length; rlength = rc; int s = length >> 1; for (int j = length; j > 1; j >>= 1) if (!(rs < rj)

9、break; HeapNode tmp = rs; rs = rj; rj = tmp; s >>= 1; void pop() HeapNode tmp = r1; r1 = rlength; rlength = tmp; heap_adjust(1, -length); HeapNode top() return r1; int size() return length; bool empty() if (length <= 0) return true; return false; ;3.分支限界法實(shí)現(xiàn)單源最短路徑void shorest(int v) priority

10、_queue heap; HeapNode enode(v,0); for(int i=1; i<=n; i+) disti=MAX; distv=0; while(1) for(int j=1; j<=n; j+) if(aenode.ij<MAX && enode.length+aenode.ij<distj) distj=enode.length+aenode.ij; HeapNode node(j,distj); heap.push(node); if(heap.empty() break; else enode=heap.top(); heap.pop(); 4.主函數(shù)int main ()cout<<"請(qǐng)輸入節(jié)點(diǎn)個(gè)數(shù):" cin>>n;cout<<"請(qǐng)輸入n*n的鏈接矩陣:"<<endl; for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) cin>>aij; if(aij=-1) aij=MAX; shorest(