Страница: 3/10
Сформулируем алгоритм последовательной компоновки конструктивных элементов.
1) t:0
2) Xf = Xt = Ø; t=t+1; Θ=1; α=nmax,
Где t, Θ – порядковые номера формируемого куска и присоединяемой вершины; α – ограничение на число вершин в куске.
3) По матрице смежности исходного графа | αhp|NxN, где N – число вершин исходного графа (при большом значении N для сокращения объема оперативной памяти ЭВМ используем не саму матрицу смежности, а её кодовую реализацию), определяем локальные степени вершин 
.
4) Из множества нераспределенных вершин X выбираем вершину xj с ρ(xj) = 
. Переходим к п.6. Если таких вершин несколько, то переходим к п.5
5) Из подмножества вершин Xl с одинаковой локальной степенью выбирают вершину xj с максимальным числом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| = 
.
6) Запоминаем исходную вершину формируемого куска графа 
. Переходим к п.10
7) По матрице смежности 
строим множество Xs = 
и определяем относительные веса вершин 
:
.
8) Из множества XS выбираем вершину 
. Переходим к п.10. Если таких вершин несколько, то переходим к п.9.
9) Из подмножества вершин Xv с одинаковым относительным весом выбираем вершину xj с максимальной локальной степенью, т.е. 
.
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 значительно больше вершин в любой части разбиения.
Реферат опубликован: 31/03/2010