北京大学：《数据结构与算法》课程教学资源（实习课件PPT）回溯（Backtracking）基本原理

解空间树 树中的每一个结点确定所求解问题的一个问题状态 ( 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的 下一个儿子（如果存在）——回溯法 „ 宽度优先：在一个扩展结点变成死结点之前，它一直是扩展 结点——分支定界法