Алгоритм, основанный на методе ветвей и границ

 Во многих случаях исходные данные задачи размещения задаются в виде расширенной матрицы цепей схемы РЭА, расположения вертикальных и горизонтальных каналов в монтажном пространстве с числами магистралей в них (магистраль представляет собой часть канала). В качестве критерия берется минимум числа внутрисхемных пересечений.

 Расширенная матрица цепей

C =

имеет n строк (по числу элементов) и в общем случае 2d х 2r столбцов, где d — число контактов верхней (нижней) части элемента; r — число магистралей вертикального канала для соединения от верхних и нижних контактов.

По матрице Сц рассчитывается вспомогательная матрица пересечений

P = kxk

где k — число цепей; рij — число пересечений между фрагментами цепей сiи cj расположенными в одном канале, причем фрагмент цепи сі расположен под фрагментом cj. Если фрагмент цепи сi не может быть расположен ниже сj,

то pij= .

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *