Страница: 3/8
10)
.
11) Если 
>m , то переходим к п.13.
12) Рассмотренные вершины включаем в формируемый кусок Xf = Xt .
13) Θ = Θ + 1.
14) Если Θ> α, то переходим к п.15, а противном случае – к п.7.
15) Если |Xf|<nmin, где nmin – минимально допустимое число вершин в куске, то переходим к п.21.
16) Выбираем окончательный вариант сформированного куска графа:
Xt = Xf ; X = X Xt ; α = nmax .
17) Если |X|> nmax , то переходим к п.20.
18) Если |X|< nmin , то переходим к п.21.
19) Определяем число внешних связей последнего куска графа:
,
где F – множество индексов вершин, входящих в X. Если 
, то переходим к п.21, в противном случае – к п.24.
20) Если t<k – 1 , где k - число кусков разрезания графа, то переходим к п.2, в противном случае – к п.23.
21) Предыдущий цикл «разрезания» считаем недействительным. Если t>1, т.е. имеется как минимум один ранее сформированный кусок, то переходим к п.22. в противном случае – к п.23.
22) Ищем другой допустимый вариант формирования предыдущего куска с меньшим числом вершин: t = t – 1; 
.
Переходим к п.7.
23) Задача при заданных ограничениях не имеет решения.
24) Конец работы алгоритма.
Рассмотренный алгоритм прост, легко реализуется на ЭВМ и позволяет получить решение задачи компоновки. Также среди достоинств данной группы алгоритмов выступает высокое быстродействие их при решении задач компоновки.
Основным недостатком последовательного алгоритма является неспособность находить глобальный минимум количества внешних связей (не анализируются возможные ситуации). Наибольшая эффективность метода последовательного разбиения графа имеет место, когда число вершин графа G значительно больше вершин в любой части разбиения.
Итерационные алгоритмы компоновки
Сущность данной группы алгоритмов заключается в выборе некоторого начального «разрезания» исходного графа на куски (вручную или с помощью последовательного метода компоновки) и последующего его улучшения с помощью итерационного парного или группового обмена вершин из различных кусков. При этом для каждой итерации осуществляется перестановка тех вершин, которая обеспечивает максимальное уменьшение числа связей между кусками графа или максимальное улучшение другого выбранного показателя качества с учетом используемых ограничений (например, на максимальное число внешних ребер любого отдельно взятого куска).
Найдем выражение для подсчета приращения числа ребер, соединяющих куски GA(XA,UA) и GB(XB,UB), при парном обмене вершин 
и 
.
Очевидно, что парная перестановка вершин xg и xh приведет к изменению числа только тех связывающих куски GA(XA,UA) и GB(XB,UB) ребер, которые инцидентны этим вершинам. Общее число соединительных ребер между GA(XA,UA) и GB(XB,UB) , инцидентных xg и xh, до перестановки вершин определяют по матрице смежности следующим образом:
,
где I и J – множества индексов вершин, принадлежащих XB и XA . В этом выражении первые два слагаемых определяют число ребер, соединяющих вершины xg с GB(XB,UB) и xh с GA(XA,UA), а наличие третьего члена обусловлено тем, что связь двух слагаемых учитывалась дважды.
После перестановки вершин xg и xh получим:
.
Третий член выражения указывает на сохранение связи (xg, xh) после перестановки вершин. Следовательно, в результате перестановки xg и xh приращение числа ребер, соединяющих GA(XA,UA) и GB(XB,UB),
.
Перестановка вершин целесообразна, если 
, причем эффективность её тем выше, чем больше 
.
Если исходный граф G(X,U) задан матрицей смежности 
, то «разрезание» G(X,U) на k кусков эквивалентно разбиению матрицы A на k x k подматриц:
Реферат опубликован: 16/12/2006