回溯法“>算法—>回溯法

設(shè)問：某人要從a路口經(jīng)過4個路口（含起始路口和目的路口）到達(dá)b路口，已知該地區(qū)的道路有一個特點：除起點和終點外，每個路口都有三條叉路。請找出一條可行的路線。
首先，我們應(yīng)該分析出我們所能找到的有關(guān)信息：
1、從起始地到目的地一共有4個路口；
2、除起點和終點外，每個路口都有三條叉路；
要解決這一問題，首先我們應(yīng)該將地形圖轉(zhuǎn)換為較規(guī)范的路徑圖，其中路徑圖中的結(jié)點對應(yīng)地圖的路口，路徑圖中的連線對應(yīng)地圖的路；然后嘗試著找出某種規(guī)則進行路的探求。當(dāng)在某個路口走不通時就回頭另找一條新的路，當(dāng)發(fā)現(xiàn)了目標(biāo)地址就可以停止尋找。
從問題的某一種可能情況出發(fā), 搜索所有能達(dá)到的可能情況，然后再以其中的一種可能情況為新的出發(fā)點，繼續(xù)向下探求，這樣就走出了一條“路”。當(dāng)這一條路走到“ 盡頭”的時候, 再倒回上個出發(fā)點, 從另一個可能情況出發(fā), 繼續(xù)搜索。這種不斷“回溯”尋找目標(biāo)的方法, 稱作“回溯法”。
回溯法的基本思想是窮舉搜索。一般適用于尋找解集或找出滿足某些約束條件的最優(yōu)解的問題。這些問題所具有的共性是順序性，即必須先探求第一個步，確定第一步采取的可能值，再探求第二個步采取的可能值，然后是第三步，……，直到達(dá)到目標(biāo)狀態(tài)。
結(jié)合設(shè)問，我們很容易找出問題所涉及到的數(shù)據(jù)與路徑圖之間的對應(yīng)關(guān)系：路口所在的層數(shù)表示探求步數(shù)對應(yīng)的編號，每個路口的分叉表示從該情況出發(fā)所有可能的情況。
在數(shù)據(jù)的具體描述中，為體現(xiàn)探求步驟的順序性，可以將層數(shù)用整數(shù)來表示；為表示每個出發(fā)點的規(guī)律性，我們通常將情況歸納一下，并用順序出現(xiàn)的整數(shù)表示。
對于每個路口而言，其分叉的形式應(yīng)是一致的。因此通常情況下我們用整數(shù)來表示，由于每個路口都有三個分叉，那么我們可以根據(jù)分叉出現(xiàn)的順序從左向右依次用整數(shù)1，2，3進行編號就可以了。
在程序中我們可以用數(shù)組a存放路徑，其中下標(biāo)表示探求的步數(shù)編號，數(shù)組元素a[k]的值表示在第k步所采取的可能值的編號。這樣對路的探求方法都可以用以下的代碼表示：
procedure find (k:integer)； {找第k步的可能性}
begin
if 到目的地 {表示一條路已找出}
then
begin
輸出路線；
結(jié)束探求
end
else
if k<=4
then
for i:=1 to 3 do {窮舉三種可能的方向并記錄下來}
begin
　　　 a[k]:=i；
find(k+1)
end
end；
由此可知，根據(jù)每個結(jié)點探求具有共性這個特點，在實現(xiàn)中我們通常采用遞歸的算法來實現(xiàn)回溯策略。下面給出的是對于該遞歸算法的非遞歸代碼:
begin
a[1]:=1；k:=1； {確定起步的路口號及尋找的初始方向}
while 未到目的地 do
begin
while a[k] 無路可走 do {回溯，返回第K-1個路口，另找一條路}
begin
k:=k-1；
a[k]:=a[k]+1
end；
k:=k+1；a[k]:=1； {設(shè)定從K+1個路口開始尋找的初始方向}
end；
輸出路線；
end；
通過觀察，我們可以發(fā)現(xiàn)實現(xiàn)回溯算法的特性：在解決過程中首先必須要先為問題定義一個解的空間，這個空間必須包含問題的一個解。在搜索路的同時也就產(chǎn)生了新的解空間。在搜索期間的任何時刻，僅保留從起始點到當(dāng)前點的路徑。因此，回溯算法的空間需求為O（從開始節(jié)點起最長路徑的長度）。
回溯的策略是一種常見的策略。它可以避免對規(guī)模很大的候選解進行一次性檢查，因此適用于一些求解規(guī)模很大的問題。在具體實現(xiàn)過程中我們應(yīng)該以找出解題方法與路徑圖對應(yīng)的數(shù)據(jù)關(guān)系為切入口，使用遞歸的算法加以實現(xiàn)。使用回溯策略，我們通常解決自然數(shù)的排列、n皇后問題、迷宮問題、數(shù)的拆分、0/1背包問題、旅行商問題、貨船裝貨和圖形覆蓋正方形等問題。