随机算法和启发式算法的区别

Question

扩展 question of streetparade 的问题，我想问一下随机算法和启发式算法之间有什么区别，如果有的话。

可以说随机算法实际上是启发式算法的一种类型吗？

- orestis21

Answer 1

据我所知，“随机算法”不是标准术语，而“随机化算法”是标准术语，这可能是本文的意思。

随机化算法：某种程度上使用了随机性。有两种类型：蒙特卡罗算法总是在有限时间内完成，但不能保证最优解；而拉斯维加斯算法不一定保证在有限时间内完成，但承诺找到最优解（通常也需要有有限期望运行时间）。常见的蒙特卡罗算法包括MCMC、模拟退火和Miller-Rabin素性测试。具有随机枢轴选择的快速排序是一种拉斯维加斯算法，总是在有限时间内完成。不使用任何随机性的算法称为确定性算法。

启发式算法：不能保证找到正确答案。非启发式算法为精确算法。

许多启发式算法对输入的“偶然”属性很敏感，这些属性不影响真正的解决方案，例如装箱问题中考虑项目顺序的首次适合启发式算法。在这种情况下，它们可以被视为蒙特卡罗随机化算法：您可以随机排列输入并重新运行它们，始终保留找到的最佳答案。另一方面，其他启发式算法没有这种属性，例如首次适合减少启发式算法是确定性的，因为它总是首先按照项目大小顺序排序。

如果特定随机化算法的可能输出集有限且包含正确答案，则运行足够长时间“几乎保证”最终找到它（在未找到它的概率可以被任意小但永远不为0的情况下）。请注意，并非自动情况下，启发式算法输入的某些排列将导致获得精确答案 - 在首次适合问题的情况下，事实证明这是正确的，但这只是在2009年被证明的。

有时可以对随机化算法的收敛性做出更强的陈述：通常是“对于任何给定的小阈值d，在t步之后，我们将以概率f（t，d）接近最优解”，其中f（t，d）是t和d的递增函数。

- j_random_hacker

---

你提到确定性算法，这让我更加困惑。难道“确定性”和“精确”的算法不是同一回事吗？ - orestis21

可以采用确定性启发式策略。例如，用于装箱问题的首次递减启发式策略就是确定性的。因为对于相同的输入，它总是会产生相同的输出。但是它并不是精确的，因为它可能无法找到最优解。 - j_random_hacker

这条评论非常有启发性。那么我们可以说我们有确定性-随机和精确-启发式两种偶极子吗？ - orestis21

是的，你可以这样做 - 我的回答中第二和第三段就是这个意思 ;) - j_random_hacker

Answer 2

Booth方法通常用于加速NP完全问题的生成和测试解决方案。

1. 随机算法使用随机性

   它们使用所有组合，但不按顺序使用，而是从整个可能性范围中选择随机组合，希望更快地找到解决方案。实现快速简便，单次迭代也很快（常数时间）。

2. 启发式算法

   它们并非基于随机选择组合，而是基于对使用过程、输入数据集或用途的某些知识进行选择。因此，它们将组合的数量显着降低到只有那些可能是解决方案的组合，并仅使用这些组合，但通常使用所有这些组合，直到找到解决方案为止。

   实现复杂度取决于问题，单次迭代通常比随机方法慢得多（常数时间），因此只有在可能性数量足够减少以使实际加速可见时才会使用启发式，即使启发式算法复杂度通常要低得多，有时常数时间也足够大，甚至会使事情变慢...（在运行时间方面）

可以将Booth方法组合在一起使用。

- Spektre

---

这个答案并不完全准确。两者都不仅适用于NP完全问题。例如，快速排序使用随机枢轴选择，Welzl算法，随机梯度下降等。启发式算法也不一定比随机化算法慢。 - IVlad

@IVlad 是的，我知道，但我从来没有写过它们只是为了那个目的...但加上词“通常”不会有坏处。速度大约是单次迭代恒定时间（我从未看到比随机方法更小的启发式恒定时间）。 - Spektre

@IVlad已经稍微改写了一下文本。如果您知道更好的改写方式，请随意编辑，我的英语技能有些生疏。 - Spektre

是的，NP难度与这个问题无关。 - David Eisenstat