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

Отсюда непосредственно следует первое из соотношений (4.39). Остальные соотношения могут быть проверены аналогично.

Использование (4.39) и (4.40) существенно сокращает трудоемкость вычислений характеристик D при расчете приращений ДL (x, y) на каждой итерации. Для времени поиска пары элементов с ДL (x, y)>0 можно предварительно упорядочить характеристики D (сортировка).

Расположим характеристики D элементов из узлов Ti и Tj следующим образом:

. (4.41)

Организуем процесс вычисления ДL (x, y) так, чтобы в первую очередь кандидатами для обмена были элементы, находящиеся в начале последовательностей x и y в (4.41), тогда если меньше, чем максимальное из ранее найденных значений ДL (x, y), то по (4.15) среди оставшихся элементов {xs: s>s*} и {yl: l>l*} нет пары с большим значением ДL (x, y), поэтому поиск может быть прекращен.

Таким образом, предварительная сортировка D позволяет сократить количество просмотров для вычисления ДL (x, y)max по сравнению с k2 просмотрами при обычном переборе.

После окончания процесса минимизации числа соединений между узлами Ti и Tj (малая итерация) аналогичная процедура может быть применена к другой паре узлов. Так как имеется г узлов, то в принципе возможно осуществить р=г (г-1)/2 малых итераций. Совокупность малых итераций составляет одну большую. После окончания большой итерации минимизацию числа межузловых соединений можно продолжить, начиная снова с первой пары узлов. Процесс заканчивается, когда либо обмены элементов между двумя любыми узлами не приводят к уменьшению целевой функции, либо было проведено р* больших итераций.

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

Идея первого метода состоит в следующем. Для упрощения предположим, что число компонуемых узлов г=2л. В качестве начального варианта используем какой-либо вариант разбиения п элементов на две группы А и В по n/2 элементов. Далее применяем основной алгоритм парных перестановок для узлов А и В. Полученные узлы снова разделяем на два и т.д. до получения узлов требуемого размера. Рисунок 7 иллюстрирует процесс разделения.

Рисунок 7 - Последовательное разделение

Вначале минимизируются связи между группами А и В, затем связи между группами A1 и A2 B1, и В3. Результат, полученный для одного уровня разделения, не ухудшается при последующих разделениях. Данный метод имеет наибольшую эффективность для схем, содержащих сильно связанные группы элементов, причем размеры этих групп приблизительно одинаковы.

Другой метод состоит в последовательном выделении (рисунок 6) из исходного множества n элементов групп по k элементов с использованием итерационного процесса обменов элементов, входящих в выделенную группу Тi элементами из множества

(4.42)

Рисунок 8 - Последовательное выделение

Рассмотрим рисунок 8. Пусть получено разбиение исходного множества элементов на две группы Т1 и T’1=E\T1. Указанное разбиение может быть, например, произведено с помощью алгоритма последовательной компоновки. Обычным образом производится минимизация числа соединений между узлом Ti и множеством элементов Т’1. Далее из множества T’1 выделяется следующая группа T2 из k элементов и осуществляется аналогичная процедура минимизации для множеств T’2 и T’2=T’1\T2 и т.д. Процесс продолжается до тех пор, пока не будут выделены г узлов.

Перейти на страницу: 1 2 3 4 5 6

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

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

Проект оконечной ОС на базе системы DX200
Современное состояние и перспективные планы развития Единой Сети Электросвязи (ЕСЭ) Российской Федерации характеризуются широким внедрением цифровых технологий и оборудования цифровых си ...

Организация системы контроля доступа и видеонаблюдения в учреждении образования
Система контроля доступа - это совокупность программно-технических средств и чётко сформированной системы управления движением персонала и временем его нахождения на объекте. Основными ...

Основные разделы

Все права защищены! (с)2025 - www.generallytech.ru