Онлайн курсы: Theoretical Computer Science. Problem set 5 #3 Greedy or not.

среда, 4 мая 2016 г.

Задача.
Доказать, что "жадный" алгоритм (Greedy) для задачи о вершинном покрытии точек графа (Vertex Cover) недостаточно эффективен: привести пример, что набор точек с покрытием всех связей графа, выбранный с помощью этого алгоритма, превысит минимальный набор больше, чем в 2 раза.

Решение:
Первый ряд: одна точка, соединена с 8 точками второго ряда.
Второй ряд: 8 точек ( 2 соединены с 5 точками третьего ряда и 1 точкой первого ряда; 6 соединены с 10 точками третьего ряда и 1 точкой первого ряда).
Третий ряд: 10 точек, соединены с 7 точками второго ряда.
Минимальный набор с покрытием всех связей: 8 точек второго ряда.
Набор алгоритма Greedy: 6 точек второго ряда с 11 связями, 1 точка первого ряда с 8 связями, 10 точек третьего ряда с 7 связями.
(10+6+1)/8 = 2.125