什么是近似算法？它适用于哪些问题？这篇文章给你答案

新冠大流行给世界带来了巨大的改变，全球科学家和研究人员在研制有效的疫苗。他们正在做的就是从广阔的样本空间中近似地收紧可能性范围，并尽力得到一些有效解。近似在我们的生活中发挥了重要作用。

以在线食品配送为例，我们经常从网上订购食物，享受快速送达的服务。但你想过这些 app 后端运行的什么算法让快递员在更短时间内抵达目的地吗？答案是近似算法。这类问题就是「旅行商问题」。

食品配送：旅行商问题的现实应用。

本文将介绍近似算法及其对某些标准问题的适用性，以及哪些因素会影响到特定算法的选择。

什么是近似算法？

近似算法是一种处理优化问题 NP 完全性的方式，它无法确保最优解。近似算法的目标是在多项式时间内尽可能地接近最优值。

它虽然无法给出精确最优解，但可以将问题收敛到最终解的近似值。其目标满足以下三个关键特性：

能够在多项式时间内高效运行；

能够给出最优解；

对于每个问题实例均有效。

背景

数学表达式的评估常伴随常量、变量分析和方程的阶，可用于衡量近似的复杂度。此类评估将问题分解为 P 和 NP 难问题。

P 问题和 NP 问题的策略

P 问题是指可以在多项式时间内求解的问题。

NP 表示不确定性多项式时间（nondeterministic polynomial time），NP 问题是指在多项式时间内近似验证答案的问题。但目前人们发现，很多此类问题需要指数时间才能求解。

本文转载自网络，原文链接：https://www.toutiao.com/i6910420083563086349/
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！