Вторая попытка: рассмотрение двух меток за раз
Идея локального поиска заключается в применении алгоритма с полиноми- альным временем для бинарной сегментации изображения с целью улучшения локальных шагов.
Начнем с простейшей реализации этой идеи, которая не всегда дает хорошую гарантию аппроксимации. Для разметкиf выберем две метки а, b L и ограничим внимание узлами, имеющими метки а или b в разметке f За один ло- кальный шаг любое подмножество этих узлов может переключить метки из а в b или из b в а. Или в более формальном определении, две разметки f и f' считаются соседними, если существуют две метки а, b L, такие, что для всех остальных ме- ток с ⅜ {а, b} и всех узлов i Vусловие f (i) = с выполняется в том, и только в том случае, если f'(i) = с. Следует заметить, что состояние f может иметь сколь угодно много соседей, так как произвольное подмножество узлов с метками а и b может переключать свою метку. Однако при этом действует следующее утверждение:(12.8) Если разметка f не является локально оптимальной для описанного выше соседского окружения, то сосед с меньшим штрафом может быть найден за k2 вы- числений минимального разреза.
Доказательство. Количество пар разных меток меньше k2, поэтому каждую пару можно проверить по отдельности. Для пары меток а, b L рассмотрим задачу нахождения улучшенной разметки посредством перестановки меток узлов между a и b. Она в точности совпадает с задачей сегментации для двух меток в подграфе узлов, которым в f назначены метки a или b. Воспользуемся алгоритмом, разра- ботанным для бинарной сегментации изображений, для поиска лучшей из таких измененных разметок. ■
Это соседское окружение намного лучше варианта с одним переключением, который был рассмотрен в начале. Например, оно предоставляет оптимальное решение случая с двумя метками. Однако даже с улучшенным окружением ло- кальные оптимумы могут быть плохими, как показано на рис. 12.6. В этом примере есть три узла s, t и z, которые должны сохранить свои исходные метки. Все осталь- ные узлы лежат на одной из сторон треугольника; они должны сохранить одну из двух меток, связанных с узлами на концах этой стороны. Эти требования легко выражаются назначением каждому узлу очень большого штрафа за назначение для неразрешенных меток. Штрафы за разделение определяются следующим об- разом: тонким ребрам на рисунке соответствует штраф 1, а толстым — большой штраф M. Теперь заметим, что разметка на иллюстрации имеет штраф M + 3, но при этом является локально оптимальной. У (глобально) оптимальной разметки штраф равен всего 3, а для ее получения на рисунке достаточно изменить метки обоих узлов рядом с s.
Рис. 12.6. Плохой локальный оптимум для алгоритма локального поиска, учитывающего только две метки |
Еще по теме Вторая попытка: рассмотрение двух меток за раз:
- Попытка портрета
- Попытка заглушить чувства алкоголем
- Глава 10. Как противостоять попыткам манипуляции.
- Отстраненность - попытка говорить отвлеченно.
- Обращение к наркотикам —попытка не ощущать то, что мы чувствуем.
- 1. О двух путях развития
- Метаязык двух слов.
- Закон двух колес
- Закон двух колес
- Ссора двух подруг
- Книга состоит из двух частей.
- Земля после Затопления двух Континентов
- НЛП целиком построено на двух фундаментальных принципах:
- Анкета - это диалог двух заинтересованных людей