估算法

意义

• 估算法的意义在于解决NP-Hard问题，对于时间复杂度大于多项式复杂度的算法而言，在数据规模相对较小时，可以使用精确算法，当数据规模足够大时，为了解决问题，只能使用估算法获取近似解

近似比率

最小化问题

• 一个算法被称为$\rho-$近似算法，如果对于任何输入，它产生的解c满足： $$ C \leq \rho \cdot C^*$$ 或者写成 $$ \frac{C}{C^*} \leq \rho $$

经典案例————装箱问题

问题定义

• 输入：
  • $n$个物品，每个物品$i$的尺寸为$s_i$，其中$0 < s_i \leq 1$
  • 无限数量的箱子，每个箱子的容量都是1
• 目标：
  • 将所有物品放入箱子中，并使用最少数量的箱子
• 这是一个NP-Hard问题，意味着对于大规模的输入，没有已知的多项式时间算法可以找到最优解。因此，我们通常依赖近似算法来找到一个足够好的解。

近似算法策略

• Next Fit(NF) - “下一个适应"算法
  • 策略：
    • 始终只维护一个“当前打开”的箱子
    • 当新物品到来时，检查它是否能放入当前箱子
    • 如果能，就放进去
    • 如果不能，就关闭当前箱子（以后再也不看了），然后打开一个新箱子，并将物品放入这个新箱子
  • 性能：
    • 近似比率$\rho = 2$。这意味着$NF(I) \leq 2 * OPT(I) - 1$，其中$NF(I)$是NF算法使用的箱子数，$OPT(I)$是最优解的箱子数
    • 缺点：非常“健忘”，可能会留下很多无法利用的小空间。例如，一个物品0.5，一个物品0.6（开新箱），下一个0.5（再开新箱），而最优解只需要两个箱子
• First Fit(FF) - “首次适应”算法
  • 策略：
    • 按编号排序维护所有已打开的箱子
    • 当新物品到来时，从第一个箱子开始检查，将它放入第一个能容纳它的箱子
    • 如果所有已打开的箱子都放不下，就打开一个新箱子，并把物品放进去
  • 性能：
    • 近似比率$\rho \approx 1.7$
    • 有点：比Next Fit更好地利用了空间
• Best Fit(BF) - “最佳适应"算法
  • 策略
    • 当新物品到来时，检查所有已打开的并能容纳它的箱子
    • 将物品放入那个放入后剩余空间最小的箱子内
    • 如果已有的箱子都放不下，打开一个新箱子
  • 性能：
    • 近似比率$\rho = 1.7$

离线算法与在线算法

离线算法

• 在开始处理前已获得了全部的输入数据，可以对所有数据进行分析、排序、预处理，以做出全局最优或近似最优的决策

在线算法

• 按顺序逐个接收输入数据，当接收到某个输入时必须立即做出决策给出输出，不能访问未来的输入数据。一旦做出决策通常是不可撤销的

不可近似性

• 在我们讨论完NP-Hard问题的不可验证性与近似计算后，我们会自然地想到，既然NP-Hard问题不能被精确求解或验证，那么能否在多项式时间内获得一个“较好”地近似呢？或者进一步说，是否所有问题都可以寻找到一个$\rho$，可以在$\rho$内近似求解

TSP问题的近似

严格TSP问题的近似

• 对于TSP问题，有如下定理：
  • 除非$P = NP$，否则对于任意的$k \geq 1$，不存在TSP的k-近似
• 证明：使用反证法，假设存在k-近似算法A，由此可知，Halmition回路问题有多项式时间算法，同时由已知Halmiton问题是多项式问题，那么有$P = NP$
• 由此我们可以认为，TSP问题是不可近似的

欧式空间中TSP问题的近似

• 在欧式空间中，TSP问题中的距离应当满足以下式子： $$ w(u, v) \leq w(u, v) + w(x, v) $$
• 此时TSP问题存在2-近似算法