状态空间明 解空间树 °8°8 根(root):问题的起点 问题状态( problem states):树中结点 ·状态空间( state space):由根结点到其它 结点的所有路径 ·解状态( solution states)S:由根到S的路 径确定了解空间中的一个元组 谷案状态( answer states)S:由根到s的路 径确定了这问题的一个解(即,它满足隐式约 穷举法(枚举法) 穷举法的代价 ·4个皇后各占一行,穷举每一行上 ·穷举问题域的所有解,找到所有最佳解 可能占有的列 减少穷举次数 共有44=256种情况 穷举的变量 ●枚举时,可以排除直观不符合条件 注意穷举的顺序 的情况,减小候选集 减少判断每种情况的时间 ·有4!=24种情况 时间代价最高 ·问题规模n,搜索空间Σ,总搜索时间是: ●最后输出合理的解 指数级时间代价 四后问题求解 八皇后问题的表示馨 回溯算法 棋盘行列、皇后依次编上0,1,,7号 ·A[0.n-1[0.n]表示n×n棋盘上的格 行号从上至下、列号从左到右依次编号为0, 八后问题的全部解向量为(x0,x )。 x表示皇后所处的列数 ·对任何0≤K8,及,有x≠x 状态空间缩小为在8! 可行则进,不行则换 没有两个皇后在同一斜线上(斜率为土1) 换不成则退 重点! 66 状态空间 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 解空间树 z 根（root）：问题的起点 z 问题状态（problem states）：树中结点 z 状态空间（state space）：由根结点到其它 结点的所有路径 z 解状态（solution states）S：由根到S的路 径确定了解空间中的一个元组 z 答案状态（answer states）S：由根到S的路 径确定了这问题的一个解（即，它满足隐式约 束条件） 穷举法（枚举法） z 4个皇后各占一行，穷举每一行上 可能占有的列 z 共有44 ＝ 256种情况 z 枚举时，可以排除直观不符合条件 的情况，减小候选集 z 有4! ＝ 24种情况 z 最后输出合理的解 穷举法的代价 z 穷举问题域的所有解，找到所有最佳解 z 减少穷举次数 z 穷举的变量 z 注意穷举的顺序 z 减少判断每种情况的时间 z 时间代价最高 z 问题规模n，搜索空间Σ，总搜索时间是： z T= |Σ| ×t，O(n!) = O(nn)，O(2n) z 指数级时间代价 四后问题求解 z 回溯算法 可行则进，不行则换 换不成则退 八皇后问题的表示 z 棋盘行列、皇后依次编上0, 1,…，7号 z A[0..n-1][0..n-1] 表示n×n棋盘上的格 z 行号从上至下、列号从左到右依次编号为0, 1,…，n-1 z 八后问题的全部解向量为(x0, x1,…，x7)。 z xi 表示皇后i所处的列数 z 对任何0≤i, j<8，及i≠j，有xi ≠xj z 状态空间缩小为在8! z 没有两个皇后在同一斜线上（斜率为±1 ） z 重点！