分支限界法實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告

《分支限界法實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、xxxxx實(shí)驗(yàn)報(bào)告課程名稱：_算法設(shè)計(jì)與分析項(xiàng)目名稱：_分支限界法實(shí)現(xiàn)_姓名：_xxxxx專業(yè)：xxxxxxx班級(jí)：__xxxxxxx_學(xué)號(hào)：__xxxxxxxxxxxxxxxxx__同組成員____無(wú)_______一、實(shí)驗(yàn)準(zhǔn)備：實(shí)驗(yàn)?zāi)康模??掌握分支限界法求解問(wèn)題的一般特征和步驟。?使用分支限界法編程，求解旅行售貨員問(wèn)題。實(shí)驗(yàn)環(huán)境準(zhǔn)備：WindowsXPMicrosoftC++2008在當(dāng)前節(jié)點(diǎn)（擴(kuò)展節(jié)點(diǎn)）處，先生成其所有的兒子節(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活節(jié)點(diǎn)（當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)）表中選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)。為了有效地選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)，加速搜索的進(jìn)程，在每一個(gè)活節(jié)

2、點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活節(jié)點(diǎn)表中選擇一個(gè)最有利的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。分支限界法解決了大量離散最優(yōu)化的問(wèn)題。1.隊(duì)列式（FIFO）分支限界法隊(duì)列式分支限界法將活節(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并將隊(duì)列的先進(jìn)先出原則選取下一個(gè)節(jié)點(diǎn)為當(dāng)前擴(kuò)展節(jié)點(diǎn)。2.優(yōu)先隊(duì)列式分支限界法優(yōu)先隊(duì)列式分支限界法將活節(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，并將優(yōu)先隊(duì)列中規(guī)定的節(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。如果選擇這種選擇方式，往往將數(shù)據(jù)排成最大堆或者最小堆來(lái)實(shí)現(xiàn)。二、實(shí)驗(yàn)過(guò)程記錄：打開MicrosoftC++2008

3、，鍵入代碼進(jìn)行編程：源代碼為：#include#include"stdafx.h"#includeusingnamespacestd;#defineMAX_CITY_NUMBER10#defineMAX_COST10000000intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];intCity_Size;intBest_Cost;intBest_Cost_Path[MAX_CITY_NUMBER];typedefstructNode{intlcost;intcc;intrcost;ints;intx

4、[MAX_CITY_NUMBER];structNode*pNext;}Node;typedefstructMiniHeap{Node*pHead;}MiniHeap;voidInitMiniHeap(MiniHeap*pMiniHeap){pMiniHeap->pHead=newNode;pMiniHeap->pHead->pNext=NULL;}voidput(MiniHeap*pMiniHeap,Nodenode){Node*next;Node*pre;Node*pinnode=newNode;pinnode->cc=node.cc;pinnode->lcost=node

5、.lcost;pinnode->pNext=node.pNext;pinnode->rcost=node.rcost;pinnode->s=node.s;pinnode->pNext=NULL;for(intk=0;kx[k]=node.x[k];}pre=pMiniHeap->pHead;next=pMiniHeap->pHead->pNext;if(next==NULL){pMiniHeap->pHead->pNext=pinnode;}else{while(next!=NULL){if((next->lcost)>(pin

6、node->lcost)){pinnode->pNext=pre->pNext;pre->pNext=pinnode;break;}pre=next;next=next->pNext;}pre->pNext=pinnode;}}Node*RemoveMiniHeap(MiniHeap*pMiniHeap){Node*pnode=NULL;if(pMiniHeap->pHead->pNext!=NULL){pnode=pMiniHeap->pHead->pNext;pMiniHeap->pHead->pNext=pMiniHeap->pHead->pNext->pNext;}re

7、turnpnode;}voidTraveler(){inti,j;inttemp_x[MAX_CITY_NUMBER];Node*pNode=NULL;intminiSum;intminiOut[MAX_CITY_NUMBER];MiniHeap*heap=newMiniHeap;InitMiniHeap(heap);miniSum=0;for(i=0;i