Итерационные алгоритмы улучшения компоновки

При обмене местами элементов ех и еу изменяется число выводов лишь на узлах 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, а внешних соединений внутренними.

Читайте также

Разработка компьютерной сети по технологии ArcNet с подключением к Internet
Организация компьютерных сетей. Назначение: Создание компьютерных сетей вызвано практической потребностью пользователей удаленных друг от друга компьютеров в одной и той же информ ...

Разработка микропроцессорного контроллера для контроля ритма дыхания больного
В последнее время микропроцессорные средства вычислительной технике стало широко применяться в приборах бытовой техники, различных контрольно-измерительных устройствах, системах управлен ...

Организация связи по оптическому кабелю магистрали Коченево-Мамонтово
Телекоммуникации являются основой развития общества. Постоянно растущий спрос, как на обычные телефонные, так и на новые виды услуг связи, включая услуги Интернет, предъявляет новые тре ...