如何确定随机算法是否可以使用？
How to decide if randomised algorithm is OK to use?
据我了解，随机算法可能会给出错误的answer.For示例，使用收缩算法解决图最小切割问题，您需要运行算法n^2*ln(n ) 次，这样得不到正确答案的可能性至多为 1/n。无论失败的可能性有多小，答案都可能是错误的，那么我们什么时候允许错误答案是正确的呢？
首先，我认为您需要区分不同的 类 随机算法：
一个Monte Carlo algorithm是一个随机的算法w.r.t。正确性。根据你的问题，随机最小切割算法就是这种算法的一个例子。
一个Las Vegas algorithm是一个随机的算法w.r.t。 运行 时间。比如随机快速排序就是这样一种算法。
你的问题似乎是指蒙特卡洛算法。
关于蒙特卡洛算法是否适合你的问题，可能无法客观地回答，因为它是基于类似ecomonic theory of utility的东西。给定两个算法，A 和 B，然后每次调用 A 或 B 需要一些时间 t 并为您提供正确性为 c 的结果。效用 U(t, c) 是一个随机变量，只有你才能确定 UA( T, C) 比 UB(T, C) 更好或更差。一些示例，其中算法 A 的执行速度是 B 的两倍，但错误概率为 1e-6 :
如果这些是网站上的偏好推荐，那么让您的网站响应速度比竞争对手快一倍对您来说可能是值得的，但冒着客户很少得到的风险错误的建议。
如果这些是核反应堆的控制系统（借用 TemplateTypedef 的评论），那么轻微的失败机会可能不值得节省时间（例如，您最好投资于处理器速度是较慢算法的两倍 运行）。
上面的两个例子表明，对于不同的设置，这两个选择中的每一个都可能是正确的。事实上，效用理论很少显示明显错误的选择集。在本书的介绍中 Randomized Algorithms by Motwani and Raghavan, however, the authors do give such an example for the fallacy of avoiding Monte-Carlo algorithms. The probability of a CPU malfunctioning due to cosmic radiation 是一些 α （我忘记了它的值）。因此，避免 运行 错误概率远低于 α 的蒙特卡洛算法可能只是不合理的。
您始终需要分析算法的属性，并确定您的应用程序是否可以承受非最佳答案的风险。 （如果答案是布尔值，则 "non-optimal" 与 "wrong." 相同）
有许多类型的编程问题，其中 一些 接近最优且在合理时间内获得的答案比最优 much 好提供的答案太迟或根本没有。
旅行商问题就是一个例子。如果您是沃尔玛并且需要为给定的城市集每晚计划送货路线，那么获得接近最佳的 a 路线比没有路线或天真地选择一条路线或可能的最佳路线要好得多2天后获得的路线。
随机算法提供多种保证。它们通常采用 error <= F(cost) 形式，其中 error 和 cost 几乎可以是任何内容。成本可以用 运行 时间或花费多少重复 运行 来寻找更好的答案来表示。 Space 也可以计入费用。错误可能是错误 1/0 答案的概率、最佳结果的距离度量、错误组件的离散计数等。
有时您不得不忍受可能是错误的答案，因为没有其他有用的选择。大数的素性测试属于这一类。尽管有多项式时间确定性测试，但它们仍然比为所有实际目的产生正确答案的概率测试慢得多。
例如，如果您有一个布尔随机函数，其中 True 结果始终正确，但 False 有 50% 的时间是错误的，那么您的状态就很好。 （Miller-Rabin素性测试实际上比这更好。）
假设您可以 运行 算法 40 次。如果 运行 中的任何一个说 False，您就知道答案是 False。如果它们都是真的，那么如果是假的，那么真实答案的概率大约是 2^40 = 1/(1 万亿)。
即使在安全关键的应用程序中，这也可能是一个不错的结果。一生中被闪电击中的几率约为 1/10,000。我们都接受了这一点，不要再考虑了。
据我了解，随机算法可能会给出错误的answer.For示例，使用收缩算法解决图最小切割问题，您需要运行算法n^2*ln(n ) 次，这样得不到正确答案的可能性至多为 1/n。无论失败的可能性有多小，答案都可能是错误的，那么我们什么时候允许错误答案是正确的呢？
首先，我认为您需要区分不同的 类 随机算法：
一个Monte Carlo algorithm是一个随机的算法w.r.t。正确性。根据你的问题，随机最小切割算法就是这种算法的一个例子。
一个Las Vegas algorithm是一个随机的算法w.r.t。 运行 时间。比如随机快速排序就是这样一种算法。
你的问题似乎是指蒙特卡洛算法。
关于蒙特卡洛算法是否适合你的问题，可能无法客观地回答，因为它是基于类似ecomonic theory of utility的东西。给定两个算法，A 和 B，然后每次调用 A 或 B 需要一些时间 t 并为您提供正确性为 c 的结果。效用 U(t, c) 是一个随机变量，只有你才能确定 UA( T, C) 比 UB(T, C) 更好或更差。一些示例，其中算法 A 的执行速度是 B 的两倍，但错误概率为 1e-6 :
如果这些是网站上的偏好推荐，那么让您的网站响应速度比竞争对手快一倍对您来说可能是值得的，但冒着客户很少得到的风险错误的建议。
如果这些是核反应堆的控制系统（借用 TemplateTypedef 的评论），那么轻微的失败机会可能不值得节省时间（例如，您最好投资于处理器速度是较慢算法的两倍 运行）。
上面的两个例子表明，对于不同的设置，这两个选择中的每一个都可能是正确的。事实上，效用理论很少显示明显错误的选择集。在本书的介绍中 Randomized Algorithms by Motwani and Raghavan, however, the authors do give such an example for the fallacy of avoiding Monte-Carlo algorithms. The probability of a CPU malfunctioning due to cosmic radiation 是一些 α （我忘记了它的值）。因此，避免 运行 错误概率远低于 α 的蒙特卡洛算法可能只是不合理的。
您始终需要分析算法的属性，并确定您的应用程序是否可以承受非最佳答案的风险。 （如果答案是布尔值，则 "non-optimal" 与 "wrong." 相同）
有许多类型的编程问题，其中 一些 接近最优且在合理时间内获得的答案比最优 much 好提供的答案太迟或根本没有。
旅行商问题就是一个例子。如果您是沃尔玛并且需要为给定的城市集每晚计划送货路线，那么获得接近最佳的 a 路线比没有路线或天真地选择一条路线或可能的最佳路线要好得多2天后获得的路线。
随机算法提供多种保证。它们通常采用 error <= F(cost) 形式，其中 error 和 cost 几乎可以是任何内容。成本可以用 运行 时间或花费多少重复 运行 来寻找更好的答案来表示。 Space 也可以计入费用。错误可能是错误 1/0 答案的概率、最佳结果的距离度量、错误组件的离散计数等。
有时您不得不忍受可能是错误的答案，因为没有其他有用的选择。大数的素性测试属于这一类。尽管有多项式时间确定性测试，但它们仍然比为所有实际目的产生正确答案的概率测试慢得多。
例如，如果您有一个布尔随机函数，其中 True 结果始终正确，但 False 有 50% 的时间是错误的，那么您的状态就很好。 （Miller-Rabin素性测试实际上比这更好。）
假设您可以 运行 算法 40 次。如果 运行 中的任何一个说 False，您就知道答案是 False。如果它们都是真的，那么如果是假的，那么真实答案的概率大约是 2^40 = 1/(1 万亿)。
即使在安全关键的应用程序中，这也可能是一个不错的结果。一生中被闪电击中的几率约为 1/10,000。我们都接受了这一点，不要再考虑了。