Разбиение графа схемы на куски

Размещено на http://www.allbest.ru/

Лекция

Последовательный алгоритм компоновки

Разбиение графа на куски с использованием матрицы цепей

матрица цепь подсхема разбиение

Рассмотрим алгоритм разбиения схем на подсхемы с использованием матрицы цепей. Критерием разбиения является минимум числа внешних соединений между подсхемами. Исходной информацией для реализации алгоритма являются матрица цепей Т и список запрещенных элементов. Оптимальному разбиению графа схемы соответствует разбиение матрицы Т на подматрицы Т₁,Т₂,…,Т_l такое, что

Т=Т_i (6.1)

??(Т_i?Т_j)=К>min, i, j=1,n (6.2)

Вспомним, что представляет собой матрица цепей. Это матрица T=||t_ij||_n*k1, строки которой соответствуют элементам, а столбцы выводам элемента, причём k₁ = max k_i , i=1,n.

Элемент матрицы t_ij представляет номер цепи, инцидентной j-му выводу i-го элемента, т.е. t₂₃ - номер цепи, связанной с выводом c₃ элемента e₂.

Для подсчета числа связей между кусками графа и числа контактов разъемов каждого узла введем вспомогательную матрицу S

S=||S_ij||_l*m, (6.3)

где

l - число кусков,

m - число электрических цепей в схеме.

S_ij если в куске G_iG имеется вершина, инцидентная j-ой цепи;

в противном случае

Матрицу S удобно строить непосредственно по матрице цепей T, т.к. построение S по графу схемы требует значительных затрат ручного труда.

Алгоритм определения матрицы S по матрице Т

Из матрицы Т выбираем любой элемент t_ij ? 0. Переход к шагу 2.

В матрице S на пересечении строки, номер которой равен номеру куска, инцидентного i-ой вершине, и столбца с номером цепи t_ij проставляем единицу. Переход к шагу 3.

Выбираем в матрице Т элемент t_pq ? 0. Считаем, что p=i, q=j, переходим к шагу 2. Если в матрице Т просмотрены все элементы, то конец работы алгоритма.

Пример.

Пусть задана матрица цепей Т:

произвольного фрагмента схемы устройства, приведенного на рис. 6.1, которую необходимо разбить на три куска. Выполним случайное разбиение схемы на три куска

G₁=(E₁,U₁), G₂=(E₂,U₂), G3=(E₃, U₃), где

E₁=e₁,e₂,e₃,e₄, E₂=e₅,e₆,e₇,e₈, E₃=e₉,e₁₀,e₁₁,e₁₂,e₁₃,

Следуя алгоритму определения матрицы S по матрице Т, сформировать матрицу S для данного разбиения. Результат приведен на следующей странице.

Рис. 1

Определение числа связей К между кусками, полученными при таком разбиении, основано на том, что цепь, инцидентную n кускам, всегда можно провести так, чтобы она образовала не более чем (n-1) внешнюю связь (соединяющее ребро).

Рассматривая матрицу S, можно, заметить, что число; единиц в любом из столбцов матрицы равно числу кусков Gj, инцидентных цепи, номер которой совпадает с номером столбца матрицы. Поэтому для нахождения К необходимо найти сумму элементов каждого столбца, уменьшенную на единицу, и полученные результаты просуммировать.

(6.4)

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

После разбиения схемы произвольным образом на три куска по матрице S видно, что К=20, а число контактов соединителя каждого куска соответственно равно 11, 20 и 9.

Основная идея алгоритма разбиения

Сначала число элементов в каждой подсхеме равно нулю. Далее, если имеются, распределяем по кускам запрещенные элементы. Если таких элементов нет, то произвольно предварительно распределяем элементы по кускам.

Последовательно выбираем строки, соответствующие элементу e_i из матрицы Т, и определяем тот кусок G_i, при помещении в который элемент e_iЕ дает наименьшее приращение количества связей между кусками. Процесс повторяется, пока все элементы не будут распределены.

Рассмотрим более подробно процесс определения приращения числа связей K_jⁱ при помещении элемента e_i в кусок G_j.

Вначале рассмотрим условие появления приращения по цепи:

По матрице Т для элемента e_i построим вспомогательную строку S₀ⁱ =||sⁱ₀||_m, где

sⁱ₀= если элемент е_i подключен к цепи с номером

в противном случае

