2015-05-30
512
Компоновка: 1) разбиением. Суть в разбиении большой схемы, представленной на элементном уровне, на ряд подсхем, что соответствует различным модулям конструктивной реализации.
2) покрытием. Для данной задачи исходные данные представляются в виде модели графа. Вершинам соответствуют элементы схемы, ребрам – электрические связи.
Известные алгоритмы компоновки можно условно разбить на 4 групп: 1) алгоритмы, использующие методы целочисленного программирования. 2) последовательные алгоритмы.3)параллельные алгоритмы.4)комбинированные алгоритмы
Алгоритмы первой группы позволяют получить точное решение задачи, но фактически не реализуемы на ЭВМ. Большее распространение получили приближенные алгоритмы компоновки.
Последовательные алгоритмы компоновки. Выбирается пара элементов, имеющих наибольшее число связей и целиком помещаются в модуль. Далее к паре присоединяется элемент, имеющий наибольшее число связей с уже размещенными элементами в модуле. Когда модуль заполнен, оставшиеся элементы распределяются между остальными модулями. +: прост, легко реализуется на ЭВМ, высокое быстродействие при решении.
Параллельные. Исходная компоновка выполняется случайным образом, а затем выполняются перестановки элементов из модуля в модуль. Выбирается любая пара элементов и выполняется пробная перестановка.
