算法设计与分析考试重点：动态规划与回溯法

"算法设计与分析考试题自测文档，涵盖算法基础概念、复杂性分析、动态规划、回溯法等相关知识点，以及二分搜索和特定问题的解决策略。" 1. 算法的五大特性是：有穷性（算法必须在有限步骤后终止）、确定性（每一步都有确切的定义，不会出现歧义）、可行性（每一步操作都在可执行的范围内）、零个或多个输入（可以没有输入，也可以有多个输入）、一个或多个输出（算法执行后必须产生至少一个结果）。这些特性确保了算法的有效性和实用性。 2. 算法的复杂性分为时间复杂性和空间复杂性，衡量算法好坏的标准通常是时间复杂度，即算法运行时间随问题规模增长的速度。时间复杂度低的算法通常更优，因为它能更快地解决问题。 3. 动态规划算法适用于那些具有最优子构造性质的问题，即局部最优解能组合成全局最优解。这是动态规划能够通过解决子问题来构建原问题解的基础。 4. 最长公共子序列（LCS）问题，给定两个序列X和Y，{A, B, C, D}是它们的一个LCS，但题目中提供的{BABCD}、{CABCD}和{CADCD}都不是正确的LCS，因为它们不是X和Y的子序列。 5. 回溯法在解决问题时，需要定义解空间并确保它至少包含一个问题的最优解。回溯法通过试探性的构造可能的解并逐步撤销无效的尝试来寻找正确解。 6. 动态规划算法通过分解问题为子问题，先求解子问题，再组合子问题的解以获得原问题的解。这种方法可以避免重复计算，提高效率。 7. 深度优先搜索（DFS）是一种采用递归方式系统搜索问题解的算法，常用于图和树的遍历。 8. 0-1背包问题，使用回溯法的计算时间复杂度为O(n2n)，而动态规划算法的时间复杂度为O(n)，这显示了动态规划在处理这类问题上的优势。 9. 动态规划算法的关键要素是最优子构造（子问题的最优解组合成原问题的最优解）和重叠子问题（许多子问题被重复计算）。 10. 二分搜索算法实际上是一种基于分治策略的算法，而非动态规划法。 二、综合题： 1. 设计动态规划算法的一般步骤包括： - 确定最优解的性质，描述其构造特征。 - 递归地定义最优值，建立子问题到整体问题的关系。 - 自底向上计算最优值，通常通过填充一个表格来实现。 - 根据计算过程中获取的信息，构造出原问题的最优解。 2. Johnson算法用于解决流水作业调度问题，首先将作业分为两类，然后按照特定规则排序，最终组合成最优调度。 3. 解决Johnson算法的具体步骤包括对作业进行分类和排序，然后按照算法规则构建最优调度方案。对于给定的作业和时间，可以通过算法找到最优调度方案并计算其最优值。