<<
>>

Вторая попытка: рассмотрение двух меток за раз

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

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

Начнем с простейшей реализации этой идеи, которая не всегда дает хорошую гарантию аппроксимации. Для разметки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. Плохой локальный оптимум для алгоритма локального поиска, учитывающего только две метки

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

Еще по теме Вторая попытка: рассмотрение двух меток за раз:

  1. Попытка портрета
  2. Попытка заглушить чувства алкоголем
  3. Глава 10. Как противостоять попыткам манипуляции.
  4. Отстраненность - попытка говорить отвлеченно.
  5. Обращение к наркотикам —попытка не ощущать то, что мы чувствуем.
  6. 1. О двух путях развития
  7. Метаязык двух слов.
  8. Закон двух колес
  9. Закон двух колес
  10. Ссора двух подруг
  11. Книга состоит из двух частей.
  12. Земля после Затопления двух Континентов
  13. НЛП целиком построено на двух фундаментальных принципах:
  14. Анкета - это диалог двух заинтересованных людей