С поиском в ширину или итеративным углублением, я думаю, что математический ответ на ваш вопрос включает в себя понятие "шарика" вокруг вершины. Определите Ball (v, n) как набор узлов на расстоянии не более n от узла v, и пусть расстояние от начального узла s до узла назначения t будет равно d. Тогда в худшем случае прямой поиск будет работать лучше, чем обратный поиск, если | Ball (s, d) | <| Ball (t, d) |. Это верно, потому что поиск в ширину всегда (и ID в худшем случае) расширяет все узлы некоторого расстояния k от начального узла, прежде чем когда-либо посещать какие-либо узлы глубины k + 1. Следовательно, если вокруг есть меньшее количество узлов начало, чем цель, прямой поиск должен быть быстрее, тогда как, если вокруг цели меньше узлов, чем поиск, и обратный поиск должен быть быстрее. К сожалению, сложно узнать это число априори; вам обычно нужно либо выполнить поиск, чтобы определить, в чем дело. Вы можете использовать <a href="http://en.wikipedia.org/wiki/Branching_factor" rel="nofollow"> коэффициент ветвления вокруг двух узлов в качестве эвристики для этого значения, но это не обязательно гарантирует, что один поиск будет быстрее.
Один интересный алгоритм, который вы могли бы рассмотреть, - двунаправленный поиск в ширину , который выполняет поиск одновременно из исходного и целевого узлов. Это имеет тенденцию быть намного быстрее, чем стандартный поиск в ширину (в частности, с коэффициентом ветвления b и расстоянием d между узлами, BFS занимает примерно O (b d ) время, в то время как двунаправленная BFS принимает O ( б д / 2 )). Это также не так сложно, если у вас есть хорошая реализация BFS.
Что касается поиска в глубину, я на самом деле не знаю хорошего способа определения, который будет быстрее, потому что в худшем случае оба поиска могли бы исследовать весь граф, прежде чем найти путь. Если у кого-то есть хорошее объяснение о том, как определить, что будет лучше, было бы здорово, если бы он мог опубликовать его.