【正文】 況下，用 ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí) O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是 ∑mi(mn)=nm(mn1)/(m1)=O(nmn) (0≤i≤n1) 2021年 11月 12日 68 提綱 一、回溯法的算法框架 二、裝載問(wèn)題 三、 n后問(wèn)題 四、 01背包問(wèn)題 五、最大團(tuán)問(wèn)題 六、圖的 m著色問(wèn)題 七、旅行售貨員問(wèn)題 2021年 11月 12日 69 旅行商問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題。經(jīng)典 ./ 可以描述為：一個(gè)商品推銷員要去若干個(gè)城市推銷商品，該推銷員從一個(gè)城市出發(fā)，需要經(jīng)過(guò)所有城市后，回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。從圖論的角度來(lái)看，該問(wèn)題實(shí)質(zhì)是在一個(gè)帶權(quán)完全無(wú)向圖中，找一個(gè)權(quán)值最小的 Hamilton 回路。由于該問(wèn)題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會(huì)產(chǎn)生組合爆炸，它是一個(gè) NP 完全問(wèn)題。由于其在交通運(yùn)輸、電路板線路設(shè)計(jì)以及物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用，國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量的研究。 2021年 11月 12日 70 哈密頓回路 天 文學(xué)家哈密頓 (William Rowan Hamilton) 提出，在一個(gè)有多個(gè)城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點(diǎn)到給定的終點(diǎn)沿 途恰好經(jīng)過(guò)所有其他城市一次的路徑。 這個(gè)問(wèn)題和著名的過(guò)橋問(wèn)題的不同之處在于，某些城市之間的旅行不 一定是雙向的。比如 A→B, 但B→A 是不允許的。換一種說(shuō)法，對(duì)于一個(gè)給定的網(wǎng)絡(luò)，確定起點(diǎn)和終點(diǎn)后，如果存在一條路徑，穿過(guò)這個(gè)網(wǎng)絡(luò)，我們就說(shuō)這個(gè)網(wǎng)絡(luò)存在哈密頓路徑。哈密頓路徑問(wèn)題在上世紀(jì)七十年代初，終于被證明是“ NP完備”的。據(jù)說(shuō)具有這樣性質(zhì)的問(wèn)題，難于找到一個(gè)有效的算法。實(shí)際上對(duì)于某些頂點(diǎn)數(shù)不到 100的網(wǎng)絡(luò)，利用現(xiàn)有最好的算法和計(jì)算機(jī)也需要比較荒唐的時(shí)間（比如幾百年）才能確定其是否存在一條這樣的路徑 。 2021年 11月 12日 71 從圖中的任意一點(diǎn)出發(fā)，路途中經(jīng)過(guò)圖中每一個(gè)結(jié)點(diǎn)當(dāng)且僅當(dāng)一次，則成為哈密頓回路。 要滿足兩個(gè)條件： ，且圖中任意兩點(diǎn)可達(dá) 經(jīng)過(guò)圖（有向圖或無(wú)向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密頓通路。 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密頓回路。 具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。 平凡圖是哈密頓圖。 2021年 11月 12日 72 哈密頓 哈密頓， W． R． (Hamilton，William Rowan) 1805年 8月 4日生于愛(ài)爾蘭都柏林； 1865年 9月 2日卒于都柏林．力學(xué)、數(shù)學(xué)、光學(xué)． 2021年 11月 12日 73 哈密頓的父親阿其巴德 (Archibald Rowan Hamilton)為都柏林市的一個(gè)初級(jí)律師．哈密頓自幼聰明，被稱為神童．他三歲能讀英語(yǔ)，會(huì)算術(shù)；五歲能譯拉丁語(yǔ)、希臘語(yǔ)和希伯來(lái)語(yǔ)，并能背誦荷馬史詩(shī)；九歲便熟悉了波斯語(yǔ)，阿拉伯語(yǔ)和印地語(yǔ)． 14歲時(shí)，因在都柏林歡迎波斯大使宴會(huì)上用波斯語(yǔ)與大使交談而出盡風(fēng)頭． 哈密頓自幼喜歡算術(shù)，計(jì)算很快． 1818年遇到美國(guó)“計(jì)算神童” Z．科耳本 (Colburn)后對(duì)數(shù)學(xué)產(chǎn)生了更深厚的興趣． 1820年再相逢時(shí)，哈密頓已閱讀了 I．牛頓 (Newton)的 《 自然哲學(xué)的數(shù)學(xué)原理 》(Mathematical principles of natural philosophy)，并對(duì)天文學(xué)有強(qiáng)烈愛(ài)好，常用自己的望遠(yuǎn)鏡觀測(cè)大體；還開(kāi)始讀 P． S．拉普拉斯 (Laplace)著作 《 天體力學(xué) 》 (M233。canique c233。1este)， 1822年指出了此書(shū)中的一個(gè)錯(cuò)誤．同年開(kāi)始進(jìn)行科學(xué)研究工作，對(duì)曲線和曲面的性質(zhì)進(jìn)行了系列研究，并用于幾何光學(xué)．他的報(bào)告送交愛(ài)爾蘭科學(xué)院后， R． J．布林克萊(Brinkley)院士評(píng)論說(shuō)：“這位年輕人現(xiàn)在是這個(gè)年齡 (17歲 )的第一數(shù)學(xué)家．” 2021年 11月 12日 74 哈密頓工作勤奮，思想活躍．發(fā)表的論文一般都很簡(jiǎn)潔，別人不易讀懂，但手稿卻很詳細(xì)，因而很多成果都由后人整理而得．僅在三一學(xué)院圖書(shū)館中的哈密頓手稿，就有 250本筆記及大量學(xué)術(shù)通信和未發(fā)表論文．愛(ài)爾蘭國(guó)家圖書(shū)館還有一部分手稿． 他的研究工作涉及不少領(lǐng)域，成果最大的是光學(xué)、力學(xué)和四元數(shù)．他研究的光學(xué)是幾何光學(xué)，具有數(shù)學(xué)性質(zhì)；力學(xué)則是列出動(dòng)力學(xué)方程及求解；因此哈密頓主要是數(shù)學(xué)家．但在科學(xué)史中影響最大的卻是他對(duì)力學(xué)的貢獻(xiàn)．哈密頓量是現(xiàn)代物理最重要的量，當(dāng)我們得到哈密頓量，就意味著得到了全部。 2021年 11月 12日 75 問(wèn)題定義 ? 某售貨員要到若干城市去推銷商品，已知各城市之間的路程或旅費(fèi)，他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市僅一遍，最后回到駐地的路線，使總的路程或總的旅費(fèi)最小。 ? 輸入 : 無(wú)向連通圖 G=(V, E), 每個(gè)頂點(diǎn)都沒(méi)有到自身的邊。 ? 輸出 : 一條由任意一個(gè)節(jié)點(diǎn)開(kāi)始， 經(jīng)過(guò)每個(gè)節(jié)點(diǎn)僅一次， 最后返回開(kāi)始節(jié)點(diǎn)的路徑 , 該路徑的代價(jià) (即權(quán)值之和 )最小。 2021年 11月 12日 76 問(wèn)題分析 ? 解空間：排列樹(shù) ? 可行性約束函數(shù)： 頂點(diǎn) x[i]與頂點(diǎn) x[i1]之間有邊相連。 ? 上界函數(shù)： 當(dāng)前費(fèi)用 +頂點(diǎn) x[i1]與頂點(diǎn) x[i]的邊的權(quán)值 當(dāng)前最優(yōu)值。 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3 最優(yōu)解 (1,3,2,4,1)，最優(yōu)值 25 2021年 11月 12日 77 算法描述 void Backtrack(int i) { if (i == n) { if (a[x[n1]][x[n]] != NoEdge amp。amp。 a[x[n]][1] != NoEdge amp。amp。 (cc + a[x[n1]][x[n]] + a[x[n]][1] bestc || bestc == NoEdge)) { for (int j = 1。 j = n。 j++) bestx[j] = x[j]。 bestc = cc + a[x[n1]][x[n]] + a[x[n]][1]。}} else {// 是否可進(jìn)入 x[j]子樹(shù) ? for (int j = i。 j = n。 j++) // 搜索子樹(shù) if (a[x[i1]][x[j]] != NoEdge amp。amp。 (cc+a[x[i1]][x[j]] bestc || bestc == NoEdge)) { Swap(x[i], x[j])。 cc += a[x[i1]][x[i]]。 Backtrack(i+1)。 cc = a[x[i1]][x[i]]。 Swap(x[i], x[j])。}} } 復(fù)雜度分析 算法 backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O((n1)!)次，每次更新 bestx需計(jì)算時(shí)間 O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。 2021年 11月 12日 78 本章回顧 ? 回溯法的基本思想： 確定問(wèn)題的解空間 ? 子集樹(shù)問(wèn)題：裝載問(wèn)題、符號(hào)三角形問(wèn)題、 01背包問(wèn)題、最大團(tuán)問(wèn)題 ? 排列樹(shù)問(wèn)題：批處理作業(yè)調(diào)度、 n后問(wèn)題、旅行售貨員問(wèn)題、圓排列問(wèn)題、電路板排列問(wèn)題 ? 其他：圖的 m著色問(wèn)題 找出適當(dāng)?shù)募糁瘮?shù) ? 約束函數(shù) ? 限界函數(shù) 以深度優(yōu)先的方式搜索解空間 ? 遞歸回溯 ? 迭代回溯