一、 迪杰斯特拉算法。
1、 对下图中的有向图，应用dijkstra优化算法计算从源顶点0到其它顶点间最短路径。
2、利用优化的dijkstra算法求解以节点1为源节点到其他各个节点。
的的最短路径。（用贪心法求解，写出具体步骤）
二、 多波段图问题。
1．用动态规划法求下图中从源点0到终点8的最短路径，写出具体步骤。
2．用动态规划法求下图中从源点1到终点12的最短路径，写出具体步骤。
三、 回溯法求0/1背包问题。
1、用回溯法求解0-1背包问题，背包的载重量m=63，物体的重量分别为。
8,16,30,32,35)，物体的价值分别为（16,28,32,45,42），求最优装入背包的物体的价值，具体过程用空间搜索树描述出来。（具体步骤要写出来）
2、 用回溯法求解0-1背包问题，背包的载重量m=51，物体的重量分别为(6,15,26,28,30)，物体的价值分别为（15,30,47,42,45），求最优装入背包的物体和价值，具体过程用空间搜索树描述出来。
四、 回溯法求子集和数问题。
1、 设有子集和数问题的实例w=(5,7,10,12,15,18,20)和m=35。求w中元素之和等于m的所有子集。用回溯法求解此问题，并画出对于这一实例sumofsum算法实际生成的那部分状态空间树。
2、 ．设n=6,w=(w0,w1,w2,w3,w4,w5,w6)=(5,10,12,13,15,18)，m=30，求w中所有元素之和为m的子集和，画出对于这一实例由sumofsub算法实际生成的那部分状态空间树。
五、 动态规划法求0/1背包问题。
1． 设n=3，（w0,w1,w2）=(2,3,5)，（p0,p1,p2）=(1,3,5)，m=8，写出利用动态规划法求解0/1背包问题的递推求解过程。
六、 floyed算法。
1．利用佛罗伊德（floyd）算法求解下图中各个结点之间的最短路径，用d数组存放最短路径值，path数组存放路径。
七、 分治法求最大元和最小元。
求解具体问题（参考上课讲的例子和作业）
八、 贪心法求背包问题（填空）
参考上课讲的例子和作业。
九、 贪心法求带时限作业排序问题（填空）
参考上课讲的例子和作业。
一十、 五大算法的基本思想。
一十一、 回溯法和分支限界法进行比较；分治法和动态规划法比较。（相同和不同）
算法设计与分析复习
12 动态规划算法基本思想 自底向上 全局最优 讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是 适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。最优子结构性质 问题的最优解包含了其子问题的最优解 子问题重叠性质 在用递归算法自顶...
算法设计与分析复习
分治法求全排列。算法描述。分治法求解问题分为三个步骤 分解 将问题分为若干个子问题。解决 递归地求解每个子问题。合并 将每个子问题的解合并成为整个问题的解。现在我们需要求具有n个元素的数组a的全排列。例如 大小为3的数组a a,b,c 为方便起见，我把引号全都省略了，其实应该是a a b c 下同 ...
算法设计与分析复习
一1.循环赛日程表问题的相关叙述。2.算法运行时所需要占用的存储空间有？3.动态规划法的求解步骤。4.解空间树是排列树的问题有。5.分治法的步骤。6.就会场安排问题，贪心法的最佳贪心策略。7.快速排序法基准元素的选取方法。8.满足满m叉树的问题有？9.分支限界法的解题步骤。10.事前分析法相关的影响...