Волновой алгоритм трассировки печатных проводников (алгоритм Ли)

Основные положения волнового алгоритма

Задача: для двух эквипотенциальных выводов на ПП требуется найти оптимальный путь прокладки печатного проводника.

КП разбивается на ячейки размеры, равные шагу сетки. Множество всех ячеек называется дискретным рабочим полем (ДРП). Каждую ячейку будем описывать парой координат (х, у), где х – номер столбца, а у – номер строки ДРП, в которой расположена ячейка.

Каждая ячейка может быть свободной или занятой. Занятые ячейки соответствуют выводам элементов, технологическим областям, ранее построенным проводникам и т.д. В процессе проведения очередного соединения свободным ячейкам приписывается рассчитанные веса и они становятся помеченными. После окончания проведения соединения те ячейки, по которым прошло соединение, причисляются к занятым.

Алгоритм Ли является развитием алгоритмов построения кратчайших путей в сети. Основу его составляют два этапа:

· поиск пути;

· проведение пути.

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

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