Это интересный вопрос. Давайте рассмотрим его, чтобы понять, почему вы видите то, что видите.
Из четырех упомянутых вами алгоритмов - BFS, DFS, Dijkstra и A * - три из них (BFS, Dijkstra и A *) предназначены для поиска кратчайших путей в структурах, где доступно несколько различных путей, и вы заинтересованы в поиске кратчайших путей. В этом смысле запуск BFS, Dijkstra и A * в некотором смысле повлечет за собой дополнительные расходы, поскольку вы платите за то, что не используете. В частности, алгоритм Дейкстры в этом случае должен работать не лучше, чем BFS. Любой шаг обойдется вам в ту же сумму, а стоимость обслуживания очереди с приоритетами или какой-либо другой структуры для поиска узла с наименьшей стоимостью в границе, вероятно, будет стоить дороже, чем стандартная очередь. В этом смысле мы, вероятно, можем исключить Дейкстру как кандидата на самый быстрый алгоритм здесь.
Это оставляет нам BFS, A * и DFS. Давайте сначала сравним BFS и DFS. Преимущество DFS заключается в том, что она теоретически быстра (линейное время), а шаблоны доступа к памяти, задействованные в работе DFS (поддержание вершины стека и места поиска рядом с самым последним посещенным местом), хорошо работают с кешами. Преимущество BFS состоит в том, что он прекращает поиск, как только находит кратчайший путь, и недостатком является то, что доступ к памяти более разрознен и менее эффективен при использовании кешей.
Давайте сделаем быструю геометрию c аргумент здесь. BFS расширяется наружу от начальной позиции, исследуя пути все более и более длинных. В этом смысле вы можете себе представить, что регионы, которые ищет BFS, образуют нечто, что приблизительно соответствует кругу с центром в начальной точке. Радиус этого круга будет равен длине кратчайшего найденного пути. В этом смысле, если бы не было никаких препятствий, вы ожидали бы, что BFS посетит некоторую постоянную долю от общего пространства в лабиринте, прежде чем найти выход, и при наличии препятствий он, вероятно, исследует большую часть, если не все, пространства. DFS останавливается, как только он находит выход, и он, вероятно, исследует множество тупиков на этом пути, поэтому есть также хороший шанс, что он исследует большую часть ячеек лабиринта. Учитывая выбор между этими двумя, я держу пари, что DFS будет немного быстрее, поскольку, вообще говоря, постоянный коэффициент для DFS ниже, чем BFS.
Тогда есть DFS против A *. Это сложнее проанализировать априори. Как правило, DFS говорит о гораздо более быстром алгоритме, чем A *, из-за связанных с этим накладных расходов на поддержание расстояний в A *, но A * имеет тенденцию искать в направлениях, которые с гораздо большей вероятностью доставят вас к месту назначения. Вероятно, это будет зависеть от формы лабиринта. Если бы лабиринт был построен таким образом, чтобы иметь много длинных извилистых проходов, то A *, вероятно, был бы лучше, потому что он избегал бы неправильного направления, пока это не было абсолютно необходимо, где DFS могла бы потратить много усилий, спускаясь в неправильном направлении. , Но вам нужно взглянуть на баланс между этими факторами, чтобы быть уверенным.
Есть еще одна проблема, и именно так возник сам лабиринт. Существует много различных алгоритмов генерации лабиринтов - например, вы можете использовать алгоритм Крускала, DFS, алгоритм Прима или алгоритм Уилсона для создания лабиринтов. Лабиринты, сделанные с помощью DFS, имеют тенденцию иметь меньше длинных коридоров, в то время как алгоритм Крускала и алгоритм Прима имеют тенденцию создавать много более коротких коридоров. Может случиться так, что в некоторых случаях DFS будет лучше, чем в других, в то время как A * может работать лучше или хуже. Так что, возможно, разница между A * и DFS связана с формой лабиринта в дополнение к их собственным деталям реализации.
В общем, я не удивлен, узнав, что ваша DFS была самым быстрым алгоритмом решения лабиринтов в основном из-за простоты DFS и хорошей локализации кэша по сравнению с другими алгоритмами. Тот факт, что он выигрывает у A *, вероятно, связан с накладными расходами, связанными с тем, что A * не стоит экономии в исследованных пространствах. Но чтобы получить больше данных, возможно, вам следует взглянуть на следующее:
Какую долю лабиринта в среднем исследует каждый алгоритм, прежде чем найти кратчайший путь?
Сколько длится кратчайший путь в лабиринтах?
Как создавались лабиринты и зависят ли ответы на вышеуказанные вопросы от используемого алгоритма?