淺談Backtracking演算法與其應用

    一般遞迴是把所有可能的路徑走過，也就是一一把答案枚舉(列舉)出來，然後再檢查答案的是否正確，但一一枚舉會非常耗時，而且常常枚舉出來的數量遠多於所需要的答案，原因在於在遞迴進行到一半的時候，如果該路徑是錯的，還是會不斷往下繼續遞迴，但其實我們可以在發現這條路徑不可能為答案的時候，就不要再往下遞迴下去，這就是Backtracking演算法。

    舉個例子來看：請對"ABCD"這四個字進行排列，我們知道有24(4!)種答案，如果是一般遞迴的算法，一一枚舉所有可能的答案，就會產生AAAA,AAAB,...AADD這種不符合的答案，而且總共產生了64(4^4)種結果，比24大了不少。先來看底下這段程式碼示範如何用Backtracking排列這4個字：

      

圖片來源

    可以發現Backtracking演算法在每次遞迴前都會先檢查答案的可行性，必須確認"到目前為止都是正確"的才會繼續往下遞迴，因此就能避免產生錯誤的答案，以上面的例子來看就少了40個錯誤了答案。
Backtracking整體的架構如下：

    如果今天是解數獨問題，那麼一般遞迴與Backtracking的差異就非常大，假設現在某數獨問題有50個空格要填，那麼一般遞迴最差情況就會產生9^50種可能。反之用Backtracking能避免掉不必要的計算，因為Backtracking每次要填入一個空格的時候，都會檢查哪些數字能填入，然後填入正確的數字後才會往下繼續遞迴，因此假設它在填第10格的時候發現根本沒有數字能填，那麼它就不會在繼續往下遞迴。Backtracking的優點在於當它填完第50格的時候就是一個數獨的解，因為它不會走到錯誤的路，底下是Backtracking在數獨上求解的結構：