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

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

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

Если бы первый пункт был единственной проблемой, то все решения можно было бы просто сделать соседями друг друга — тогда локальных оптимумов вообще не будет, а глобальный оптимум всегда будет находиться в одном шаге!

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

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

Вероятно, простейшее соседское отношение для паросочетаний выглядит так: M’ является соседом M, если M’ может быть получено вставкой или удалением одного ребра в M.

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

Но предположим, мы попытаемся определить более сложное (и даже асимметричное) соседское отношение: M’ является соседом M, если при создании соответствующей потоковой сети M’ может быть получено из M одним увеличивающим путем.

Что можно сказать о паросочетании M, если оно является локальным максимумом с этим соседским отношением? В этом случае увеличивающего пути не существует, поэтому M в действительности должно быть (глобальным) максимальным паросочетанием.

Другими словами, с таким соседским отношением единственными локальными максимумами являются глобальные максимумы, так что прямой градиентный подъем приведет к максимальному паросочетанию.

Если поразмыслить над тем, что делает алгоритм Форда–Фалкерсона в нашем сведении от двудольного паросочетания к максимальному потоку, это выглядит логично: размер паросочетания строго возрастает на каждом шаге, и нам никогда не приходится «отступать» из локального максимума.

Следовательно, тщательно выбирая соседское отношение, мы превратили зазубренную поверхность оптимизации в простую воронку.

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

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