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

- 68 - считается ячейка, в которой проходит трасса некоторого соединения, располо- жен переход, контактная площадка и т.д. При распространении волны свобод- ным ячейкам ДРП i ( i = 1,2,…, n ) присваивается индекс длины P i и индекс коли- чества переходов ν i При расчете индекса длины P i переходы учитываются пу- тем добавления k единиц длины на каждый переход. Индекс ν i используется в процедуре проведения пути для минимизации числа переходов. Рис. 38 В процедуре распространения волны для каждого слоя i используются следующие массивы: ДРП i − состояние ячеек i -го слоя, L i – ячейки текущего фронта волны i -м слое, M i – ячейки слоя i , соседние к ячейкам из L i . При обра- зовании очередного фронта для i -го слоя наряду с ячейками из M i используются те свободные ячейки i -го слоя, в которых возможен переход из других слоев и которые при этом имеют тот же индекс P . Поскольку алгоритм Хейса для многослойных схем требует существен- ных затрат времени и памяти, остановимся более подробно на его реализации для двухслойных схем.