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

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