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

Question

https://vimeo.com/70999946

我实现了一个递归寻路算法。这种递归算法基于预先设置的连接在一起的节点集。每个节点都有四个包含进一步方向的指针:Top、Button、Left 和 Right。递归算法简单地遍历每个节点并逐个寻找这四个方向中的每一个以到达其最终目的地；举个例子，考虑以下 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)

这些节点在整体 View 中会显示如下图。

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

在这个例子中，假设walker的起始节点是节点A，并想去节点H作为它的最终目的地。节点A按顺序查看自己的Right、Button、Left和Top；它的右边指向节点 B，因此他选择去节点 B；相同模式的节点B选择向右走，即节点C。当步行者到达节点C时；由于它的 Right、Top 和 Button 被阻止，节点 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#，你可以从这里下载 link .

案例研究中出现的问题:正如您对这段代码的理解；它有一个弱点，来说明它；考虑以下节点整体 View ，假设起始节点为节点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可以看出问题的细节。但是，我想知道是否有人可以修改递归算法以找到最短路径。

谢谢，

Answer 1

为什么不简单地将它与 Dijkstra 进行比较呢？和 A* search ？

请注意，通过使用递归而不是循环，您可能会在 1025 次递归时获得 StackOverflow。