随机算法和启发式算法之间的区别
Difference between a stochastic and a heuristic algorithm
扩展question of streetparade，我想问一下随机算法和启发式算法之间有什么区别，如果有的话。
说随机算法实际上是一种启发式算法对吗？
Booth 方法通常用于加速生成和测试 NP 完全问题的解决方案
随机算法使用随机性
他们使用所有组合但不按顺序使用，而是使用来自所有可能性范围的随机组合，希望尽快找到解决方案。实现快速简单，单次迭代也很快（常数时间）
启发式算法
他们不是随机选择组合，而是基于对使用的过程、输入数据集或用法的一些了解。因此，他们将组合的数量显着减少到只有那些可能是解决方案的组合，并且只使用那些但通常是所有组合，直到找到解决方案。
实施复杂性取决于问题，单次迭代通常比随机方法（恒定时间）慢得多，因此仅当可能性的数量降低到足以使实际加速可见时才使用启发式方法，因为即使算法复杂度启发式算法通常要低得多，有时常数时间足够大，甚至可以减慢速度……（在运行时方面）
展位方式可以组合在一起
TTBOMK，"stochastic algorithm" 不是标准术语。然而，"Randomized algorithm" 可能就是这里的意思。
Randomized: 以某种方式使用随机性。有两种风格：Monte Carlo 算法总是在限定时间内完成，但不保证最优解，而 Las Vegas 算法不一定保证在任何有限时间内完成，但承诺找到最佳解决方案。 （通常它们也需要有一个有限的 expected 运行 时间。）常见 Monte Carlo 算法的示例：MCMC、模拟退火和 Miller-Rabin 素性测试.具有随机枢轴选择的快速排序是一种总是在有限时间内完成的拉斯维加斯算法。不使用任何随机性的算法是 确定性.
启发式：不保证找到正确答案。非启发式算法是 exact.
许多启发式算法对输入的 "incidental" 属性很敏感，这些属性不会影响真正的解决方案，例如装箱问题的 First-Fit 启发式算法中考虑了订单项。在这种情况下，它们可以被认为是 Monte Carlo 随机算法：您可以随机排列输入并重新运行它们，始终保持找到的最佳答案。 OTOH，其他启发式方法没有这个属性——例如First-Fit-Decreasing 启发式是确定性的，因为它总是首先按大小递减顺序对项目进行排序。
如果特定随机算法的可能输出集是有限的并且包含真实答案，那么运行它足够长"practically guaranteed"到最终找到它（从某种意义上说 not 找到它的概率可以任意小，但永远不会为 0）。请注意，启发式输入的某些排列不会自动导致获得准确的答案——在 First-Fit 的情况下，事实证明 是 true , 但这仅在 2009 年得到证实。
有时可以对随机算法的收敛性做出更强有力的陈述：这些通常遵循 "For any given small threshold d, after t steps we will be within d of the optimal solution with probability f(t, d)"，其中 f(t, d) 是 t 和 d 的递增函数。
扩展question of streetparade，我想问一下随机算法和启发式算法之间有什么区别，如果有的话。
说随机算法实际上是一种启发式算法对吗？
Booth 方法通常用于加速生成和测试 NP 完全问题的解决方案
随机算法使用随机性
他们使用所有组合但不按顺序使用，而是使用来自所有可能性范围的随机组合，希望尽快找到解决方案。实现快速简单，单次迭代也很快（常数时间）
启发式算法
他们不是随机选择组合，而是基于对使用的过程、输入数据集或用法的一些了解。因此，他们将组合的数量显着减少到只有那些可能是解决方案的组合，并且只使用那些但通常是所有组合，直到找到解决方案。
实施复杂性取决于问题，单次迭代通常比随机方法（恒定时间）慢得多，因此仅当可能性的数量降低到足以使实际加速可见时才使用启发式方法，因为即使算法复杂度启发式算法通常要低得多，有时常数时间足够大，甚至可以减慢速度……（在运行时方面）
展位方式可以组合在一起
TTBOMK，"stochastic algorithm" 不是标准术语。然而，"Randomized algorithm" 可能就是这里的意思。
Randomized: 以某种方式使用随机性。有两种风格：Monte Carlo 算法总是在限定时间内完成，但不保证最优解，而 Las Vegas 算法不一定保证在任何有限时间内完成，但承诺找到最佳解决方案。 （通常它们也需要有一个有限的 expected 运行 时间。）常见 Monte Carlo 算法的示例：MCMC、模拟退火和 Miller-Rabin 素性测试.具有随机枢轴选择的快速排序是一种总是在有限时间内完成的拉斯维加斯算法。不使用任何随机性的算法是 确定性.
启发式：不保证找到正确答案。非启发式算法是 exact.
许多启发式算法对输入的 "incidental" 属性很敏感，这些属性不会影响真正的解决方案，例如装箱问题的 First-Fit 启发式算法中考虑了订单项。在这种情况下，它们可以被认为是 Monte Carlo 随机算法：您可以随机排列输入并重新运行它们，始终保持找到的最佳答案。 OTOH，其他启发式方法没有这个属性——例如First-Fit-Decreasing 启发式是确定性的，因为它总是首先按大小递减顺序对项目进行排序。
如果特定随机算法的可能输出集是有限的并且包含真实答案，那么运行它足够长"practically guaranteed"到最终找到它（从某种意义上说 not 找到它的概率可以任意小，但永远不会为 0）。请注意，启发式输入的某些排列不会自动导致获得准确的答案——在 First-Fit 的情况下，事实证明 是 true , 但这仅在 2009 年得到证实。
有时可以对随机算法的收敛性做出更强有力的陈述：这些通常遵循 "For any given small threshold d, after t steps we will be within d of the optimal solution with probability f(t, d)"，其中 f(t, d) 是 t 和 d 的递增函数。