A2 A1 A B3 A2 A1 B2 C2 B1 C1
A
跳马问题
4. 从C1出发，可以有三条路径，选择D1。 但到了D1以后，我们无路可走且D1也不 是最终目标点，因此，选择D1是错误的， D3 B3 我们退回C1重新选择D2。同样D2也是错 B2 C2 误的。再回到C1选择D3。D3只可以到E1， A2 但E1也是错误的。返回D3后，没有其他 C1 A1 B1 选择，说明D3也是错误的，再回到C1。 A 此时C1不再有其他选择，故C1也是错误 的，退回B1，选择C2进行尝试。
x
path:array[1..m] of integer; 其中，path[i]：表示第i个节点所走的方向
方向t，下一步的位置就是 (x+dx[t], y+dy[t])。
跳马问题
约束条件：
不越界： (x + dx[i] <= n) and (y + dy[i] > 0) and (y + dy[i] <= n)
回溯
Backtracking
回溯 N皇后问题 跳马问题 迷宫问题 图的着色问题 0-1背包问题 装载问题 批处理作业调度 填数问题 组合输出问题 算24点问题 ACM应用
学习要点
掌握回溯的概念 掌握经典问题的回溯解决方法 掌握回溯与其它方法的异同
回溯法
有许多问题，当需要找出它的解集或者要求回答什么 解是满足某些约束条件的最佳解时，往往要使用回溯 法。 ► 回溯法的基本做法是搜索，或是一种组织得井井有条 的，能避免不必要搜索的穷举式搜索法。这种方法适 用于解一些组合数相当大的问题。 ► 回溯法在问题的解空间树中，按深度优先策略，从根 结点出发搜索解空间树。算法搜索至解空间树的任意 一点时，先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对该结点为根的子树的搜索，逐层向 其祖先结点回溯；否则，进入该子树，继续按深度优 先策略搜索。
跳马问题
分析： 按题意，马每一步可以有4种走法！
搜索过程： 1. 当马一开始位于左下角的时候，根据规 则，它只有两条线路可以选择（另外两 条超出棋盘的范围），我们无法预知该 走哪条，故任意选择一条，到达A1。 2.当到达A1点后，又有三条线路可以 选 择，于是再任意选择一条，到达B1。 3.从B1再出发，又有两条线路可以选择， 先选一条，到达C1。
注意：同一个问题可以有多种表示，有些表示方法更简单， 所需表示的状态空间更小（存储量少，搜索方法简单）。
n=3时的0-1背包问题用完全二叉树表示的解空间
生成问题状态的基本方法
► ► ► ►
► ►
扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的节点称 做活结点 死结点:一个所有儿子已经产生的结点称做死结点 深度优先的问题状态生成法：如果对一个扩展结点R，一旦 产生了它的一个儿子C，就把C当做新的扩展结点。在完成 对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成 扩展结点，继续生成R的下一个儿子（如果存在） 宽度优先的问题状态生成法：在一个扩展结点变成死结点 之前，它一直是扩展结点 回溯法：为了避免生成那些不可能产生最佳解的问题状态， 要不断地利用限界函数(bounding function)来处死那些实 际上不可能产生所需解的活结点，以减少问题的计算量。 具有限界函数的深度优先生成法称为回溯法
回溯部份： 即状态恢复，使其恢复到进 入该分支前的状态，继续新的 分支 x[k]:=0; Dec(k);
程序实现： 回溯算法可用非递归和递归两种方法实现！
N皇后问题
非递归写法： 算法描述： Nqueens() 1. 产生一种新放法 begin 2. 冲突，继续找，直到找到不冲 Flag ← true x[1] ← 0 突----不超范围 3. if 不冲突 then k<nk+1 k←1 k=n一组解 while k>0 do While flag do 4. if 冲突 then 回溯 begin x[k] ← x[k] +1 while x[k]<=n and (not place(k)) do x[k] ← x[k] +1 if x[k]<=n then if k=n then sum ← sum+1 if k=n then print;flag ←false else begin k ← k+1 x[k] ← 0 end else k ← k-1 end end
{每层均有n种放法} {寻找放置皇后的位置}
{放置皇后) {８个皇后都放置好,输出} {若只想找一组解，halt} {继续递归放置下一个皇后}
end;
跳马问题
在n×m棋盘上有一中国象棋中的马： 1. 马走日字； 2. 马只能往右走。 请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走 到右上角（n，m）。 输入：9 5 输出：(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)
K=1
K=2
* * *** * *
回溯
*
*
出解后 可以继 续刚才 的做法
K=3
* * * * ** * * * * * * * * * * *
回溯
*
*
* *
*
K=4
* *
*
N皇后问题
程序结束条件： 一组解：设标志，找到一解后更改标志，以标志做为结束循环的条 件所有解：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:= false
N皇后问题
在一个n*n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都 不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上。 输出N，⑴求N皇后问题的一种放法；
⑵求N皇后问题的所有放法
分析： N=4时，右图是一组解
要素一： 解空间
一般想法：利用二维数组，用[i,j]确定一个皇后位置！
优化：利用约束条件，只需一维数组即可！ x:array[1..n] of integer; x[i]：i表示第i行皇后 x[i]表示第i行上皇后放第几列
迭代回溯
采用树的非递归深度优先遍历算法，可将回溯法表示为一个非 递归迭代过程。
void iterativeBacktrack () { int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} } else t--; } }
►
回溯法
回溯算法是所有搜索算法中最为基本的一种算法,是一 种能避免不必要搜索的穷举式的搜索算法，其基本思想 就是穷举搜索。 算法思想： 采用了一种“走不通就掉头”的思想。搜索时往往有多分支， 按某一分支为新的出发点，继续向下探索，当所有可能情况都 探索过且都无法到达目标的时候，再回退到上一个出发点，继 续探索另一个可能情况，这种不断回头寻找目标的方法称为 “回溯法”。
N皇后问题
递归写法： procedure try(k:byte); var i:byte; begin for i:=1 to n do if place(k) then begin x[k]:=i; if k=n then print else try(k+1); end;
分析：状态恢复（回溯）在什 么地方实现？
要素三：状态树
将搜索过程中的每个状态用树的形式表示出来！ 画出状态树对书写程序有很大帮助！
K=0
过程：进入新一行， 该行上按顺序逐个 格子尝试，直到能 放为止（不冲突、 不越界）
N皇后问题
* **
算法描述： 1. 产生一种新放法 2. 冲突，继续找，直到找到不冲 突----不超范围 3. if 不冲突 then k<nk+1 k=n一组解 4. if 冲突 then 回溯
D2 E1 D1
5. 从C2出发，有四条路径可以选择，选择 D4，从D4出发又有两条路径，选择E1错 误，返回D4选择E2，从E2出发有两条路 径，先选择F1错误，返回E2选择B，而B 恰好是我们要到达的目标点，至此，一 条路径查找成功。
B3 A2 B2 C2 A1 B1 D4 E2
BAE1 F1来自马问题④③ ② ①
⑤
⑤ ⑥
④
② ① ③
Path[5]:=1
④
⑤ ⑥
⑤ ⑥
⑦
⑤
⑤
跳马问题
跳马问题（非递归）
Horse() begin path[1] ← 0，k ← 1，x ←1，y ←1 while (x<>m) and (y<>n) do begin path[k] ←path[k] +1 while (x + dx[i] <= n) and (y + dy[i] > 0) and (y + dy[i] <= n) and (path[k]<=4) do path[k] ← path[k] +1 if path[k]<=4 then {在4种走法中找到不越界的走法} begin x ←x+dx[i]，y ←y+dy[i] if (x<>m) and (y<>n) then print else begin k ← k+1 path[k] ← 0 end end else path[k] ← 0，k ← k-1 end end