Снятие предположения об известном оптимальном радиусе
Вернемся к исходному вопросу: как выбрать хорошее множество из k центров, если оптимальный радиус покрытия неизвестен?
В таких ситуациях часто можно начать с алгоритма, спроектированного с учетом этого предположения, и преобразовать его в алгоритм, обеспечивающий сравнимые гарантии производительности простым перебором по диапазону «предположений» относительно оптимального значения.
В ходе выполнения алгоритма эта последовательность предположений становится все более и более точной, пока не будет достигнуто приближенное решение.
Для задачи о выборе центров это может происходить так: мы начинаем с очень слабых исходных предположений относительно радиуса оптимального решения: известно, что оно больше 0 и что оно не превышает максимального расстояния rmax между любыми двумя местами.
Итак, сначала мы делим разность между ними надвое и применяем разработанный выше жадный алгоритм со значением r = rmax/2.
Затем в соответствии со структурой алгоритма происходит одно из двух: либо мы находим множество из k центров с радиусом покрытия не более 2r, либо заключаем, что решения с радиусом покрытия не более r не существует.
В первом случае можно понизить оценку радиуса оптимального решения; во втором она должна быть повышена.
Так по радиусу проводится своего рода «бинарный поиск»: алгоритм итеративно определяет значения r0 < r1, чтобы мы знали, что оптимальный радиус больше r0, но решение имеет радиус не более 2r1.
По этим значениям описанный выше алгоритм выполняется с радиусом r = (r0 + r1)/2; затем мы либо решаем, что радиус оптимального решения больше r > r0, либо получаем решение с радиусом не более 2r = (r0 + r1) < 2r1. В любом случае оценка уточняется с одной или с другой стороны так же, как это происходит при бинарном поиске.
Алгоритм прекращает работу, когда оценки r0 и r1 оказываются достаточно близкими друг к другу; в этой точке наше решение с радиусом 2r1 близко к 2-аппроксимации оптимального радиуса, так как мы знаем, что оптимальное решение больше r0 (а следовательно, близко к r1).
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу