一、状态空间树——描述问题解空间的树形结构
- 问题状态：树中每个结点。
- 解状态：若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态。
- 答案状态：若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态。
- 最优答案结点：如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优值的最优答案结点。
二、穷举法
- 使用深度优先或广度优先搜索方法，检查状态空间树中每个问题状态；
- 如果是解状态则用判定函数判定它是否是答案结点；
- 对于最优化问题，搜索过程中还需对每个答案结点计算其目标函数值，记录下其中最优者。
——这种遍历状态空间树的求解方法是问题求解的穷举法。
回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。
三、回溯法
采用深度优先产生状态空间树的结点，并使用剪枝函数的方法称为——回溯法。
- 在求解的过程中，以深度优先方式逐个生成状态空间树中结点，求问题的可行解或最优解。
- 为提高搜索效率，在搜索过程中用约束函数和限界函数（统称剪枝函数）来剪去不必要搜索的子树，减少问题求解所需实际生成的状态空间树结点数，从而避免无效搜索。
剪枝函数（约束函数、限界函数）——可以剪去不必要搜索的子树，压缩问题求解所需要实际生成的状态空间树的结点。
- 约束函数——剪去不含答案状态（可行解）的子树
- 限界函数——剪去不含最优答案结点（最优解）的子树
约束函数（显式约束、隐式约束）
-
显示约束——规定了所有可能的元组，组成问题的候选解集（解空间）
- 排列树——用于确定n个元素的排列满足某些性质的状态空间树，一般有n!个叶结点（解状态）。
- 子集树——从n个元素的集合中找出满足某些性质的子集的状态空间树，一般有2^n个解状态。
-
隐式约束——给出了判定一个候选解是否为可行解的条件。
回溯法和分支限界法都是通过搜索问题的状态空间树求解。
四、蒙特卡洛方法
用蒙特卡罗（Monte Carlo）方法估计回溯法处理实例时，实际生成的结点数：
- 在状态空间树中,从根开始随机选择一条路径(x0,x1,…,xn-1);
- 假定搜索树中这条随机选出的路径上，代表部分向量(x0,x1,…,xk-1)的结点X处不受限制的孩子数目,和其他路径上与X同层的的结点不受限制的孩子数目一样，都是mk;
- 则可以估计整个状态空间树上实际生成的结点数为: m=1+m0+m0m1+m0m1m2+…
五、n-皇后问题
- 算法思想和程序实现
- 显式约束、隐式约束条件，显式约束对应的状态空间树
- Monte Carlo算法估计实际生成的状态空间树结点数
- 补充题（蒙特卡罗方法）
六、子集和数（画出状态空间树）
- （可变长度解、固定长度解）对应的状态空间树不同（P183-184）
- 约束函数定义
- 课后习题8-2（固定长度解元组）
七、图的着色——四色定理（四种颜色可对地图着色）
- 以深度优先方式生成状态空间树中的结点，寻找所有答案结点，即m-着色方案。
- 搜索中使用约束函数剪去不可能包含答案结点的分枝。
- 对给定的无向图G和m，列出图中结点所有可能的m-着色方案。
总时间复杂度O(nm^n)
八、哈密顿环——课后习题8-10
连通图G=(V,E)中的一个回路，经过图中每个顶点，且只经过一次。
一个哈密顿环就是从某个结点v0开始，沿着图G的n条边环行的一条路径(v0,v1,…,vn-1,vn)。
- 除v0=vn外，路径上其余结点各不相同。
- (vi,vi+1) ∈E (0≤i<n)。
- 它访问图中每个结点且仅访问一次，最后返回开始结点。
京公网安备 11010502036488号