我是一名计算机科学本科生，我正在攻读总决赛 . 我遇到了一个与各种动态编程类型问题不一致的问题 . 我会这样总结一下：
我给了一个有效的随机算法A，它返回一个独立的集合 . 该算法返回最大独立集，概率至少为1 /（n ^ 3），其中n是图中顶点的数量 . 建议另一种算法，使用A，返回最大集合，概率至少为1/2 .
我研究过随机算法，但这似乎只是一个简单的实现案例 . 如果我要运行A n ^ 3次，则最大独立集合接近1的概率 . 然后我可以说运行它n ^ 3/2次会产生预期的效果吗？我只是想让这更难吗？任何帮助表示赞赏 .
2 回答
关闭但不准确，其中一次运行返回正确答案的概率至少为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） .
我没有研究最大的独立集，所以我不能给你太多的帮助 . 但是，在声明运行时间之前，应首先写出算法 .
如果为n ^ 3运行算法A，则得到n ^ 3个最大独立集 . 但是，您只需要返回一组最大值 . 你如何在n ^ 3中找出正确的一个？在这里，您可能需要一个在您的问题中缺少的验证算法 .
根据问题本身（最大独立集），您可以获得足够的信息来查找正确的最大独立集，该集需要的运行次数远小于O（n ^ 3） .