1、概念
回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過(guò)程,主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解,當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí),就“回溯”返回,嘗試別的路徑。
回溯法是一種選優(yōu)搜索法,按選優(yōu)條件向前搜索,以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí),發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo),就退回一步重新選擇,這種走不通就退回再走的技術(shù)為回溯法,而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。
許多復(fù)雜的,規(guī)模較大的問(wèn)題都可以使用回溯法,有“通用解題方法”的美稱。
2、基本思想
在包含問(wèn)題的所有解的解空間樹(shù)中,按照深度優(yōu)先搜索的策略,從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)。當(dāng)探索到某一結(jié)點(diǎn)時(shí),要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解,如果包含,就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去,如果該結(jié)點(diǎn)不包含問(wèn)題的解,則逐層向其祖先結(jié)點(diǎn)回溯。(其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法)。
若用回溯法求問(wèn)題的所有解時(shí),要回溯到根,且根結(jié)點(diǎn)的所有可行的子樹(shù)都要已被搜索遍才結(jié)束。而若使用回溯法求任一個(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ù)避免無(wú)效搜索。
4、算法框架
(1)問(wèn)題框架
設(shè)問(wèn)題的解是一個(gè)n維向量(a1,a2,………,an),約束條件是ai(i=1,2,3,…..,n)之間滿足某種條件,記為f(ai)。
(2)非遞歸回溯框架
(3)遞歸的算法框架
回溯法是對(duì)解空間的深度優(yōu)先搜索,在一般情況下使用遞歸函數(shù)來(lái)實(shí)現(xiàn)回溯法比較簡(jiǎn)單,其中i為搜索的深度,框架如下:
-
回溯算法
+關(guān)注
關(guān)注
0文章
10瀏覽量
6590
原文標(biāo)題:五大常用算法【回溯法】
文章出處:【微信號(hào):xx-cyy,微信公眾號(hào):C語(yǔ)言編程基礎(chǔ)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論