Недетерминированный алгоритм для покрытия вершин

Question

У меня была проблема в моей викторине, чтобы написать недетерминированный алгоритм для Vertex Cover. Мы обсудили решение с нашим инструктором, и он сказал, что уровень неопределенности не должен быть слишком высоким. Это должно быть разумно хорошо.
Я не понимаю, какой вопрос мне следует задавать недетерминированному компьютеру?

Answer 1

Очевидный вопрос: "какая вершина следующая"?

Простой жадный алгоритм приближения для покрытия вершин многократно выбирает вершину с наиболее раскрытыми смежными вершинами.

Простой недетерминированный алгоритм аппроксимации для покрытия вершин многократно выбирает следующую вершину случайным образом, но с вероятностью, назначенной каждой вершине, пропорциональной ее числу непокрытых смежных вершин. Делайте это снова и снова, вспоминая лучшее решение на данный момент.