随机算法概率最大化
我是一名计算机科学专业的本科生，我正在为期末考试而学习。我遇到了一个与各种动态规划类型问题有点不相称的问题。我将这样总结：
我得到了一个有效的随机算法 A，它返回一个独立的集合。该算法以至少 1/(n^3) 的概率返回最大独立集，其中 n 是图中的顶点数。建议另一种算法，使用 A，以至少 1/2 的概率返回最大集。
我研究过随机算法，但这似乎只是一个简单的实现案例。如果我运行 A n^3 次，最大独立集的概率接近 1。那么我是否可以说运行它 n^3/2 次就能达到预期的效果？我只是想让这件事变得更难吗？任何帮助表示赞赏。
I'm a computer science undergrad and I'm just studying for finals. I came across a problem that was kind of out of place with the various dynamic programming type problems. I'll summarize it like this:
I'm given an efficient randomized algorithm, A, that returns an independent set. This algorithm returns the maximum independent set with probability at least 1/(n^3) where n is the number of vertices in the graph. Suggest another algorithm, using A, that returns the maximum set with probability at least 1/2.
I've studied randomized algorithms, but this just seems like a simple case of implementation. If I was to run A n^3 times, the probability that the maximum independent set is close to 1. Could I then say that running it n^3/2 times would give the desired effect? Am I just trying to make this harder? Any help is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
接近但不准确，其中一次运行返回正确答案的概率至少为 1/n^3。这意味着一次运行得到错误答案的概率是(1-1/n^3)，也就是说M次运行后得到正确答案的概率是1-(1-1/n^3)^M 。
现在回想一下 e（维基百科链接） 的公式，如果运行 n^3 次，概率为 1-1/e，大于 1/2（尽管不是很接近 1），获得精确的运行次数以达到 1/2 - (n^3)* 也是微不足道的ln(2).
Close but not accurate, the probability for one of the runs to return the correct answer is at least 1/n^3. That means that the probability of getting the wrong answer in one run is (1-1/n^3), which means the probability of getting the right answer after M runs is 1-(1-1/n^3)^M.
Now recall the formula for e (Wikipedia link), if you run n^3 times, the probability is 1-1/e which is more than 1/2 (although not very close to 1), it is also trivial to get the exact number of runs to get to exactly 1/2 - (n^3)*ln(2).
我没有研究过最大独立集所以我不能给你太多帮助。但是，在声明运行时间之前，您应该先写出算法。
如果对 n^3 运行算法 A，您将得到 n^3 最大独立集。但是，您只需要返回一组最大集合。你如何找出 n^3 中正确的一个？在这里，您可能需要您的问题中缺少的验证算法。
根据问题本身（最大独立集），您可能有足够的信息来找到正确的最大独立集，其需要的运行次数远小于 O(n^3)。
I haven't study the maximum independent set so I cannot give you too much help. However, you should first write out the algorithm first before claiming the number of running time.
If you run the algorithm A for n^3, you get n^3 maximum independent set. However, you need to return only ONE maximum set. How do you figure out the correct one within those n^3? Here you may want a verification algorithm that is missing in your question.
Depending on the problem itself (maximum independent set), it is possible for you to have enough information to find the correct maximum independent set that requires number of running much less than O(n^3).