算法设计复习：动态规划与分治法要点解析

算法设计复习资料涵盖了多种常见的算法概念和应用，适合深入理解和准备算法相关的考试或学习。以下是一些关键知识点的详细解释： 1. 动态规划法：动态规划是一种解决问题的方法，它具有三个基本要素：最优子结构性质（问题的最优解可以通过其子问题的最优解推导得出）、子问题重叠性质（同一子问题可能会被多次求解，但结果可以被缓存以避免重复计算）和自底向上的求解策略（从最简单的子问题开始，逐步解决更复杂的子问题，最终组合成原问题的解）。子问题相互独立并不是动态规划的必备要素。 2. 排列树：排列树是一种用于表示排列问题的树形数据结构，如n皇后问题（一种典型的回溯算法问题，涉及在n×n棋盘上放置n个皇后，确保任何两个皇后不在同一行、同一列或同一斜线上）。0-1背包问题和旅行商问题的解空间通常不是排列树，因为它们的结构不同。 3. 分治法：这是一种将大问题分解为较小的相同或相似子问题，然后递归地解决这些子问题，并将子问题的解合并为原问题解的策略。选项B错误，因为分治法中的子问题通常相互独立，每个子问题独立于其他子问题。 4. 算法描述：算法可以用自然语言、数学模型、图形（如流程图或状态转换图）以及伪代码等多种方式进行表述。自然语言直观易懂，数学模型精确严谨，图形便于理解，伪代码则便于编程实现。 5. 贪心策略：会议安排问题中，通常采用结束时间早的优先（EEDF，Earliest End Date First）策略，因为这样可以尽早结束会议，但并非所有问题都适用此策略，需视具体情况判断。 6. 旅行商问题：这是一个著名的组合优化问题，具有可行解，解空间由n个城市间的顺序组成，即n元组，且约束条件涉及到邻接矩阵。选项A错误，认为没有可行解是不正确的。 7. Dijkstra算法：这是一种用于求解有向带权图中单源最短路径的算法，不是用于无向图。该算法按距离递增顺序选择节点，不是先求长度最小，而是直到找到终点。选项C错误，选项D错误表述了该方法能够找到最短路径。 8. 分治法特征：分治法要求问题分解成相同或相似的子问题，子问题独立，且子问题的解可以合并。选项A错误，因为子问题可能不同。 9. 渐进上界和下界：渐进上界O()和渐进下界Ω()是复杂性理论中衡量算法效率的标准，分别表示函数增长速度的最大和最小界限。渐进确界θ()表示上界和下界的交集。 10. 贪心法：贪心策略是每一步选择当前状态下最优解，不考虑全局最优。选项A错误，贪心法并不总是追求对以后最有利。 11. 哈夫曼编码：哈夫曼树是根据字符频率自底向上构建的，叶子结点对应字符，通过合并操作形成树。选项C描述了构建过程，选项A、B和D都是正确的描述。 以上知识点总结了算法设计中的一些核心概念和方法，对于准备算法考试或深入理解算法原理非常有帮助。