1.   Постановка задачи, критерии оптимизации и ограничения.

С математической точки зрения – трассировка наисложнейшая задача выбора из огромного числа вариантов оптимального решения.

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

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

Исходными данными для задачи трассировки являются: список цепей, параметры конструкции элементов и коммутационного поля, данные по размещению элементов.

В зависимости от способа реализации соединений (печатный или проводной монтаж) критериями оптимальности трассировки могут быть: минимальная суммарная длина соединений, минимальное число слоев монтажа, минимальное число переходов из слоя в слой, минимальные наводки в проводниках, процент трассировки и т.д.

Оценка качества ведется по доминирующему критерию при ограничениях на другие критерии, либо применяют аддитивную форму целевой функции:

, где - весовой коэффициент; - частный критерий.

Ограничения для задачи трассировки можно разделить на конструкторские и технологические. К технологическим ограничениям относятся (для печатного монтажа): ширина проводников и расстояния между ними, максимальное число слоев, минимальное расстояние между контактными площадками и т.п.

К конструктивным ограничениям относятся: размеры коммутационного поля, наличие проводников, трассы которых уже заданы, максимальная длина проводников, участки, запрещенные для трассировки и т.п.

2.   Этапы решения задачи трассировки.

Для каждого способа реализации монтажа (проводной и печатный) существуют свои методы и алгоритмы решения задачи трассировки.

Рассмотрим основные методы и алгоритмы на примере решения задачи трассировки соединений многослойной печатной платы. Задача решается в несколько самостоятельных этапов:

1.    Определение перечня (списка) всех проводников, которые должны быть проложены между парами различных контактов.

2.    Распределение проводников по слоям.

3.    Определение последовательности трассировки проводников в каждом слое.

4.    Собственно трассировка проводников.

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

Наибольшее распространение для решения этой задачи получил алгоритм Прима. На первом шаге для произвольного контакта находится ближайшая вершина и соединяется ребром. На остальных n-2 шагах из множества не подсоединенных контактов выбирается тот, который находится ближе всего к группе уже связанных контактов, и соединятся кратчайшим ребром.

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

Отметим еще раз, что данные алгоритмы используются лишь для выделения списка проводников, подлежащих соединению (подцепей в системе PCAD).

На втором этапе определяется планарность графовой модели схемы (возможность расположения ребер на плоскости без пересечений) на основе теории графов и если она планарная, производится её плоская укладка. Если же модель не планарная, решают задачу распределения ребер графа по слоям. В зависимости от организации процесса трассировки, расслоение осуществляется либо до, либо после, либо в процессе трассировки.

Основная идея алгоритмов расслоения, работающих до трассировки, заключается в априорном выделении групп проводников, которые ввиду неизбежных пересечений невозможно назначить в один слой. Один из способов основан на построении охватывающего прямоугольника для каждой цепи . Считается, что две цепи перекрываются, если . Затем строится граф перекрытий: , где E – множество вершин, соответствующих цепям, а U – множество ребер, соответствующих  перекрытиям.

Затем определяется минимальная раскраска графа, и цепи с одним цветом попадают в один слой. Этот способ дает завышенное количество пересечений (и слоев).

Если процесс расслоения происходит после трассировки, то используют алгоритм, основанный на построении графа пересечений и нахождении его минимальной раскраски.

При определении порядка трассировки проводников используют в основном два подхода:

1)   соединение проводников в порядке возрастания длины проводников;

2)   соединение в порядке убывания длины.

Первый способ основан на том соображении, что короткие проводники вносят меньше конфликтных ситуаций, а второй на том, что длинные проводники труднее трассировать.

Собственно трассировка соединений заключается в последовательном построении трасс в каждом слое для всех пар контактов, с учетом определенных требований и ограничений. В большинстве известных алгоритмов вся плоскость платы разбивается на квадраты (хотя возможны треугольники или другие фигуры). Максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников. Минимальные размеры обуславливаются объемом памяти ЭВМ и соотношением: , где  - расстояние между центрами ячеек; - ширина проводника; - минимальное расстояние между проводниками.

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