回溯算法-课件PPT（精）.ppt

,是一种能避免不必要搜索的穷举式的搜索算法,其基本思想就是穷举搜索。算法思想:采用了一种“走不通就掉头”的思想。搜索时往往有多分支,按某一分支为新的出发点,继续向下探索,当所有可能情况都探索过且都无法到达目标的时候,再回退到上一个出发点,继续探索另一个可能情况,这种不断回头寻找目标的方法称为“回溯法”。搜索的方式主要采用深度优先搜索的方式回溯三要素:1) 解空间:该空包含问题的解2) 约束条件3) 状态树在一个n*n的国际象棋棋盘上放置n个皇后,使得它们中任意2个之间都不互相“攻击”,即任意2个皇后不可在同行、同列、同斜线上。输出N,⑴求N皇后问题的一种放法;⑵求N皇后问题的所有放法分析:N=4时,右图是一组解要素一:解空间题一:N皇后问题一般想法:利用二维数组,用[i,j]确定一个皇后位置!优化:利用约束条件,只需一维数组即可!x:array[1..n] of integer; x[i]:i表示第i行皇后x[i]表示第i行上皇后放第几列x[3,1,4,2]要素二:约束条件不同行:数组x的下标保证不重复不同列:x[i]<>x[j] (i<=I,j<=n;i<>j)不同对角线:abs(x[i]-x[j])<>abs(i-j)要素三:状态树将搜索过程中的每个状态用树的形式表示出来!画出状态树对书写程序有很大帮助!填到第K行时,就与前1~(K-1)行都进行比较Function Place(k:integer):boolean; place:=true; for j←1 to k-1 do if |k-j|=|x[j]-x[k]| or x[j]=x[k] then place:= falseK=0K=1**************回溯**********回溯***********K=3K=2K=4****出解后可以继续刚才的做法过程:进入新一行,该行上按顺序逐个格子尝试,直到能放为止(不冲突、不越界)算法描述:,继续找,直到找到不冲突---- 不冲突then k<n?k+1 k=n? 冲突then 回溯回溯部份:即状态恢复,使其恢复到进入该分支前的状态,继续新的分支x[k]:=0; Dec(k);程序结束条件:一组解:设标志,找到一解后更改标志,以标志做为结束循环的条件所有解:k=0程序实现:回溯算法可用非递归和递归两种方法实现!判断约束函数Function Place(k:integer):boolean; place:=true; for j←1 to k-1 do if |k-j|=|x[j]-x[k]| or x[j]=x[k] then place:= falseNqueens()begin x[1] ← 0 k ← 1while k>0 do beginx[k] ← x[k] +1 while x[k]<=n and (not place(k)) do x[k] ← x[k] +1if x[k]<=n then if k=n then sum ← sum+1elsebegin k ← k+1 x[k] ← 0endelse k ← k-1endend非递归写法:if k=n then print;flag ←false算法描述:,继续找,直到找到不冲突---- 不冲突then k<n?k+1 k=n? 冲突then 回溯Flag ← trueWhile flag doprocedure try(k:byte);procedure try(k:byte);varvar i:byte; i:byte;beginbeginfor i:=1 to n dofor i:=1 to n do{{每层均有每层均有nn种放法种放法}}if place(k) then if place(k) then {{寻找放置皇后的位置寻找放置皇后的位置}}beginbeginx[k]:=i; x[k]:=i; {{放置皇后放置皇后))if k=n the