Approximation Algorithm

Definition / 释义

近似算法：在某些问题（尤其是 NP-难的优化问题）上，不能或不便求出最优解时，改用能在多项式时间内给出“足够好”的解的算法；常用近似比（approximation ratio）来衡量其解与最优解的差距。也可泛指任何产生近似解的算法（不同语境下严格程度不同）。

Pronunciation / 发音

/əˌprɑːksɪˈmeɪʃən ˈælɡəˌrɪðəm/

Examples / 例句

We used an approximation algorithm to get a good solution quickly.
我们使用近似算法来快速得到一个较好的解。

For the traveling salesman problem, an approximation algorithm can provide a route whose cost is guaranteed to be within a known factor of the optimal.
对于旅行商问题，近似算法可以给出一条路线，并保证其成本在最优解的某个已知倍数范围内。

Etymology / 词源

approximation 来自拉丁语 approximare（“靠近、接近”），表示“接近真实值/最优值的过程”。
algorithm 源于阿拉伯数学家花剌子密（Al-Khwarizmi）的名字，经中世纪拉丁化后演变为 algorithm，后来泛指“解决问题的步骤与方法”。合起来即“用于求近似解的方法”。

Related Words / 相关词

• Heuristic
• Optimization
• Approximation Ratio
• NP-hard
• Polynomial-time
• Greedy
• PTAS
• FPTAS

Notable Works / 文学与著作

• Approximation Algorithms（Vijay V. Vazirani）：经典教材，系统介绍近似算法与近似保证。
• The Design of Approximation Algorithms（David P. Williamson & David B. Shmoys）：强调设计方法与证明技巧。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：讨论 NP-难问题背景，常引出近似与启发式思路。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在相关章节中涉及近似算法思想与典型例子。