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

Отсюда непосредственно следует первое из соотношений (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

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

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

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

Подвеска оптического кабеля на опорах
В настоящее время на ВОЛП-ВЛ применяются следующие типы ОК: ОКГТ - оптический кабель, встроенный в грозозащитный трос; ОКСН - оптический кабель самонесущий; ОКНН - оптический ...

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

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