遞歸回溯

對解空間進行深搜，一般情況下，可用遞歸來實現。

遞歸回溯框架：

1 void Backtrack(int t){ 2 if ( t > n ) Output(x); 3 else{ 4 for (int i = f(n,i); i<= g(n,i) ;i++){ 5 x[t] = h(i); 6 if ( Constraint(t) && Bound(t) ) Backtrack(t+1); 7 } 8 } 9 }

其中，參數t 代表當前的遞歸深度。

t > n ，即算法已經搜索到葉子節點。即遞歸的遞歸出口。輸出可行解x。

f(n,i) g(n,i) 分別代表在當前的遞歸深度下，未搜索子樹的起始編號和結束編號。

h(i)? 代表可選值。

此時，如果滿足 約束函數 和 邊界條件 ，可以進入下一層。

如果不滿足，就進行了剪枝操作。

執行完 for 循環，已經搜索遍當前這一層。返回 t-1 層繼續執行。

當? ?t=1時，若已經測試完所有? x[1] 的 可選值，外層調用就全部結束。

調用一次 Backtrack(1)即可完成整個回溯搜索的過程。

?

例題? leetcode 22

?

轉載于:https://www.cnblogs.com/vector11248/p/10450407.html

總結

以上是生活随笔為你收集整理的回溯法 backtrack的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。