Трассировка печатной платы с использованием лучевого алгоритма

Трассировка с использованием другого эвристического алгоритма – лучевого – показана на рисунке 3. При использовании этого алгоритма между соединяемыми точками А (5, 3) и В (4, 8) проводится луч. Основное направление (0) выбирается из начальной точки вдоль большей стороны прямоугольника, диагональю которого является луч (АВ). При переходе к следующей точке монтажного пространства определяется направление трассы, минимально отличающейся от направления луча. При необходимости обхода препятствий, образованных занятыми позициями, учитываются указанные на диаграмме приоритеты (нумерация направлений), начиная с нулевого. После проведения соединения (или в случае неудачного соединения), направление меняется на противоположное (ВА). Соответственно меняется и приоритет направлений. Из полученных соединений выбирается оптимальное. На рисунке 3 штриховой линией отмечен оптимальный путь (его длина в два раза меньше первого), проложенный при проведении луча от В к А, т.е. в обратном направлении.

Обычно с помощью лучевого алгоритма удается провести до 80% трасс, а более сложные по конфигурации неразведенные трассы проводят с помощью волнового алгоритма или вручную.

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

Трасса выбирается таким образом, чтобы минимизировать совокупный показатель, характеризующий качество трассы по используемым критериям.

Рисунок 9 - Трассировка соединений лучевым алгоритмом

при наличии препятствий