algorithm - 顶点覆盖的非确定性算法

Question

我在课堂测验中遇到了一个问题，要为 Vertex Cover 编写一个非确定性算法。我们和我们的导师讨论了解决方案，他告诉我们水平不确定性不应该太高。它应该是明智的。
我对我应该向非确定性计算机问什么问题感到困惑？

Answer 1

显而易见的问题是“下一个顶点”？

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

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