Недостатки простого жадного алгоритма

Для начала обсудим жадные алгоритмы для этой задачи. Как и прежде, понятие «жадности» по необходимости получается несколько размытым; фактически мы рассматриваем алгоритмы, которые перебирают места одно за другим «недальновидно», то есть при выборе каждого места не учитывается, куда попадут остальные.

Как выясняется, такой подход излишне упрощен, чтобы быть эффективным: в некоторых случаях он приводит к очень плохим решениям.

Чтобы убедиться в этом, рассмотрим пример с двумя местами s и z и k = 2. Допустим, s и z располагаются на плоскости — на расстоянии, равном стандартному евклидовому расстоянию на плоскости, а любая точка плоскости подходит для размещения центра.

Обозначим d расстояние между s и z. В этом случае лучшее расположение для одного центра c1 находится в середине пути между s и z, а радиус покрытия этого центра равен r({c1}) = d/2.

Жадный алгоритм разместит первый центр в точке c1. Неважно, где бы ни был размещен второй центр, по крайней мере для одного из мест s и z центр c1 окажется ближе, поэтому радиус покрытия множества двух центров останется равным d/2.

При этом в оптимальном решении с k = 2 центры размещаются в s и z, что приведет к радиусу покрытия 0. В более сложном примере, демонстрирующем ту же проблему, используются два плотных «скопления» мест возле s и z.

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