Непонятен ответ, который получил в задаче автор курса.
Задача.
Рассматривается "жадный" алгоритм (Greedy) для задачи о вершинном покрытии точек графа (Vertex Cover).
Я построила граф по инструкции в этой лекции, и вот какие результаты у меня получились:
Первый ряд содержит 24 точки.
Второй ряд - 12 точек, каждая из которых соединена с двумя точками первого ряда (2 связи на каждую точку).
Третий ряд - 8 точек, каждая из которых соединена с тремя точками первого ряда (3 связи на каждую точку).
Четвертый ряд - 12 точек, каждая из которых соединена с 6 точками первого ряда (6 связей на каждую точку).
Пятый ряд - 6 точек, каждая из которых соединена с 8 точками первого ряда (8 связей на каждую точку).
Шестой ряд - 8 точек, каждая из которых соединена с 12 точками первого ряда (12 связей на каждую точку).
Седьмой ряд - 11 точек, каждая из которых соединена с 24 точками первого ряда (24 связи на каждую точку).
Каждая точка первого ряда в итоге имеет 22 связи.
Минимальное покрытие для данного графа - 24 точки первого ряда.
"Жадный" алгоритм должен выбрать 11 точек седьмого ряда (24 связи у каждой) и 24 точки первого ряда (22 связи у каждой) и остановиться, поскольку покрытие графа достигнуто. Всего получится 35 точек.
Автор курса получил результат - 57 точек, а также отношение количества точек "жадного" алгоритма к количеству точек минимального покрытия, приблизительно равное 2.38 (57/24).
На самом деле здесь этот алгоритм дает достаточно неплохой коэффициент аппроксимации 35/24 = 1.46.
Задача.
Рассматривается "жадный" алгоритм (Greedy) для задачи о вершинном покрытии точек графа (Vertex Cover).
Второй ряд - 12 точек, каждая из которых соединена с двумя точками первого ряда (2 связи на каждую точку).
Третий ряд - 8 точек, каждая из которых соединена с тремя точками первого ряда (3 связи на каждую точку).
Четвертый ряд - 12 точек, каждая из которых соединена с 6 точками первого ряда (6 связей на каждую точку).
Пятый ряд - 6 точек, каждая из которых соединена с 8 точками первого ряда (8 связей на каждую точку).
Шестой ряд - 8 точек, каждая из которых соединена с 12 точками первого ряда (12 связей на каждую точку).
Седьмой ряд - 11 точек, каждая из которых соединена с 24 точками первого ряда (24 связи на каждую точку).
Каждая точка первого ряда в итоге имеет 22 связи.
Минимальное покрытие для данного графа - 24 точки первого ряда.
"Жадный" алгоритм должен выбрать 11 точек седьмого ряда (24 связи у каждой) и 24 точки первого ряда (22 связи у каждой) и остановиться, поскольку покрытие графа достигнуто. Всего получится 35 точек.
Автор курса получил результат - 57 точек, а также отношение количества точек "жадного" алгоритма к количеству точек минимального покрытия, приблизительно равное 2.38 (57/24).
На самом деле здесь этот алгоритм дает достаточно неплохой коэффициент аппроксимации 35/24 = 1.46.
Комментариев нет:
Отправить комментарий