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

- 77 - Таким образом, получаем дискретное рабочее поле (ДРП). В нем опре- деляется множество занятых ячеек, соответствующее зонам, запрещенным для проведения соединений. Это выводы элементов, технологические области, ра- нее проведенные соединения и т.д. Основу алгоритма Ли составляет процедура построения оптимального в заданном смысле пути между двумя ячейками ДРП. Процедура состоит их двух этапов: поиска пути и проведения пути (рис.45). Этап 1 (поиск пути). Из ячейки-источника А моделируют распро- странение числовой волны до тех пор, пока ее фронт не достигнет ячейки– приемника В (путь найден), либо наступает момент, когда в очередной фронт нельзя включить ни одну новую незанятую ячейку ДРП (пути не существует). В процессе распространения волны ячейкам ДРП присваивается весовой коэффи- циент, связанный с критерием оптимальности. Этап 2 (проведение пути). Для этого из ячейки-приемника следует дви- гаться в направлении, противоположном направлению распространения волны, от ячейки с большим весом к ячейке с меньшим весом, пока не достигнем ячей- ки-источника. Для сокращения числа поворотов трассы может быть использо- вано следующее правило приоритета: при переходе от ячейки Рис. 45 Рис. 46 k -го фронта к ячейке ( k –1)-го фронта сохранять, если это возможно, направле- ние, определяемое переходом от ячейки ( k +1)-го фронта к ячейке k -го фронта.