12、动态规划算法基本思想（自底向上、全局最优）：讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是：适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。
最优子结构性质（问题的最优解包含了其子问题的最优解）
子问题重叠性质（在用递归算法自顶向下求解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次）
备忘录方法（动态规划算法变形）：用**保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。
13、最优二叉搜索树性质：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。
14、贪心算法（自顶向下、局部最优）：通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择。
贪心选择性质（所求问题的整体最优解可以通过一系列局部最优的选择来达到，是贪心算法与动态规划算法的主要区别）
最有子结构性质（一个问题的最优解包含其子问题的最优解）
15、哈夫曼编码：是广泛用于数据文件压缩的十分有效的编码方法。
16、最短路径：给定一个，其中每条边的权是非负实数。
17、最小生成树性质：用贪心算法设计策略可以设计出构造最小生成树的有效算法。
18、回溯法（盲人爬山、迷宫问题、n后问题）：在解问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。
19、基本思想：从开始结点（根节点）出发，以深度有限方式搜索整个解空间。
20、分枝限界法基本思想：以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
分枝限界法求解目标是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
回溯法求解目标是找出解空间中满足约束条件的所有解。
21、随机化算法基本特征：对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。
随机数在随机化算法设计中扮演着十分重要的角色。
算法设计与分析复习
分治法求全排列。算法描述。分治法求解问题分为三个步骤 分解 将问题分为若干个子问题。解决 递归地求解每个子问题。合并 将每个子问题的解合并成为整个问题的解。现在我们需要求具有n个元素的数组a的全排列。例如 大小为3的数组a a,b,c 为方便起见，我把引号全都省略了，其实应该是a a b c 下同 ...
算法分析与设计复习
一 迪杰斯特拉算法。1 对下图中的有向图，应用dijkstra优化算法计算从源顶点0到其它顶点间最短路径。2 利用优化的dijkstra算法求解以节点1为源节点到其他各个节点。的的最短路径。用贪心法求解，写出具体步骤 二 多波段图问题。1 用动态规划法求下图中从源点0到终点8的最短路径，写出具体步骤...
算法设计与分析复习
一1.循环赛日程表问题的相关叙述。2.算法运行时所需要占用的存储空间有？3.动态规划法的求解步骤。4.解空间树是排列树的问题有。5.分治法的步骤。6.就会场安排问题，贪心法的最佳贪心策略。7.快速排序法基准元素的选取方法。8.满足满m叉树的问题有？9.分支限界法的解题步骤。10.事前分析法相关的影响...