如何修改递归算法以找到最短路径？

Question

https://vimeo.com/70999946

我实现了一个递归路径查找算法。这个递归算法基于一组预设的相互连接的节点工作。每个节点都有四个指针，包含进一步的方向：上、下、左和右。递归算法简单地遍历每个节点，并依次寻找这四个方向中的每一个，以达到其最终目的地；例如，考虑以下7个节点：A、B、C、D、E、F、G、H。

    A (Button->D, Right->B)
    B (Right->C, Left->B)
    C (Left->B)
    D (Button->G, Right->E, Top->A)
    E (Right->F, Left->D)
    F (Left->E)
    G (Right->H, Top->D)
    H (Left->G)

这些节点在整体视图中将显示以下图像。

A—B—C
|
D—E—F
|
G—H

在这个例子中，假设行走者的起始节点是A节点，他的最终目的地是H节点。节点A按照顺序查看自己的右侧、下方、左侧和上方；由于它的右侧指向节点B，所以它选择前往节点B；节点B按照同样的模式选择其右侧的节点C。当行走者到达节点C时，由于它的右侧、上方和下方被阻挡，节点C回到了节点B。节点B也回到了节点A。行走者再次回到了起点。然后，节点A按照顺序前往其下方的节点D。节点D先前往其右侧的节点E，然后再前往节点F。由于节点F被阻挡，它返回到了节点E和节点D。之后，节点D按照行走者的顺序选择前往其下方的节点G。从那里，节点G前往节点H。最终，行走者到达了他的最终目的地。

Pseudocode: Recursive Path Finding Algorithm
ArrayList findPath(GameObject currentPoint , GameObject targetPoint , ArrayList InputArrayList)
{
1-Duplicate InputArrayList as tempArrayList

2-If the currentPoint equals to target Point return inputArrayList
//*** End Condition found target

3-If the Right side of the currentPoint is empty goto step 4
3.1- Add currentPoint to tempArrayList
//*** Call Right
3.2- tempArrayList = findPath(currentpoint.Right, targetPoint, tempArrayList);
3.3- If tempArrayList is not null return tempArrayList
4-If the Button side of the currentPoint is empty goto step 5
4.1- Add currentPoint to tempArrayList
//*** Call Button
4.2- tempArrayList = findPath(currentpoint.Button, targetPoint, tempArrayList);
4.3- If tempArrayList is not null return tempArrayList
5-If the Left side of the currentPoint is empty goto step 6
5.1- Add currentPoint to tempArrayList
//*** Call Left
5.2- tempArrayList = findPath(currentpoint.Left, targetPoint, tempArrayList);
5.3- If tempArrayList is not null return tempArrayList
6-If the Top side of the currentPoint is empty goto step 7
6.1- Add currentPoint to tempArrayList
//*** Call Top
6.2- tempArrayList = findPath(currentpoint.Top, targetPoint, tempArrayList);
6.3- If tempArrayList is not null return tempArrayList
7-Return null;
//*** End Condition does not found target
}

注意：实际代码是用C#编写的，您可以从此链接下载。

案例研究中出现的问题： 当您理解这段代码时，会发现它有一个弱点。为了说明这一点，请考虑以下节点的总体视图，假设起始节点是A节点，终点是H节点。

A—B—C
|
D—E—F—I
|   | |
G—H—J—K

尽管最佳路径解决方案是（A，D，G，H），但解释递归路径查找算法将（A，D，E，F，I，K，J，H）作为其解决方案；这似乎表明机器人是一个愚蠢的机器人:D！

图1：递归路径查找算法 图2：具有学习能力的递归路径查找算法 我通过为节点添加学习能力来解决了这个问题。您可以从此link了解问题的详细信息。但是，我想知道是否有人可以修改递归算法以找到最短路径。 谢谢，

- Dan

---

+1 非常好的演示 :) - Kay

你的递归需要做的就是实际存储最短路径。目前它基于你的绕路顺序（右，左，上，下）返回到目标的第一条有效路径。不要在找到“目标”时返回路径，而是将currentPath + target与类成员“shortestPath”进行比较，如果更短，则存储为新的“shortestPath”。话虽如此，Geoffrey的答案更具普适性。 - Jerdak

谢谢@Kay，实际上我是在我的博客上写了这个解释，然后把它粘贴到这里:D - Dan

@Jerdak，感谢您特别指出我的错误，尤其是关于按钮的问题：))。您是正确的，目前递归算法会返回第一个可能的解决方案。但是，我在这里提出问题的意思是，如何修改递归算法以找到所有可能的解决方案，无论是否有目标设备限制（iPad）。 - Dan

Answer 1

为什么不直接将其与Dijkstra和A*搜索进行比较呢？

需要注意的是，使用递归而不是循环，可能会在1025次递归时出现堆栈溢出。

- Geoffrey De Smet

---

