四皇后问题的解空间树 直观分析一搜索代价 四皇后问题的状态空间树上共有24个叶 时间代价 结点(4)就是问题的所有可能解 空间树共有65个结点,24个叶结点,但在搜紫过 树的内部结点代表问题的部分解;例如 程中,只遍历了16个绪点,其中2个叶结点 36为部分解(x1X2X3)=(312) 如果要找所有解的话,则还要繼续搜紫下去 ■结点的编号是按DFs( Deep First ■空间代价 Search)方式排列的,其实也就是按回 与树的高度有关,而不是和树的总结点数有关 溯方式遍历搜索的次序 回溯算法中,并不需要真正创建一个解空间树 原理描述一问题的解空间 原理描述一生成问题状态的基本方法 ■问题的解向量:回溯法希望一个问题的 扩展结点:个正在产生儿子的结点称为扩展结点 解能够表示成一个n元式(x1x2y…Xn)的 活结点:一个自身已生成但其儿子还没有全部生成的结 形式。 点称做活结点 显约束:对分量x的取值限定 死结点:一个所有儿子已经产生的结点称做死结点 问题状态生成法 ■隐约束:为满足问题的解而对不同分量 间施加的约束。 c,就把c当做新的扩展结点。在完成对子树c(以c为根的子 ■解空间:对于问题的一个实例,解向量 满足显式约束条件的所有多元组,构成 宽度优先:在一个扩展结点变成死结点之前,它一直是扩晨 站点—分支定界法 了该实例的一个解空间。 回滴算法 原理描述一回溯法的基本思想 结点分支判定条件: 基本思想: 满足约束条件-分支扩张解向量 (1)针对所给问题,定义问题的解空间 不满足约束条件,回溯到该结点的父结点 (2)确定易于搜家的解空间结构 ■结点状态:动态生成 )以源度优先方式搜索解空间,并在搜索过程中 三种: 常用剪枝函数 a尚未访问 用约束函数在扩展结点处剪去不满足约束的子树; b正在访问该结点为根的子树(活动结点、扩展 结点) c该结点为根的子树遍历完成 ■递归回溯vs选代回溯 存储:当前路径回溯算法 7 四皇后问题的解空间树 „ 四皇后问题的状态空间树上共有24个叶 结点(4!),就是问题的所有可能解， „ 树的内部结点代表问题的部分解；例如 36为部分解(x1,x2,x3)=(3,1,2) „ 结点的编号是按DFS（Deep First Search)方式排列的，其实也就是按回 溯方式遍历搜索的次序 回溯算法 8 直观分析—搜索代价 „ 时间代价 „ 空间树共有65个结点，24个叶结点，但在搜索过 程中，只遍历了16个结点，其中2个叶结点 „ 如果要找所有解的话，则还要继续搜索下去 „ 空间代价 „ 与树的高度有关，而不是和树的总结点数有关 „ 回溯算法中，并不需要真正创建一个解空间树 回溯算法 9 原理描述—问题的解空间 „ 问题的解向量：回溯法希望一个问题的 解能够表示成一个n元式(x1,x2,…,xn)的 形式。 „ 显约束：对分量xi 的取值限定。 „ 隐约束：为满足问题的解而对不同分量 之间施加的约束。 „ 解空间：对于问题的一个实例，解向量 满足显式约束条件的所有多元组，构成 了该实例的一个解空间。 回溯算法 10 原理描述—生成问题状态的基本方法 „ 扩展结点:一个正在产生儿子的结点称为扩展结点 „ 活结点:一个自身已生成但其儿子还没有全部生成的结 点称做活结点 „ 死结点:一个所有儿子已经产生的结点称做死结点 „ 问题状态生成法： „ 深度优先：如果对一个扩展结点R，一旦产生了它的一个儿子 C，就把C当做新的扩展结点。在完成对子树C（以C为根的子 树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的 下一个儿子（如果存在）——回溯法 „ 宽度优先：在一个扩展结点变成死结点之前，它一直是扩展 结点——分支定界法 回溯算法 11 „ 结点分支判定条件： 满足约束条件---分支扩张解向量 不满足约束条件，回溯到该结点的父结点 „ 结点状态：动态生成 三种： a 尚未访问 b 正在访问该结点为根的子树（活动结点、扩展 结点） c 该结点为根的子树遍历完成 „ 存储：当前路径 回溯算法 12 原理描述—回溯法的基本思想 „ 基本思想： „ (1)针对所给问题，定义问题的解空间； „ (2)确定易于搜索的解空间结构； „ (3)以深度优先方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索。 „ 常用剪枝函数 „ 用约束函数在扩展结点处剪去不满足约束的子树； „ 对于优化问题，还可以用限界函数(Bounding Function)处死那些实际上不可能产生所需解的活 结点，也就是剪去得不到最优解的子树。 „ 递归回溯 vs 迭代回溯