Аппроксимация задачи о максимальном разрезе с применением локального поиска - Локальный поиск

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

Задача

В задаче о максимальном разрезе имеется ненаправленный граф G = (V, E) с положительными целочисленными весами каждого ребра е. Для разбиения (A, B) множества вершин w(A, B) обозначает общий вес ребер, один конец которых принадлежит A, а другой принадлежит B:

Целью является поиск разбиения (A, B) вершинного покрытия, максимизирующего w(A, B). Задача о максимальном разрезе является NР-сложной в том смысле, что для взвешенного графа G и границы β принятие решения о том, существует ли разбиение (A, B) вершин G с w(A, B) ≥ β, выполняется с NР-сложностью. В то же время, конечно, задача о максимальном разрезе напоминает задачу о минимальном разрезе s-t для потоковых сетей, имеющую полиномиальное решение. Основная причина ее неразрешимости обусловлена тем фактом, что мы стремимся максимизировать, а не минимизировать вес проходящих через разрез ребер.

И хотя задача нахождения устойчивой конфигурации сети Хопфилда не была оптимизационной задачей как таковой, мы видим, что задача о максимальном разрезе с ней тесно связана. На языке сетей Хопфилда задача о максимальном разрезе представляет собой экземпляр, в котором все веса ребер положительны (а не отрицательны), а конфигурации состояний узлов Sестественно соответствуют разбиениям (A, B): узлы имеют состояние -1 в том, и только в том случае, если они принадлежат множеству A, и состояние +1 — в том, и только в том случае, если они принадлежат множеству B. Целью является такое распределение состояний, при котором как можно большая часть веса приходится на хорошие ребра — те, у которых конечные точки находятся в разных состояниях. В такой формулировке задача о максимальном разрезе направлена на максимизацию величины Ф(S), которая использовалась в доказательстве (12.3) в том случае, когда все веса ребер положительны.

Разработка алгоритма

Алгоритм переключения состояния, использованный для сетей Хопфилда, предоставляет алгоритм локального поиска для аппроксимации целевой функции максимального разреза Ф(S) = w(A, B). В контексте разбиений он говорит следующее: если существует узел u, для которого суммарный вес ребер из u в узлы на соответствующей стороне разбиения превышает общий вес ребер из u в узлы на другой стороне разбиения, то узел u следует переместить на другую сторону разбиения.

Введем понятие “ближнего соседства”: разбиения (A, B) и (A', B') называются ближними соседними решениями, если (A', B') можно получить из (A, B) перемещением одного узла с одной стороны разбиения на другую. Естественно задать два основных вопроса:

♦ Можно ли сказать что-то конкретное о качестве локальных оптимумов в окружении ближнего соседства?

♦ Так как ближнее соседство определяется предельно просто, какие варианты соседства могут предоставить более сильные алгоритмы локального поиска для максимального разреза?

Сначала мы ответим на первый из этих вопросов, а вторым займемся в следующем разделе.

Анализ алгоритма

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

(12.5) Пусть (A, B) — разбиение, которое является локальным оптимумом для задачи о максимальном разделе в ближайшем соседстве, а (А*, В*) — глобально-оптимальное разбиение. Тогда w(A, В) ≥ 1/2w(А*, В*).

Доказательство. Пусть W = ∑_ew_e. Мы также немного расширим систему обозначений: для двух узлов u и v запись w_uv будет обозначать w_e, если существует ребро е, соединяющее u и v, и 0 в противном случае.

Для любого узла u ∈ A должно выполняться условие

так как в противном случае узел u должен быть перемещен на другую сторону разбиения, и разбиение (A, B) не будет локально оптимальным. Просуммируем эти неравенства для всех u ∈ A; любое ребро, оба конца которого принадлежат A, будет находиться в левой части ровно двух таких неравенств, тогда как любое ребро, один конец которого принадлежит A, а другой принадлежит B, будет находиться в правой части ровно одного из таких неравенств. Следовательно, мы получаем

Аналогичные рассуждения можно применить к множеству B, получая

Сложив неравенства (12.1) и (12.2) и разделив результат на 2, получаем:

В левой стороне неравенства (12.3) учитываются веса всех ребер, не переходящих из A в B; следовательно, если прибавить w(A, B) к обеим сторонам (12.3), левая сторона станет равна W. Правая сторона превращается в 2w(A, В), поэтому имеем W ≤ 2w(A, В), или w(A, В) ≥ 1/2W. ■

Обратите внимание: в доказательстве (12.5) мы особенно не задерживались на оптимальном разбиении (A*, B*); в действительности было доказано более сильное утверждение о том, что в любом локально оптимальном решении в ближнем соседстве по крайней мере половина общего веса ребер в графе пересекает разбиение.

Утверждение (12.5) доказывает, что локальный оптимум представляет собой 2-аппроксимацию максимального разреза. Это наводит на мысль, что локальная оптимизация может быть хорошим алгоритмом для приближенной максимизации значения разреза. Тем не менее нужно рассмотреть еще одно обстоятельство: время выполнения. Как было показано в конце раздела 12.3, алгоритм переключения состояния только псевдополиномиальный, и вопрос о том, возможно ли найти локальный оптимум за полиномиальное время, остается открытым. Однако в данном случае мы можем добиться практически такого же результата, просто остановив алгоритм при отсутствии “достаточно значительных” улучшений.

Пусть (A, B) — разбиение с весом w(A, B). Для фиксированного є > 0 переключение одного узла будет называться значительным, если оно улучшает значение разреза минимум на , где n= |V|. Теперь рассмотрим версию алгоритма переключения состояния, которая принимает только значительные переключения и завершается при отсутствии таких переключений, даже если текущее разбиение не является локальным оптимумом. Утверждается, что эта версия алгоритма приведет почти к не худшей аппроксимации и выполняется за полиномиальное время. Прежде всего можно расширить предыдущее доказательство и продемонстрировать, что полученный разрез почти не хуже. Достаточно добавить к каждому неравенству, так как нам известно лишь об отсутствии значительных переключений.

(12.6) Пусть (A, B) — разбиение, для которого невозможно значительное переключение, а (A* B*) — глобально-оптимальное разбиение. В этом случае (2 + є) w(A, B) ≥ w(A*, B*).

Теперь обратимся ко времени выполнения.

(12.7) Версия алгоритма переключения состояния, принимающая только значительные переключения, завершается максимум после O(є^-1n log W) переключений (в предположении, что веса целочисленны, a W = ∑_ew_e.

Доказательство. Каждое переключение улучшает целевую функцию минимум на множитель (1 + є/n). Так как (1 + 1/x)^x ≥ 2 для любого x ≥ 1, мы видим, что (1 + є/n)ⁿ/є ≥ 2, а следовательно, целевая функция возрастает не менее чем вдвое каждые n/є переключений. Вес не может превысить W, а следовательно, он может удваиваться не более log W раз. ■