1、回溯法及分支限界法求解旅行商問題的上機(jī)報(bào)告實(shí)驗(yàn)名稱：旅行商問題；實(shí)驗(yàn)內(nèi)容與要求：用回溯策略或分支限界策略，求解旅行商問題的最優(yōu)解；回溯策略：代碼淺析：出于對(duì)無向圖存儲(chǔ)的考慮，首先采用鄰接表，node設(shè)置visit來顯示該節(jié)點(diǎn)是否已在列表中；簡(jiǎn)化問題將城市名稱做成查找表，用0N代替名字進(jìn)行存儲(chǔ)，打印時(shí)查找數(shù)組NumExChar來輸出；使用STL中的list來存儲(chǔ)路徑；初始化最小耗費(fèi)為MAX，加入節(jié)點(diǎn)為0；初始化鄰接表，將數(shù)據(jù)存儲(chǔ)在txt中避免手工頻繁輸入；DFS為回溯函數(shù)，對(duì)所有可行解遍歷，不可行則回溯；printQ對(duì)list進(jìn)行打印輸出，copyQ用于將最小耗費(fèi)的路徑拷貝到List_min中；

2、 初始化時(shí)，a為相鄰節(jié)點(diǎn)，b為鄰邊權(quán)值，數(shù)據(jù)存儲(chǔ)在txt中方便運(yùn)行；加入節(jié)點(diǎn)為5時(shí)，比較min_cost，若小于則更新min_cost和List_min（因?yàn)橹挥幸粋€(gè)List_min，所以無法將全部最小耗費(fèi)的路徑打印出，結(jié)果是DFS遍歷到的第一條最小路徑）；若訪問過則繼續(xù)訪問下一個(gè)相鄰節(jié)點(diǎn)直至未訪問或全部加入為止；對(duì)更新進(jìn)行恢復(fù)，p=p-next訪問下一個(gè)可行解；示例結(jié)果：從結(jié)果可以看出，其實(shí)共有兩條最短路徑：abdeca；acedba；算法淺析：容易看出，回溯法求解旅行商問題最好為O(n)時(shí)間，最壞為O(n-1)!)，隨著問題規(guī)模的增大，求解問題的時(shí)間將極為恐怖；有一個(gè)樸素的改進(jìn)法：不用遍歷

3、所有可行解，在已有的min_cost下，下一步可行解一旦超出min_cost則將其剪枝（遇見更小的min_cost則更新），此例由于完全圖的性質(zhì)共有24種可行解，而若采取樸素剪枝法，則只需四次O(n)的遍歷。當(dāng)然，這不是最優(yōu)的剪枝法。分支限界法：代碼淺析：沿襲了回溯法代碼的風(fēng)格，不過由于本次示例是完全圖，索性將鄰接表改成鄰接矩陣，同時(shí)將各節(jié)點(diǎn)最小兩鄰邊寫入矩陣Two_Smallest中，由于數(shù)據(jù)規(guī)模較小直接寫入減小編程量；CLb進(jìn)行每次廣度搜索時(shí)lb的計(jì)算并將結(jié)果存儲(chǔ)在c_lb中；Final在節(jié)點(diǎn)全部加入時(shí)計(jì)算回路路徑的長度；printQ、copyQ如上。先進(jìn)行廣度搜索確定最小lb；對(duì)于已達(dá)到

4、的可行解進(jìn)行min_l更新，未達(dá)到的對(duì)子樹進(jìn)行BFS（注意還原現(xiàn)場(chǎng)以實(shí)現(xiàn)對(duì)不同方式的最小路徑搜索）； CLb的函數(shù)實(shí)現(xiàn)部分，參照PPT進(jìn)行編寫，對(duì)各節(jié)點(diǎn)最小兩鄰邊進(jìn)行更新，棄用上取整形式，直接采用lb*2，避免對(duì)函數(shù)實(shí)現(xiàn)的取整煩擾，同時(shí)并不影響分支的結(jié)果；、示例結(jié)果：在bound.cpp最短路徑更新時(shí)將寫法與back.cpp區(qū)別開來，則back.cpp輸出的最短路徑恰是第一條，而bound.cpp恰是最后一條，參考back.cpp的運(yùn)行結(jié)果，則bound.cpp此例并未出現(xiàn)錯(cuò)誤；、算法淺析：在對(duì)每個(gè)子節(jié)點(diǎn)進(jìn)行BFS時(shí)，運(yùn)用了O(h)的時(shí)間（期中h為剩余未加入節(jié)點(diǎn)數(shù)），若每層子節(jié)點(diǎn)最小lb均只出現(xiàn)一次，則時(shí)間復(fù)雜度最壞為O(n2)，這個(gè)結(jié)果已經(jīng)非常好；然而如果考慮搜索最壞情況，則依然是O(n-1)!)。、疑惑：個(gè)人對(duì)分支限界法有一點(diǎn)疑問，如何保證使得限界函數(shù)最優(yōu)的子樹中生成的最優(yōu)解始終優(yōu)于或至少等于被剪枝的子樹的最優(yōu)解？這應(yīng)當(dāng)需要一個(gè)數(shù)學(xué)證明，我相信前輩們?cè)缇徒o出證明，不過我始終沒能想明白。因?yàn)樵诠軤栴D回路中，最