回溯( Backtracking)基本原理 2007年9月26日 张铭
回溯算法 1 回溯(Backtracking)基本原理 2007年9月26日 张铭
认识“回溯” 感性认识——皇后问题 解空间树 ■搜索过程 直观分析 原理描述 总体步骤 ■搜索过程 ■实现方式 方式一:递归回溯 方式二:迭代回溯 效率分析 回溯算法
回溯算法 2 认识“回溯” 感性认识——皇后问题 解空间树 搜索过程 直观分析 原理描述 总体步骤 搜索过程 实现方式 方式一：递归回溯 方式二：迭代回溯 效率分析
八皇后问题 问题描述:在国际象棋的8*8格棋盘上放置8 个皇后,使任意两个皇后不在同一行上,不在 同一列上,不在同一条斜角线上 设第1个皇后放在第一行的x1位置,第个皇后 放在第行的x位置,则八皇后问题的一个解可 以表示为一个向量(x1x2…yxg)显然 x1xy…xg是(12…8)的一个排列;所有可 能的向量(可能解)有8!个 回溯算法
回溯算法 3 八皇后问题 问题描述：在国际象棋的8*8格棋盘上放置8 个皇后，使任意两个皇后不在同一行上，不在 同一列上，不在同一条斜角线上。 设第1个皇后放在第一行的x1位置，第i个皇后 放在第i行的xi位置，则八皇后问题的一个解可 以表示为一个向量(x1,x2,...,x8);显然 x1,x2,...x8是(1,2,...,8)的一个排列；所有可 能的向量（可能解）有8!个
八皇后问题的一个解图示 Q Q对应的向量 Q (4,6,8,2,71,35) Q Q 回溯算法
回溯算法 4 八皇后问题的一个解图示 Q Q Q Q Q Q Q Q 对应的向量： (4,6,8,2,7,1,3,5)
四皇后问题及其解空间树 解表示成一个4维向量, (放置列号) Q 搜索空间:4叉树(排列树)
回溯算法 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维向量， （放置列号） 搜索空间：4叉树（排列树）
解空间树 树中的每一个结点确定所求解问题的一个问题状态 ( problem states)。 ■由根结点到其它结点的所有路径则确定了这个问题的 状态空间( state space) ■解状态( solution states)是这样一些问题状态S 对于这些问题状态,由根到s的那条路径确定了这解空 间中的一个元组。 答案状态( answer states)是这样的一些解状态S, 对于这些解状态而言,由根到S的这条路径确定了这问 题的一个解(即,它满足隐式约束条件)。 解空间的树结构称为状态空间树( state space tree) 回溯算法
回溯算法 6 解空间树 树中的每一个结点确定所求解问题的一个问题状态 （problem states）。 由根结点到其它结点的所有路径则确定了这个问题的 状态空间（state space）。 解状态（solution states）是这样一些问题状态S， 对于这些问题状态，由根到S的那条路径确定了这解空 间中的一个元组。 答案状态（answer states）是这样的一些解状态S， 对于这些解状态而言，由根到S的这条路径确定了这问 题的一个解（即，它满足隐式约束条件）。 解空间的树结构称为状态空间树（state space tree）
四皇后问题的解空间树 四皇后问题的状态空间树上共有24个叶 结点(4)就是问题的所有可能解, 树的内部结点代表问题的部分解;例如 36为部分解(X1X2x3)=(312) 结点的编号是按DFs( Deep First Search)方式排列的,其实也就是按回 溯方式遍历搜索的次序 回溯算法
回溯算法 7 四皇后问题的解空间树 四皇后问题的状态空间树上共有24个叶 结点(4!),就是问题的所有可能解， 树的内部结点代表问题的部分解；例如 36为部分解(x1,x2,x3)=(3,1,2) 结点的编号是按DFS（Deep First Search)方式排列的，其实也就是按回 溯方式遍历搜索的次序
直观分析一搜索代价 时间代价 n空间树共有65个结点,24个叶结点,但在搜索过 程中,只遍历了16个结点,其中2个叶结点 如果要找所有解的话,则还要继续搜索下去 ■空间代价 与树的高度有关,而不是和树的总结点数有关 ■回溯算法中,并不需要真正创建一个解空间树 回溯算法
回溯算法 8 直观分析—搜索代价 时间代价 空间树共有65个结点，24个叶结点，但在搜索过 程中，只遍历了16个结点，其中2个叶结点 如果要找所有解的话，则还要继续搜索下去 空间代价 与树的高度有关，而不是和树的总结点数有关 回溯算法中，并不需要真正创建一个解空间树
原理描述一同题的解空间 ■问题的解向量:回溯法希望一个问题的 解能够表示成一个n元式(x1x2…xn)的 形式。 ■显约束:对分量x的取值限定。 隐约束:为满足问题的解而对不同分量 之间施加的约束。 解空间:对于问题的一个实例,解向量 满足显式约束条件的所有多元组,构成 了该实例的一个解空间 回溯算法
回溯算法 9 原理描述—问题的解空间 问题的解向量：回溯法希望一个问题的 解能够表示成一个n元式(x1,x2,…,xn)的 形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量 之间施加的约束。 解空间：对于问题的一个实例，解向量 满足显式约束条件的所有多元组，构成 了该实例的一个解空间
原理描述一生成问题状态的基本方法 扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的结 点称做活结点 死结点:一个所有儿子已经产生的结点称做死结点 ■问题状态生成法: n深度优先:如果对一个扩展结点R,一旦产生了它的一个儿子 c,就把c当做新的扩展结点。在完成对子树C(以C为根的子 树)的穷尽搜索之后,将R重新变成扩展结点,继续生成R的 下一个儿子(如果存在)一回溯法 宽度优先:在一个扩展结点变成死结点之前,它一直是扩展 结点——分支定界法 回溯算法
回溯算法 10 原理描述—生成问题状态的基本方法 扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的结 点称做活结点 死结点:一个所有儿子已经产生的结点称做死结点 问题状态生成法： 深度优先：如果对一个扩展结点R，一旦产生了它的一个儿子 C，就把C当做新的扩展结点。在完成对子树C（以C为根的子 树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的 下一个儿子（如果存在）——回溯法 宽度优先：在一个扩展结点变成死结点之前，它一直是扩展 结点——分支定界法