目錄
- 1.回溯算法
1.1 回溯算法簡介
1.2 一般回溯方法 - 2.收費公路重建問題（通過考慮最大值策略焦匈，對可能性空間Xi進行了大幅度裁剪）
2.1 問題描述
2.2 一個例子
2.3 收費公路重建算法
2.4 算法分析 - 3.博弈
3.1 問題描述
3.2 極小極大策略
3.3 極小極大策略用于更復雜的游戲——西洋跳棋、國際象棋
3.4 α-β裁剪 - 4.三著色問題
4.1 問題描述
4.2 問題求解 - 5.八皇后問題
5.1 問題描述
5.2 考慮4皇后問題的解法 - 6.哈密爾頓回路問題
6.1 問題描述
6.2 問題求解
1.回溯算法
1.1 回溯算法簡介
- 像大多數NP難問題一樣，通過窮盡搜索數量巨大但有限多個可能性蛛碌，可以獲得一個解瞻颂。而且，事實上對于所有這些問題都不存在用窮盡搜索之外的方法來解決問題粱侣。所以產生了開發(fā)系統(tǒng)化的搜索技術的需要饭玲，并且希望能夠將搜索空間減少到盡可能小侥祭。
- 回溯法就是一種組織搜索的一般技術。回溯法可以被描述為有組織的窮舉搜索矮冬，它常程竿穑可以避免搜索所有的可能性。
一般適用于求解那些有潛在的大量解胎署，但有限個數的解已經檢查過的問題吆录。
1.2 一般回溯方法
1）一般回溯方法概念
一般回溯方法應用到一類搜索問題中，這類問題的解由滿足事先定義好的某個約束的向量(x1, x2, ..., xi)組成琼牧。這里i是0到n之間的某個整數恢筝，其中n是一個取決于問題闡述的常量。
1-1） 對于一些問題巨坊，i是固定不變的
例如三著色和八皇后問題
1-2） 另一些問題中撬槽，i對于不同的解可能有所不同（可轉換為統(tǒng)一的長度）
- 考慮定義如下的PARTITON問題中的一個變型。給定一個n個整數的集合X={x1, x2, ..., xn}和整數y趾撵，找出和等于y的X的子集Y侄柔。比如說，如果X = {10, 20, 30, 40, 50, 60}和y = 60占调，則有三種不同的解暂题，它們分別是{10, 20, 30}, {20,40}和{60}。設計一個回溯算法求解并不困難究珊。
這個問題可以用另一種方法明確表達薪者，使得解釋一種明顯的長度為n的布爾向量，于是上面的三個解可以用布爾變量表示為{1, 1, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1}剿涮。
2）一般回溯方法的描述
- 解向量中每個xi都屬于一個有限的線序集Xi
- 回溯法按詞典序考慮笛卡爾積X1 × X2 × ... × Xn 言津。
（開始）算法最初從空向量開始，然后選擇X1中最小的元素作為x1幔虏，如果(x1)是一個部分解纺念，算法通過從X2中選擇最小的元素作為x2繼續(xù)，如果(x1想括， x2)是一個部分解陷谱，那么就包括X3中最小的元素，否則x2被置為X2重的下一個元素瑟蜈。
（一般情況）假定算法已經檢測到為(x1烟逊， x2, ..., xj)，它然后考慮向量v = (x1铺根， x2, ..., xj, xj + 1)宪躯，有以下情況：
1.如果v表示問題的最后解，算法記錄下它作為一個解位迂，在僅希望獲得一個解時終止访雪，或者繼續(xù)去找出其他解详瑞。
2.（向前步驟）。如果v表示一個部分解臣缀，算法通過選擇集合Xj+2中的最小元素向前坝橡。
3.如果v既不是最終解，也不是部分解精置，則有兩種子情況
3-1.如果從集合Xj+1中還有其他的元素可選擇计寇，算法將xj + 1置為Xj+1中的下一個元素。
3-2.（回溯步驟）脂倦。如果從集合Xj+1中沒有更多的元素可選擇番宁，算法通過將xj置為Xj中的下一個元素回溯；如果從集合Xj中仍然沒有其他的元素可以選擇赖阻，算法通過將xj-1置為Xj-1中的下一個元素回溯蝶押，依次類推。
3）（獲得一個解）回溯算法的偽代碼描述
- 通常如果需要使用回溯法來搜索一個問題的解政供，可以使用這兩個原型算法之一作為框架播聪，圍繞它設計出專門為具體問題而裁剪出的算法來。
1）遞歸形式
遞歸回溯算法
2）迭代形式
迭代回溯算法
2.收費公路重建問題（通過考慮最大值策略布隔，對可能性空間Xi進行了大幅度裁剪）
2.1 問題描述
根據N(N-1)/2個形如|xi - xj|（i≠j）的距離，重新構造這N個點集稼虎。
在物理學和分子生物學中都有應用衅檀。
重建問題沒有人能夠給出一個算法保證在多項式時間內完成計算。在最壞情形下可能要花費指數時間霎俩。
2.2 一個例子
D是距離集合哀军，并設|D| = N(N-1)/2。
D = {1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10}
可知N = 6.
- step1.（x1 = 0打却，x6 = 10）算法開始置x1 = 0杉适。顯然x6 = 10。
從D中刪除x6 - x1 = 10柳击。
- step2.（x5 = 8）剩下的距離中最大是8猿推，要么x2 = 2，要么x5 = 8捌肴。由對稱性蹬叭，斷定這種選擇是不重要的，可置x5 = 8状知。
從D中刪除x5 - x1 = 8 和 x6 - x5 = 2秽五。
- step3.（x4 = 7或x2 = 3）剩下距離中最大的是7，要么x4 = 7饥悴，要么x2 = 3（特別注意：已經排除了x2 = 1坦喘，如果選定x2 = 1盲再，則|x6 - x1| = 9 > 7）。
step3-1.考慮x4 = 7瓣铣。從D刪除x4 - x1 = 7 答朋， x5 - x4 = 1和 x6 - x4 = 3。
step3-2.考慮x2 = 3坯沪。從D刪除x2 - x1 = 3 绿映， x5 - x2 = 5和 x6 - x2 = 7。
- step4.首先考慮step3-1的情況腐晾，此時x4 = 7叉弦。剩下距離中最大的距離是6，要么x3 = 6藻糖，要么x2 =4淹冰。
step4-1.考慮x3 = 6。那么x4 - x3 1巨柒，不可能樱拴，因為1不再屬于D。繼續(xù)搜索洋满。
step4-2.考慮x2 = 4晶乔。那么x2 - x0 = 4，x5 - x2 = 4牺勾，這也不可以正罢，因為4在D中只出現一次。
回溯考慮step3-2的情況驻民。此時x2 = 3翻具。剩下距離中最大的距離是6，要么x3 = 6回还，要么x2 =4裆泳。
step4-3.考慮x3 = 4。不可能柠硕，該選擇有兩個4工禾，而D中只有一個。
step4-4.考慮x4 = 6仅叫。唯一剩下的選擇是x3 = 5帜篇。正好可以。
收費公路重建問題的決策樹
2.3 收費公路重建算法
算法的核心思路：
- 驅動代碼诫咱，首先確定無爭議的x1笙隙，xN和xN-1
- 回溯步驟：以遞歸方式實現。傳遞同樣的參數以及界Left和Right坎缭，xLeft竟痰，...签钩，xRight是視圖放置的點的x坐標。
驅動代碼
回溯步驟
2.4 算法分析
可以將D作為平衡二叉查找樹保存（代碼需要修改）坏快。如果從未回溯铅檩，那么最多有O(N2)涉及到對D（平衡二叉查找樹）的查找和刪除操作。因此莽鸿，在沒有回溯的情況下昧旨，運行時間為O(N2logN)。
3.博弈
3.1 問題描述
- 考慮計算機用來進行戰(zhàn)略游戲的策略祥得，如西洋跳棋和國際象棋兔沃。以簡單得多的三連游戲棋（tic-tac-toe）來進行表述。
-
三連棋的游戲規(guī)則：
兩人輪流在一有九格方盤上劃加字或圓圈级及，誰先把三個同一記號排成橫線乒疏、直線、斜線饮焦，即是勝者怕吴。
tic-tac-toe
3.2 極小極大策略
- （賦值）更一般的策略是使用一個賦值函數來給一個位置的“好壞”定值。能使計算機獲勝的位置+1县踢；平局得0转绷；使計算機輸棋的位置-1.
- （終端位置）通過考察盤面能夠確定這局輸贏的位置叫做終端位置。
- （極小極大策略）如果一個位置不是終端位置硼啤，那么該位置的值通過遞歸地假設雙方最優(yōu)棋步而確定暇咆。下棋的一方（人）試圖使這個位置的值極小化，而另一方（計算機）卻要使它的值極大丙曙。
FindCompMove計算機選擇具有最大值的一步行棋。
FindHumanMove行棋人在此基礎上找出具有最小值的一步行棋其骄。 - （后繼位置）位置P的后繼位置是通過從P走一步棋可以達到的任何位置Ps亏镰。
如果當在某個位置P計算機要走棋，那么它遞歸地求出所有的后繼位置的值拯爽。計算機選擇具有最大值的一步行棋索抓，這就是P的值。
為了得到任意后繼位置Ps的值毯炮，要遞歸地算出Ps的所有后繼位置的值逼肯，然后選取其中最小的值。這個最小值代表行棋人一方最贊成的應招桃煎。
（draw在英語表示和棋）
- 第1行和第4行直接給和棋篮幢、贏棋賦值；其他情況为迈，則該位置是非終端位置三椿。
- Value應該包括所有可能后繼位置的最大值缺菌，這就是5-13行的事情
回溯在于第8行的Place(Board, i, Comp)和第10行Unplace(Board, i)。 - FindHumanMove遞歸調用FindCompMove搜锰。如果下棋人對一步棋的應招給計算機留下比計算機前面最佳棋步所得到的位置更好的位置伴郁，那么Value和BestMove將被更新。
3.3 極小極大策略用于更復雜的游戲——西洋跳棋蛋叼、國際象棋
- （遞歸深度焊傅、求值函數）搜索到終端節(jié)點的全部棋步不可行，達到某個深度（層）之后只能停止搜索狈涮。遞歸停止出的結點則成為終端結點狐胎。這些終端結點的值由一個估計位置的值的函數計算出來了。
求值函數對于成功是至關重要的薯嗤，因為計算機的行棋選步是基于將這個函數極大化顽爹。最好的計算機下棋程序的求值函數驚人的復雜。 - （置換表）如果已經計算過骆姐，那么一個位置在第二次出現時就不必再重新計算镜粤，將這些值存儲在散列表中。
3.4 α-β裁剪
3.4.1 博弈樹（game tree）
-
博弈樹：假象的棋局中用來給某些某個假設的位置求值的一些遞歸調用的跡玻褪。
- 上圖中幾乎有一半的終端節(jié)點沒有被檢驗肉渴。以下兩個裁剪將證明計算它們的值將不改變樹根的值。
3.4.2 α裁剪
- 如圖所示带射，D不需要求值同规。
-
實現α裁剪的方法，FindCompMove將它的嘗試性的極大值α傳遞給FindHumanMove窟社。如果FindHumanMove的嘗試性的極小值低于這個值券勺，那么FindHumanMove立即返回。
α裁剪
3.4.3 β裁剪
- 如果所示灿里，C不用求值关炼。
-
實現β裁剪的方法，FindHumanMove將它的嘗試性的極小值β傳遞給FindCompMove匣吊。如果FFindCompMove的嘗試性的極大值大于這個值儒拂，那么FindCompMove立即返回。
β裁剪
β裁剪
4.三著色問題
4.1 問題描述
- 給出一個無向圖G = (V, E)色鸳，需要用三種顏色之一為V中的每個頂點著色社痛，三種顏色分別為1, 2, 3，使得沒有兩個鄰接的頂點有同樣的顏色命雀。
- 一種著色可用n元組(c1, c2, ..., cn)來表示蒜哀，使ci ∈ {1, 2, 3}，1 ≤ i ≤ n咏雌。
- 一個n個頂點圖共有3n種可能的著色（合法的和非法的）凡怎，所有可能的著色的集合可以用一棵完全的三叉樹表示校焦，稱為搜索樹。在這棵樹中统倒，從根到葉節(jié)點的每一條路徑代表一種著色指派寨典。（跟n個元素的全排列類似，只不過只有兩種可能房匆，大于和小于的決策樹耸成，參見排序算法總結）
三結點的三著色搜索樹
4.2 問題求解
回溯法求解三著色問題
回溯法的基本特征：
- 結點是用深度優(yōu)先搜索的方法生成
- 不需要存儲整棵搜索樹，只需要存儲根到當前活動結點的路徑
4.2.1 遞歸算法（假設頂點集合是{1, 2, ..., n}）
-
回溯由graphcolor(k)中的for循環(huán)體現浴鸿。
4.2.3 迭代算法
- 內層while循環(huán)實現前進（生成新結點）
-
外層while循環(huán)實現回溯的過程
4.2.4 時間復雜度
最壞情況下生成了O(3n)個結點井氢，對于每個結點，都需要O(n)的時間來檢查岳链。因此花竞，最壞情況為O(n3n)。
5.八皇后問題
5.1 問題描述
- 8皇后問題：如何在8 × 8的國際象棋棋盤上安排8個皇后掸哑，使得沒有兩個皇后能相互攻擊约急？如果兩個皇后處在同一行、同一列或同一條對角線上苗分，則她們能互相攻擊厌蔽。
- n皇后問題：如何在n × n的國際象棋棋盤上安排n個皇后，使得沒有兩個皇后能相互攻擊摔癣？ n ≥ 1奴饮。
5.2 考慮4皇后問題的解法
5.2.1 解空間——搜索空間
- （沒有兩個皇后在同一行）每行上有4個位置，就有44種可能的布局择浊，每種可能的布局可以用一個4分量的向量x = {x1, x2, x3, x4}描述戴卜。
- （沒有兩個皇后在同一行和同一列）搜索空間由44減少到4!。
5.2.2 回溯法求解
- 算法嘗試生成并以深度優(yōu)先方式搜索一棵完全四叉有根樹
樹根對應于沒有放置皇后的情況琢岩；
第一層的結點對應于皇后的第一行的可能放置情況叉瘩；
第二層的結點對應于皇后在第二行的可能放置情況；
依此類推粘捎。 - 合法——表示一個不互相攻擊的4個皇后的放置
部分——表示一個不互相攻擊的少于4個皇后的放置 - xi與xj相互攻擊
同一列——xi = xj
同一對角線——xi - xj = i -j 或 j - i
回溯法求解4皇后問題的搜素樹
6.哈密爾頓回路問題
6.1 問題描述
- 尋找無向圖G=(V, E)中的哈密頓回路。
- 設無向圖G=(V, E)危彩，v1v2...vn是G的一條通路攒磨，若G中每個頂點在該通路中出現且僅出現一次，則稱該通路為哈密頓通路汤徽。若v1=vn娩缰，則稱該通路為哈密爾頓回路。
6.2 問題求解
- 假定G=(V, E)的頂點集為V={0,1,...,n-1}谒府。
- 按照回路中頂點的順序拼坎，用n元向量X=(x0, x1, ..., xn-1)來表示回路中的頂點編號浮毯，其中xi ∈{0, 1, ..., n-1}。
-
用布爾數組c[n][n]來表示圖的鄰接矩陣泰鸡，如果頂點i和j相鄰接债蓝，則c[i][j]為真。則哈密頓回路滿足如下約束：
回溯法步驟：
- step1.把頂點0作為回路中第一個頂點盛龄，搜索與頂點0相鄰接的編號最小的頂點饰迹，作為它的后續(xù)頂點
- step2.假定在搜索過程中已經生成了通路l = x0x1...xi-1
尋找與xi-1相鄰接的并且不屬于l的編號最小的頂點。如果搜索成功余舶，就把這個頂點作為通路中的頂點xi啊鸭，然后繼續(xù)搜索下一個頂點。 - step3.如果不成功匿值，就把l中的xi-1刪除赠制，從xi-1的頂點編號加1的位置開始，繼續(xù)搜索與xi-2相鄰接的并且不屬于l的編號最小的頂點
- step4.當搜索到l中的頂點xn-1時挟憔，如果xn-1與x0相鄰接钟些，則所生成的回路就是一條哈密頓回路；
否則曲楚，把l中的xn-1刪除厘唾，繼續(xù)回溯。最后龙誊，如果在回溯過程中抚垃，l中只剩下一個頂點x0，則表明圖中不存在哈密頓回路趟大。（如果圖中存在一個哈密頓回路鹤树，那么從任何一個頂點出發(fā)都能找到一個，如果回溯到只有一個頂點逊朽，則表明x0與其相鄰接的頂點的所有可能性都常識過了罕伯，都不能形成哈密頓回路，因此必然不存在叽讳。）
6.3 一個示例
