第8章回溯法
第8章 回溯法
回溯法概述 回溯法可以系统的搜索一个问题的所有解或任 个解 ◇它在包含问题的所有解的解空间树中,按照深度 优先的策略,从根结点岀发搜索解空间树。算法 搜索到某一结点时,如果断定该结点肯定不包含 问题的解,则跳过以该结点为根的子树的搜索, 逐层向其祖先结点回溯 这种以深度优先方式搜索问题的解的方法称为回 溯法
回溯法概述 回溯法可以系统的搜索一个问题的所有解或任一 个解 它在包含问题的所有解的解空间树中，按照深度 优先的策略，从根结点出发搜索解空间树。算法 搜索到某一结点时，如果断定该结点肯定不包含 问题的解，则跳过以该结点为根的子树的搜索， 逐层向其祖先结点回溯 这种以深度优先方式搜索问题的解的方法称为回 溯法
可用回溯法求解的问题 其中的x取自于某个有穷集5,并苴这些解 必须使得某一规范函数P(x1,x)(也称限 界函数)取极值或满足该规范函数条件。 例子:A(1:n)个元素的分类问题 问题的解为n元组; x取自有穷集 规范函数P:A(x)=A(x1+)
可用回溯法求解的问题 问题的解可以用一个n元组(x1 ,…,xn )来表示， 其中的xi取自于某个有穷集Si，并且这些解 必须使得某一规范函数P(x1 ,…,xn )（也称限 界函数）取极值或满足该规范函数条件。 例子：A(1:n)个元素的分类问题 ◼ 问题的解为n元组； ◼ xi取自有穷集； ◼ 规范函数P：A(xi )<=A(xi+1)
问题求解的方法 列出所有候选解,逐个检查是否为所需要的解 理论上,候选解数量有限,并且通过检查所有或部分候 选解能够得到所需解时,上述方法可行 实际中则很少使用,因为候选解的数量通常都非常大 (比如指数级,甚至是大数阶乘),即便采用最快的计 算机也只能解决规模较小的问题。 避免对很大的候选解集合进行完全检查 大大减少问题的求解时间 通常用来求解规模较大的问题
问题求解的方法 硬性处理法 ◼ 列出所有候选解，逐个检查是否为所需要的解 ◼ 理论上，候选解数量有限，并且通过检查所有或部分候 选解能够得到所需解时，上述方法可行 ◼ 实际中则很少使用，因为候选解的数量通常都非常大 （比如指数级，甚至是大数阶乘），即便采用最快的计 算机也只能解决规模较小的问题。 回溯或分枝限界法 ◼ 避免对很大的候选解集合进行完全检查 ◼ 大大减少问题的求解时间 ◼ 通常用来求解规模较大的问题
回溯法思想 o第一步:为问题定义一个状态空间 state space), 这个空间必须至少包含问题的一个解 ◇第步;组织状奩空间以便它能被容易地搜索。典 型的组织方法是图或树 ◇第三步:按深度优先的方法从开始结点进行搜索 开始结点是一个活结点(也是E结点: expansion node 如果能从当前的E结点移动到一个新结点,那么这个新 结点将变成一个活结点和新的E结点,旧的E结点仍是 个活结点。 如果不能移到一个新结点,当前的E结点就“死”了 即不再是一个活结点),那么便只能返回到最近被考 察的活结点(回溯),这个活结点变成了新的E结点。 当我们已绎找到了答案或者回溯尽了所有的活结点时, 搜索过程结束
回溯法思想 第一步：为问题定义一个状态空间(state space)， 这个空间必须至少包含问题的一个解 第二步：组织状态空间以便它能被容易地搜索。典 型的组织方法是图或树 第三步：按深度优先的方法从开始结点进行搜索 ◼ 开始结点是一个活结点（也是 E-结点：expansion node） ◼ 如果能从当前的E-结点移动到一个新结点，那么这个新 结点将变成一个活结点和新的E-结点，旧的E-结点仍是 一个活结点。 ◼ 如果不能移到一个新结点，当前的E-结点就“死”了 （即不再是一个活结点），那么便只能返回到最近被考 察的活结点（回溯），这个活结点变成了新的E-结点。 ◼ 当我们已经找到了答案或者回溯尽了所有的活结点时， 搜索过程结束