<<
>>

Знать оптимальный радиус полезно

Поиски улучшенного алгоритма мы начнем с полезного мысленного эксперимента. Представьте на минуту, что вам кто-то подсказал значение оптимального радиуса r. Пригодится ли эта информация? То есть предположим, что нам известно, что суще- ствует множество из к центров С с радиусом r(C*) < r и мы хотим найти некоторое множество из к центров из С, радиус покрытия которых ненамного больше r.
Как выясняется, найти множество из к центров c радиусом покрытия, не превышаю- щим 2r, относительно несложно.

Идея заключается в следующем: мы можем использовать факт существования этого решения С в своем алгоритме несмотря на то, что мы не знаем, как выгля- дит С*. Рассмотрим любое место 5 S. Должен существовать центр c С*, по-

крывающий место 5, и этот центр c находится на расстоянии не более r от 5. Теперь в качестве центра в нашем решении выбирается это место 5 вместо с*, потому что мы понятия не имеем, что собой представляет с*. Нам хотелось бы сделать так, что- бы из 5 покрывались все места, покрываемые с в неизвестном решении С*.

Задача решается увеличением радиуса с r до 2r. Все места, находившиеся на расстоянии не более r от центра с*, находятся на расстоянии не более 2r от 5 (это следует из неравенства треугольника). Простая иллюстрация этого аргумента представлена на рис. 11.4.
Центр с , используемый в оптимальном решении

Место s покрывается из с

Рис. 11.4. Все места, покрываемые с радиусом r из с*, также покрываются с радиусом 2r из 5

S' будет представлять все места, для которых еще нужно обеспечить покрытие Инициализировать S' = S Присвоить C = 0 Пока S' = 0

Выбрать любое место s e S' и добавить s в C

Удалить из S' все места, находящиеся на расстоянии не более 2r от s Конец Пока Если |C| r.

U = Центры, используемые оптимальным решением

Рис.

11.5. Критический шаг в анализе жадного алгоритма, которому известен оптимальный радиус r. Никакой центр, используемый оптимальным решением, не может принадлежать двум разным кругам, поэтому количество оптимальных центров должно быть по крайней мере не меньше количества центров, выбранных жадным алгоритмом

Доказательство. Предположим обратное: существует множество C* содер- жащее не более к центров, с радиусом покрытия r(C*) < r. Каждый центр c C,

выбираемый жадным алгоритмом, является одним из исходных мест в S, и мно- жество C* имеет радиус покрытия не более r, поэтому должен быть центр с* |C |, а поскольку |C | > k, это противоречит нашему предположению о том, что C содержит не более k центров.

Итак, нужно лишь показать, что ни один оптимальный центр с* C не мо- жет быть близким к каждому из двух центров с, с' C. Причина изображена

на рис. 11.5: каждая пара центров с, с' C разделяется расстоянием более 2r,

поэтому нахождение с* на расстоянии не более r от каждого из них приведет к нарушению неравенства треугольника), поскольку dist(с, с*) + dist(с', с') > > dist(с, с') > 2r. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Знать оптимальный радиус полезно:

  1. Знать меру... А как ее знать? особая четкость с детьми - инвалидами
  2. Оптимальные условия
  3. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  4. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  5. 6.2.4. Поиск оптимальной финансовой модели СМИ
  6. ЗНАТЬ и ПОНИМАТЬ
  7. 1.1.4. Оптимальная модель социальной сферы современного общества
  8. Знать
  9. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  10. ЗНАТЬ ОСНОВНЫЕ МАНИПУЛЯЦИИ
  11. НЕВОЗМОЖНО ЗНАТЬ ЗАРАНЕЕ
  12. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  13. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  14. Формула «чтобы уметь — надо знать»