Backtracking

程度★ 難度★★★

手把青秧插滿田,低頭便見水中天,     

六根清淨方為道,退步原來是向前。《插秧詩》

Backtracking

中文稱作「回溯法」,枚舉多維度數據的方法。把多維度數據看作是一個多維度向量(solution vector),然後運用遞迴依序窮舉各個維度的值,製作出所有可能的數據(solution space),並且在遞迴途中避免枚舉出不正確的數據。

撰寫程式時,可用陣列來實作solution vector的概念。

另外,當我們所需的數據只有唯一一組時,可以讓程式提早結束。

附贈一張圖片。畫了很久。

© 2010 tkcn. All rights reserved.

結合Pruning

回溯法會在遞迴途中避免枚舉出不正確的數據,其意義其實就等同於搜尋樹的pruning技術。

結合Branch and Bound

回溯法可以結合Branching。

回溯法可以結合Bounding。

特色

Backtracking的好處,是在遞迴過程中,能有效的避免枚舉出不正確的數據,省下很多時間。

另外還可以調整維度的順序、每個維度中枚舉值的順序。如果安排得宜,可以更快的找到數據。

這裡是我找到的一些Backtracking題目,不過我還沒有驗證它們是否都是Backtracking問題。

UVa 140 165 193 222 259 291 301 331 399 435 524 539 565 574 598 628 656 732 10624 | 10186 10344 10364 10400 10419 10447 10501 10503 10513 10582 10605 10637

另外還有一些容易被誤認成其他類型,實際上卻可以用Backtracking解決的題目。

UVa 193 129 10160 10802

Enumerate n-Tuples

程度★ 難度★

n-tuple

n-tuple是指n個維度的座標,例如(2, 3, 4)是一個3-tuple,(23, 32, 11, 92)是一個4-tuple。

n-tuple其實就是一個n維向量。要枚舉所有n-tuple,當然可以使用Backtracking囉!

n-tuple這個數學名詞,對大家來說可能比較抽象。下面舉一個實際的範例,如此就不必繼續談論這個抽象的數學名詞了。

範例:枚舉出「數字1到10選擇五次」全部可能的情形

製作一個陣列,用來存放一組可能的情形。

例如solution[0] = 4表示第一個抓到的數字是4,solution[4] = 9表示第五個抓到的數字是9。陣列中不同的格子,就是solution vector當中不同的維度。

遞迴程式碼設計成這樣:

輸出結果會照字典順序排列。附送一張簡圖:

Enumerate Permutations

程度★ 難度★★

Permutation

permutation是「排列」的意思,便是數學課本中「排列組合」的排列。但是這裡並不是要計算排列有多少種,而是實際枚舉出所有的排列:

現在有一個集合,裡面有1到n的數字,列出所有數字的排列,同樣的排列不能重複列出來。例如{1,2,3}所有的排列就是{1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2}、{3,2,1}。

想要枚舉所有排列,可以使用Backtracking!原理跟枚舉所有n-tuple是一樣的,只需要做小小的修改。

依序枚舉每個位置,針對每個位置,試著填入各種數字

一般來說,重複很多次的程式碼,都會用迴圈進行簡化:

依序枚舉每個數字,針對每個數字,試著填入各個位置

另外還有一種作法是生做這樣的:

這也是一個不錯的方法,列出來提供大家參考。多接觸各式各樣的方法,能激發一些創意呢!

字串排列

有個常見的問題是:列出字串abc的所有排列,要依照字典順序列出。其實這就跟剛才介紹的東西大同小異,只要稍加修改程式碼即可。

避免重複排列

若是字串排列的問題改成:列出abb的所有排列,依照字典順序列出。答案應該為abb、aba、baa。不過使用剛剛的程式碼的話,答案卻會變成這樣:

abb
abb
bab
bba
bab
bba

這跟預期的不一樣。會有這種結果,是由於之前的程式有個基本假設:字串中的每個字母都不一樣。儘管出現了一樣的字母,但是程式還是把它當作是不一樣的字母,依舊把所有可能的排列都列出,也就是現在的結果──有一些排列重複出現了。

要解決問題,在枚舉某一個位置的字母時,就必須避免一直填入一樣的字母。如此就可以避免產生重複的排列。

因為輸入的字串由小到大排序過,字母會依照順序出現,所以只要檢查上一個使用過的字母,判斷一不一樣之後,就可以避免枚舉一樣的字母了。

程式碼也可以改寫成這種風格:

