網頁

2014年3月11日 星期二

淺談Backtracking演算法與其應用

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

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

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

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

沒有留言:

張貼留言