7.5. Лучевые алгоритмы трассировки

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

Рассмотрим следующие лучевые алгоритмы:

1. Алгоритм Л.Б. Абрайтиса;

2. Алгоритм Миками – Табучи (K.Mikami, K. Tabuchi).

7.5.1. Алгоритм Абрайтиса

Работа алгоритма заключается в следующем. Задается число лучей, распространяемых из точек A и B, а также порядок присвоения путевых координат (обычно число лучей для каждой ячейки - источника принимается одинаковым). Лучи A(1), A(2),…, A(n) и B(1), B(2),…, B(n) считают одноименными, если они распространяются из одноименных источников A или B. Лучи A(i) и B(i) являются разноименными по отношению друг к другу.

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

Возьмем для источников А и В по два луча с противоположными направлениями. Если А выше и левее В, то А¹ - , ; А²- , ; В¹ - , ; В²- , .

Если на пути луча встречается препятствие, то с помощью альтернативного луча алгоритм пытается обойти препятствие, например, если препятствие встретилось у луча А² , то препятствие обходится с помощью луча . При первой возможности основной луч выходит на свое направление.

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

Пример. Соединить алгоритмом Абрайтиса ячейки А и В (рис. 7.36 (а))

А В
		А	
						
		
						
						
						
						В

		А	
						
		
						
						
						
						В

а

б

в

Рисунок 7.36. Построение пути алгоритмом Абрайтиса

На рис. 7.36 (б) показан процесс распространения лучей. Овалами показаны ячейки, в которых луч меняет направление распространения на альтернативное. Вертикальный луч ячейки В на четвертом шаге «затух». Ячейка встречи разноименных лучей С (). Начиная с нее, строится путь к ячейка источникам (рис. 7.36 (в)).

Из рисунков видно, что площадь, занятая метками, значительно меньше, чем у волнового алгоритма.

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

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

7.5.2. Алгоритм Миками – Табучи (малоповоротный алгоритм)

Из ячеек А и В до встречи с препятствием проводятся по два перпендикулярных луча. Если разноименные лучи пересеклись, то путь найден (рис. 7.37 (а).

	А		

Если нет (рис. 7.37 (б), то ячейки ранее построенных лучей становятся источниками для проведения перпендикулярных лучей (рис. 7.37 (в) и т.д.

	А
		В

	А
		В

	А
		В

	А
		В

а б в г д

Рисунок 7.37. Порядок построения пути алгоритмом Миками - Табучи

На рис.7.37 (г) показаны вторичные лучи ячеек А и В. Разноименные лучи пересеклись. Путь строится по лучам, построенным раньше (рис. 3.37.(д)).

Формально алгоритм Миками – Табучи можно записать следующим образом:

1. Положить i = 0.

2. Через ячейки А и В провести перпендикулярные лучи. Ячейки, по которым прошли лучи поместить в списки А_i и В_i.

3. Если А_i  В_i  , то путь найден. Конец.

4. Если нет, то для всех А_i и В_i найти точки ветвления.

5. Положить i = i + 1. Провести через них перпендикулярные лучи. Ячейки, по которым прошли лучи поместить в списки А_i и В_i

6. Если А_i  В_i  , то путь найден. Конец.

7. Пока А_i  В_i   или А_i  А_i-1 или В_i  В_i-1 повторить п.п. 3-5.

8. Пути между ячейками не существует.

Если ограничить число повторов п.п. 3-5 одним, то будут построены малоповоротные пути (рис.7.38).

Рисунок 7.38. Конфигурации трасс с разным числом поворотов k

Рассмотрим работу алгоритма для примера рис. 7.36 (а).

Проведем через ячейки А и В перпендикулярные лучи. Ячейки, по которым прошли лучи поместим в списки А₀ и В₀. Найдем точки ветвления (рис 7.39 (а)).

А₀  В₀ = . Положим i = i + 1 и проведем вторичные лучи (рис 7.39 (б)).

А ₁  В₁  . Строим путь (рис. 7.19 (в)). Заметим, что к ячейке В трасса поворачивает в луче В₀, а не в В₁ (ячейка, помеченная ), так как пересеклись вторичные лучи вертикальный А и горизонтальный В.

		А
						В

		
		А	
		
		
						
						
						
						В	

		А
						В

Рисунок 7.39. Построение пути алгоритмом Миками - Табучи

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

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

В меньшей степени этот недостаток свойственен канальным алгоритмам.