随机化算法与近似算法

随机化算法和近似算法以牺牲精确性或确定性来换取效率：随机化算法利用随机选择来提高速度或简化操作，而近似算法则为难以精确求解的问题找到可证明的接近最优的解决方案。

Definition

随机化算法在执行过程中进行随机选择，并对其预期运行时间或正确性概率进行分析；近似算法高效运行，并返回在硬优化问题中可证明在最优解的某个因子范围内的解决方案。

Scope

该领域涵盖了放宽对精确、确定性答案要求的算法。它包括具有概率保证的随机化算法（拉斯维加斯算法和蒙特卡洛算法）；针对NP-hard优化问题且具有可证明近似比的近似算法；以及必须在未知未来信息的情况下做出决策，并通过竞争比进行分析的在线算法。这些是应对难处理性和不确定性环境的标准方法，建立在复杂性分析和设计范式之上。

Sub-topics

• approximation algorithms
• online algorithms
• randomized algorithms

Core questions

• 随机化如何提高运行时间、简化性或鲁棒性？
• 拉斯维加斯算法和蒙特卡洛算法的保证有何不同？
• 近似算法的质量如何通过近似比量化？
• 哪些NP-hard问题允许良好的近似，哪些则难以近似？
• 在没有未来信息的情况下做出的在线决策如何进行竞争性评估？

Key concepts

• 随机化算法
• 拉斯维加斯算法和蒙特卡洛算法
• 预期运行时间
• 集中不等式
• 近似比
• 多项式时间近似方案
• 在线算法
• 竞争比

Key theories

随机化提高效率

随机选择可以产生比最佳确定性算法更快或更简单的算法，并对预期时间（拉斯维加斯算法）或错误概率（蒙特卡洛算法）提供保证，分析时常使用集中不等式。

NP-hard问题的近似比

当精确解难以处理时，近似算法提供一个可证明在最优解某个因子（近似比）范围内的解决方案；可实现的近似比表征了问题可近似的程度。

Clinical relevance

这些方法是解决困难和不确定问题的实用工具包：随机化算法推动了密码学中的素性测试、哈希和负载均衡；近似算法为NP-hard的调度、路由、聚类和设施选址问题提供了可用的解决方案；在线算法则模拟了缓存、分页和资源分配等必须实时做出决策的场景。

History

随机化算法在20世纪70年代随着Solovay-Strassen和Rabin素性测试以及Rabin对概率方法的广泛倡导而获得重视。近似算法与20世纪70年代的NP完全性理论一同发展，在线算法的竞争分析由Sleator和Tarjan在20世纪80年代正式提出，共同构成了不精确和概率算法的现代研究。

Key figures

• Rajeev Motwani
• Prabhakar Raghavan
• Vijay Vazirani
• Michael Rabin
• Robert Solovay
• Volker Strassen

Seminal works

• motwani1995
• vazirani2001
• cormen2009

Frequently asked questions

随机化算法因为使用随机性而不可靠吗？

不是。拉斯维加斯算法总是返回正确答案，只是其运行时间有所不同。蒙特卡洛算法可能会出错，但通过重复可以使错误概率任意降低。它们的保证是精确的概率陈述，而非不可预测性。

为什么使用近似算法而不是直接寻找最优解？

对于NP-hard优化问题，对于大型输入，找到精确最优解可能不可行。近似算法在多项式时间内运行，并保证找到一个在最优解已知因子范围内的解决方案，这通常已经足够好，并且比等待精确答案更实用。