算法分析与设计复习大纲(全)(4)

掌握最小生成树的两种贪心算法：prim算法和kruskal算法（P145-148），给出具体的例子，能够用两种方法画出树的生成过程。

掌握背包问题的贪心算法（P148-151），给出一个具体的例子，能够写出解决问题的过程。习题7-2 问题：求如下背包问题的最优解：有7个物品，价值P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量W=15. 解决方法： 先对物品的单位重量价值按照降序排列 物品重量 物品价值 物品价值/物品重量 1 2 4 5 1 3 7 6 10 18 15 3 5 7 6 5 4.5 3 3 1.67 1 依次把物品放入容量为15的背包，直到背包被装满 1+2+4+5+1=13，前5个物品装入背包，还剩下容量为2，第6个物品只能装入2/3 所以总价值为：6+10+18+15+3+5*2/3=55.3333 第8章 回溯法

了解回溯法的设计思想

设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。 步骤：

确定解向量和分量的取值范围，构造解空间树； 确定剪枝函数；

对解空间树按深度优先搜索，搜索过程中剪枝； 从所有的可能解中确定最优解。

了解可以用回溯法解决的问题：

属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问题，八皇后问题（4皇后问题），批处理作业调度问题。

掌握m颜色图着色判定问题的回溯法算法，并能画出解空间树的搜索过程（P168-170），习题8-4 对图8.14使用回溯法求解图问题，画出生成的搜索空间。

解：图着色问题求解的是满足图着色要求的最小颜色数。对图8.14应该从1、2、3、4……种颜色依次尝试用回溯法判定是否满足M着色的要求。

经搜索，1种和2种颜色均不能满足图着色的要求，3种颜色可以满足图着色要求，搜索过程如下，所以图8.14的着色的最少颜色数应该为3 搜索空间为：

掌握0/1背包问题的回溯算法，并能画出解空间树的搜索过程 掌握图着色问题的回溯算法，并能画出解空间树的搜索过程

第9章 分治限界法

了解分支限界法的设计思想 设计思想：

1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数； 2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；

3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；

4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；

5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。 步骤： 确定解空间树 确定限界函数

按广度优先搜索解空间树，计算限界函数的值，填入PT表

从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。

了解可以使用分支限界法解决的问题：

TSP问题，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1背包问题。 掌握TSP问题的分支限界法 掌握0/1背包问题的分支限界法 掌握批处理作业问题的分支限界法

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计复习大纲(全)(4)在线全文阅读。