Поиск в ширину.
Начиная со стартового узла, этот алгоритм сначала определяет все непосредственно соседние узлы, затем все узлы в двух шагах, затем в трех, и так далее, пока цель не достигнута. Типичным является то, что для каждого узла его непроверенные соседи помещаются в список Open, который обычно является FIFO очередью. Алгоритм может работать так, как показано в Листинге 1. Рисунок 4 демонстрирует процесс поиска. Можно заметить, что он находит путь вокруг препятствий, и этот путь является кратчайшим, то есть одним из нескольких кратчайших в длину путей, если все шаги имеют одинаковую стоимость. Тут имеется множество простых проблем. Одна заключается в том, что поиск идет равномерно во всех направлениях, вместо того, чтобы быть направленным в сторону цели. Другая проблема в том, что не все шаги равны, по крайней мере, шаги по диагонали должны быть длиннее ортогональных.
Рис. 4.
Двунаправленный поиск в ширину.
Это улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Как показано на рисунке 5, это может улучшить простой поиск в ширину (обычно в 2 раза), но все еще является очень неэффективным. Хитрости, наподобие этой, хорошо запомнить, так как они могут пригодиться в дальнейшем.
Рис. 5.
Алгоритм Дийкстры.
Е. Дийкстра разработал классический алгоритм для прохода по графам, грани которых имеют различный вес. На каждом шаге, он ищет необработанные узлы близкие к стартовому, затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие расстояния от старта. Этот алгоритм имеет два преимущества по сравнению с поиском в ширину: он принимает во внимание стоимость или длину пути и обновляет узлы, если к ним найден лучший путь. Для реализации, список Open с очередью FIFO заменяется приоритетной очередью, где извлеченный узел имеет лучшее значение - здесь, это наименьшая стоимость пути от старта. (См. Листинг 2.) На рисунке 6 показана хорошая адаптация алгоритма к стоимости местности. Однако, он имеет слабость поиска в ширину, игнорируя направление к цели.
Рис. 6.
Поиск в глубину.
Этот поиск противоположен поиску в ширину. Вместо посещения вначале всех соседей, а потом их наследников, он сначала посещает всех наследников, а только затем переключается на соседей. Для уверенности в том, что поиск закончится, необходимо предусмотреть остановку на определенной глубине. Можно использовать тот же самый код, что и в поиске в ширину, если добавить параметр для отслеживания глубины каждого узла и заменить Open с очереди FIFO на стек LIFO (last-in-first-out). На самом деле можно полностью избавиться от списка Open и вместо этого сделать поиск рекурсивной подпрограммой, что уменьшит расход памяти использованной под Open. Необходимо, чтобы каждая ячейка маркировалась как "посещенная" при продвижении в глубь и эта пометка снималась на обратном ходу, чтобы избежать генерации путей, которые посещают дважды одну и ту же ячейку. На рисунке 7 можно заметить, что этого недостаточно, алгоритм все равно может путаться вокруг себя и тратить время на бессмысленные пути. Для геометрического поиска пути можно сделать два дополнения. Первое будет заключаться в добавлении метки на каждую ячейку с длиной найденного к ней кратчайшего пути; алгоритм больше не посетит эту ячейку пока не будет иметь к ней путь с меньшей стоимостью. Другое заключается в выборе вначале соседей, которые ближе к цели. С этими двумя дополнениями, можно заметить, что поиск в глубину быстро найдет путь. Могут обрабатываться даже взвешенные пути, если сделать остановку по общей накопленной стоимости вместо общего расстояния.
Рис. 7.
Алгоритм последовательных приближений при поиске в глубину (IDDFS).
В действительности в алгоритме поиска в глубину существует еще одна проблема - выбор правильной глубины остановки. Если она будет слишком маленькой, то путь не будет найден; если слишком большой, то потенциально можно потратить много времени впустую, исследуя слишком глубоко, или найти путь с очень высокой стоимостью. Эти проблемы решаются итеративным углублением - техника, при которой выполняется поиск в глубину с увеличивающейся глубиной до тех пор, пока путь не будет найден. При поиске пути мы можем не начинать с глубины равной единице, а сразу начать с глубины равной расстоянию по прямой от старта к цели. Этот поиск является асимптотически оптимальным среди всех переборных алгоритмов по времени и памяти.
Алгоритм “лучший-первый”.
Это первый рассматриваемый эвристический поиск, который принимает во внимание знания о пространстве поиска для направления своих усилий. Он похож на алгоритм Дийкстры, за исключением того, что узлы в списке Open оцениваются по приблизительному оставшемуся расстоянию до цели. Эта оценка так же не требует наличия обновлений, в отличие от алгоритма Дийкстры. Рисунок 8 показывает работу алгоритма. Это самый быстрый из всех планирующих алгоритмов рассмотренных ранее, который направляется по прямой к цели. Он так же имеет и свои слабости. На рисунке 8А, показано, что он не принимает во внимание накопленную стоимость пути, направляясь по прямой через зону с высокой стоимостью, а не обходя ее. И на рисунке 8Б можно увидеть, что найденный путь вокруг препятствия не прямой, а изгибается вокруг препятствия на манер алгоритма трассировки, рассмотренного ранее.
Рис. 8А.
Рис. 8Б.
