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

В этом алгоритме уменьшение временных затрат достигается за счёт распространения волны не по всему полю платы, а только вдоль лучей. Идея: при распространении волны фронт занимает не все свободные соседние ячейки ДРП, а лишь одну, т.о. последовательность фронтов – луч.

Во-вторых, лучевой алгоритм трасс Абрайтеса из начала А и конца В трассы распространяются навстречу друг другу по двум лучам А₁, А₂, В₁, В₂.

Лучи А_1,2 и В_1,2 называются разноимёнными, лучи поочерёдно распространяются (шагают) до тех пор, пока разноимённые лучи не пересекутся или пока 4 луча не смогут продвигаться дальше, т.е. окажутся в тупике. В первом случае, осуществляется переход ко второму этапу – проведению трассы. Для этого от пересечения лучей осуществляют возврат по ячейкам, принадлежащим лучам, в исходные А и В ячейки трассы (используя метод путевых координат). Во втором случае, трассу проложить невозможно.

Пример приведён на рисунке:

						­	®	®	®	®
		А	®^А2	®	®	®­	#	#	­
		¯^А1				¯­	#	¯­^В1	­^В2
		¯				¯­	#	¯¬	В
		¯				¯­	#	¯
		¯			#	#	#	¯
		¯	¬	¬	¬	¬	¬	¯

Прежде всего, необходимо выбрать приоритетные направления движения лучей:

Для луча А₁ – вниз (основное), вправо (дополнительное);

А₂ – вправо(основное), вниз (дополнительное);

В₁ – влево (основное), вверх (дополнительное);

В₂ – вверх (основное), влево (дополнительное).

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

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

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

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

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

Если все 4 луча будут заблокированы, то трассу проложить нельзя.

Отметим, что при выводе i-го луча из тупика, другие лучи останавливаются для того, чтобы продвижение лучей было равномерным.

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

При выводе из тупика, В1 сначала возвращается в ячейку (8,4), затем делает шаги в ячейке (8,3) и (8,2) и далее продвигается по своему основному направлению до встречи с лучом А1.

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

Вероятность нахождения пути этим алгоритмом меньше, чем алгоритмом Ли.

Методы ускорения работы волнового алгоритма.

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

Используются различные методы ускорения выполнения 1-го этапа алгоритма.

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

Рис.1.

Из-за рассмотрения рис.1 видно, что при выборе в качестве источника распространения волны ячейки А, максимально удалённой от центра платы, просматривается меньшее число свободных ячеек ДПР. Это становится очевидным по мере роста числа протрассированных цепей.

2). Более эффективен метод встречной волны (рис.2)

- выигрыш в количестве ячеек.

Для реальных состояний ДРП выигрыш во времени будет отличаться от 2. Однако, в среднем, оценка является объективной.

Использование данной идеи приводит к усложнению алгоритма.

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

Начальная площадь прямоугольника (печатной платы) обычно на 10-20% больше площади прямоугольника, проходящего через ячейки А и В. Если при этом соединение найти не удалось, то границы охватываемого прямоугольника рассматриваются. Данный метод обладает большей эффективностью ускорения работы алгоритма по сравнению с методами 1 и 2.

Дата добавления: 2014-01-14