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

Question

扩展streetparade的问题,我想问一下随机算法和启发式算法之间有什么区别(如果有的话).

说随机算法实际上是一种启发式算法是正确的吗？

Answer 1

TTBOMK,"随机算法"不是标准术语.然而,"随机算法"可能就是这里所说的.

随机:以某种方式使用随机性.有两种风格:蒙特卡罗算法总是在有限的时间内完成,但不保证最佳解决方案,而拉斯维加斯算法不一定能保证在任何有限的时间内完成,但承诺找到最佳解决方案.(通常它们也需要具有有限的预期运行时间.)常见蒙特卡罗算法的示例:MCMC,模拟退火和Miller-Rabin素性测试.具有随机枢轴选择的Quicksort是拉斯维加斯算法,总是在有限的时间内完成.不使用任何随机性的算法是确定性的.

启发式:无法保证找到正确答案.一种非启发式算法是精确的.

许多启发式方法对输入的"偶然"属性很敏感,这些属性不会影响真正的解决方案,例如在Bin Packing问题的First-Fit启发式中考虑订单项.在这种情况下,它们可以被认为是蒙特卡罗随机算法:您可以随机置换输入并重新运行它们,始终保持您找到的最佳答案.OTOH,其他启发式算法没有这个属性 - 例如,First-Fit-Decreasing启发式算法是确定性的,因为它总是首先按递减的大小顺序对项目进行排序.

如果特定随机算法的可能输出的集合是有限的并且包含真实答案,则运行它足够长的"实际上保证"最终找到它(在某种意义上,未找到它的概率可以任意小,但绝不是0).请注意,启发式输入的某些排列将导致获得确切的答案并非自动的情况 - 在First-Fit的情况下,事实证明这是真的,但这仅在2009年得到证实.

有时可以做出关于随机算法收敛的更强有力的陈述:这些陈述通常沿着"对于任何给定的小阈值d,在t步之后我们将在具有概率f(t,d)的最优解的d内", f(t,d)t和d的递增函数.

Answer 2

展位方法通常用于加快NP完整问题的类型和测试解决方案

1. 随机算法使用随机性

   他们使用所有组合，但不按顺序使用，而是使用各种可能性中的随机组合，希望能更快找到解决方案。实现起来非常容易，并且单次迭代也很快（恒定时间）

2. 启发式算法

   他们不是随机收集组合，而是基于对使用的过程，输入数据集或用法的一些了解。因此，它们将组合的数量显着降低到仅可能是解决方案的组合，并且仅使用但通常使用所有组合直到找到解决方案。

   实现复杂度取决于问题，单次迭代通常要比随机方法慢得多（恒定时间），因此，只有在可能性数量降低到足以实际加速的情况下，才使用启发式算法，因为即使启发式算法的算法复杂度通常很高降低恒定时间有时足够大，甚至可以减慢速度……（以运行时术语）

展位方法可以结合在一起