Математический аппарат для конструкторского проектирования РЭС

курсовая работа

4.3 Трассировка печатного монтажа. Волновой алгоритм Ли

Многие методы трассировки печатных соединений основаны на идеях волнового алгоритма, предложенного Ли. Последний представляет собой развитие алгоритмов построения кратчайших путей в сети и позволяет находить маршруты соединений, оптимальные по ряду параметров.

Основу всех модификаций алгоритма Ли составляет процедура построения оптимального в заданном смысле пути между двумя известными ячейками ДРП. Процедура состоит из двух этапов: поиска пути и проведения пути.

На первом этапе из одной из заданных ячеек ДРП - источника моделируется распространение числовой волны до тех пор, пока её фронт не достигнет второй отмеченной ячейки ДРП. В первом случае искомый путь существует, во втором - нет.

На втором этапе алгоритма осуществляется проведение пути. Для этого следует, начиная от ячейки - цели двигаться в направлении, противоположном направлению распространения волны, переходя последовательно от ячейки с большим весом к соседней ячейке с меньшим весом до тех пор, пока не будет достигнута ячейка - источник. Ячейки ДРП, выделенные в ходе указанного процесса, и определяют искомую оптимальную трассу.

Делись добром ;)