Алгоритмы решения задач трассировки

Задача трассировки при целевой функции в виде минимума суммарной длины всех соединений может быть сформулирована как задача построения для графа G(V,R) покрывающего дерева минимальной длины, и сведена в дальнейшем к проблеме соединения между собой пар дискрет. Большое значение при этом имеет определение очередности проведения трасс. Первыми обычно соединяются контакты, расположенные на кратчайшем расстоянии друг от друга или имеющие минимальныиприоритетныи номер (под приоритетным номером подразумевается количество контактов, подлежащих соединению, внутри прямоугольника, построенного на дискретах, через которые должна быть проведена трасса). Например, контакты, показанные на рис. 5.17, будут трассироваться в следующей последовательности: 1 — (С-С), 2 — (В-В), 3 — (А-А).