Тогда первым условием появления приращения по цепи q является условие,

sⁱ_0q=1 (6.5)

то есть элемент e_i связан с цепью q.

Вторым условием появления приращения по цепи q является условие, что до внесения элемента e_i в кусок j ни один элемент этого куска не имел связь с цепью q, то есть s_jq=0 или s_jq=1 (6.6)

Третьим условием является наличие связей цепи q с элементами других кусков, исключая кусок G_j, то есть

(6.7)

Тогда наличие приращения связи по цепи q определится по формуле (результат конъюнкции равен 1, если все элементы операции равны 1):

(6.8)

При k_qⁱ=1 приращение имеется, при k_qⁱ=0 - нет, а по всем m цепям:

(6.9)

Тогда алгоритм будет следующим:

В матрице Т выбираем строку e_i.

Строим строку sⁱ₀.

Определяем приращения элемента e_i. K_jⁱ, j=1,p при помещении его в куски 1,2,…,p;

Выбираем

(6.10)

Строку S_j* матрицы S модифицируем путем поразрядной дизъюнкции со строкой S_i⁰.

Если число элементов в куске G_j равно заданному, то кусок G_j сформирован, если меньше, то берем очередной элемент и повторяем сначала.

Пример применения алгоритма

Пусть задана матрица цепей Т:

Исходной информацией является граф схемы G=(E,U), |E|=13, Е={e₁,e₂,…,e₁₃}. T - его матрица цепей. Граф схемы необходимо разбить на три куска G₁=(E₁,U₁), G₂=(E₂,U₂), G3=(E₃, U₃), где G_i=G, (i=1,3) с минимальным числом соединительных ребер между кусками. Число вершин в каждом куске должно быть соответственно равно |E₁|=4, |E₂|=4, |E₃|=5.

Пусть после нескольких шагов алгоритма найдено, что элементы e₄,e₁,e₇E₁; e₂,e₅E₂, e₃,e₆E₃. Вспомогательная матрица S в этом случае примет следующий вид (31 столбец, т.к. max № цепи в матрице Т равен 31):

Согласно описанному алгоритму разбиения, из матрицы Т выбираем строку e₈ (т.к. элементы e₁ - e₇ уже вошли в разбиение), соответствующую еще не рассмотренному элементу e₈, и строим для нее строку

Далее находим K₁⁸, K₂⁸, K₃⁸ - приращения числа связей при помещении элемента e₈ в куски G₁, G₂, G₃. Для этого сначала определяем поэлементную дизъюнкцию строк (формулы (6.7),(6.8)):

Затем определяем инверсии строк s₁, s₂, s₃ матрицы S (см. (6.6.):

Для вычисления K_jⁱ согласно (6.8) находим поэлементную конъюнкцию строк (первый сомножитель берется согласно (6.7)):

Суммируя число единиц в каждой из полученных строк (согласно (6.9)), имеем: K₁⁸=0, K₂⁸=5, K₃⁸=5.

Так как K₁⁸=0, то элемент e₈ помещается в кусок G₁. При этом число связей между кусками не изменится.

Далее строка s₁ матрицы S модифицируется поэлементной дизъюнкцией со строкой s₀⁸. Так как при внесении e₈ в G₁ число элементов равно заданному, то кусок G₁ сформирован. Осталось распределить e₉, e₁₀, e₁₁, e₁₂, e₁₃ между кусками G₂ и G₃.

Из матрицы Т выбираем строку, соответствующую элементу e₉ и для нее повторяем все операции, произведенные со строкой, соответствующей элементу e₈. Аналогично поступаем с оставшимися элементами e₁₀-e₁₃, пока не будут сформированы куски G₂ и G₃.

В рассматриваемом примере в результате работы алгоритма сформированы следующие куски:

G₁= (E₁,U₁), U₁=e₁,e₄,e₇,e₈ (6.11)

G₂= (E₂,U₂), U₁=e₂,e₅,e₉,e₁₀

G₃= (E₃,U₃), U₁=e₃,e₆,e₁₁,e₁₂,e₁₃

Число внешних связей уменьшилось с К=20 (для произвольного разбиения) до К=8. Окончательный вариант компоновки графа схемы с рис. 6.1. приведен на рис. 6.2. Алгоритм наиболее эффективен, когда схема содержит значительное число разветвленных цепей и элементов.

Рис. 1

Рис.2

Размещено на Allbest.ru