<<
>>

Снятие предположения об известном оптимальном радиусе

Вернемся к исходному вопросу: как выбрать хорошее множество из k центров, если оптимальный радиус покрытия неизвестен?

Стоит рассмотреть два разных ответа на этот вопрос. Во-первых, при разработке аппроксимирующих алгоритмов часто бывает концептуально полезно предполо- жить, что значение, обеспечиваемое оптимальным решением, известно.

В таких ситуациях часто можно начать с алгоритма, спроектированного с учетом этого предположения, и преобразовать его в алгоритм, обеспечивающий сравнимые га- рантии производительности простым перебором по диапазону «предположений» относительно оптимального значения. В ходе выполнения алгоритма эта последо- вательность предположений становится все более и более точной, пока не будет достигнуто приближенное решение.

Для задачи о выборе центров это может происходить так: мы начинаем с очень слабых исходных предположений относительно радиуса оптимального решения: известно, что оно больше 0 и что оно не превышает максимального расстояния r между любыми двумя местами.

Итак, сначала мы делим разность между ними на- двое и применяем разработанный выше жадный алгоритм со значением r = rmax/2. Затем в соответствии со структурой алгоритма происходит одно из двух: либо мы находим множество из k центров с радиусом покрытия не более 2r, либо заключаем, что решения с радиусом покрытия не более r не существует. В первом случае мож- но понизить оценку радиуса оптимального решения; во втором она должна быть повышена. Так по радиусу проводится своего рода «бинарный поиск»: алгоритм итеративно определяет значения r0 < r1, чтобы мы знали, что оптимальный радиус больше r0, но решение имеет радиус не более 2r1. По этим значениям описанный выше алгоритм выполняется с радиусом r = (r0 + r1)/2; затем мы либо решаем, что радиус оптимального решения больше r > r0, либо получаем решение с радиусом

не более 2r = (r0 + rl) < 2rl. В любом случае оценка уточняется с одной или с другой стороны так же, как это происходит при бинарном поиске. Алгоритм прекращает работу, когда оценки r0 и r1 оказываются достаточно близкими друг к другу; в этой точке наше решение с радиусом 2r1 близко к 2-аппроксимации оптимального радиуса, так как мы знаем, что оптимальное решение больше r0 (а следовательно, близко к r1).

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

Еще по теме Снятие предположения об известном оптимальном радиусе:

  1. § 20 Исполнение денежное или платеж. – Кому следует платить? – Кто обязан и вправе платить. – Платеж от стороннего лица. – Платеж по частям. – Расписка в платеже и другие его доказа- тельства. – Признаки и предположения о платеже. – Отноше- ние платежа к известному долгу. – Платеж и уплата по рус- скому закону. – Доказательства платежа. – Текущий счет.
  2. Статья 91. Снятие судимости
  3. Статья 108. Погашение и снятие судимости
  4. Снятие страхов
  5. СНЯТИЕ ВЕНЦА БЕЗБРАЧИЯ
  6. Известные подходы
  7. Не известная ситуация.
  8. Известный пример.
  9. Оптимальные условия
  10. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  11. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  12. 6.2.4. Поиск оптимальной финансовой модели СМИ
  13. Известный опыт. (последние разъяснения)
  14. Известный опыт. (последние разъяснения)
  15. СПОР О ДОСТОВЕРНО ИЗВЕСТНОМ ФАКТЕ
  16. 1.1.4. Оптимальная модель социальной сферы современного общества
  17. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  18. Глава 30 Три способа сделать мужа известным
  19. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  20. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.