【正文】 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)先的方式搜索解空間 ? 遞歸回溯 ? 迭代回溯 。 Swap(x[i], x[j])。 Backtrack(i+1)。 (cc+a[x[i1]][x[j]] bestc || bestc == NoEdge)) { Swap(x[i], x[j])。 j++) // 搜索子樹(shù) if (a[x[i1]][x[j]] != NoEdge amp。}} else {// 是否可進(jìn)入 x[j]子樹(shù) ? for (int j = i。 j++) bestx[j] = x[j]。 (cc + a[x[n1]][x[n]] + a[x[n]][1] bestc || bestc == NoEdge)) { for (int j = 1。 a[x[n]][1] != NoEdge amp。 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。 2021年 11月 12日 76 問(wèn)題分析 ? 解空間：排列樹(shù) ? 可行性約束函數(shù)： 頂點(diǎn) x[i]與頂點(diǎn) x[i1]之間有邊相連。 ? 輸入 : 無(wú)向連通圖 G=(V, E), 每個(gè)頂點(diǎn)都沒(méi)有到自身的邊。1este)， 1822年指出了此書中的一個(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é)院圖書館中的哈密頓手稿，就有 250本筆記及大量學(xué)術(shù)通信和未發(fā)表論文．愛(ài)爾蘭國(guó)家圖書館還有一部分手稿． 他的研究工作涉及不少領(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日 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。 具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。 要滿足兩個(gè)條件： ，且圖中任意兩點(diǎn)可達(dá) 經(jīng)過(guò)圖（有向圖或無(wú)向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密頓通路。實(shí)際上對(duì)于某些頂點(diǎn)數(shù)不到 100的網(wǎng)絡(luò)，利用現(xiàn)有最好的算法和計(jì)算機(jī)也需要比較荒唐的時(shí)間（比如幾百年）才能確定其是否存在一條這樣的路徑 。哈密頓路徑問(wèn)題在上世紀(jì)七十年代初，終于被證明是“ NP完備”的。比如 A→B, 但B→A 是不允許的。 2021年 11月 12日 70 哈密頓回路 天 文學(xué)家哈密頓 (William Rowan Hamilton) 提出，在一個(gè)有多個(gè)城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點(diǎn)到給定的終點(diǎn)沿 途恰好經(jīng)過(guò)所有其他城市一次的路徑。由于該問(wèn)題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會(huì)產(chǎn)生組合爆炸，它是一個(gè) NP 完全問(wèn)題。應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。因此，回溯法總的時(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)題。 } 2021年 11月 12日 67 復(fù)雜性分析 ?圖 m可著色問(wèn)題的解空間樹(shù)中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是∑mi(0≤i≤n1)。(x[j]==x[k])) return false。j++) if ((a[k][j]==1)amp。 } } bool Color::Ok(int k) // 檢查第 k個(gè)頂點(diǎn)當(dāng)前所選顏色 x[k]的可用性； { for (int j=1。i++) { x[t]=i。 } else for (int i=1。 39。 i=n。 2021年 11月 12日 66 算法描述 void Color::Backtrack(int t) { if (tn) { sum++。 2021年 11月 12日 65 問(wèn)題分析 ? 解向量： (x1, x2, … , xn)表示頂點(diǎn) i所著顏色 x[i] 。 ? 四色定理：任何平面圖都是可以 4著色的。 ? 求一個(gè)圖的色數(shù) m的問(wèn)題稱為圖的 m可著色優(yōu)化問(wèn)題。這個(gè)問(wèn)題是圖的 m可著色判定問(wèn)題。用這些顏色為圖 G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。} } 復(fù)雜度分析 最大團(tuán)問(wèn)題的回溯算法 backtrack所需的計(jì)算時(shí)間為 O(n2n)。} if ( + n i bestn) {// 進(jìn)入右子樹(shù) x[i] = 0。 x[i] = 0。 ++。 break。amp。 j i。} int OK = 1。 bestn = 。 j = n。 ? 上界函數(shù)： 有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹(shù)中找到更大的團(tuán)。 ? U是 G的最大團(tuán)當(dāng)且僅當(dāng) U是 G的最大獨(dú)立集。 ? G的最大獨(dú)立集 ：是 G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。 1 2 4 5 3 2021年 11月 12日 58 ? 空子圖 ：如果 U?V且對(duì)任意 u， v?U有 (u， v)?E，則稱U是 G的空子圖。 ? 團(tuán) ： G的完全子圖 U是 G的團(tuán)當(dāng)且僅當(dāng) U不包含在 G的更大的完全子圖中。 2021年 11月 12日 56 提綱 一、回溯