扩展streetparade 的问题，我想问一下随机算法和启发式算法之间有什么区别（如果有的话）。
说随机算法实际上是一种启发式算法是否正确？
问问题
9545 次
2 回答
9
TTBOMK，“随机算法”不是一个标准术语。然而，“随机算法”是，这可能就是这里的意思。
随机化：以某种方式使用随机性。有两种风格：蒙特卡洛算法总是在有限时间内完成，但不保证最佳解决方案，而拉斯维加斯算法不一定保证在任何有限时间内完成，但承诺找到最佳解决方案。（通常还要求它们具有有限的预期运行时间。）常见的蒙特卡罗算法示例：MCMC、模拟退火和 Miller-Rabin 素数测试。具有随机枢轴选择的快速排序是一种拉斯维加斯算法，总是在有限时间内完成。不使用任何随机性的算法是确定性的。
启发式：不保证找到正确的答案。非启发式算法是精确的。
许多启发式方法对不影响真实解决方案的输入的“附带”属性很敏感，例如在装箱问题的 First-Fit 启发式方法中考虑了订单项。在这种情况下，它们可以被认为是蒙特卡洛随机算法：您可以随机排列输入并重新运行它们，始终保持您找到的最佳答案。OTOH，其他启发式方法没有这个属性——例如，First-Fit-Decreasing 启发式方法是确定性的，因为它总是首先按尺寸递减的顺序对项目进行排序。
如果特定随机算法的可能输出集是有限的并且包含真实答案，那么运行它足够长的时间“实际上可以保证”最终找到它（从某种意义上说，找不到它的概率可以任意小，但绝不是 0)。请注意，启发式输入的某些排列并不会自动导致获得准确答案——在 First-Fit 的情况下，事实证明这是正确的，但这仅在 2009 年得到证明。
有时可以对随机算法的收敛性做出更强有力的陈述：这些通常类似于“对于任何给定的小阈值 d，经过 t 步后，我们将以概率 f(t, d) 处于最优解的 d 范围内”，其中f(t, d) 是 t 和 d 的递增函数。
于 2015-01-22T10:18:25.473 回答
7
Booth 方法通常用于加速生成和测试NP 完全问题的解决方案
随机算法使用随机性
他们使用所有组合，但不是按顺序使用，而是使用各种可能性中的随机组合，希望尽快找到解决方案。实现快速简单，单次迭代也很快（恒定时间）
启发式算法
他们不是随机选择组合，而是基于使用的流程、输入数据集或使用的一些知识。因此，他们将组合的数量显着降低到只有那些可能是解决方案的组合，并且只使用那些但通常是所有组合，直到找到解决方案。
实现复杂性取决于问题，单次迭代通常比随机方法（恒定时间）慢得多，因此仅当可能性的数量降低到足以看到实际加速时才使用启发式算法，因为即使启发式算法的复杂性通常很多有时较低的常数时间足够大，甚至可以减慢速度……（在运行时方面）
展位方式可以组合在一起
于 2015-01-22T09:27:19.903 回答