Страница: 2/8
Последовательные алгоритмы компоновки
В последовательных алгоритмах компоновки «разрезание» исходного графа G(X,U) на куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) сводится к следующему. В графе G(X,U) находят вершину xi 
X с минимальной локальной степенью 
.
Если таких вершин несколько, то предпочтение отдают вершине с максимальным числом кратных ребер. Из множества вершин, смежных с вершинами формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает минимальное приращение связей куска с еще нераспределенными вершинами. Данную вершину xi X X1 включают в G1(X1,U1), если не происходит нарушения ограничения по числу внешних связей куска, т.е.
,
где αjε – элемент матрицы смежности исходно графа G(X,U); δ(xg) – относительный вес вершины xg, , равный приращению числа внешних ребер куска G1(X1,U1) при включении вершины xg во множество X1; E – множество индексов вершин, включенных в формируемый кусок графа на предыдущих шагах алгоритма; m – максимально допустимое число внешних связей отдельно взятого куска со всеми оставшимися.
Указанный процесс продолжается до тех пор, пока множество X1 не будет содержать n элементов либо присоединение очередной нераспределенной вершины xj к куску G1(X1,U1) не приведет к нарушению ограничения по числу внешних соединений куска, равному
Следует отметить, что величина не является монотонной функцией |X1|, поэтому, для того чтобы убедится в невозможности дальнейшего формирования куска вследствие нарушения последнего ограничения, необходимо проверить его невыполнимость на последующих шагах увеличения множества X1 вплоть до n. В качестве окончательного варианта выбирают кусок G10(X10,U10), содержащий максимально возможное число вершин графа G(X,U), для которого выполняются ограничения на число внешних связей и входящих в него вершин (nmin-nmax).
После преобразования куска G10(X10,U10) процесс повторяют для формирования второго, третьего и т.д. кусков исходного графа с той лишь разницей, что рассмотрению подлежат вершины, не вошедшие в предыдущие куски.
Сформулируем алгоритм последовательной компоновки конструктивных элементов.
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 с максимальной локальной степенью, т.е. 
.
Реферат опубликован: 16/12/2006