版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、旅行商售貨員問題的分支限界算法旅行商售貨員問題的分支限界算法姓名:姓名:學號:學號:一、實驗?zāi)康呐c要求一、實驗?zāi)康呐c要求1、掌握旅行商售貨員問題的分支限界算法;2、區(qū)分分支限界算法與回溯算法的區(qū)別,加深對分支限界法的理解。二、實驗題:二、實驗題:編程實現(xiàn):某售貨員要到若干城市去推銷商品,已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā),經(jīng)過每個城市一次,最后回到駐地的路線,使總的路程(或總旅費)最小。三、實驗提示三、實驗提示旅行商
2、問題的解空間是一個排列樹。有兩種實現(xiàn)的方法。第一種是只使用一個優(yōu)先隊列,隊列中的每個元素中都包含到達根的路徑。另一種是保留一個部分解空間樹和一個優(yōu)先隊列,優(yōu)先隊列中的元素并不包含到達根的路徑。以下為第一種方法。由于我們要尋找的是最小耗費的旅行路徑,因此可以使用最小耗費分枝定界法。在實現(xiàn)過程中,使用一個最小優(yōu)先隊列來記錄活節(jié)點,隊列中每個節(jié)點的類型為MinHeapNode。每個節(jié)點包括如下區(qū)域:x(從1到n的整數(shù)排列,其中x[0]=1),
3、s(一個整數(shù),使得從排列樹的根節(jié)點到當前節(jié)點的路徑定義了旅行路徑的前綴x[0:s]而剩余待訪問的節(jié)點是x[s1:n1]),cc(旅行路徑前綴,即解空間樹中從根節(jié)點到當前節(jié)點的耗費),lcost(該節(jié)點子樹中任意葉節(jié)點中的最小耗費),rcost(從頂點x[s:n1]出發(fā)的所有邊的最小耗費之和)。當類型為MinHeapNode(T)的數(shù)據(jù)被轉(zhuǎn)換成為類型T時,其結(jié)果即為lcost的值。代碼:代碼:#include#includeusingna
4、mespacestd宏定義#defineMAX_CITY_NUMBER10城市最大數(shù)目#defineMAX_COST10000000兩個城市之間費用的最大值全局變量intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]表示城市間邊權(quán)重的數(shù)組intCity_Size表示實際輸入的城市數(shù)目intBest_Cost最小費用intBest_Cost_Path[MAX_CITY_NUMBER]最小費用時的路
5、徑定義結(jié)點typedefstructNodeintlcost優(yōu)先級intcc當前費用intrcost剩余所有結(jié)點的最小出邊費用的和prepNext=pinnode放在末尾出堆NodeRemoveMiniHeap(MiniHeappMiniHeap)Nodepnode=NULLif(pMiniHeappHeadpNext!=NULL)pnode=pMiniHeappHeadpNextpMiniHeappHeadpNext=pMiniHea
6、ppHeadpNextpNextreturnpnode分支限界法找最優(yōu)解voidTraveler()intijinttemp_x[MAX_CITY_NUMBER]NodepNode=NULLintminiSum所有結(jié)點最小出邊的費用和intminiOut[MAX_CITY_NUMBER]保存每個結(jié)點的最小出邊的索引MiniHeapheap=newMiniHeap分配堆InitMiniHeap(heap)初始化堆miniSum=0f(i=
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 旅行售貨員問題的DNA分子算法.pdf
- 畢業(yè)論文--旅行售貨員問題
- 做售貨員心得___五篇
- 關(guān)于珠寶售貨員的實習報告
- 索菲亞從售貨員到女富豪
- 2022年大學生售貨員寒假實習報告
- 2022年大學生售貨員寒假實習報告
- 樹算法求解旅行商問題.pdf
- 中國售貨員和顧客會話的結(jié)構(gòu)分析以及禮貌原則的實現(xiàn).pdf
- 基于流水算法的旅行商問題求解
- 求解旅行商問題的進化算法.pdf
- 分支限界算法設(shè)計與應(yīng)用
- 旅行商問題的兩種算法.pdf
- 時間依賴網(wǎng)絡(luò)中國郵路問題的分支限界算法.pdf
- 基于蟻群算法的旅行商問題研究
- 算法論文分治法和分支限界
- 應(yīng)用智能螞蟻算法解決旅行商問題.pdf
- 關(guān)于旅行商問題的改進遺傳算法.pdf
- 求解旅行商問題的微粒群算法研究.pdf
- 旅行商問題的基因片段插入算法研究.pdf
評論
0/150
提交評論