顶点覆盖的非确定性算法

Question

我的 class 测验中遇到了为 Vertex Cover 编写非确定性算法的问题。我们和我们的导师讨论了解决方案，他告诉我们水平不确定性不应该太高。感觉应该不错。
我对我应该向非确定性计算机提出什么问题感到困惑？

Answer 1

显而易见的问题是 "which vertex next"?

一个简单的顶点覆盖贪心近似算法重复选择具有最多未覆盖相邻顶点的顶点。

一种简单的顶点覆盖非确定性近似算法重复随机选择下一个顶点，但分配给每个顶点的概率与其未覆盖的相邻顶点数成正比。一遍又一遍地这样做，记住迄今为止最好的解决方案。