淺談Backtracking演算法與其應用

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

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

	#include <iostream>
	#include <string>
	using namespace std;
	string str;
	string Ans; // 過程中保存答案用
	bool choosed[100] = {0}; // choosed[i]==1表示編號i已經出現過
	void backtracking(const int &N);
	int main()
	{
	str = "ABCD";
	backtracking(4);
	}
	void backtracking(const int &N) // N表示有N個字
	{
	if (Ans.size() == N) { // 終止條件檢查
	cout << Ans << endl;
	return;
	}
	for (int i = 0; i < N; ++i) {
	if (choosed[i] == 0){ // 如果這個編號還沒出現過(可行性檢查)
	Ans.push_back(str[i]); // 則將它放入Ans
	choosed[i] = 1; // 並且讓choosed[i]變成1,避免下個遞迴選到
	backtracking(N); // 進入下一層遞迴
	Ans.pop_back(); // 將編號i這個字從Ans移除
	choosed[i] = 0; // 並標示成未選過
	}
	}
	}

view raw backtracking1.cpp hosted with ❤ by GitHub

      

圖片來源

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

	void backtracking (int N, int Len)
	{
	if (Len == N) {
	輸出答案;
	return;
	}
	for (可能的數字) {
	if (這數字符合)
	backtracking(N, Len + 1);
	}
	}

view raw backtracking2 hosted with ❤ by GitHub

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

	void backtracking()
	{
	if (填完所有空格) {
	輸出解答;
	return;
	}
	for (int i = 1; i <= 9; ++i) {
	if (i符合規則) {
	將i填入空格;
	backtracking(); // 遞迴下去填下個空格
	將i從空格移除;
	}
	}
	}

view raw backtracking3 hosted with ❤ by GitHub