另一種資料結構

如果字母重覆出現次數很多次的話,可以用一個128格的陣列,每一格個別存入128個ASCII字元的出現次數。程式碼會簡化成這樣:

UVa 195 441 10098 10063 10776

延伸閱讀:Next Permutation

問題:給一個由英文字母組成的字串。現在以這個字串當中的所有字母,依照字典順序列出所有排列,請找出這個字串所在位置的下一個字串是什麼?

有一個很簡單的方法。我們先製作字母卡,一張卡上有一個英文字母。然後用這些字母卡排出字串。要找出下一個排列,依照人類本能,會先將字串最右邊的字母卡,先拿一些起來,看看能不能利用手上的字母卡,重新拼成下一個字串;若是不行的話,就再多拿一點字母卡起來,看看能不能拼成下一個字串。這是很直觀的想法。詳細的辦法就不多說了。

若你想出了解題的演算法,可以繼續往下看。這裡提供一個不錯的資料結構:令一個 int 陣列 array[] 的第 x 格所存的值,是ASCII碼 'a'+x 這個字母於字串中出現的個數。用這個資料結構來紀錄手上的字母卡有哪些,是最好不過的了,只要加加減減就可以了!打個簡單的比喻,若是題目給定的字串是aabbc,那麼將所有字母卡都拿在手上時, array[0] 就存入 2、array[1] 就存入 2、array[2] 就存入1。當然,一開始的時候就將所有卡片排成aabbc,所以陣列裡面的值都是 0;隨著卡片越拿越多起來,陣列的值也就越加越多了。用這個資料結構寫起程式來會相當的方便!它可以省去排序的麻煩。

有些比較機車的題目,會提到說有些字母卡可以互相代替著用,例如p可以轉一下變成b,w可以轉一下變成m之類的。這個時候就得小心的紀錄可用的字母卡張數了。有個可行的辦法是:若一張字母卡有多種用途,像是p和b通用──當多了一張p或b的字母卡可用時,那麼就在 array['p'-'a'] 和 array['b'-'a'] 的地方同時加一;當少了一張p或b的字母卡可用時,那麼就在 array['p'-'a'] 和 array['b'-'a'] 的地方同時減一。仔細想想看為什麼可行吧!這方法很不錯吧? :p

程式碼就留給大家自行創造吧!這裡是題目。

UVa 146 845

Enumerate Combinations(Enumerate Subsets)

程度★ 難度★

Enumerate Subsets

枚舉子集合。這裡示範:枚舉出{0,1,2,3,4}的所有子集合。

該如何枚舉呢?先觀察平時我們計算子集合總數的方法。{0,1,2,3,4}所有子集合的個數總共2^5個:0可取可不取,有兩種情形、1可取可不取,有兩種情形、...、4可取可不取,有兩種情形。根據乘法原理,總共2*2*2*2*2 = 2^5種情形。

backtracking枚舉數據的概念等同於乘法原理。首先我們要先建立一個陣列,用來當作是一個集合。

其中solution[i] = true時表示這個集合擁有第i個元素(本站文件「Set資料結構: 索引儲存」)。陣列中不同的格子,就是solution vector當中不同的維度。

遞迴程式碼設計成這樣:

輸出結果會照字典順序排列。附送一張簡圖:

另一種資料結構

這裡改用int陣列來當作set的資料結構(本站文件「Set資料結構: 循序儲存」)。儘管solution vector已面目全非、消滅殆盡,但是該遞迴程式碼仍具有backtracking的精神。

任意集合的所有子集合

另一種枚舉法

這個方法並非backtracking,但也是一種很有特色的枚舉方式。請比照程式碼和附圖,自行揣摩一下。

將陣列先排序好,輸出結果就會照字典順序排列。簡圖:

8 Queen Problem

程度★ 難度★★

8 Queen Problem

問題:在8x8的西洋棋棋盤上擺放八隻皇后,讓他們恰好無法互相攻擊對方。

一個非常簡單的想法:每一格都有「放」和「不放」兩種選擇,枚舉所有可能,並避免枚舉出皇后互相攻擊的情形。設計solution vector為8x8的bool陣列,代表一個8x8的棋盤盤面情形。例如solution[0][0] = true表示(0,0)這個位置有放置皇后。

接著要避免枚舉出不可能出現的答案:任一直線、橫線、左右斜線上面只能有一隻皇后。分別建立四個bool陣列,紀錄皇后在各條線上擺放的情形,這個手法很常見,請見程式碼。

