Снятие предположения об известном оптимальном радиусе
Стоит рассмотреть два разных ответа на этот вопрос. Во-первых, при разработке аппроксимирующих алгоритмов часто бывает концептуально полезно предполо- жить, что значение, обеспечиваемое оптимальным решением, известно.
В таких ситуациях часто можно начать с алгоритма, спроектированного с учетом этого предположения, и преобразовать его в алгоритм, обеспечивающий сравнимые га- рантии производительности простым перебором по диапазону «предположений» относительно оптимального значения. В ходе выполнения алгоритма эта последо- вательность предположений становится все более и более точной, пока не будет достигнуто приближенное решение.Для задачи о выборе центров это может происходить так: мы начинаем с очень слабых исходных предположений относительно радиуса оптимального решения: известно, что оно больше 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).
Еще по теме Снятие предположения об известном оптимальном радиусе:
- § 20 Исполнение денежное или платеж. – Кому следует платить? – Кто обязан и вправе платить. – Платеж от стороннего лица. – Платеж по частям. – Расписка в платеже и другие его доказа- тельства. – Признаки и предположения о платеже. – Отноше- ние платежа к известному долгу. – Платеж и уплата по рус- скому закону. – Доказательства платежа. – Текущий счет.
- Статья 91. Снятие судимости
- Статья 108. Погашение и снятие судимости
- Снятие страхов
- СНЯТИЕ ВЕНЦА БЕЗБРАЧИЯ
- Известные подходы
- Не известная ситуация.
- Известный пример.
- Оптимальные условия
- АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
- ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
- 6.2.4. Поиск оптимальной финансовой модели СМИ
- Известный опыт. (последние разъяснения)
- Известный опыт. (последние разъяснения)
- СПОР О ДОСТОВЕРНО ИЗВЕСТНОМ ФАКТЕ
- 1.1.4. Оптимальная модель социальной сферы современного общества
- 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
- Глава 30 Три способа сделать мужа известным
- Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
- Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.