3D 迷宫中的最短路径 [英] Shortest path in a 3D maze

问题描述

我正在尝试编写一个程序来使用递归找到 3D 迷宫中的最短路径.

I'm trying to write a program to find the shortest path in a 3D maze using recursion.

我能够编写在迷宫中找到随机路径的代码，但我想知道如何修改我的代码以找到最短路径.

I am able to write the code that finds a random path through the maze but I'm wondering how I can modify my code in order to find the shortest path.

请注意，我想保留递归方法.

Please note that I want to keep the recursive approach.

有人可以提出解决方案吗?

Can someone suggest a solution?

这是一个示例 2D 迷宫:

Here is a sample 2D maze:

s    
XXXX 
XX X
XXX  
Xe  X

从s开始到e.X 是障碍物， 是路径.

One starts from s going to e. X is an obstacle and is the route.

推荐答案

这取决于您正在实施的算法.如果您想要递归方法，那么找到随机路径是一个很好的起点(尽管如果问题太复杂，那么错误的选择可能会对收敛所需的尝试次数产生巨大影响).之后您需要修改路径，例如检查新路径是否比之前的路径短；如果是，那么您继续在同一方向修改您的参数.否则你必须改变你的方向.算法/程序的退出标准通常是找到的解决方案和理想的解决方案之间的差异.因此，如果您事先知道理想路径的长度(最佳解决方案，您不需要知道路径本身而只知道其长度)，那么您可以定义一个 10^-9 的误差范围，例如，一旦两个解决方案之间存在差异小于您的算法退出的这个保证金.

It depends on the algorithm you are implementing. If you want a recursive approach then finding a random path is a good start point (although if the problem is too complex then a bad choice could have huge effects on number of attempts needed for convergence). Afterwards you need to modify the path and for example check whether the new path is shorter than the pervious one; if yes then you continue modifying your parameters in the same direction. Otherwise you have to change your direction. Exit criterium for the algorithm/ program is normally the difference between the found solution and the ideal solution. So if you know the length of the ideal path (the optimal solution, you need not know the path itself but only its length) in advance then you can define an error margin of 10^-9 for example and once the difference between both solutions is less than this margin your algorithm exits.

总之，这个问题是一个数学优化问题.优化是一个拥有完善文献的领域，尽管它有点复杂.但是，如果我是你，我会搜索最短路径算法并实现最适合我的应用程序的算法(3D 迷宫)

In conclusion, this question is a mathematical optimization problem. Optimization is a field which has well-established literature eventhough it is a little bit complex. However if I were you I would search for shortest path algorithms and implement one which is best suited to my application (3D Maze)

这篇关于3D 迷宫中的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！