深度优先图搜索返回到目标的路径

Question

我已经一整个星期在尝试，但就是无法解决这个问题。

我知道需要一个辅助函数来递归并返回路径。但是我似乎无法理解递归。

我太困惑了，以至于我甚至无法准确地说明问题，除了递归之外。

感谢任何帮助。

编辑：好的，我稍微澄清一下。有一件事让我困惑，那就是当节点没有邻居时返回什么路径。目标路径可能会首先返回，但是因为辅助函数仍在递归，它可能会返回一条死路。我想我对回溯感到困惑。

- mikey555

---

你怎么使用这种方法进行回溯呢？ - mikey555

针对您的编辑，如果一个节点没有邻居，则深度优先搜索返回包含自身的路径（如果它是目标），并返回空路径（如果不是）。您是否正在寻找某种特定语言的DFS算法？ - Ray Toal

@Ray Toal：递归方法正是按照您所描述的方式进行操作，但使用操作系统堆栈而不是显式的应用程序堆栈。我不会建议一个刚学习计算机科学的程序员使用显式堆栈，因为虽然它更高效，但需要编写更多的代码才能实现相同的算法。 - Borealid

@Boreald 好的，我认为你是对的。递归解决方案确实需要更少的代码。 - Ray Toal

Answer 1

维基百科 上提供了一些非常好的深度优先遍历的伪代码。这些遍历算法会给图中所有节点标上它们在遍历中出现的顺序。但是你想要在找到目标时立即返回到目标的路径。

因此，我们需要修改维基百科上的算法：

( INCORRECT ALGORITHM DELETED WHICH THE OP COMMENTED ON CORRECTLY BELOW )

以下是Python的实现：

g = {
    'A': ['B', 'C', 'D'],
    'B': ['C', 'E', 'F'],
    'C': ['A'],
    'D': ['B', 'F', 'G', 'H'],
    'E': ['G'],
    'F': ['A', 'F'],
    'G': ['H', 'I'],
    'H': [],
    'I': []
}

def DFS(g, v, goal, explored, path_so_far):
    """ Returns path from v to goal in g as a string (Hack) """
    explored.add(v)
    if v == goal: 
        return path_so_far + v
    for w in g[v]:
        if w not in explored:
            p = DFS(g, w, goal, explored, path_so_far + v)
            if p: 
                return p
    return ""

# Hack unit test
assert DFS(g, 'A', 'I', set(), "") == "ABEGI"
assert DFS(g, 'A', 'E', set(), "") == "ABE"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'A', 'M', set(), "") == ""
assert DFS(g, 'B', 'A', set(), "") == "BCA"
assert DFS(g, 'E', 'A', set(), "") == ""

这里的想法是在图g中找到从v到目标goal的路径，假设您已经沿着path_so_far的路径来到了v。 path_so_far应该在v之前结束。

如果v是目标，您可以将v添加到路径中，这就完成了。

否则，您需要探索从v发出的所有边缘，这些边缘没有已经探索过的节点在边缘的另一端。 对于这些边缘中的每一个，您可以使用当前节点和已有路径进行搜索（递归）。如果从v到目标没有路径，则返回空路径。

好处是您使用递归来“自动回溯”，因为您将增强的路径传递给递归调用。

- Ray Toal

---

能否在这个方法中加入一个栈？我想使用一个栈并返回一条路径，但我认为这是不可能的。一个节点必须直接被其父节点调用才能保留其路径，因为我不能让节点拥有其后面的路径属性（这是一个作业要求）。使用一个栈会导致一个节点被孤立地评估，我无法通过节点的父节点将路径传递给该节点。 - mikey555

嗯，我在上面的代码中发现了一个问题。for循环检查节点的所有子节点，但它将在看到第一个未探索的节点时到达return语句，而不管该节点是否在正确的方向上。它将没有机会检查其他子节点。我错了吗？我的修复：对于所有子节点{ 如果子节点未被访问{ pathToGoal = DFS( ... , pathSoFar + v); 如果pathToGoal不是None { 返回PathToGoal; } } } 返回None - mikey555

@michael.greenwald，向您致敬并表示感谢，指出这一点！编写伪代码是个坏主意。今晚我会花些时间开发一个真正的路径查找应用程序。 - Ray Toal

@michael.greenwald 再次感谢。我写了一个实际的Python实现，可能对你有用。一个技巧是累积路径是一个字符串而不是一个数组，但我认为你可以处理它。 :) 希望有所帮助。 - Ray Toal

谢谢你的帮助，伙计。我找到了最简单的方法：不要把后继节点放在栈上，只需将元组（后继节点，到目前为止的路径）放在栈上即可！这是一种更占内存的解决方案，但它提供了路径历史记录。 - mikey555

Answer 2

递归是将一个问题缩小为一组较小的问题。

在这种情况下，假设您正在尝试从节点A到节点Z找到路径。首先，您查看A的邻居。假设它们是B、C和D。

现在你有三个子问题：从B到Z、从C到Z和从D到Z找到路径。如果您可以解决其中任何一个问题，您也已经解决了从A到Z寻找路径的更大问题。

所以，你进行递归。你在B、C和D上使用你的findPath方法，给每个方法一个包含A（防止它们向后移动）的已访问节点列表[1]。如果它们中的任何一个说“我找到了一条路径”，你就采用他们返回的路径，将A放在开头，然后结束。

在递归调用中，最终你会发现自己处于Z的邻居节点（如果A和Z实际上是连接的）。当这种情况发生时，您已经解决了问题：返回该链接。如果你最终到达一个死胡同节点，每个邻居都已经被访问过，返回一些代码，让你的调用者知道这是一个死胡同，他们不应该使用该节点来尝试构建解决方案。

[1] 顺便提一下：如果你特别聪明，你还可以将 B 放在传递给 C 的递归调用列表中，并将 B+C 放在传递给 D 的列表中。

- Borealid