认识“回溯” 感性认识—皇后问题 解空间树 搜索过程 回溯( Backtracking)基本原理 直观分析 原理描述 2007年9月26日 ■总体步骤 搜索过程 张铭 实现方式 方式一:递归回溯 方式二:选代回溯 效率分析 八皇后问题 八皇后问题的一个解图示 问题描述:在国际象棋的8*8格棋盘上放置8 个皇后,使任意两个皇后不在同一行上,不在 同一列上,不在同一条斜角线上。 设第1个皇后放在第一行的x1位置,第个皇后 lQ对应的向量 放在第行的x位置,则八皇后问题的一个解可 Q 以表示为一个向量(x1,X2y…X)显然 (4,6,8,2,71,3,5) x1x2y…x8是(1,2灬8)的一个排列;所有可 能的向量(可能解)有8!个 回滴算法 衡算法 四皇后问题及其解空间树 解空间树 解表示成一个4维向量,<X,x2,8,A4> (放量列号 中的每一个结点确定所求解问题的一个问题状态 搜索空间:4又树(排列树) 由根结点到其它结点的所有路径则确定了这个问题的 状态空间( state space 答案状态( answer states)是这样的一些解状态s 题的一个解(即,它满足隐式约束条件) 解空间的树结构称为状态空间树( state space tree) 00的明的9的的的的回溯算法 1 回溯(Backtracking)基本原理 2007年9月26日 张铭 回溯算法 2 认识“回溯” „ 感性认识——皇后问题 „ 解空间树 „ 搜索过程 „ 直观分析 „ 原理描述 „ 总体步骤 „ 搜索过程 „ 实现方式 „ 方式一：递归回溯 „ 方式二：迭代回溯 „ 效率分析 回溯算法 3 八皇后问题 „ 问题描述：在国际象棋的8*8格棋盘上放置8 个皇后，使任意两个皇后不在同一行上，不在 同一列上，不在同一条斜角线上。 „ 设第1个皇后放在第一行的x1位置，第i个皇后 放在第i行的xi 位置，则八皇后问题的一个解可 以表示为一个向量(x1,x2,...,x8);显然 x1,x2,...x8是(1,2,...,8)的一个排列；所有可 能的向量（可能解）有8!个 回溯算法 4 八皇后问题的一个解图示 Q Q Q Q Q Q Q Q 对应的向量： (4,6,8,2,7,1,3,5) 回溯算法 5 四皇后问题及其解空间树 1 2 4 3 5 6 7 4 3 9 8 10 11 12 2 4 4 2 3 14 13 15 16 17 2 3 3 2 4 X1=1 18 20 19 21 22 23 3 4 4 3 1 25 24 26 27 28 1 4 4 1 3 30 29 31 32 33 1 3 3 1 4 2 34 36 35 37 38 39 2 4 4 2 1 41 40 42 43 44 1 4 4 1 2 46 45 47 48 49 1 2 2 1 4 3 50 52 51 53 54 55 2 3 3 2 1 57 56 58 59 60 1 3 3 1 2 62 61 63 64 65 1 2 2 1 3 4 X2=2 X3=3 X4=4 Q Q Q Q „ 解表示成一个4维向量，<x1,x2,x3,x4> （放置列号） „ 搜索空间：4叉树（排列树） 回溯算法 6 解空间树 „ 树中的每一个结点确定所求解问题的一个问题状态 （problem states）。 „ 由根结点到其它结点的所有路径则确定了这个问题的 状态空间（state space）。 „ 解状态（solution states）是这样一些问题状态S， 对于这些问题状态，由根到S的那条路径确定了这解空 间中的一个元组。 „ 答案状态（answer states）是这样的一些解状态S， 对于这些解状态而言，由根到S的这条路径确定了这问 题的一个解（即，它满足隐式约束条件）。 „ 解空间的树结构称为状态空间树（state space tree）