列车路径规划算法

Question

我正在为火车游戏中的路径查找问题寻找解决方案，其中存在不同种类的分歧路。我希望火车可以从一条铁轨上走到另一条，除了路径查找以外，其他功能都已实现。

我需要获取铁轨列表以便火车能够按照顺序行驶。现在的问题是如何获取列表。

我尝试过A*算法，但它会在节点（铁轨）已被访问时停止搜索，这是一个问题，因为到达某个点的方法可能是通过最长的路线行驶。

我也尝试过泛洪算法，这次如果已经访问过，则不会停止搜索，但问题是如何重构路径以及如何选择不再返回。

事实上，有些情况下火车必须多次经过一条铁轨才能到达目的地。

有什么想法吗？

起点为A，终点为B。如您所见，绿色路径是它应该行驶的路线。黑色圆圈表示火车将多次经过的铁轨，在本例中为2次。

显然，您需要从2号黑色开始才能到达3号红色。您不能只是走1号黑色- > 2号红色- > 1号红色- > 3号红色。

- marcg11

---

你能举个例子，说明在编程中何时需要多次通过一个轨道吗？ - Vitaly Olegovitch

我不明白A算法有什么问题，你不是想要走最短的路径吗？“也许到达一个点的方式是通过走最长的路线。”如果有一条路径存在，A算法会找到它，如果有多条路径，它会找到最短的那一条，为什么你要选择更长的那一条呢？ - pseudoDust

“也许到达一个点的方式是通过走最长的路线”，这句话的确切意思是什么？在什么情况下您不想选择最短的路线呢？ - BlueRaja - Danny Pflughoeft

所以你有一个由轨道连接的站台组成的图形，火车可以在站台上切换到任何一条轨道...简单地说，在每个站台上，火车会选择距离（下一站，目的地）最小的轨道。 - Khaled.K

这是一个图形，不完全由轨道构成，而是极限边界的轨道。让我上传一张图片... - marcg11

Answer 1

看这张图片

看起来你的问题可以用有向图很好地表示出来。在图中为每个停靠点和每个交叉口都分别给予两个节点，代表火车行驶的两个方向。Dijkstra算法非常适用于有向图，因此一旦将问题转化为这种形式，剩下的就很容易了。

例如，在上面的图片中，从A开始，我们移动到交叉口1。从那里，只有一个地方可以移动到，即交叉口2，因此会有一个箭头从A --> 交叉口1和一个箭头从交叉口1 --> 交叉口2。无论做出哪种选择，最终都会到达交叉口1，但是朝着另一个方向前进，因此我们需要创建一个单独的节点。从那里，您可以选择去A或B。

请注意，我去掉了一个J1，因为它是多余的（只有一个地方可去）。

如果列车可以在像A这样的停靠点停下并掉头，我们可以双向连接这两个节点的边，或者将它们合并为一个节点。

您可以给边赋权重以指定距离。

- BlueRaja - Danny Pflughoeft

---

我不明白，看起来你的图片描述了我所拥有的东西。链接 - marcg11

所以，我需要节点之间的两个连接而不是一个（双向）。Dijkstra算法如果已经访问过一个节点，它不会停止吗？我认为这里的问题在于算法，我需要一个可以重新检查节点并构建路径的算法。 - marcg11

@marcg11：最短路径永远不会包含同一个节点超过一次。正如我在答案中提到的，你应该将访问同一个节点但面对不同方向视为两个不同的节点。你的问题不在于算法错误，而在于问题表示方式错误。 - BlueRaja - Danny Pflughoeft

真正让我困惑的是，你说“作为两个独立的节点”，但在你的图像中，一个节点只是一个节点而不是两个……但我想我明白了。这意味着如果我改变表示方法，A*算法也可以工作，对吗？ - marcg11

我想澄清的是，你实际上并不需要为每个交叉点使用两个节点，我认为最好的方法是不要将交叉口视为节点，而是将节点视为“需要做决策的地方”，这样交叉口只是一个方向上的节点，在本例中为 A-->J2 ，因为那是第一个需要做选择的地方。如果这让人感到困惑，请忽略我的建议。 - pseudoDust

Answer 2

泛洪填充应该真的可以解决这个问题（我在类似的情况下使用了它）- 但您只需要仔细处理开关和段。

算法应该允许以不同的方向通过相同的段，但不能在同一方向上通过。也就是说，每个段实际上应该被视为两个独立的部分。

为了重建路径，您应该在泛洪时为段分配数字，以便从N-1到达的每个段都标记为N - 然后在向后移动时，跟踪段应该逐渐减少一个数字。

这确实有点像BFS。

- Rodion Gorkovenko

---

非常令人困惑，你能否发布一些伪代码，这将非常有帮助。你所说的“segments”是什么意思？我有一些节点它们之间有连接。 - marcg11