Классификация
алгоритмов трассировки соединений.
В качестве целевой функции
(критерии качества) в алгоритмах трассировки используют:
1.
Минимальную
суммарную длину сигнальных соединений
2.
Минимальное
количество слоев соединений
3.
Минимальное
количество межслойных переходов
4.
Минимальное
количество отдельных фрагментов соединений в целях связи элементов – проводник
должен иметь по возможности простейшую конфигурацию в идеале представлять собой
отрезок прямой линии.
5.
Минимальное
количество взаимных пересечений сигнальных соединений.
Все алгоритмы
трассировки соединений делятся на три группы:
1.
Волновые алгоритмы трассировки, основанные на идеи Ли и его модификации
Данные алгоритмы позволяют учитывать
технологическую специфику печатного монтажа, со всей совокупностью
конструктивных ограничений. Эти алгоритмы всегда гарантируют построение трассы,
если путь для нее в принципе существует (поскольку они сканируют все поле
трассировки при проведении каждого отдельного проводника). Они выдают высокое
качество решений, но менее быстродействующие.
2.
Ортогональные алгоритмы
Строят трассировку в ортогональной
матрице каналов. Эти алгоритмы очень быстродействующие ( в
75-100 раз быстрее волновых ), но не гарантируют построение трассы.
3.
Эвристические алгоритмы трассировки
В основе этих алгоритмов, как правило,
лежит некий эвристический прием, который должен приводить к удовлетворительному
результату. Эти алгоритмы очень быстродействующие, но не гарантируют построения
трассы и решения задачи на поле.