-
Четырехлучевой алгоритм
Из начальной и конечной точек выходят одновременно по четыре луча. Лучи движутся строго по заданным направлениям и “затухают”, если достигли края координатной сетки, либо встретили запрещенный элемент.
1
1
1 A 1
1 B 1
1
1
Пример 3.
|
|
2 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
A |
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
2 |
2 |
1 |
B |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
Маршрутный алгоритм.
Маршрутный алгоритм получил свое название, потому что осуществляет одновременно и формирование фронта и прокладывание трассы. Источником волны на каждом шаге является конечный элемент участка трассы проложенной на предыдущих шагах.
В маршрутном алгоритме рассматриваются восьмиэлементная окрестность исходного элемента.
i-1,j-1
i,j-1
i+1,j-1 i-1,j A
i+1,j i-1,j+1
i,j+1
i+1,j+1
От каждого элемента окружения оценивается расстояние d до конечного элемента B.
d =
или d =
Таким образом определяются восемь значений расстояний, из которых выбирается минимальное. Элемент для которого d оказалось минимальным считаем элементом трассы. Процесс повторятся до тех пор пока расстояние не будет равным нулю (d=0) т.е. пока не будет достигнут конечный элемент. Обход запрещенных элементов осуществляется исходя из интуиции разработчика.
Пример:
-
9
B
1
2
7
3
A
4
8
10
5
6
