认识“回溯 99 感性认识——皇后问题 ■解空间树 ■搜索过程 直观分析 ■原理描述 总体步骤 n搜索过程 实现方式 方式一:递归回溯 方式二:迭代回溯 效率分析
11 认识 “回溯 ” ◼ 感性认识——皇后问题 ◼ 解空间树 ◼ 搜索过程 ◼ 直观分析 ◼ 原理描述 ◼ 总体步骤 ◼ 搜索过程 ◼ 实现方式 ◼ 方式一：递归回溯 ◼ 方式二：迭代回溯 ◼ 效率分析
八皇后问题 ■问题描述:在国际象棋的8*8格棋盘上放置8 个皇后,使任意两个皇后不在同一行上,不在 同一列上,不在同一条斜角线上。 n设第1个皇后放在第一行的x1位置,第个皇后 放在第的x位置,则八皇后问题的一个解可 以表示为一个向量(x1X2Xg显然 X 1/2r xg是(128)的一个排列;所有可 能的向量(可能解)有8!个
12 八皇后问题 ◼ 问题描述：在国际象棋的8*8格棋盘上放置8 个皇后，使任意两个皇后不在同一行上，不在 同一列上，不在同一条斜角线上。 ◼ 设第1个皇后放在第一行的x1位置，第i个皇后 放在第i行的xi位置，则八皇后问题的一个解可 以表示为一个向量(x1 ,x2 ,...,x8);显然 x1 ,x2 ,...x8是(1,2,...,8)的一个排列；所有可 能的向量（可能解）有8!个
八皇后问题的一个解图示 Q对应的向量: (4,6,8,2,7,1,35) Q 13
13 八皇后问题的一个解图示 Q Q Q Q Q Q Q Q 对应的向量： (4,6,8,2,7,1,3,5)
四皇后问题及其解空间树 解表示成一个4维向量,<X1,x,3,x> (放置列号) 搜索空间:4叉树(排列树) 2 00@的的0她的国的民8的自国间 14
14 四皇后问题及其解空间树 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叉树（排列树）
解空间树 ■树中的每一个结点确定所求解问题的一个问题状态 ( problem states)。 由根结点到其它结点的所有路径则确定了这个问题的 状态空间( state space)。 解状态( solution states)是这样一些问题状态S, 对于这些问题状态,由根到S的那条路径确定了这解空 间中的一个元组。 答案状态( answer states)是这样的一些解状态S, 对于这些解状态而言,由根到S的这条路径确定了这问 题的一个解(即,它满足隐式约束条件)。 解空间的树结构称为状态空间树( state space tree)
15 解空间树 ◼ 树中的每一个结点确定所求解问题的一个问题状态 （problem states）。 ◼ 由根结点到其它结点的所有路径则确定了这个问题的 状态空间（state space）。 ◼ 解状态（solution states）是这样一些问题状态S， 对于这些问题状态，由根到S的那条路径确定了这解空 间中的一个元组。 ◼ 答案状态（answer states）是这样的一些解状态S， 对于这些解状态而言，由根到S的这条路径确定了这问 题的一个解（即，它满足隐式约束条件）。 ◼ 解空间的树结构称为状态空间树（state space tree）