分支限界算法設(shè)計(jì)與應(yīng)用

1、實(shí)驗(yàn)七實(shí)驗(yàn)七分支限界的應(yīng)用分支限界的應(yīng)用一基本原理的概括一基本原理的概括一個(gè)具體問題，其解決的方法可能有很多種，可采用各種不同的算法設(shè)計(jì)方法。二該類算法設(shè)計(jì)與實(shí)現(xiàn)的要點(diǎn)二該類算法設(shè)計(jì)與實(shí)現(xiàn)的要點(diǎn)熟練掌握各種算法設(shè)計(jì)方法三實(shí)驗(yàn)?zāi)康暮鸵笕龑?shí)驗(yàn)?zāi)康暮鸵笠笥梅种藿缫约爸辽僖环N其它算法求解旅行商問題，提高綜合應(yīng)用各種算法設(shè)計(jì)方法的能力。四實(shí)驗(yàn)內(nèi)容（分支限界算法四實(shí)驗(yàn)內(nèi)容（分支限界算法宏定義#defineMAX_CITY_NUMBER10城

2、市最大數(shù)目#defineMAX_COST10000000兩個(gè)城市之間費(fèi)用的最大值全局變量intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]表示城市間邊權(quán)重的數(shù)組intCity_Size表示實(shí)際輸入的城市數(shù)目intBest_Cost最小費(fèi)用intBest_Cost_Path[MAX_CITY_NUMBER]最小費(fèi)用時(shí)的路徑定義結(jié)點(diǎn)typedefstructNode發(fā)現(xiàn)一個(gè)優(yōu)先級(jí)大的，則置于其前面

3、pinnodepNext=prepNextprepNext=pinnodebreak跳出pre=nextnext=nextpNextprepNext=pinnode放在末尾出堆NodeRemoveMiniHeap(MiniHeappMiniHeap)Nodepnode=NULLif(pMiniHeappHeadpNext!=NULL)pnode=pMiniHeappHeadpNextpMiniHeappHeadpNext=pMiniHe

4、appHeadpNextpNextreturnpnode分支限界法找最優(yōu)解voidTraveler()intijinttemp_x[MAX_CITY_NUMBER]NodepNode=NULLintminiSum所有結(jié)點(diǎn)最小出邊的費(fèi)用和intminiOut[MAX_CITY_NUMBER]保存每個(gè)結(jié)點(diǎn)的最小出邊的索引MiniHeapheap=newMiniHeap分配堆InitMiniHeap(heap)初始化堆miniSum=0f(i