迷宫至少变成

我有一个问题，我无法解决。我有一个迷宫，我必须找到一个从S点到E点的路径，它具有最少的转向点。据了解，E点是可以重复使用的。我只能在四个方向上移动，左右上下移动。它不一定是最短的路径，只是最少的转弯。迷宫至少变成

我试图存储优先队列中的转数。例如，当我到达迷宫中的某个位置时，我将添加转数直到那里。从那里我将他的邻居添加到优先级队列中，如果它们还没有被访问或者它们不是墙壁，那么当前块的值就是我所坐的位置，例如t + x，它可以具有以下值（0 - 如果邻居面向同一个方向，我是当我靠近他时面对，或者如果它在不同的方向，则为1）。似乎这种方法不适用于每种情况。

我会很感激，如果有人可以给我一些提示，没有任何代码。

来源

2015-01-26 user3141709

枚举所有路径，取最小的那个。为了优化，记住迄今为止的最短解决方案，并且一旦它不能再导致更短的路径，就中止对部分解决方案的探索。 – 2015-01-26 22:26:51

你了解广度优先搜索的想法吗？ – Beta 2015-01-26 22:34:38

将迷宫中给定交叉点** A **的邻居列表更改为包含直线上从** A **可到达的每个交叉点。（“交叉点”包括迷宫的开始和结束。）现在找到最短路径。 – beaker 2015-01-26 22:39:59

您正处在正确的轨道上。你需要实现的这个问题是Dijkstra's algorithm。你只需要考虑不只是点作为图顶点，而是对(point,direction)。从每个顶点(p,d)你有5个边缘（尽管最后一个可以被墙壁阻挡）：(p,0),(p,1),(p,2),(p,3),。前四个边的重量为1（当你转弯时），最后一个的重量为0（不转，只是向前移动）。算法足够好，可以忽略循环，并且对于权重为0的边都可以正常工作。当从优先级队列中提取任何顶点(end point, _)时，应该结束。

该方法有一个问题，因为在该过程中检查了太多的顶点。如果你的迷宫很小，那不是问题。否则，请考虑一个名为A*的轻微修改。你需要一个很好的启发式功能，描述目标转弯次数的下限。

来源

2015-01-26 22:49:40 deniss

这基本上是正确的，但我被5个边缘弄糊涂了。由于移动只是U，D，L和R，我认为每个位置至多有4个图顶点，每个顶点对应于传入的方向，并且每个顶点都可以被墙堵塞。（您可能希望开始位置有一个特殊的“不关心”方向 - 在这种情况下，只会有一个顶点与该位置相对应。） – 2015-01-27 11:04:02

迷宫至少变成

回答

相关问题