感谢Dijkstra算法和A*搜索。正如您所说，实现这样的算法确实非常困难。我的算法非常简单和轻巧。它基于先到先服务的原则，根据顺序选择任何可用的方向，行者选择该方向的节点进行进一步调查。我希望找到任何轻巧且具有递归解决方案的方法。 - Dan

我实际上的意思是：任何递归代码都可以重写为循环代码，而不改变实际算法。因此，它的行为完全相同，只是如果递归深度超过1024级，则不会抛出堆栈溢出。 - Geoffrey De Smet

在1024次递归调用时，栈将会有几千字节。我非常怀疑你会因为这个而引发堆栈溢出。 - BlueRaja - Danny Pflughoeft

@GeoffreyDeSmet，你说得对，我也曾经用这个简单算法遇到过堆栈溢出的问题。我的节点总数大约是100个。如果你注意到了，目前我的“结束条件找到目标”在第二行。起初我把它放在第7行，然后把未找到目标移到第8行。但是算法遇到了堆栈溢出错误。总的来说，我可以说这个项目没有任何机会实现Dijkstra和A*搜索。再次感谢。 - Dan

@Daniel，你可以在不遇到stackoverflow问题的情况下实现Dijkstra算法。创建一个未处理的递归队列，然后不要调用递归方法，而是将一个项目添加到该队列中。然后只需使用while循环，直到队列为空为止。 - Geoffrey De Smet

Answer 2

你正在进行深度优先搜索，但你需要做的是广度优先搜索。后者需要使用队列而不是递归。维基页面很好地解释了如何实现它，因此我在这里不再重复。

从那里开始，实现A*并不需要太多工作，这应该可以加速您的结果。这将需要一个优先队列而不是一个队列；C#在基本库中没有优先队列，但是，幸运的是，我是一个专门用于路径查找的优化C#优先队列实现的作者。

另外，既然你提到了Unity，我要指出有许多专门为Unity构建的寻路库。这可能是最安全的路线，因为在视频游戏中进行高效的寻路是非常复杂的。

- BlueRaja - Danny Pflughoeft

---

哇，谢谢啊，你解释的算法正是深度优先搜索。我真的需要思考一下你的解决方案，因为我唯一明白的是我对这里所代表的四种不同算法一无所知 :D !!!!? （迪杰斯特拉、A*搜索、深度优先搜索、广度优先搜索） - Dan

广度优先搜索不能用递归写，这种说法正确吗？ - Dan

@Danial：BFS、Dijkstra 和 A* 算法基本上类似。请参阅 此处 和此处 获取更多信息。针对您的第二个问题：使用队列来实现 BFS。 - BlueRaja - Danny Pflughoeft

我大致看了一下。我认为，正如你所提到的，BFS是我想要的另一个解决方案。如果实现Dijkstra和A*算法，我会遇到堆栈溢出问题，这是毫无疑问的，对吗？ - Dan

@Danial：不， 请阅读我链接的帖子。BFS和Dijkstra在无权图上是相同的 *(至少在像你这样的无权图上)。A只是对这些算法的简单扩展，使用额外信息（即“启发式”）使算法更快。 - BlueRaja - Danny Pflughoeft

Answer 3

这是一份深度优先的代码（编写更快），但并不推荐用于路径查找。BlueRaja和Geoffrey的回答是更通用、稳定且更好的路径查找算法。但我想回答OP的直接问题。

为了简化示例，边缘具有成本/权重1。最短路径==到达目标节点所需的最少节点数的路径（技术上length == |path| - 1，因为我计算的是节点而不是边缘，但无论如何，思想是相同的）。该代码将不处理循环，因此其他算法是更好的选择。

public class PathNode {
    public string Id;
    public PathNode[] Children = new PathNode[4];
}

public class PathFinder : MonoBehaviour {
public List<PathNode> shortestPath = null;

/// <summary>
/// Sets shortest path to `candidatePath` if `candidatePath` is shorter
/// or no shortest path yet.
/// </summary>
public void SetShortestPath(List<PathNode> path){
    if(shortestPath == null){
        shortestPath = new List<PathNode>(path);
        return;
    }
    if(path.Count < shortestPath.Count)
        shortestPath = new List<PathNode>(path);
    }

/// <summary>
/// depth-first shortest path
/// </summary>
public void FindShortestPath(PathNode target, List<PathNode> path){
    PathNode next = path[path.Count-1]; //get next node from path
    if(target == next){
        SetShortestPath(path);
        return;
    }
    // dfs - iterate children
    foreach (PathNode node in next.Children){
        if(node!=null){
            path.Add(node);             
            FindShortestPath(target,path);
            path.Remove(node);          
        }
    }
}
public PathNode ExampleEdgeCreation(){
    PathNode a = new PathNode{Id="A"};
    a.Children[(int)Direction.Left] = new PathNode{Id="B"};
    return a;
}
}

假设 PathNode.Children[0] == PathNode.Children[Left] 等等。我在代码中枚举了它们，但是我想让这个示例保持简短。

- Jerdak

---

感谢您修订算法，:) - Dan