人工智能算法（Python語言版）PPT第6章-回溯法

提綱回溯法的基本思想n后問題總結引例(1)8-皇后問題QQQQQQQQ

圖的m-著色問題不存在用窮舉搜索之外的方法來解決問題引例(2)0-1背包問題的回溯分析-n=3,w={16,15,15},p={45,25,25},c=30-所有可能的情況vs.減小了的搜索空間cw=16bestp=cp=45cw=15cp=25cw=30bestp=cp=50rp=25rp<bestp減小了的搜索空間

回溯法的基本思想(1)問題的提出-很多問題通過窮舉搜索數(shù)量巨大但有限多個可能性可以獲得問題的解-很多問題不存在用窮舉搜索之外的方法來解決問題的算法-找出問題的解集、回答什么是滿足約束條件的最佳解、……回溯法概述-系統(tǒng)化的搜索，并且希望能將搜索空間盡可能減少-有組織的搜索，常常可以避免搜索所有的可能性-適用于解一些組合數(shù)（解空間）相當大的問題-問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式回溯法的基本思想(2)問題的解空間

-顯約束：對分量xi的取值限定-隱約束：為滿足問題的解而對不同分量之間施加的約束-解空間：解向量滿足顯式約束條件的所有元組；將解空間組織為樹問題狀態(tài)的生成-擴展節(jié)點、活節(jié)點、死節(jié)點-深度優(yōu)先的問題狀態(tài)生成回溯法提出-避免無效搜索、提高效率——利用約束函數(shù)和限界函數(shù)來處死那些實際上不可能產(chǎn)生所需解的活節(jié)點，以減少問題的計算量-

具有限界函數(shù)的深度優(yōu)先生成法——回溯法回溯法的基本思想(3)遍歷子集樹需O(2n)計算時間（最壞）

遍歷排列樹需要O(n!)計算時間（最壞）

backtrack(intt)ift>nthenoutput(x)elsefori←0to1do

x[t]←iif(legal(t))backtrack(t+1)endforbacktrack(t)ift>nthenoutput(x)elsefori←ttondoswap(x[t],x[i])if(legal(t))backtrack(t+1)swap(x[t],x[i])endfor子集樹與排列樹回溯法的基本思想(4)求解思路-確定解空間結構-深度優(yōu)先搜索解空間+剪枝函數(shù)常用剪枝函數(shù)-用約束函數(shù)在擴展節(jié)點處剪去不滿足約束的子樹（問題本身的約束）-用限界函數(shù)剪去得不到最優(yōu)解的子樹（相對于已得到的解）主要特征-不需要存儲整棵搜索樹，只需存儲根到當前擴展節(jié)點的路徑-設h(n)為從根到葉的最長路徑長度-對于子集樹解空間——O(2h(n))

對于排列樹解空間——O((h(n))!)提綱回溯法的基本思想n后問題總結n后問題(1)問題-在n×n格的棋盤上放置彼此不受攻擊的n個皇后-n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上算法思想

-解空間：完全n叉樹-解向量：(x1,x2,…,xn)-每行放一個皇后，x[i]表示皇后i被放在第i行x[i]列，約束：(1)(2)n后問題(2)n皇后問題的回溯算法booleanplace(k)forj=1tokdoif|k?j|=|(x[j]?x[k]|)or|x[j]=x[k]|thenreturnfalsereturntrueendforvoidbacktrack(t)

ift>nthensum←sum+1elsefori=1tondo

x[t]←i

ifplace(t)thenbacktrack(t+1)endfor時間復雜度：O(nn)和蠻力法相比？

初始化：

fori←0tondo

x[i]←0調(diào)用：

backtrack(1)n后問題(3)4-后問題的回溯法求解示例生成子集樹中的27個節(jié)點n后問題(4)4-后問題的蠻力法求解示例

回溯法與蠻力法相比，優(yōu)勢何在？n后問題(5)

當n較小時，蠻力法優(yōu)于回溯法；當n較大時，回溯法優(yōu)于蠻力法；n越大，回溯法的優(yōu)勢越顯著結論：提綱回溯法的基本思想n后問題總結總結(1)回溯法效率分析-

好的約束函數(shù)能顯著地減少所生成的節(jié)點數(shù)

，往往計算量較大

-考慮生成節(jié)點數(shù)與約束函數(shù)計算量之間的折衷重排原理-盡可能減小搜索空間-對于許多問題而言，在搜索試探時選取x[i]