Реклама:

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

Поиск в глубину

Предыдущий алгоритм иногда называют поиском в ширину, потому что он уровень за уровнем просматривает ближайшие клетки. Поиск в глубину выбирает какое-то одно направление и просматривает его вглубь на заданное число клеток, переходит к следующему направлению и т.д., пока не найдет конечную точку. Представленная ниже рекурсивная функция находит не все возможные пути. Чтобы найти кратчайший путь, надо вызвать эту функцию для каждой из клеток, прилегающих к начальной клетке. Во вспомогательном булевом массиве Mark такого же размера, как и остальная карта, хранится 1, если текущая клетка уже пройдена алгоритмом, и 0 — в противном случае. В переменных Destination^ и Destination_y должны храниться координаты точки, куда в итоге надо попасть. В глобальной перемененной Length будет храниться длина текущего пути, чтобы мы не залетели вглубь матрицы дальше, чем max_length.

Procedure DepthSearch(x,у: integer); Var

i : integer; Begin

If Length>MAX_LENGTH then exit; Mark[x.y] := True;

If (x=Destination_x) and (y=Destination_y) then Begin

(Мы нашли эту точку! Искомый путь представлен значениями True в массиве Mark. Здесь вы можете запомнить построенный путь и очистить Mark[x,y], чтобы продолжить поиск, или же остановиться, если задачей было найти хотя бы один путь.} End;

Length:=Length+l;

If Mark[x+l,y]=false then DepthSearch(x+l,y); If Mark[x,y+l]=false then DepthSearch(x,y+l); If Mark[x+l,y+l]=false then DepthSearch(x+l,y+l) ; If Mark[x-l,y-l]=false then DepthSearch(x-l,y-l); If Mark[x-l,y]=false then DepthSearch(x-l,y) ; If Mark[x,y-l]=false then DepthSearch(x,y-l) ; Length : =Length-l ; End;

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

Алгоритм Дей кстры

Алгоритм Дейкстры выигрывает у всех предыдущих алгоритмов как по скорости, так и по качеству поиска. Его легко адаптировать как для клетчатых полей, так и для списков опорных точек. Он берет в расчет весовые коэффициенты связей между точками. То есть, с его помощью можно рассчитывать пути на картах с разными типами местности и с учетом расстояния между опорными точками. Минус у него только один: относительная сложность реализации, хотя по принципу действия он очень похож на поиск в ширину. Из-за того, что в нем используется приоритетная очередь, его реализация для разных задач будет разной. Поэтому я приведу только псевдокод, а в конце дам рекомендации, как этот псевдокод превратить в код реальный, исходя из того, что вам нужно.


⇐ Предыдущая страница| |Следующая страница ⇒