Волновой алгоритм (алгоритм Ли)

Данный алгоритм включает в себя несколько этапов:

1. Монтажное поле разбивается на квадратные площадки, размеры которых определяются допустимой шириной трасс, зазоров между ними и размерами контактных площадок.

2. Площадки поля делятся на занятые и свободные. В занятых площадках (ранее проложенные проводники, установленные элементы и т.п.) проведение трасс запрещено. Трасса может быть проложена только через соседние площадки, если они свободны.

3. Распространение волны заключается в присвоении площадкам, соседним с ранее рассмотренными определенного значения весовой функции. Вес ячеек К-того фронта функции равен: Р_К = Р_К-1 +1

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

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

Пример. Имеем монтажное поле, разделенное на элементарные площадки. Пусть необходимо соединить площадки А и В. Выбираем пл. А в качестве источника волны с весом Р_К-1 = 0.Тогда всем площадкам, соседним с Апри трассировке только по ортогональным направлениям присваиваются веса, равные Р_К = 1. 10-тый фронт волны достигает цели – площадки В.

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

1

4 2

3Рисунок 3.8 –Путевые координаты.

						9В
	0А

Рисунок 3.8. – Иллюстрация этапов распространения волны

и проведения трассы.

В этом примере точки соединяются на 9-том фронте. Поскольку из точки В с весом 9 можно перейти в две соседние ячейки с весом 8, то переход осуществляется по предпочтительному направлению 3, пока убывают веса площадок и не будет проведена трасса. Волна в запрещенных ячейках не распространяется, т.е. нумеровать их нельзя.

Алгоритм Ли позволяет строить путь минимальной длины, но требует значительных затрат времени при работе на ЭВМ. При этом 90% времени затрачивается на распространение волны, 10% - на проведение трасс.

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

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

Метод встречной волны заключается в то, что источником распространения волны является не одна ячейка, а несколько, или отрезок ранее построенного пути. Если волны встречаются, то трассу провести можно.

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

Пример. Для контактных площадок А и В задается количество распространяемых лучей и разрешенные им направления. При прохождении луча через ячейку ей присваивается путевая координата. На рисунке показан пример проведения трассы двухлучевым алгоритмом, причем лучу А1 разрешено движение вправо и вниз, лучу А2 – вниз и вправо, лучу В1 – вверх и влево, лучу В2 – влево и вверх.

А1

А2

В1

В2

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