Как уже указал mquander или Will, алгоритм A * может быть немного лучше вашей проблемы.
Я просто дам вам несколько советов, какой другой алгоритм вы можете использовать для решения проблемы.
Я не хочу объяснять, как работают эти алгоритмы, так как вы можете найти много хорошего описания в Интернете. Однако, если у вас есть вопрос, не стесняйтесь спрашивать меня.
Вы можете использовать некоторые алгоритмы, которые относятся к виду "неинформированного поиска". Там у вас есть, например, поиск в ширину, поиск в глубину, поиск с равномерной стоимостью, поиск с ограниченной глубиной или итеративный поиск с углублением. Если вы используете поиск в ширину или поиск с равномерной стоимостью, то вам, возможно, придется столкнуться с проблемой доступного пространства памяти, поскольку эти алгоритмы имеют экспоненциальную сложность пространства (и вам нужно сохранить все пространство поиска в памяти). Поэтому использование глубокого поиска (сложность O (b * m)) более дружественно для памяти, так как левая часть дерева, которое вы посещаете в первую очередь, может быть опущена, если она не содержит решения. Поиск с ограничением по глубине и итеративный поиск с углублением почти одинаковы, тогда как при итеративном поиске с углублением вы увеличиваете уровень поиска вашего дерева итеративно.
Если вы сравните временную сложность (b = коэффициент ветвления дерева, m = максимальная глубина дерева, l = предел уровня глубины, d = глубина решения):
в ширину: b ^ (d + 1)
равномерная стоимость: b ^?
глубина кулак: б ^ м
ограничено по глубине: b ^ l, если (l> d)
итеративное углубление: b ^ d
Так что, как вы можете видеть, итеративное углубление или поиск в ширину работают довольно хорошо. Проблема поиска с ограниченной глубиной состоит в том, что если ваше решение находится глубже, чем уровень поиска, вы не найдете решение.
Затем у вас есть так называемый «информированный поиск», такой как поиск по принципу «лучший сначала», «жадный поиск», «восхождение на гору» или имитация отжига. Короче говоря, для поиска в лучшем случае вы используете функцию оценки для каждого узла в качестве оценки «желательности». Цель жадного поиска - расширить узел, который приближает вас к цели. Подъем на холм и имитация отжига очень похоже. Стюарт Рассел объясняет восхождение на холм следующим образом (что мне очень нравится ...): алгоритм восхождения на холм похож на восхождение на Эверест в густом тумане с амнезией ». Это просто петля, которая постоянно движется в направлении увеличения стоимости. Таким образом, вы просто «идете» в направлении, которое увеличивает вашу функцию оценки.
Я бы использовал один из алгоритмов поиска в форме, так как они очень просты в реализации (вам просто нужно правильно запрограммировать дерево и пройти по нему). Информированный поиск обычно работает лучше, если у вас есть хорошая функция оценки ...
Надеюсь, это поможет вам ...