Для печатного монтажа и пленочных соединений в ИС, БИС, СБИС недопустимо пересечение трасс в одном слое и необходимо строить проводники не только типа «вывод — вывод», но и соединения типа «вывод — проводник» и «проводник — проводник».
Задача соединения множества вершин одной цепью может быть решена введением промежуточных вершин с целью формирования более короткого дерева соединений и образования соединений типа «проводник — проводник» и «вывод— проводник». Эта задача называется задачей Штейнера (а деревья — штейнеровскими деревьями) и формулируется так: для заданного множества-вершин, фиксированных на плоскости, требуется найти такую систему прямолинейных отрезков, чтобы две любые из данных вершин были связаны системой отрезков, а общая длина цепи была минимальной.
В общем виде задача трассировки печатных и пленочных соединений сводится к построению бесперекрестного минимального леса и отысканию кратчайшего пути между его вершинами. На коммутационной поверхности заданы координаты , элементов множества размещенных конструктивных модулей ={, , ...,„}. Выводы этих модулей образуют некоторое множество из связанных подмножеств ={, ,... , }, причем каждое подмножество объединяет электрически связанные выводы. Кроме того, заданы расположение групп контактных площадок и переходных отверстий на плате, а также ряд технологических требований (ширина проводников, зазор между ними, координаты и размеры контактных площадок, число слоев, способы перехода со слоя на слой и др.).
Требуется соединить выводы конструктивных модулей внутри каждого подмножества так, чтобы полученные соединения отвечали выбранному критерию. Обычно минимизируется длина проводников в каждой цепи.
Все коммутационное (КП) покрывается масштабной сеткой. Каждая клетка сетки называется дискретом, которые выбирают исходя из технологических ограничений на ширину проводников и на расстояние между проводниками (шаг металлизации) таким образом, чтобы в одном дискрете помещался один проводник и зазор. Трассировка цепей производится в результате последовательного заполнения ячеек масштабной сетки трассами. Так как отдельные проводники в большинстве случаев конкурируют между собой, то их конфигурация определяется последовательностью выполнения трассировки отдельных соединений.
Алгоритмы трассировки печатных соединений являются последовательными, их условно можно разбить на четыре группы:
волновые алгоритмы;
лучевые алгоритмы;
канальные алгоритмы;
алгоритмы гибкой (топологической) трассировки;
алгоритмы эвристического типа, основанные на эвристическом приеме поиска пути в лабиринте.