algorithm - 随机算法概率最大化

Question

我是一名计算机科学本科生，正在为期末考试学习。我遇到了一个与各种动态编程类型问题有点不相称的问题。我会这样总结:

我得到了一个高效的随机算法 A，它返回一个独立的集合。该算法返回概率至少为 1/(n^3) 的最大独立集，其中 n 是图中的顶点数。建议另一种算法，使用 A，以至少 1/2 的概率返回最大集合。

我研究过随机算法，但这似乎只是一个简单的实现案例。如果我要运行 A n^3 次，最大独立集接近 1 的概率。那么我可以说运行它 n^3/2 次会产生预期的效果吗？我只是想让这更难吗？感谢您的帮助。

Answer 1

接近但不准确，其中一次运行返回正确答案的概率至少为 1/n^3。这意味着在一次运行中得到错误答案的概率是(1-1/n^3)，这意味着在M次运行后得到正确答案的概率是1-(1-1/n^3)^M .

现在回想一下 e (Wikipedia link) 的公式，如果你运行 n^3 次，概率是 1-1/e 大于 1/2(虽然不是很接近 1)，获得准确的运行次数以准确地达到 1/也是微不足道的2 - (n^3)*ln(2).