罗素曾说：所有精确科学都被近似思想所主宰。本文介绍了近似算法及其对某些标准问题的适用性。

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

以在线食品配送为例，我们经常从网上订购食物，享受快速送达的服务。但你想过这些 app 后端运行的什么算法让快递员在更短时间内抵达目的地吗？答案是近似算法。这类问题就是「旅行商问题」。 本文将介绍近似算法及其对某些标准问题的适用性，以及哪些因素会影响到特定算法的选择。

什么是近似算法？

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

它虽然无法给出精确最优解，但可以将问题收敛到最终解的近似值。其目标满足以下三个关键特性：能够在多项式时间内高效运行；能够给出最优解；对于每个问题实例均有效。

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

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

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

分区问题（Partition Problem）

在计算机科学领域，该问题的定义是：给定多重正整数集 X，它可以被分割为两个元素之和相等的子集 X1 和 X2，即每个子集的数值之和与另一个子集相等。

近似算法

如上所述，将分区问题分解为多路分割与子集和问题后，我们就可以考虑为这些问题而开发的算法，包括： 贪婪数字分割（Greedy number Partitioning） 该算法循环遍历所有数字，将每个数字分配给总和最小的子集。如果数字未以排序方式排列，则其运行时复杂度为 O(n)，近似率约为 3/2。

适用性：该算法可以根据情况进行修改，以便改善运行时复杂度。每一级的首要目标是构建一个分支，将当前数字分配给总和最小的子集。首先通过贪婪数字分割找出总和，然后切换到优化，得到全多项式时间近似解。

Karmarkar-Karp 算法

Karmarkar-Karp 算法指以降序方式排列数字的最大差分方法，该方法将差值替换掉原来的数字不断放进集合中.该算法包含输入集 S 和参数 k。将 S 分割成 k 个子集，使这些子集中的数字总和相等，从而构建期望输出。该算法包含如下关键步骤： 以降序方式排列数字； 用差值替换掉原来的数字，直到只有一个数字； 采用回溯算法，完成分区。

适用性：该算法通过构建二叉树来假设分区。每一级表示一对数字，左侧的分支表示用差值替换数字，右侧的分支表示将差值放置在同一个子集中。该算法先通过最大差分求得解，然后继续寻找更好的近似解。它所需的空间复杂度为 O(n)，但最糟糕的情况下所需的时间复杂度可能会达到 O(2^n)。

装箱问题

装箱问题有多种现实应用。例如，如何从根本上改善印度的垃圾管理系统。这个问题就可以通过装箱问题来解决，帮助当局决定 x 量的垃圾需要多少个垃圾箱。 在计算机科学领域中，该问题可用于多种内存管理技术。在该算法中，我们可以通过去除冗余和最小化空间浪费来包装不同形状和大小的对象。

例如：给定一个包含 n 个项的集合，每个项的大小分别为 s1,s2,..,sn (0<=si<=1, 1<=i<=n)，如何将它们装进最少数量的箱子？

经典方法：

  1. 邻近适应算法 (Next Fit)：查看当前项是否适合当前箱子。如果适合，则将物品放置在箱子里，否则开启一个新的箱子。 2.最先匹配法 (First Fit)：按顺序浏览箱子，在第一个箱中放置新的项，直到放不下再启用新的箱子。 3.最优匹配法 (Best Fit)：按顺序浏览箱子，将每一个新的项放在最适合的箱子里。如果不适合，则创建一个新的箱子。

原文链接：https://medium.com/aryan-gupta18/how-to-decide-suitability-of-approximation-algorithms-d8e45b90e530

内容中包含的图片若涉及版权问题，请及时与我们联系删除