При обмене местами элементов ех и еу изменяется число выводов лишь на узлах Ti и Tj.
Вычислим приращение в числе выводов на узле Ti:
(4.35)
где vi, - и v'i - соответственно число выводов на узле до и после обмена. Заметим, что приращение числа выводов Дvi(x, у) равно приращению числа соединений между элементами узла Ti и элементами, не входящими в узел Ti. Поэтому формула для расчета Дvi(x, у) может быть непосредственно получена из (4.35) при замене узла Tj на множество элементов :
(4.36)
где
(4.37)
. (4.38)
Аналогичная формула имеет место для приращений числа выводов на узле Tj. Для ее получения необходимо лишь заменить везде в (4.36), (4.37), (4.38) символ Ii на Ij обозначающий множество элементов, не входящих в узел Tj: I;=E\Tj, символ х на у, а символ у на х.
Заметим, что для многоконцевых соединений равенство, аналогичное (4.16), уже не выполняется.
Далее рассмотрим алгоритм минимизации числа межузловых соединений.
Пусть известен некоторый вариант разбиения схемы на г узлов. Можно считать, что в каждом узле содержится ровно k элементов, причем n=kг. В случае, когда в каком-либо узле число элементов kr меньше k, всегда можно дополнительно ввести nд=k-kr фиктивных элементов, не связанных с другими элементами схемы: rsj=0, s=n+1,…, n + nд, j=1, 2,…, n + nд.
Рассмотрим два узла Ti, и Tj, (i, j=1, 2 г). В соответствии с (4.15) приращение числа межузловых соединений при обмене местами элементов еxTi, и eyTj будет равно ДL (x, y)=Dx+Dy-2rxv, где характеристики Dx и Dv рассчитываются по матрице соединений R.
Опишем процесс выбора пары элементов ех и ev для обмена. Сначала определяются характеристики Dz, для всех элементов еz, принадлежащих Ti, или Tj. Число этих характеристик равно 2k.
Далее находится пара элементов Тi и Tj, для которой (4.15) принимает максимальное значение. Если ДL (x, y)>0, то производится обмен. В результате образуются узлы Т’i и Т’j.
Зафиксировав положение элементов и соответственно в узлах T'j и T'i, выполняем аналогичный расчет для элементов из множеств и и определяем новую пару элементов для обмена и . Процесс обменов продолжается до тех пор, пока на очередном шаге s+1 среди элементов не найдется ни одной пары, для которой ДL (x, у) > 0. Узлы Tsi и Tsj отвечают результату минимизации числа межузловых соединений между исходными узлами Ti и Tj.
Заметим, что при обмене элементов не все из рассчитанных на предыдущем шаге характеристик D изменяются. Имеют место следующие соотношения:
(4.39)
(4.40)
Справедливость (4.39) может быть легко проверена. Действительно, внутренних соединений элемента ех в результате обмена становятся внешними по отношению к узлу Ti, а внешних соединений внутренними.
Читайте также
Проектирование релейной защиты и автоматики
В электрической системе имеются следующие источники: ТЭЦ-1, ТЭЦ-2,
ТЭЦ-3, ТЭЦ-4, ТЭЦ-5, ГРЭС, СарГЭС и БАЭС. ТЭЦ-1, ГРЭС допускается отдельно не
учитывать, так как их мощность по сравнению с ...
Разработка микропроцессорного контроллера для контроля ритма дыхания больного
В последнее время микропроцессорные средства
вычислительной технике стало широко применяться в приборах бытовой техники,
различных контрольно-измерительных устройствах, системах управлен ...
Программно-аппаратный комплекс, позволяющий проводить эксперименты по одновременному управлению несколькими мобильными объектами
В настоящее время в области искусственного интеллекта (ИИ) происходят
заметные преобразования. Источниками этих преобразований служат распределенный
искусственный интеллект (РИИ), центра ...