算法设计范式

算法设计范式是用于为计算问题构建正确且高效算法的重复出现的高级策略，包括分治法、动态规划、贪心选择以及带剪枝的穷举搜索。

Definition

算法设计范式是解决一类问题的通用模板或策略，其特点是分解问题和组合子解决方案的方式，以及问题必须具备的结构属性才能应用该范式。

Scope

该领域涵盖了独立于任何单一问题领域构建算法的通用技术。它探讨了问题的结构（最优子结构、重叠子问题、贪心选择性质、可分解性）如何提示匹配的策略，以及如何对每种范式的正确性进行推理并分析其运行时间。它不包括实现这些算法的数据结构（在基础数据结构中涵盖）以及任何算法所能达到的复杂性理论限制（在算法复杂性与分析中涵盖）。

Sub-topics

• backtracking and branch and bound
• divide and conquer
• dynamic programming
• greedy algorithms

Core questions

• 问题的何种结构特性使得给定范式适用且正确？
• 如何通过记忆化或表格法将递归分解转化为高效算法？
• 局部最优（贪心）选择何时能导致全局最优解？
• 如何推导基于范式的算法的运行时间，例如通过递推关系？
• 穷举搜索范式如何剪枝搜索空间以在典型实例上保持可行性？

Key concepts

• 分治法
• 递推关系
• 动态规划
• 记忆化和表格法
• 贪心选择和交换论证
• 回溯法
• 分支定界法
• 最优子结构
• 穷举搜索和剪枝

Key theories

最优子结构

当一个最优解可以由其子问题的最优解组装而成时，问题就具有最优子结构；这一性质是动态规划和许多贪心算法的基础。

重叠子问题和记忆化

当递归分解重复访问相同的子问题时，存储每个子问题的解决方案（记忆化或自底向上表格法）将指数级的重复计算减少到多项式时间——这是动态规划的基础。

贪心选择性质

有些问题可以通过重复做出当前看起来最好的选择来获得全局最优解；正确性通常通过交换论证或通过拟阵理论来证明。

Clinical relevance

设计范式是实用软件的工作词汇：分治法是快速排序和信号处理的基础；动态规划为生物信息学中的序列比对和最短路径子程序提供支持；贪心方法驱动调度和数据压缩（霍夫曼编码）；分支定界法是组合优化和运筹学的核心。

History

分治法思想早于计算机出现，但在20世纪60年代随着归并排序和Karatsuba乘法等快速算法的出现而变得核心。Richard Bellman在20世纪50年代引入了动态规划。将范式作为统一视角进行系统性教科书处理，通过Aho、Hopcroft和Ullman的设计与分析教材以及后来的CLRS和Kleinberg-Tardos等著作而成熟。

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos
• Robert Sedgewick

Seminal works

• cormen2009
• kleinberg2006
• sedgewick2011

Frequently asked questions

动态规划和贪心算法有什么区别？

两者都利用最优子结构，但贪心算法在每一步都致力于一个局部最优选择，并且从不重新考虑，而动态规划则考虑并组合所有相关子问题的解决方案。贪心算法在适用时速度更快，但适用于的问题较少。

我如何知道应该使用哪种范式？

查看问题的结构：如果可以分解为独立的子问题，则建议使用分治法；如果存在重叠子问题和最优子结构，则建议使用动态规划；如果存在可证明的贪心选择性质，则建议使用贪心算法；否则，可能需要使用带剪枝的系统搜索（回溯法或分支定界法）。