學(xué)習(xí)電腦信息五大常用算法之四：回溯法

Page3五大常用算法之四：回溯法五大常用算法之四：回溯法1、概念

回溯算法事實(shí)上一個(gè)類(lèi)似枚舉的搜尋嘗試過(guò)程，主要是在搜尋嘗試過(guò)程中找尋問(wèn)題的解，當(dāng)發(fā)覺(jué)已不滿(mǎn)意求解條件時(shí)，就“回溯”返回，嘗試別的路徑。

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

很多困難的，規(guī)模較大的問(wèn)題都可以運(yùn)用回溯法，有“通用解題方法”的美稱(chēng)。2、基本思想

在包含問(wèn)題的全部解的解空間樹(shù)中，根據(jù)深度優(yōu)先搜尋的策略，從根結(jié)點(diǎn)動(dòng)身深度探究解空間樹(shù)。當(dāng)探究到某一結(jié)點(diǎn)時(shí)，要先推斷該結(jié)點(diǎn)是否包含問(wèn)題的解，假如包含，就從該結(jié)點(diǎn)動(dòng)身接著探究下去，假如該結(jié)點(diǎn)不包含問(wèn)題的解，則逐層向其祖先結(jié)點(diǎn)回溯。（其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜尋算法）。

若用回溯法求問(wèn)題的全部解時(shí)，要回溯到根，且根結(jié)點(diǎn)的全部可行的子樹(shù)都要已被搜尋遍才結(jié)束。

而若運(yùn)用回溯法求任一個(gè)解時(shí)，只要搜尋到問(wèn)題的一個(gè)解就可以結(jié)束。3、用回溯法解題的一般步驟：

（1）針對(duì)所給問(wèn)題，確定問(wèn)題的解空間：

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

（2）確定結(jié)點(diǎn)的擴(kuò)展搜尋規(guī)則

（3）以深度優(yōu)先方式搜尋解空間，并在搜尋過(guò)程中用剪枝函數(shù)避開(kāi)無(wú)效搜尋。4、算法框架

（1）問(wèn)題框架

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

（2）非遞歸回溯框架1:inta[n],i;2:初始化數(shù)組a[];3:i=1;4:while(i>0(有路可走)and(未達(dá)到目標(biāo)))//還未回溯到頭5:{6:if(i>n)//搜尋到葉結(jié)點(diǎn)7:{8:搜尋到一個(gè)解，輸出；9:}10:else//處理第i個(gè)元素11:{12:a[i]第一個(gè)可能的值；13:while(a[i]在不滿(mǎn)意約束條件且在搜尋空間內(nèi))14:{15:a[i]下一個(gè)可能的值；16:}17:if(a[i]在搜尋空間內(nèi))18:{19:標(biāo)識(shí)占用的資源；20:i=i+1;//擴(kuò)展下一個(gè)結(jié)點(diǎn)21:}22:else23:{24:清理所占的狀態(tài)空間；//回溯25:i=i–1;26:}27:}

（3）遞歸的算法框架

回溯法是對(duì)解空間的深度優(yōu)先搜尋，在一般狀況下運(yùn)用遞歸函數(shù)來(lái)實(shí)現(xiàn)回溯法比較簡(jiǎn)潔，其中i為搜尋的深度，框架如下：1:inta[n];2:try(inti)3:{4:if(i>n)5:輸出結(jié)果;6:else7:{8:for(j=下界;j<=上界;j=j+1)//枚舉i全部可能的路徑9:{10:if(fun(j))//滿(mǎn)意限界函數(shù)和約束條件11:{12:a[i]=j;13:...//其他操作14:try(i