Самый короткий путь в 3D-лабиринте

Question

Я пытаюсь написать программу, чтобы найти кратчайший путь в 3D-лабиринте с использованием рекурсии.

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

Обратите внимание, что я хочу сохранить рекурсивный подход.

Может кто-нибудь предложить решение?

Вот пример 2D лабиринт:

s  
XXXX 
XX X 
XXX 
Xe X 

Один начинается с s собирается e. X является препятствием, и является маршрутом.

Answer 1

Это зависит от алгоритма, который вы реализуете. Если вам нужен рекурсивный подход, то поиск случайного пути - хорошая начальная точка (хотя, если проблема слишком сложная, плохой выбор может иметь огромное влияние на количество попыток, необходимых для конвергенции). Затем вам нужно изменить путь и, например, проверить, является ли новый путь короче, чем предыдущий; если да, то вы продолжаете изменять свои параметры в одном направлении. В противном случае вы должны изменить свое направление. Критерий выхода для алгоритма/программы обычно является разницей между найденным решением и идеальным решением. Поэтому, если вы знаете длину идеального пути (оптимальное решение, вам не нужно знать сам путь, а только его длину), то вы можете определить допустимое поле ошибки 10^-9, например, и различие между обоими решениями меньше этого поля, ваш алгоритм выходит.

В заключение этот вопрос является проблемой математической оптимизации. Оптимизация - это область, которая имеет хорошо известную литературу, хотя она немного сложна. Однако, если бы я был вами, я бы искал алгоритмы кратчайшего пути и реализовал тот, который лучше всего подходит для моего приложения (3D Maze)