Существующие алгоритмы прокладки трасс условно можно разделить на следующие группы:

1)      Волновые алгоритмы, основанные на идеях Ли. Они получили широкое распространение, так как позволяют легко учитывать конструкторские и технологические ограничения. Они всегда гарантируют построение трассы, если путь для нее существует.

2)      Канальные алгоритмы, они обладают большим быстродействием, чем волновые. Недостатком является большое количество переходов со слоя на слой, отсутствие 100% гарантии проведения ряда трасс, большим количеством параллельно идущих проводников. Большее применение они получили при трассировке топологии кристаллов микросхем.

3)      Алгоритмы эвристического типа (лучевые). В них каждое соединение проводится по кратчайшему пути, обходя встречающиеся на пути препятствия. Эти алгоритмы являются наиболее быстродействующими, но трассы в них не оптимизируются.

4)      Генетические алгоритмы. Это поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики.

3. Бессеточные трассировщики.

В современных САПР чаще всего используются так называемые бессеточные (Shape-Based) трассировщики. Например, в программе SPECCTRA согласно этой технологии все объекты моделируются в виде совокупности геометрических фигур (прямоугольник, круг, дуга, трасса, полигон), которым приписаны определенные электрические и физические характеристики и правила проектирования. В отличие от привязанных к сеткам технологиям (Grid-Based) каждый объект моделируется геометрически точно, за счет чего достигается более плотный монтаж с меньшим числом слоев. За счет точного моделирования геометрических форм объектов бессеточными технологиями образуется дополнительное свободное пространство, которое можно использовать для более тесного расположения компонентов и проводников. Характерная особенность бессеточной технологии – меньшие затраты памяти. Если для бессеточных технологий объем памяти не зависит от шага сетки, то при использовании сеточных технологий при уменьшении шага сетки необходимый объем памяти возрастает в квадратичной зависимости. В бессеточных технологиях память тратится только на описание геометрических форм объектов, а не на запоминание координат помеченных узлов сетки. В табл.1 приведен пример расчета количества элементарных геометрических объектов при использовании обеих технологий.

Трассировщик SPECCTRA использует адаптивные алгоритмы, реализуемые за несколько проходов трассировки. На первом проходе реализуется соединение абсолютно всех проводников, не обращая внимания на возможные конфликты, заключающиеся в пересечении проводников и нарушениях зазоров. На каждом последующем проходе трассировщик пытается уменьшить количество конфликтов, разрывая и прокладывая вновь связи (метод Rip-up-and-Retry) и проталкивая проводники, раздвигая соседние (метод Push-and-shove). Информация о конфликтах на текущем проходе используется для «обучения» - изменения весовых коэффициентов (штрафов), так, чтобы путем изменения стратегии уменьшить количество конфликтов на следующем проходе.