Backtracking

backtracking

中文稱做「回溯法」,窮舉多維度數據的方法,可以想作是多維度的Exhaustive Search。

大意是:把多維度數據看做是是一個多維向量(solution vector),然後運用遞迴依序遞迴窮舉各個維度的值,製作出所有可能的數據(solution space),並且在遞迴途中避免列舉出不正確的數據。

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

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

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

結合pruning

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

結合branch and bound

回溯法可以結合branching。

回溯法可以結合bounding。

特色

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

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

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

UVa 140 165 193 222 259 291 301 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

Enumerate all n-tuples

Enumerate all n-tuples

列舉重複排列。這裡示範:列舉出「數字1到10選擇五次」全部可能的情形。

製作一個陣列,用來存放一組可能的排列(數據)。

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

遞迴程式碼設計成這樣:

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

Permutation

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}。

permutation的問題可以使用backtracking的技術來解決!如果不懂backtracking也沒關係,暫且繼續看下去吧。細嚼慢嚥,一定可以融會貫通的!

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

一般來說,permutation的程式碼都會長成這樣的格式:

permutation的問題都可以使用這段程式碼來解決。而且這支程式,是以字典順序來列舉出所有排列。所以它真的很有用,不妨參考看看。

permutation是一種簡單又容易理解的問題。「Programming Challenges」這本書在教導backtracking的概念時,就用了permutation來當做入門的例子。如果有人想要教導backtracking的程式碼要怎麼撰寫,以permutation當做範例會是個不錯的選擇。

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

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

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

為了講解方便,以下的文章以一開始提到的方法當作基準。

字串排列

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

程式碼改寫成這樣會更清楚:

避免重複排列

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

abb
abb
bab
bba
bab
bba

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

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

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

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

另一種資料結構

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

這裡枚舉一些permutation的題目。

UVa 195 441 10098 10063 10776

Next Permutation

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 all subsets

Enumerate all 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

0/1 Knapsack Problem

0/1背包問題

問題:將一群各式各樣的物品儘量塞進背包裡,令背包裡物品總價值最高。

這個問題當數值範圍不大時,可用Dynamic Programming快速的解決掉。可以參考上面幾篇文章。

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

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

Pruning

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

Inclusion-Exclusion Principle

排容原理

類似於列舉所有子集合(本站文件「Backtracking─Enumerate All Subsets」),但是每個子集合有正負號之別──奇數個集合的交集為正號、偶數個集合的交集為負號。

舉例:求出1到100當中可被3或5或8整除的整數,且除數均兩兩互質。

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

另一種實作方法

列舉所有子集合有兩種窮舉方法,排容原理亦有兩種對應的實作方法。此方法並非backtracking,故不贅述。

UVa 10325