Очередность прокладки соединений

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

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

Но для такого расположения рисунок 7.4.1, в и г выгодно проводить в первую очередь более длинные соединения рисунок 7.4.1, г, обосновывается это тем, что они «более трудны» для трассировки.:

,

а) б)

в) г)

Рис.7.4.1. Различные порядки трассировки.

Суммарная длина получается по-разному, в зависимости от используемого алгоритма. Но практика показывает, что любая из рассмотренных тактик упорядочения приводит к примерно одинаковым результатам трассировки.