7

我整个星期都在尝试这个，但为了我的一生，我无法弄清楚。

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

我很困惑，以至于除了递归之外，我什至无法准确地制定出问题所在。

谢谢你的帮助。

编辑：好的，我会澄清一点。让我感到困惑的一件事是当节点没有邻居时返回什么路径。目标路径可能会先返回，但随后，由于助手仍在递归，它可以返回死路。我想我对回溯感到困惑。

4

2 回答 2

9

Wikipedia实际上有一些非常好的用于深度优先遍历的伪代码。这些遍历算法用它们在遍历中出现的顺序标记图中的所有节点。相反，您希望在找到目标后立即返回目标路径。

所以让我们修改一下维基百科的算法：

( 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。 path_so_far实际上应该在之前结束v。

如果v是目标，您可以添加v到到目前为止的路径中，仅此而已。

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

好消息是您正在使用递归来“自动回溯”，因为您将增强路径传递到递归调用中。

于 2011-09-10T22:37:46.357 回答
1

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

在这种情况下，假设您试图找到从节点 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 的列表中。

于 2011-09-10T22:25:17.990 回答