На этом шаге мы приведем несколько алгоритмов, используемых для оптимального разбиения графа.
Метод рекурсивного деления пополам
Для решения задачи оптимального разбиения графа можно рекурсивно применить метод бинарного деления, при котором на первой итерации граф разделяется на две равные части, далее на втором шаге каждая из полученных частей также разбивается на две части и т.д. В данном подходе для разбиения графа на k частей необходимо log2k уровней рекурсии и выполнение k-1 деления пополам. В случае, когда требуемое количество разбиений k не является степенью двойки, каждое деление пополам необходимо осуществлять в соответствующем соотношении.
Алгоритм Кернигана-Лина
В алгоритме Кернигана-Лина используется несколько иной подход для решения проблемы оптимального разбиения графа - при начале работы метода предполагается, что некоторое начальное разбиение графа уже существует, затем имеющееся приближение улучшается в течение некоторого количества итераций. Используемый способ улучшения в алгоритме Кернигана-Лина состоит в обмене вершинами между подмножествами имеющегося разбиения графа. Для формирования требуемого количества частей графа может быть использована рекурсивная процедура деления пополам.
Общая схема одной итерации алгоритма Кернигана-Лина может быть представлена следующим образом.
1. Формирование множества пар вершин для перестановки. Из вершин, которые еще не были переставлены на данной итерации, формируются все возможные пары (в парах должны присутствовать по одной вершине из каждой части имеющегося разбиения графа).
2. Построение новых вариантов разбиения графа. Каждая пара, подготовленная на шаге 1, поочередно используется для обмена вершин между частями имеющегося разбиения графа для получения множества новых вариантов деления.
3. Выбор лучшего варианта разбиения графа. Для сформированного на шаге 2 множества новых делений графа выбирается лучший вариант. Данный способ фиксируется как новое текущее разбиение графа, а соответствующая выбранному варианту пара вершин отмечается как использованная на текущей итерации алгоритма.
4. Проверка использования всех вершин. При наличии в графе вершин, еще неиспользованных при перестановках, выполнение итерации алгоритма снова продолжается с шага 1. Если же перебор вершин графа завершен, далее следует шаг 5.
5. Выбор наилучшего варианта разбиения графа. Среди всех разбиений графа, полученных на шаге 3 проведенных итераций, выбирается и фиксируется наилучший вариант разбиения графа.
Поясним дополнительно, что на шаге 2 итерации алгоритма перестановка вершин каждой очередной пары осуществляется для одного и того разбиения графа, выбранного до начала выполнения итерации или определенного на шаге 3. Общее количество выполняемых итераций, как правило, фиксируется заранее и является параметром алгоритма (за исключением случая остановки при отсутствии улучшения разбиения на очередной итерации).
Со следующего шага мы начнем рассматривать параллельные алгоритмы.
