Материал: 2426

Методики и алгоритмы поиска кратчайшего пути на графах можно разделить на две группы: методики и алгоритмы неинформированного (слепого) поиска и методики и алгоритмы информированного (эвристического) поиска.

К первой группе относятся: поиск в ширину (BFS, Breadth-first search, волновой алгоритм); поиск в глубину (DFS, Depth-first search);

поиск с ограничением глубины; поиск в глубину с итеративным углублением; двунаправленный поиск [74, 175, 234].

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

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

При поиске в ширину необходим большой объем памяти (значительная пространственная сложность). Это может представлять гораздо большую проблему, чем временная сложность метода.

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

При поиске в глубину (DFS – Depth First Search, бэктрекинг, поиск с возвращением) всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Суть этого метода – продвижение вперед в неисследованную область, пока это возможно. Если вокруг все уже исследовано, необходимо отступить на шаг назад и искать новые пути для продвижения вперед. Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин (вершина, у которой не все инцидентные ребра уже исследованы), которая была посещена последней. Достоинством поиска в глубину является малая пространственная сложность.

40

Двунаправленный поиск заключается в том, что запускаются два одновременных поиска в ширину из начального и конечного узлов. Остановка происходит, когда узел из одного фронта поиска находит узел из другого фронта (рис. 1.11, а). Это позволяет сократить как время вычислений, так и объем используемой памяти. Площадь двух небольших кругов (см. рис. 1.11, а) меньше площади одного большого круга с центром в начальном узле, который охватывает конечный узел поиска (рис. 1.11, б).

Рис. 1.11. Схематическое представление двунаправленного (а) и однонаправленного (б) поиска в ширину: 1 – начальный узел; 2 – конечный узел

Поиск с ограничением глубины – это поиск в глубину с заранее определенным пределом глубины l. Т.е. узлы на глубине l рассматриваются как не имеющие преемников. Применение предела глубины позволяет не рассматривать бесконечные или слишком длинные пути.

Поиск в глубину с итеративным углублением заключается в постепенном увеличении глубины поиска (который сначала принимается равным 0 шагов, затем 1, 2 и т.д. шагов) до тех пор, пока не будет найдена цель. При этом сочетаются преимущества поиска в глубину и поиска в ширину. Как и поиск в глубину, он характеризуется малой пространственной сложностью. Как и поиск в ширину, он является полным, если коэффициент ветвления (максимальное количество преемников любого узла) конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла [137, 175].

В табл. 1.1 приведено сравнение стратегий неинформированного поиска по четырем показателям эффективности, приведенным выше (полнота, оптимальность, временная сложность, пространственная сложность) согласно [175]. Используются следующие обозначения: b

41

–коэффициент ветвления; d – глубина самого глубокого решения; m – максимальная глубина дерева поиска; l – предел глубины; c* – стоимость оптимального решения для метода поиска по критерию стоимо-

сти. Ограничения, обозначенные верхними индексами, означают следующее: а – метод полный, если коэффициент ветвления b конечен; б

–метод полный, если стоимость каждого этапа ≥ε при некотором положительном значении ε; в – метод оптимальный, если стоимости всех этапов являются одинаковыми; г – метод применим, если в обоих направлениях осуществляется поиск в ширину.

Таблица 1.1. Сравнение методов неинформированного поиска на графах

Алгоритмы неинформированного поиска целесообразно использовать, когда заранее неизвестно расположение цели (переменное положение) либо целей несколько. В настоящей монографии в предположении организованности пространства более целесообразным представляется использование методов информированного поиска.

К группе методов информированного поиска относятся: «жадный» поиск «по первому наилучшему совпадению», или best-first search (алгоритмы Дейкстры, Беллмана-Форда); алгоритм Аcтар (альтернативные названия: A*, «А-звездочка», направленный волновой алгоритм); алгоритм A* с итеративным углублением (IDA*); рекурсивный поиск по первому наилучшему совпадению (Recursive BestFirst Search – RBFS); упрощенный поиск A* с ограничением памяти

(SMA* – Simplified Memory-bounded А*); алгоритмы роевого интел-

лекта (муравьиных колоний, роя частиц и др.).

Методики и алгоритмы информированного поиска перечислены в порядке возрастания их эффективности [137, 175, 241].

Охарактеризовать временную и пространственную сложности алгоритмов информированного поиска довольно трудно, т.к. она зави-

42

сит и от точности эвристической функции, и от вычислительной реализации алгоритма, и от того, насколько часто происходит смена наилучшего пути по мере развертывания узлов, и т.п.

A* является более эффективным алгоритмом, чем поиск в ширину (волновой алгоритм) [224, 234]. Алгоритмы RBFS и SMA* представляют собой надежные, оптимальные алгоритмы поиска, в которых используются ограниченные объемы памяти. При наличии достаточного количества времени эти алгоритмы могут решать такие задачи, которые не позволяет решать алгоритм А*, поскольку исчерпыва-

ет доступную память [74, 175, 224, 232, 241].

Методики эвристического поиска используют известные знания, специфические для конкретной задачи. Информированные методики поиска находят решения более эффективно, чем слепые, при этом расходуется меньший объем памяти. Эвристическая информация о глобальном характере графа и общем расположении цели поиска может быть использована для направления поиска в сторону цели, раскрывая в первую очередь наиболее «перспективные» узлы графа. Общее обозначение методов информированного поиска, связанных с выбором наилучшего варианта, – BFS (best-first search). Ключевой компонентой информированных методов является эвристическая функция h(n), которая оценивает наименьшую стоимость пути от узла n до целевого узла. Эвристику можно рассматривать в качестве некоторого правила влияния, которое, хотя и не гарантирует успеха, в большинстве случаев оказывается весьма полезным [74, 175, 224, 232, 234, 241].

Основной проблемой эвристических методов является правильный подбор эвристической функции, которая, с одной стороны, позволяет сократить временную и пространственную сложность алгоритма, с другой стороны, должна обеспечивать оптимальность поиска. Если h близка к истинной стоимости оставшегося пути, то эффективность будет высокой. С другой стороны, если h будет слишком низким, это отразится на эффективности в худшую сторону. Подбор зачастую осуществляется опытным путем и представляет собой поиск компромисса между временной и пространственной сложностью алгоритма и его оптимальностью. В случае неправильного подбора эвристической функции не гарантируется оптимальность найденной траектории [175].

Способы дискретизации непрерывного пространства с препят-

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

43