Лучевой алгоритм трассировки

⇐ ПредыдущаяСтр 4 из 4

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

Достоинство:

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

Недостатки:

1. приводит к снижению вероятности нахождения пути сложной конфигурации,

2. усложняет учет конструктивных требований к технологии печатной платы.

Работа алгоритма заключается в следующем.

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

Лучи А⁽¹⁾, А⁽²⁾, ..., А⁽ⁿ⁾ и В⁽¹⁾, В⁽²⁾,..., В⁽ⁿ⁾ считают одноименными, если они распространяются из одноименных источников А или В.

Лучи А⁽ⁱ⁾ и В⁽ⁱ⁾ являются разноименными по отношению друг к другу.

Распространение лучей производят одновременно из обоих источников до встречи двух разноименных лучей в некоторой ячейке С.

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

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

Пример (рисунок 7.4).

Рисунок 7.4 – Пример для лучевого алгоритма трассировки

Выбираем для источников А и В по два луча с противоположными направлениями: А⁽¹⁾ - вверх, влево; А⁽²⁾ - влево, вверх; В⁽¹⁾ - вниз, вправо; В⁽²⁾ - вправо, вниз.

Если ячейка В располагалась бы не справа, а слева от А, то путевые координаты влево и вправо необходимо было бы поменять.

На первом шаге просматривают ячейки с координатами (2, 4), (5, 2) и (6, 3).

На втором шаге луч В⁽¹⁾ и луч А⁽²⁾ оказываются заблокированными.

Лучи В⁽²⁾ и А⁽¹⁾ встречаются в ячейке С с координатами (4, 3) на четвертом шаге.

Проводим трассу.

Например, если бы ячейка с координатами (4, 3) была заняты (имелись проводники), то все лучи оказались бы заблокированными и решение найдено не было, хотя путь из А в В провести можно.

Рисунок 7.5 –Путевые координаты для лучей

Обычно с помощью лучевого алгоритма удается построить до (70-80)% трасс, остальные проводят, используя волновой алгоритм или вручную.

Его применение особенно выгодно при проектировании печатных плат с невысокой плотностью монтажа.

Эвристические алгоритмы трассировки

Достоинство:

1. относятся к числу наиболее быстродействующих и простых в программировании.

Недостаток:

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

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

Пример.

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

Рисунок 7.6 –Пример для эвристического алгоритма трассировки

Рисунок 7.7 – Путевые координаты для лучей

Зададим следующий приоритетный порядок проведения пути: вверх, вправо, вниз, влево (вариант I).

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

Считаем, что трасса удаляется от цели, если на очередном шаге алгоритма расстояние до данной прямой возрастает.

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

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

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

Другой вариант эвристического алгоритма, не требующий разбиения монтажного поля на ячейки, основан на проведении соединений по кратчайшему пути в обход препятствий, представляемых в виде прямоугольников, задаваемых координатами своих углов. Размеры прямоугольников выбирают такими, чтобы по его сторонам могли прокладываться новые проводники. При встрече с препятствием трасса проводится по периметру соответствующего прямоугольника. Каждое конкретное направление обхода оценивается с точки зрения удлинения строящегося проводника и числа возможных пересечений его с ранее построенными и еще непроведенными трассами. При этом выбирается то направление, которому соответствует лучшее значение оценки. При невозможности обхода очередного препятствия в программе предусмотрена процедура возврата к предыдущему препятствию и выбору иного варианта его обхода. Использование этой процедуры позволяет сократить число неразведенных цепей. Для экономии оперативной памяти ЭВМ в алгоритме применен принцип фрагментарного проведения трасс, при котором все монтажное поле разбивается на отдельные дискреты, хранящиеся во внешнем ЗУ и вызываемые в оперативную память по мере необходимости при прокладывании проводника внутри соответствующего дискрета. Это создает благоприятные условия для трассировки плат практически любого размера.

⇐ Предыдущая 1 2 34