发布时间 : 星期二 文章大学算法分析与设计复习总结更新完毕开始阅读257cde0a172ded630a1cb698
活动安排： 最优装载：
第8章 回溯法 了解回溯法的设计思想
设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。 步骤：
确定解向量和分量的取值范围，构造解空间树； 确定剪枝函数；
对解空间树按深度优先搜索，搜索过程中剪枝；
从所有的可能解中确定最优解。
了解可以用回溯法解决的问题：
属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问题，八皇后问题（4皇后问题），批处理作业调度问题。
掌握m颜色图着色判定问题的回溯法算法，并能画出解空间树的搜索过程（P168-170），习题8-4
对图8.14使用回溯法求解图问题，画出生成的搜索空间。
解：图着色问题求解的是满足图着色要求的最小颜色数。对图8.14应该从1、2、3、4??种颜色依次尝试用回溯法判定是否满足M着色的要求。
经搜索，1种和2种颜色均不能满足图着色的要求，3种颜色可以满足图着色要求，搜索过程如下，所以图8.14的着色的最少颜色数应该为3 搜索空间为：
掌握n皇后问题的回溯法算法，并能画出解空间树的搜索过程（P173-174）, 自己看书
掌握0/1背包问题的回溯算法，并能画出解空间树的搜索过程（P163-164），习题8-5 自己看书
第9章 分治限界法 了解分支限界法的设计思想 设计思想：
1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数；
2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；
3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；
4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；
5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。 步骤： 确定解空间树 确定限界函数
按广度优先搜索解空间树，计算限界函数的值，填入PT表
从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。
了解可以使用分支限界法解决的问题：
TSP问题，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1背包问题。 掌握任务分配问题的分支限界法（P195-197），习题9-5 掌握0/1背包问题的分支限界法（P184-185），习题9-6 掌握批处理作业问题的分支限界法（P198-200），习题9-7