Итерационный алгоритм улучшения начального разрезания гиперграфа схемы

Итерационные алгоритмы имеют высокую вычислительную сложность. Наиболее простыми из них являются алгоритмы, использующие метод парных перестановок. Рассмотрим идею этого метода. Пусть множество вершин разбито на два непересекающихся подмножества и , т.е. имеется начальная компоновка схемы на две подсхемы с некоторым значением ЦФ . В соответствии с постановкой задачи разрезания перестановка вершин и целесообразна, если после этого значение ЦФ убывает. Для всех возможных обменов вершин с вершинами будем подсчитывать и определять .

Для определения будем подсчитывать количества ребер, которые приходят в разрез и уходят из него при включении в и в . Перестановка вершин и вызывает изменение состояния только тех ребер, которые инцидентны этим вершинам. Для ребер, инцидентных вершине возможны следующие состояния:

1. Останутся в разрезе между кусками и те ребра, которые содержат вершину или хотя бы по одной вершине и .

2. Будут удалены из разреза между кусками и те ребра, которые не содержат вершины и ни одной из вершин . Множество вершин , входящих в такое ребро должно удовлетворять условию:

3. Появятся в разрезе между кусками и те ребра, в которые не входили вершины из куска . Для подмножеств вершин таких ребер должно выполняться условие:

Аналогичные замечания справедливы и для ребер, инцидентных вершине .

На основании изложенного приращение:

где и - количество ребер, которые будут удалены из разреза при перестановке вершин и соответственно; и - количество ребер, которые появятся в разрезе при перестановке вершин и соответственно.

Основные пункты алгоритма итерационного улучшения парными перестановками вершин гиперграфа.

1. Для пары вершин и определяем инцидентные им ребра: .

2. Находим множество вершин, входящих в каждое ребро:

3. Подсчитываем показатели , , , .

4. Определяем приращение .

5. Повторяем пп.1-4 для всех возможных парных обменов.

6. Находим . Проверяем условие . Если оно выполняется, то переходим к п.7, иначе – к п.8 (на окончание алгоритма).

7. Осуществляем перестановку вершин и , переходим к п.1.

8. Конец работы алгоритма.

Оценка сверху вычислительной сложности для данного алгоритма равна .

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

Определим вершины, для парных обменов которых необходимо пересчитывать . Необходимо найти подмножества вершин, имеющие общие ребра с и , обозначим эти подмножества и .

Поскольку эти подмножества могут иметь общие вершины: . Вершины могут принадлежать как , так и . Разобьем на два подмножества: и . Таким образом, показатели будем пересчитывать для:

Доработаем алгоритм с учетом вышесказанного:

Первые 6 пунктов алгоритма останутся прежними. Приведем последующие пункты:

7. Осуществляем перестановку и .

8. Находим

9.

10. Переход к п.1, но в п.5 все возможные пары обменов будут:

11. Конец алгоритма.

Примечание: в п.6 переход на окончание алгоритма – к п.11.

Оценка сверху вычислительной сложности доработанного алгоритма равна .