《算法设计与分析》实验指导书--xin.doc

算法设计与分析实验指导书实验一 递归与分治1、实验目的（1）掌握设计有效算法的分治策略；（2）通过合并排序和快速排序两个示例学习分治策略设计技巧。2、实验要求（1）熟练掌握分治法的基本思想及其应用实现；（2）理解所给出的算法，并对其加以改进。3、实验内容（1）分治法基本思想如果原问题可分割成k个子问题，1=Wi), fi-1,j 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为fv；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是fv-c再加上通过放入第i件物品获得的价值。 这样，可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是fn,w 。实验三 贪心算法1、 实验目的（1）掌握设计贪心算法的基本思想；（2）通过最优装载、单源最短路径实例理解贪心算法设计的策略。2、实验要求（1）熟练掌握贪心算法的基本思想及其应用实现；（2）理解所给出的算法，并对其加以改进。3、实验内容贪心算法：总是作出在当前看来最好的选择，而不考虑对后面的未处理部分这种选择是否合理，并且已有的选择不会改变。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。注意：贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解，如单源最短路经问题，最小生成树问题等；在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。4、实验方法1）最优装载：一批集装箱要装上一艘载重量为 c 的轮船。其中集装箱 i 的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 2）单源最短路径：给定带权有向图G =(V,E)，其中每条边的权是非负实数。给定V中的一个顶点，称为源。要求：计算从源到所有其它各顶点的最短路长度。说明：路的长度是指路上各边权值之和。注意：路长最短不一定边数最少。实验四 回溯法1、 实验目的（1）掌握设计回溯法的基本思想；（2）通过-n后问题、旅行售货员问题理解回溯算法设计的策略。2、实验要求（1）熟练掌握回溯算法的基本思想及其应用实现；（2）理解所给出的算法，并对其加以改进。3、实验内容回溯法：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树；算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。4、实验方法1）n后问题：在88的棋盘上摆放八个皇后；使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上；把八皇后问题扩展到n皇后问题，即在nn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。2）旅行售货员问题：某售货员要到若干城市去推销商品，已知各