Итерационный алгоритм, использующий матрицу смежности

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

 В общем случае алгоритм состоит из двух этапов:

 1) начальное «разрезание» графа (например, механическое деление матрицы смежности на части) — это вспомогательный этап;

 2) основной этап, в ходе которого выполняется итерационное улучшение решения на основе парного или группового обмена вершин из различных частей.

 Несмотря на то, что итерационный алгоритм позволяет достичь оптимального результата, его недостатком является наличие большого числа громоздких процедур, связанных с перестановкой элементов.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *