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

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

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

Пример записи фильма в формате DVCAM
звуковой формат Цель данной работы показать работу в условиях записи фильма в формате Dvcam, записи зистового звука на HD-рекордер. Были выбраны 2 рассказа А.П. Чехова: "Кот" и ...

Проектирование передатчика телевизионной системы на печатной плате
Телевизионный передатчик: совокупность специализированных технических средств, применяемых в процессе телевещания (кроме источника сигнала и его тракта, источника электропитания и энерго ...

Проектирование сооружений городской районной телефонной сети
Основными задачами, стоящими перед отраслью связи на городской телефонной сети (ГТС), являются улучшение характеристик качества обслуживания и предоставление новых видов услуг св ...