Ch6、回溯法.pdf

: .
第六讲第六讲第六讲 回溯法回溯法

回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问回溯法的基本思想、回溯法的递归流程、用回溯法解决问
题的步骤；注意概念：解空间、可行解、约束函数、限界题的步骤；注意概念：解空间、可行解、约束函数、限界题的步骤；注意概念：解空间、可行解、约束函数、限界
函数。函数。

定和子集问题的回溯算法；定和子集问题的回溯算法；定和子集问题的回溯算法；定和子集问题的回溯算法；定和子集问题的回溯算法；定和子集问题的回溯算法；

n-皇后问题的回溯算法；皇后问题的回溯算法；

Hamilton 回路与旅行商问题的回溯算法；回路与旅行商问题的回溯算法；回路与旅行商问题的回溯算法；

图的顶点着色问题回溯算法；图的顶点着色问题回溯算法；图的顶点着色问题回溯算法；

0-1 背包问题的回溯算法。背包问题的回溯算法。
1 : .
1 回溯法的基本思想回溯法的基本思想回溯法的基本思想
1.1 解空间解空间解空间解空间解空间解空间解空间解空间
回溯法有回溯法有回溯法有 “通用解题法通用解题法通用解题法通用解题法 ”之称。应用回溯法解问题时，首先之称。应用回溯法解问题时，首先
应该明确问题的解空间。一个复杂问题的解决往往由多部分构应该明确问题的解空间。一个复杂问题的解决往往由多部分构
成，即一个大的解决方案可以看作由若干个小决策组成。很多成，即一个大的解决方案可以看作由若干个小决策组成。很多
时候它们构成一个决策序列。解时候它们构成一个决策序列。解时候它们构成一个决策序列。解时候它们构成一个决策序列。解 决一个问题的所有可能的决策决一个问题的所有可能的决策决一个问题的所有可能的决策决一个问题的所有可能的决策决一个问题的所有可能的决策决一个问题的所有可能的决策决一个问题的所有可能的决策决一个问题的所有可能的决策
序列构成该问题的解空间。解空间中满足约束条件的决策序列序列构成该问题的解空间。解空间中满足约束条件的决策序列序列构成该问题的解空间。解空间中满足约束条件的决策序列序列构成该问题的解空间。解空间中满足约束条件的决策序列
称为可行解。一般说来，解任何问题都有一个目标，在约束条称为可行解。一般说来，解任何问题都有一个目标，在约束条
件下使目标达到最优的可行解称为该问题的最优解。在解空间件下使目标达到最优的可行解称为该问题的最优解。在解空间
中，前中，前中，前中，前中，前中，前中，前中，前 k 项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为项决策已经确定的所有决策序列的集合称为 k 定子解定子解定子解定子解定子解定子解
空