以及避免枚舉出不可能出現的答案:最終的棋盤上面不足八隻皇后。

改進

由於一條線必須剛好擺放一隻皇后,故可以以線為單位來遞迴窮舉。重新設計solution vector為一條一維int陣列,solution[0] = 5表示第零個直行上的皇后,擺在第五個位置。

縮成迴圈是一定要的啦!

接著要避免枚舉出不可能出現的答案。

改進

8 Queen Problem的答案是上下、左右、對角線對稱的。排除對稱的情形,可以節省枚舉的時間。這裡不加贅述。

另一種左右斜線判斷方式

比用陣列紀錄還麻煩。自行斟酌。

這裡是練習題。

UVa 167 750 10513 639

Sudoku

程度★ 難度★

數獨

解決方法和8 Queen Problem十分相似。設計solution vector為二維的int陣列,solution[0][0] = 2表示(0,0)的位置填了數字2。

縮成迴圈是一定要的啦!

接著要避免枚舉出不可能出現的答案:直線、橫線、3x3方格內不能有重複的數字。分別建立三個bool陣列,紀錄數字在各地方使用的情形,這個手法很常見,請見程式碼。

再加上原本格子裡就有數字的判斷。

這裡是練習題。

UVa 989 10893 10957

Euclidean Shortest Path

程度★ 難度★★

© 2010 tkcn. All rights reserved.

二維座標平面,兩點之間的最短路徑

在一張地圖上有很多個地點,鄰近的地點有筆直道路相通,我們也知道每一段道路的長度。現在要沿著道路,從一個地點走到另一個地點,請問要怎麼走距離會最短呢?

一條最短的路徑,肯定不會繞圈子的。我們可以使用Backtracking窮舉所有排列,製造出所有可能的路徑。每當生成一條路徑時,就判斷這條路徑是不是歷來最短的路徑,隨時記得歷來最短的路徑是那一條。

pruning的程式碼,除了可以放在遞迴函式一開始的地方,也可以挪到遞迴函式呼叫的前一刻。大家可以視情況,選用直觀易懂的寫法。

很多人會誤認以Backtracking窮舉所有排列,就是圖論中的DFS,然而兩者並沒有直接關係,兩者唯一相似的地方是:Backtracking遇到不合理的解答會馬上回溯,DFS遇到拜訪過的節點會馬上回溯。

結合Bounding

遞迴過程中,如果當下產生的片段路徑,已經超過歷來最短的路徑長度,則可以馬上回溯。堅持遞迴下去,片段路徑只會越變越長,將來仍然是超過歷來最短的路徑長度,根本不可能構成正確解答──不如當下就回溯,及早發現及早治療。

結合Heuristic Bounding

遞迴過程中,如果當下產生的片段路徑,我們預測它延伸到終點之後,鐵定超過歷來最短的路徑長度,則可以馬上回溯。先知先覺,防範未然,少走許多冤枉路。

延伸閱讀

這個問題可以直接使用最短路徑演算法解決,甚至可以使用A*、IDA*解決。不過這已經超出backtracking的範圍了,將以另文介紹。

0/1 Knapsack Problem

程度★ 難度★★★

0/1背包問題

問題:一群各式各樣的物品,重量與價值皆不同。一個背包,有耐重限制。現在要將物品儘量塞進背包裡,令背包裡物品總價值最高。

一個簡單的想法:每個物品都有「要」和「不要」兩種選擇,窮舉所有可能,並避免枚舉出背包超載的情形。設計solution vector為一個一維bool陣列,solution[0] = true表示第零個物品有放進背包,即是set的概念(本站文件「Set資料結構: 索引儲存」)。

檢查背包超載的部分可以修改成更美觀的樣子。

Pruning

各位可嘗試將物品重量排序,再執行backtracking程式碼,看看效率有何不同。

可以使用heuristic bound加快速度,各位不妨想想看。

Inclusion-Exclusion Principle

程度★ 難度★★★

排容原理

類似於枚舉所有子集合,但是每個子集合有正負號之別──奇數個集合的交集為正號、偶數個集合的交集為負號。

舉例:求出1到100當中不可被3或5或8整除的整數有幾個。3、5、8均兩兩互質。

考慮數字之間不互質的一般情形:

另一種實作方法

窮舉所有子集合有兩種窮舉方法,排容原理亦有兩種對應的實作方法。

UVa 10325