Волновой алгоритм.

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

• В лабиринте( на подложке ) выбираются две точки А(начальная) и В(конечная). Из начальной точки в четырех направлениях выходит волна. Цифрами обозначается номер фронта волны или ее путевые координаты .

	1
1	А	1
	1

• Путевые координаты определяют шаг распространения волны. Каждый элемент первого фронта волны является источником вторичной волны.

		2
	2	1	2
2	1	А	1	2
	2	1	2
		2

Элементы второго фронта генерируют третий фронт и т.д. От запрещенных элементов волна не распространяется.

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

Вверх , Вниз , Влево , Вправо.

От того в каком порядке заданы приоритеты зависит скорость решения задачи.

При построении траектории используется два принципа:

1. Движение осуществляется строго по заданным приоритетам.

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

Пример 1. Пусть задан лабиринт, где запрещенные элементы заштрихованы.

Найти путь между элементами А и В.

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

6		10	9	8		10
5				7		9	10
4			5	6		8	9	B
3	2		4	5		7	8		10
	1	2	3	4		6			9
1	А	1	2	3	4	5	6	7	8
2	1		3				7
3	2		4	5	6		8	9	10