五大常用算法之回溯法

1、概念

回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。

許多復(fù)雜的，規(guī)模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。

2、基本思想

在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點時，要先判斷該結(jié)點是否包含問題的解，如果包含，就從該結(jié)點出發(fā)繼續(xù)探索下去，如果該結(jié)點不包含問題的解，則逐層向其祖先結(jié)點回溯。（其實回溯法就是對隱式圖的深度優(yōu)先搜索算法）。

若用回溯法求問題的所有解時，要回溯到根，且根結(jié)點的所有可行的子樹都要已被搜索遍才結(jié)束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束。

3、用回溯法解題的一般步驟：

（1）針對所給問題，確定問題的解空間：

首先應(yīng)明確定義問題的解空間，問題的解空間應(yīng)至少包含問題的一個（最優(yōu)）解。

（2）確定結(jié)點的擴展搜索規(guī)則。

（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

4、算法框架

（1）問題框架

設(shè)問題的解是一個n維向量(a1,a2,………,an),約束條件是ai(i=1,2,3,…..,n)之間滿足某種條件，記為f(ai)。

（2）非遞歸回溯框架

(3）遞歸的算法框架

回溯法是對解空間的深度優(yōu)先搜索，在一般情況下使用遞歸函數(shù)來實現(xiàn)回溯法比較簡單，其中i為搜索的深度，框架如下：