Теория и практика параллельных вычислений
Алгоритм Кернигана – Лина
В алгоритме Кернигана – Лина (the Kernighan – Lin algorithm) используется несколько иной подход для решения проблемы оптимального разбиения графа – предполагается, что некоторое начальное разбиение графа уже существует, затем имеющееся приближение улучшается в течение некоторого количества итераций. Применяемый способ улучшения в алгоритме Кернигана – Лина состоит в обмене вершинами между подмножествами имеющегося разбиения графа (см. рис. 10.16). Для формирования требуемого количества частей графа может быть использована, как и ранее, рекурсивная процедура деления пополам.
Общая схема одной итерации алгоритма Кернигана – Лина может быть представлена следующим образом.
Алгоритм 10.3. Общая схема алгоритма Кернигана – Лина
- Формирование множества пар вершин для перестановки. Из вершин, которые еще не были переставлены на данной итерации, формируются все возможные пары (в парах должно присутствовать по одной вершине из каждой части имеющегося разбиения графа).
- Построение новых вариантов разбиения графа. Каждая пара, подготовленная на шаге 1, поочередно используется для обмена вершин между частями имеющегося разбиения графа для получения множества новых вариантов деления.
- Выбор лучшего варианта разбиения графа. Для сформированного на шаге 2 множества новых делений графа выбирается лучший вариант. Этот вариант далее фиксируется как новое текущее разбиение графа, а соответствующая выбранному варианту пара вершин отмечается как использованная на текущей итерации алгоритма.
- Проверка использования всех вершин. При наличии в графе вершин, еще не использованных при перестановках, выполнение итерации алгоритма снова продолжается с шага 1. Если же перебор вершин графа завершен, далее следует шаг 5.
- Выбор наилучшего варианта разбиения графа. Среди всех разбиений графа, полученных на шаге 3 проведенных итераций, выбирается (и фиксируется) наилучший вариант разбиения графа.
Поясним дополнительно, что на шаге 2 итерации алгоритма перестановка вершин каждой очередной пары осуществляется для одного и того же разбиения графа, выбранного до начала выполнения итерации или определенного на шаге 3. Общее количество выполняемых итераций, как правило, фиксируется заранее и является параметром алгоритма (за исключением случая остановки при отсутствии улучшения разбиения на очередной итерации).
Рис. 10.16. Пример перестановки двух вершин (выделены серым) в методе Кернигана – Лина
