Алгоритмы локального поиска при разбиении графов

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

Возможно, самым естественным обобщением является соседское окружение с k-переключением для k ≥ 1: разбиения (A, B) и (A’, B’) называются соседними по правилу k-переключения, если (A’, B’) можно получить из (A, B) перемещением не более k узлов с одной стороны разбиения на другую.

Очевидно, если (A, B) и (A’, B’) являются соседями по правилу k-переключения, то они также являются соседями по правилу k’-переключения для всех k’ > k. Следовательно, если разбиение (A, B) является локальным оптимумом по правилу k’-переключения, то оно также является локальным оптимумом по правилу k-переключения для всех k < k’.

Но сокращение множества локальных оптимумов посредством повышения величины k обходится дорого: для просмотра множества соседей (A, B) по правилу k-переключения необходимо рассмотреть все Θ(nk) способов перемещения до k узлов на другую сторону разбиения. Затраты времени становятся неприемлемыми даже при небольших значениях k.

Керниган и Лин (1970) предложили альтернативный способ генерирования соседних решений; он обладает существенно большей вычислительной эффективностью, но все при этом позволяет выполнять крупномасштабные преобразования решений за один шаг. Их метод, который мы будем называть эвристикой К-Л, определяет соседей разбиения (A, B) по следующей n-фазной процедуре.

  • В фазе 1 выбирается один узел для переключения — так, чтобы значение полученного решения было как можно больше. Переключение выполняется даже в том случае, если значение решения убывает относительно w(A, B). Узел, изменивший состояние, помечается, а полученное решение обозначается (A1, B1).
  • В начале фазы k для k > 1 мы имеем разбиение (Ak–1, Bk–1), и k – 1 узлов помечены. Один непомеченный узел выбирается для переключения таким образом, что значение полученного решения является максимальным среди всех возможных. (И снова это происходит даже в том случае, если в результате значение решения уменьшится.) Переключенный узел помечается, а полученное решение обозначается (Ak, Bk).
  • После n фаз каждый узел окажется помеченным; это указывает на то, что он переключался ровно один раз. Соответственно последнее разбиение (An, Bn) в действительности является зеркальным отображением исходного разбиения (A, B): An = B и Bn = A.

Наконец, эвристика К-Л определяет n – 1 разбиений (A1, B1), …, (An–1, Bn–1) как соседей (A, B). Следовательно, (A, B) является локальным оптимумом по эвристике К-Л в том, и только в том случае, если w(A, B) ≥ w(Ai, Bi) для 1 ≤ i n

Итак, мы видим, что эвристика К-Л определяет очень длинную серию переключений, даже если ситуация на первый взгляд ухудшается, в надежде на то, что некоторое разбиение (Ai, Bi), сгенерированное по пути, окажется лучше (A, B).

Но даже при том, что она генерирует соседей, очень отличных от (A, B), выполняется только n переключений и на каждое тратится время всего O(n). С вычислительной точки зрения это намного разумнее правила k-переключения для больших значений k.

Более того, эвристика К-Л на практике показала отличные результаты несмотря на то, что формальный анализ ее свойств в значительной степени остается открытой проблемой.

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)