Алгоритмы локального поиска при разбиении графов
Перейдем к соседским отношениям, порождающим соседские окружения большего размера по сравнению с правилом одного переключения и соответственно пытающимся сократить распространенность локальных оптимумов.
Очевидно, если (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.
Более того, эвристика К-Л на практике показала отличные результаты несмотря на то, что формальный анализ ее свойств в значительной степени остается открытой проблемой.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу