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

《算法设计与分析》实验指导书 实验一? 1、实验目的 （1）掌握设计有效算法的分治策略（2）通过快速排序两个示例学习分治策略设计技巧2、实验要求 （1）熟练掌握分治法的基本思想及其应用实现（2）理解所给出的算法，并对其加以改进。 3、分治法如果原问题可分割成k个子问题，1k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。 算法设计模式如下： Divide-and-Conquer(P) if |P|≤n0 then return(ADHOC(P)) 将P分解为较小的子问题 P1 ,P2 ,...,Pk for i←1 to k 5.??? do yi ← Divide-and-Conquer(Pi)??? 递归解决Pi 6.? T ← MERGE(y1,y2,...,yk)???????????? 合并子问题return(T) 4、实验方法 对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理： 分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。 递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。 实验二? 1、实验目的 （）掌握设计有效算法的 （）通过学习设计技巧2、实验要求 （1）熟练掌握的基本思想及其应用实现（2）理解所给出的算法，并对其加以改进。 3、实验内容 1）找出最优解的性质，并刻划其结构特征。 2）递归地定义最优值。 3）以自底向上的方式计算出最优值。 4）根据计算最优值时得到的信息，构造最优解。 4、实验方法 (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。 结论：2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。 2）0-1背包在件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn对于背包问题，由于计算过程中会出现重叠的，符合动态规划中子问题重叠的性质。同时，如果通过第N次选择得到的是一个最优解，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。 用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值 f[i,j]=max{f[i-1,j-Wi]+Pi (j=Wi), f[i-1,j]} 　　这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f[v-c]再加上通过放入第i件物品获得的价值。 这样，可以自底向上地得出在前件物品中取出若干件放进背包能获得的最大价值，也就是f[,w] 。 实验三?贪心算法 1、? 实验目的 （1）掌握设计 （）通过2、实验要求 （1）熟练掌握的基本思想及其应用实现 （2）理解所给出的算法，并对其加以改进。 3、 2）单源最短路径：给定带权有向图G =(V,E)，其中每条边的权是非负实数。给定V中的一个顶点，称为源。要求：计算从源到所有其它各顶点的最短路长度。 说明：路的长度是指路上各边权值之和。 注意：路长最短不一定边数最少。 实验?回溯法 1、? 实验目的 （1）掌握设计 （）通过--n2、实验要求 （1）熟练掌握的基本思想及其应用实现 （2）理解所给出的算法，并对其加以改进。 3、8×8的棋盘上摆放八个皇后；使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上；把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。