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

新冠大流行给世界带来了巨大的变化，世界各地的科学家和研究人员都在研制有效的疫苗。他们所做的是从广阔的样本空间中近似收紧可能性的范围，并试图获得一些有效的解决方案。近似值在我们的生活中扮演着重要的角色。以在线送餐为例，我们经常在线订购食物并享受快速送货服务。但是你有没有想过，这些APP的后台运行着什么算法，让快递员能够在更短的时间内到达目的地？答案是近似算法。这类问题就是“旅行商问题”。送餐：旅行商问题的实际应用。本文介绍了近似算法及其对某些标准问题的适用性，以及影响特定算法选择的因素。什么是近似算法？近似算法是一种处理NP完全优化问题的方法，它不能保证最优解。近似算法的目标是在多项式时间内尽可能接近最优值。虽然它不能给出一个精确的最优解，但是可以使问题收敛到最终解的一个近似值。它的目标是满足以下三个关键属性：能够在多项式时间内高效运行；能够给出最优解；并且对每个问题实例都有效。背景数学表达式的求值往往伴随着常数、变量的分析、方程的阶数，可以用来衡量逼近的复杂程度。这样的评估将问题分解为P和NP-hard问题。P问题和NP问题的策略P问题是可以在多项式时间内解决的问题。NP表示nondeterministicpolynomialtime（非确定性多项式时间），NP问题是指在多项式时间内近似验证答案的问题。但现在发现，其中许多问题需要指数级的时间来解决。P和NP策略。真正的争论是P=NP还是P≠NP。之前的一些研究表明两者都是正确的。如果问题是多项式的，则存在多个最优算法。因此，在NP-complete问题中，有两种方法可以找到一个近似最优解，然后选择最合适的算法。如果输入规模较小，则可能适合采用指数运行时间的算法。其次，通过用近似算法代替确定性算法，我们仍然能够在多项式时间内找到接近最优的解。可以从输入大小和近似因子推断出近似算法的复杂度。接下来，我们将使用一些示例来深入探讨如何将这些算法应用于现实世界的问题。划分问题（PartitionProblem）在计算机科学领域，该问题的定义是：给定一组多个正整数X，可以将其划分为元素和相等的两个子集X1和X2，即每个子集的值并且等于另一个子集。例如X={3,4,1,3,3,2,3,2,1}可以拆分为X1={3,3,2,3}和X2={4,2,3,1,1}，两个值之和为11。同理，X={1,3,1,2,1,2}可分为X1={2,1,1,1}和X2={3,2}，两个子集的值之和为5。有趣的是，这并不是唯一的解。X1={1,3,1}和X2={2,1,2}的值也和为5，这说明有几个可能的子集。这是一个NP完全问题，存在一个伪多项式时间动态规划解，可以获得一个近似最优解。方法论和决策步骤现在，我们开始通过将其分解为多个单独的标准问题来分析该问题。这里，我们要找到与多重集的元素和相等的子集，那么问题可以分解为以下两个问题：子集和问题：子集X的元素和等于数W。MultiwayDigitPartitioning：给定一个整数参数W，确定如何将X分成W个相等的子集。逼近算法如上所述，将划分问题分解为多路划分和子集求和问题后，我们可以考虑针对这些问题开发的算法，包括：number到具有最小和的子集。如果数字未按排序方式排列，则其运行时复杂度为O(n)，约为3/2的近似率。其Python伪代码如下：deffind_partition(numbers):"""将可用数字分成两个等和系列。args:numbers：数字的集合，例如整数列表。返回：两个数字列表。"""X=[]Y=[]sum_X=0sum_Y=0forninsorted(numbers,reverse=True):ifsum_X1){intval1=heap.poll();intval2=heap.poll();heap.add(val1-val2);}returnheap.poll();}该算法包含输入集S和参数k。将S划分为k个子集，使得这些子集中的数字之和等于构造所需的输出。该算法包括以下关键步骤：将数字降序排列；用差值替换原来的数字，直到只有一个数字；使用回溯算法完成分区。适用性：该算法假设通过构建二叉树进行分区。每一层代表一对数字，左边的分支表示用差值代替数字，右边的分支表示将差值放在同一个子集中。该算法先通过最大差求解，然后继续寻找更好的近似解。它需要O(n)的空间复杂度，但最坏情况的时间复杂度可能达到O(2^n)。装箱问题装箱问题在现实世界中有很多应用。例如，如何从根本上改善印度的废物管理系统。这个问题可以用垃圾箱包装问题来解决，这有助于当局决定需要多少个垃圾箱来处理x数量的垃圾。集装箱船：包装问题的实际应用。在计算机科学中，这个问题适用于各种内存管理技术。在这个算法中，我们可以通过去除冗余和最小化空间浪费来打包不同形状和大小的对象。例如：给定一个包含n个项目的集合，每个项目的大小为s1,s2,.如果合适，将物品放入箱子，否则打开一个新箱子。看一个例子：物品分别为0.5、0.7、0.5、0.2、0.4、0.2、0.5、0.1、0.6，箱子尺寸为1。基于邻近自适应算法的装箱方案（M=总箱数=6).2.FirstFit：按顺序浏览箱子，在第一个箱子里放新的物品，再开始一个新的箱子，直到放不下为止。举个例子：物品有0.5、0.7、0.5、0.2、0.4、0.2、0.5、0.1、0.6，箱子的尺寸都是1。箱=5)。3.最适合：按顺序浏览箱子并将每个新物品放入最适合的箱子中。如果不合适，则会创建一个新的容器。看一个例子：物品为0.5、0.7、0.5、0.2、0.4、0.2、0.5、0.1、0.6，箱子的尺寸都是1。基于最优匹配法的装箱方案（M=箱子总数=5).这种方法的输出和第一种匹配方法是一样的，但是这种方法的优点是可以比FFD更快的实现，即时间复杂度为O(nlogn)。自然方法：如果我们预先知道所有项目的大小，那么自然的解决方案是首先从大到小排序，然后应用以下启发式：首先匹配降序最佳匹配降序假设相同的示例0.7、0.6、0.5，0.5、0.5、0.4、0.2、0.2、0.1，顺序为0.7、0.6、0.5、0.5、0.5、0.4、0.2、0.2、0.1。优化方法（M=总箱数=4）。