Информационные технологии проектирования электронных средств

- 71 - с меньшим значением индекса P , осуществляется переход в другой слой и про- цесс продолжается. На рис.40 показан путь для рассматриваемого примера. Он имеет длину 15 и один переход в ячейке (5,5). Заметим, что при использовании буферных списков для возможных пере- ходов можно увеличить цену одного перехода до n единиц. В этом случае могут быть построены пути, имеющие меньше переходов, но большую длину. Далее легко получить обобщение алгоритма, позволяющее находить соединения меж- ду заданными множествами ячеек. В алгоритме Хейса волна распространяется независимо в каждом из n слоев схемы. Это приводит к значительным затратам времени и памяти при ре- ализации алгоритма на ЭВМ. Расслоение до трассировки Так как этот этап идет после размещения элементов, то определяют сте- пень “взаимодействия” отдельных соединений или связывающих деревьев при условии их одновременного расположения на одной плоскости. Рис. 41 Рис. 42 Простейший способ – выделение преимущественных направлений, группирование соединений в соответствии с этими направлениями и разнесе- ние этих групп на отдельные слои (вертикальные и горизонтальные). Меру “взаимодействия” соединений можно задавать различным образом. Так при ор- тогональной прокладке соединений для каждого комплекса V i строится мини-