#94 演算法的 Backtracking 策略

 Backtracking 是一種演算法的策略,可用來解決三種面向的問題,分別是 Decision problem, Optimization problem, 以及 Enumeration problem.有關 Optimization problem 在前面的文章裡已經談過不少,這裡不多說明.一個 Decision problem 可能會有至少一個或一個以上的解答,這種問題我們通常只要找一個可用的解答.Enumeration problem 和 Optimization problem 蠻相近,就是要將所有解答找出來.舉個例子,之前講過的老鼠走迷宮是一種問題,如果我們要找一條可行的路,那麼老鼠走迷宮將是 Decision problem.如果我們要找出一條最短的路,此時便是 Optimization problem.如果要將所有可行的路找出來,這便是 Enumeration problem.不同的問題需要不同的解決策略.Backtracking 就這麼巧地可以用來做為這三種問題的解決策略.

以西洋棋裡 n-Queen 問題來說明,一般以 n = 8 為市面上較為熱門的題目,現在我們把 input size 縮小一點,將 n=4. 而棋盤和其中一個可行的解答如下:

Source: https://www.geeksforgeeks.org/backtracking-introduction/

n-Queen 問題的解決策略如果用最直覺的暴力法來做,其解法如下

1. 列出所有 Queen 的排列座標,例如

    Answer candidate 1: (0,0) (0,1) (0,2) (0,3)

    Answer candidate 2: (0,0) (0,1) (0,2) (1,3)

    Answer candidate 3: (0,0) (0,1) (0,2) (2,3)

    Answer candidate 4: (0,0) (0,1) (0,2) (3,3)

    Answer candidate 5: (0,0) (0,1) (1,2) (0,3)

    .... 以此類推, 一共有 4x4x4x4 = 256 種位置.

2. 然後將每一個候選答案放到一個檢查器.這個檢查器就是題目要求的,要讓每個皇后所在的位置不會影響到其他的皇后.這個檢查器要執行的程式碼就是問題本身所給出的限制.你我都知道,暴力法簡單粗暴,保證一定讓你能找到答案,但不保證能快速找到答案.這個問題的 "限制" 本身就是一個有點複雜的運算了.如果你忘了西洋棋的皇后走法,你需要複習一下才能知道這裡所說有點複雜運算的意思了.

如果是用 Backtracking 的策略,該怎麼做呢 ?

Backtracking 的策略在我看來和暴力法是有一點接近的.只是差別在於 Backtracking 不會一開始將所有可能列出來,然後再進行對每個輸入一一地檢查.Backtracking 的策略是在產生所有可能的排序方式過程中,就直接檢查了.如果在過程中不符合 "限制" 時,則中斷這條路,然後跳到下一組排列來做.

以上述的答案候選為例子:

一開始,第一個皇后放在 (0,0),然後試著將第二個皇后放在 (0,1),執行檢查器,這樣檢查器會回傳 false,因為棋盤上同一行只能有一個皇后.於是,後面答案候選裡面只要是 (0,0) (0,1) 開頭的組合便可跳過.前面兩個皇后的位置已經不合法了,所以後面的皇后也不用浪費時間檢查.若以程式的角度來看,某一層次的 for loop 將可以整個跳過去而不執行.所以,下一個要檢查的便是從 (0,0) (1,1) 開頭的答案. 

以上的過程的解題思考就是 Backtracking.

看到這裡,雖然我們沒有寫出細節的程式碼,但我相信你能感受到 Backtracking 的解題策略的精神是什麼了.Backtracking 適合用在需要 recursion 來解決的問題.在我們試著將所有的可能答案窮舉出來的過程中,就執行著 "檢查器",一旦發現檢查器不通過,就直接跳開這一個層次的答案,直接轉往下一個層次,這就是 Backtracking 能夠省出時間的方式.上述的 n-Queen 是一個常見的例子,Sudoku 也是一個常見的例子. 我相信在你的工作中 Backtracking 能派上用場的時機點是很多的.

底下的程式碼是我小徒弟在數個月前練習解決 Sudoku 題目的程式碼,其解決策略是 Backtracking.

Share:

0 意見:

張貼留言