Выбор соседского отношения

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

Какие аспекты следует учитывать при выборе соседского отношения? Этот выбор может быть весьма непростым, хотя на высоком уровне альтернатива опи- сывается достаточно тривиально.

(i) Соседское окружение решения должно быть достаточно широким, чтобы алгоритм не застревал в плохих локальных оптимумах.

(ii) Соседское окружение решения не должно быть слишком большим, потому что мы хотим иметь возможность эффективно искать в множестве соседей воз- можные локальные перемещения.

Если бы первый пункт был единственной проблемой, то все решения можно было бы просто сделать соседями друг друга — тогда локальных оптимумов вообще не будет, а глобальный оптимум всегда будет находиться в одном шаге! Второй пункт выявляет (очевидный) недостаток такого подхода: если бы соседское окру- жение текущего решения состояло из всех возможных решений, то парадигма ло- кального поиска вообще не приносила никакой пользы и сводилась бы к простому перебору соседского окружения методом «грубой силы».

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

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

Но предположим, мы попытаемся определить более сложное (и даже асимме- тричное) соседское отношение: M' является соседом M, если при создании соот- ветствующей потоковой сети M' может быть получено из M одним увеличиваю- щим путем. Что можно сказать о паросочетании M, если оно является локальным максимумом с этим соседским отношением? В этом случае увеличивающего пути не существует, поэтому M в действительности должно быть (глобальным) мак- симальным паросочетанием. Другими словами, с таким соседским отношением единственными локальными максимумами являются глобальные максимумы, так что прямой градиентный подъем приведет к максимальному паросочетанию. Если поразмыслить над тем, что делает алгоритм Форда-Фалкерсона в нашем сведении от двудольного паросочетания к максимальному потоку, это выглядит логично: размер паросочетания строго возрастает на каждом шаге, и нам никогда не приходится «отступать» из локального максимума. Следовательно, тщательно выбирая соседское отношение, мы превратили зазубренную поверхность оптими- зации в простую воронку.

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

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

Еще по теме Выбор соседского отношения:

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