Волновой алгоритм трассировки и пример его реализации

Л.Н. Сизова,
н. с., lusysz@ipu.ru
ИПУ РАН, г. Москва

В статье дано определение задачи трассировки, представлен краткий обзор алгоритмов трассировки, подробно описан волновой алгоритм, приведен пример нахождения кратчайшего пути в ориентированной сети и представлен пример реализации усовершенствованной версии алгоритма в интерактивном программном комплексе «Графика – ТР».

The article defines the task of tracing, provides a brief overview tracing algorithms described wave algorithm is an example of finding the shortest paths in directed network and provides an example of the implementation of an improved version of the algorithm in an interactive program complex «Grafika – TR».

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

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

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

Магистраль - отрезок прямой, по которой может проходить соединение в преимущественном направлении.

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

Эвристические алгоритмы частично основаны на эвристическом приеме поиска пути в лабиринте. При этом каждое соединение проводится по кратчайшему пути, обходя встречающиеся на пути препятствия. Эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм. Эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:

· не гарантирует нахождение лучшего решения;

· не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»);

· может дать неверное решение в некоторых случаях.

В основу алгоритма автоматической трассировки соединений между элементами на принципиальной электрической схеме и печатной плате в интерактивном программном комплексе «Графика – ТР» положен широко применяемый в различных приложениях алгоритм определения кратчайшей цепи в ориентированных сетях - волновой алгоритм. Суть алгоритма заключается в следующем.

Пусть имеется ориентированная сеть G(B, A), где B - множество вершин сети, A - множество ориентированных дуг сети, соединяющих в любом порядке i- ую вершину с j- ой. Все вершины пронумерованы от 1 до N (общее число вершин сети). Всем дугам присваиваются значения a(i, j)≥ 0. Требуется найти кратчайший путь от вершины 1 до вершины N. Алгоритм состоит из двух частей: вычисления минимального веса последней вершины сети и фиксации кратчайшей цепи.

1. i = 1, j = 1

2. Вершине b₁ присваивается вес 0. Остальным вершинам b _2,… b _N присваивается ∞

3. j = j +1

4. Вычисляется вес вершины b _j = b _i + a (i, j). Определяется b _{j min}. Если j = N, то j = 1 и переход на п.5, иначе переход на п.3.

5. Вершина j min помечается специальным маркером и в дальнейших расчетах в качестве конца дуги не используется, если j min = N, то переход на п.6, иначе i = j min и переход на п.3.

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

Рассмотрим пример определения кратчайшего пути в сети (см. рис.1) на основе вышеприведенного алгоритма. В сети номера вершин проставлены в кружках. На дугах сети в разрыве указаны длина каждой дуги.

рис. 1 Ориентированная сеть

В табл. 1 указаны последовательные шаги алгоритма и значения вершин, вычисляемые на каждом шаге.

Таблица 1 Вычисление значений вершин

Шаг алгоритма	Веса вершин
	1	2	3	4	5	6	7
Нач.установки	0	∞	∞	∞	∞	∞	∞
1	-	14	2	6	∞	4	∞
2	-	14	-	6	∞	3	∞
3	-	14	-	6	∞	-	18
4	-	9	-	-	20	-	18
5	-	-	-	-	12	-	18
6	-	-	-	-	-	-	18

В рассматриваемом примере кратчайший путь проходит через вершины 1, 3, 6, 4, 2, 5, 7.

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

рис. 2 Зависимость вида трассы от шага распространения волны

Автоматическая трассировка соединений в программном комплексе «Графика – ТР» реализует алгоритм определения кратчайшего пути на графе с пересечениями соединений и без пересечений. Предварительно векторная 2D модель схемы проецируется на плоскую матрицу, в которой формируется растровая модель схемы. Ячейки матрицы – это вершины сети. Дуги – направление расчета кратчайшего пути. Ортогональные дуги имеют вес 1, диагональные - √2. Последовательно рассчитываются веса вершин, прилегающих к началу трассы, исключая вершины-препятствия. Далее аналогично последовательно рассчитываются веса следующих вершин до получения веса вершины конца трассы. Затем фиксируется трасса по минимальным весам.

Вычислительная сложность K операций реализации алгоритма определяется следующей формулой:

(1)

где m ₀ - количество операций по вычислению веса одной вершины, N - общее число ячеек матрицы, N _p - количество ячеек занятое препятствиями р.

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

Управляющие процессом трассировки параметры Pn определяют следующие характеристики:

- P1 - трассировка с пересечениями трасс (P1 = 1), без пересечений (P1 = 2), под углом 45° (P1=0);

- P2 – размер контактной площадки (нормально P2 = 1);

- P3 – задает скорость стремления к цели (нормально P3 = 2);

- P4 - определяет вес элементарного шага при поиске кратчайшего пути (нормально P4 = 1);

- P5 - уменьшает общее количество изгибов трассы (Р5 может принимать значения от 1 до 30), чем больше значение параметра, тем меньше число изгибов трассы (для печатной платы P5 = 1 или P5 = 2;

- P6 - уменьшает общее количество пересечений трасс (P6 может принимать значения от 1 до 20), чем больше значение параметра, тем меньше общее число пересечений;

- P7 и P8 - минимальное расстояние между автоматически трассируемыми соединениями по осям Х и У, то есть отношение максимальных размеров аналогового поля чертежа к общему числу соответственно столбцов и строк его дискретной модели. Например, если выбрать Р7 = Р8 = 5, то размеру изображения на экране дисплея 500х300 мм будет соответствовать матрица дискретной модели 100х60.

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

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

рис. 3 Принципиальная схема установки прототипирования

рис. 3 Принципиальная схема блока защиты и автоматики

Литература

1. Сизова Л. Н. Программный комплекс «Графика - ТР» //Информационные технологии в проектировании и производстве. Научно-технический журнал / ФГУП «ВИМИ», 2009, №1.

2. Разумовский А. И., Сизова Л. Н. Проектирование и трассировка печатных плат с использованием программного комплекса "Графика—ТР", Информационные технологии. — 2010, №2.

3. Артамонов Е. И., Коновалов И. В., Сизова Л.Н.,Тенякшев А.М., Тишкевич Е. Программно-технический комплекс (ПТК) автоматической трассировки соединений между элементами на плоскости // Материалы 37-й междунар. конф. и дикуссионного научного клуба «Информационные технологии в науке, социологии, экономике и бизнесе (IT+SE'10)». — Открытое образование. — 2010. С.132-134.

4. Л.Н. Сизова Компьютерное моделирование схем // 11-я международная конференция "Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта" (CAD/CAM/PDM - 2011), М.:ИПУ РАН, 2011, С.193-195.