Итерационный алгоритм улучшения начального разрезания гиперграфа схемыИтерационные алгоритмы имеют высокую вычислительную сложность. Наиболее простыми из них являются алгоритмы, использующие метод парных перестановок. Рассмотрим идею этого метода. Пусть множество вершин Для определения 1. Останутся в разрезе между кусками 2. Будут удалены из разреза между кусками 3. Появятся в разрезе между кусками Аналогичные замечания справедливы и для ребер, инцидентных вершине На основании изложенного приращение: где Основные пункты алгоритма итерационного улучшения парными перестановками вершин гиперграфа. 1. Для пары вершин 2. Находим множество вершин, входящих в каждое ребро: 3. Подсчитываем показатели 4. Определяем приращение 5. Повторяем пп.1-4 для всех возможных парных обменов. 6. Находим 7. Осуществляем перестановку вершин 8. Конец работы алгоритма. Оценка сверху вычислительной сложности для данного алгоритма равна Как уже отмечалось, перестановка вершин Определим вершины, для парных обменов которых необходимо пересчитывать Поскольку эти подмножества могут иметь общие вершины:
Доработаем алгоритм с учетом вышесказанного: Первые 6 пунктов алгоритма останутся прежними. Приведем последующие пункты: 7. Осуществляем перестановку 8. Находим 9. 10. Переход к п.1, но в п.5 все возможные пары обменов будут:
11. Конец алгоритма. Примечание: в п.6 переход на окончание алгоритма – к п.11. Оценка сверху вычислительной сложности доработанного алгоритма равна
|
разбито на два непересекающихся подмножества 
и 
, т.е. имеется начальная компоновка схемы на две подсхемы с некоторым значением ЦФ 
. В соответствии с постановкой задачи разрезания перестановка вершин 
и 
целесообразна, если после этого значение ЦФ убывает. Для всех возможных обменов вершин 
и определять 
.
и 
вызывает изменение состояния только тех ребер, которые инцидентны этим вершинам. Для ребер, инцидентных вершине 
и 
те ребра, которые содержат вершину 
и 
.
, входящих в такое ребро 
должно удовлетворять условию: 
и 
- количество ребер, которые будут удалены из разреза при перестановке вершин 
и 
- количество ребер, которые появятся в разрезе при перестановке вершин 
.
. Проверяем условие 
. Если оно выполняется, то переходим к п.7, иначе – к п.8 (на окончание алгоритма).
и 
, переходим к п.1.
.
и 
не изменятся у тех вершин, которые не имели общих ребер с переставленными. Значит, после каждой итерации можно пересчитывать показатель 
только для тех парных обменов, в которых хотя бы одна вершина имеет общие ребра хотя бы с одной из переставленных.
и 
, обозначим эти подмножества 
и 
.
. Вершины 
могут принадлежать как 
и 
. Таким образом, показатели 
.
