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迷宫:

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 Maze)

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屋！