Я нашел этот псевдокод в учебнике, но я не совсем его понимаю, и он был плохо объяснен.
Algorithm 8: Greedy Vertex Cover Algorithm Example(G=(V,E))
1) C := ;.
2) while (E 6= ;)
• Select a node v of maximal degree in G.
• C := C [{v}.
• Remove all edges e from E that are covered by v,
i.e. for which e\v 6= ; holds.
3) Return C.
Алгоритм представляет собой жадный алгоритм для решения проблемы вершинного покрытия. Кто-нибудь узнает его и знает его имя? Я хотел бы узнать больше об этом.
Я думаю, вы можете найти этот конкретный алгоритм на странице 8 этой презентации задачи вершинного покрытия предоставлено Гаджанандом Шармой.
Кажется, он называется Approx-Vertex-Cover, также известным как Алгоритм аппроксимации вершинного покрытия.
На последующих страницах есть пример алгоритма и того, как он работает.
Также в Алгоритмы аппроксимации: покрытие вершин document на странице 2 вы можете найти другое хорошее объяснение:
Алгоритм 1: приблизительное вершинное покрытие (G)
1
C←∅2
while E 6= ∅pick any {u, v} ∈ E C ← C ∪ {u, v} delete all edges incident to either u or v
return C
