Алгоритмы решения задач трассировки

Задача трассировки при целевой функции в виде минимума суммарной длины всех соединений может быть сформулирована как задача построения для графа G(V,R) покрывающего дерева минимальной длины, и сведена в дальнейшем к проблеме соединения между собой пар дискрет. Большое значение при этом имеет определение очередности проведения трасс. Первыми обычно соединяются контакты, расположенные на кратчайшем расстоянии друг от друга или имеющие минимальныиприоритетныи номер (под приоритетным номером подразумевается количество контактов, подлежащих соединению, внутри прямоугольника, построенного на дискретах, через которые должна быть проведена трасса). Например, контакты, показанные на рис. 5.17, будут трассироваться в следующей последовательности: 1 — (С-С), 2 — (В-В), 3 — (А-А).

Трассировку соединений в большинстве случаев осуществляют с помощью эвристических алгоритмов и алгоритмов, основанных на методе динамического программирования. Общим для этих алгоритмов является разбиение монтажного поля на ячейки — дискреты, размеры которых выбирают исходя из ширины соединительных проводников и расстояния между ними.

Лучевые алгоритмы

 Эти алгоритмы представляют собой упрощенные модификации волнового алгоритма. Они используются для печатных плат с невысокой плотностью монтажа или для трассировки значительной части соединений (до 70 — 80 %) с последующей доводкой другими способами. Достоинствами лучевых алгоритмов являются простота, быстродействие, малый объем занимаемой памяти. Основной их недостаток — не гарантируется нахождение трассы, которая в действительности существует.

 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *