任何人都可以解释深度优先搜索的这种实现吗？

Question

所以我现在正在学习搜索算法，如果有人能解释一下深度优先搜索的实现方式，我将不胜感激，我确实理解深度优先搜索作为一种算法工作，但我很难理解它是如何在这里实现的。

感谢您的耐心理解，代码如下：

map = {(0, 0): [(1, 0), (0, 1)],
   (0, 1): [(1, 1), (0, 2)],
   (0, 2): [(1, 2), (0, 3)],
   (0, 3): [(1, 3), (0, 4)],
   (0, 4): [(1, 4), (0, 5)],
   (0, 5): [(1, 5)],
   (1, 0): [(2, 0), (1, 1)],
   (1, 1): [(2, 1), (1, 2)],
   (1, 2): [(2, 2), (1, 3)],
   (1, 3): [(2, 3), (1, 4)],
   (1, 4): [(2, 4), (1, 5)],
   (1, 5): [(2, 5)],
   (2, 0): [(3, 0), (2, 1)],
   (2, 1): [(3, 1), (2, 2)],
   (2, 2): [(3, 2), (2, 3)],
   (2, 3): [(3, 3), (2, 4)],
   (2, 4): [(3, 4), (2, 5)],
   (2, 5): [(3, 5)],
   (3, 0): [(4, 0), (3, 1)],
   (3, 1): [(4, 1), (3, 2)],
   (3, 2): [(4, 2), (3, 3)],
   (3, 3): [(4, 3), (3, 4)],
   (3, 4): [(4, 4), (3, 5)],
   (3, 5): [(4, 5)],
   (4, 0): [(5, 0), (4, 1)],
   (4, 1): [(5, 1), (4, 2)],
   (4, 2): [(5, 2), (4, 3)],
   (4, 3): [(5, 3), (4, 4)],
   (4, 4): [(5, 4), (4, 5)],
   (4, 5): [(5, 5)],
   (5, 0): [(5, 1)],
   (5, 1): [(5, 2)],
   (5, 2): [(5, 3)],
   (5, 3): [(5, 4)],
   (5, 4): [(5, 5)],
   (5, 5): []}

visited = []
path = []
routes = []


def goal_test(node):
    if node == (5, 5):
        return True
    else:
        return False


found = False


def dfs(visited, graph, node):
    global routes
    visited = visited + [node]
    if goal_test(node):
        routes = routes + [visited]
    else:
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)


dfs(visited, map, (0, 0))
print(len(routes))
for route in routes:
    print(route)

Answer 1

此实现采用了几种不良做法：

map 是一个原生的 Python 函数，所以用那个名字创建一个变量是个坏主意。
visited 不需要在全局范围内初始化：调用者对此不感兴趣，因为它只在 DFS 算法本身中发挥作用
routes 也不应该初始化为一个空列表，而且 dfs 改变这个全局变量是不好的。相反 dfs 应该 return 向调用者提供该信息。这使得一个 dfs 调用 self-contained，因为它 return 是从当前节点到目标的可能路径。由调用者使用附加节点扩展此 returned 集合中的路由。
goal_test的正文应该写成return node == (5, 5)。 if ... else 只是将布尔值转换为相同的布尔值。
函数 goal_test 似乎有点矫枉过正，因为您只能将参数传递给代表目标节点的 dfs 函数。这也使它更通用，因为您不需要 hard-code 函数内的目标位置。
path 和 found 已初始化但从未使用过。
dfs 会运行进入堆栈溢出。它不会发生在给定的图上，因为该图是非循环的，但是如果您在给它循环图时也可以依赖此函数会更好。
dfs 将多次访问同一个单元格，因为它可以通过不同的路径找到（例如 (2,2)），因此它将从那里执行之前已经进行过相同的 DFS 搜索。通过存储上次访问该单元格的结果，可以稍微提高效率，即我们可以使用记忆。收益很小，因为大部分时间都花在创建和复制路径上。如果函数只计算路径的数量，而不是构建它们，那么（使用记忆化）的收益将是显着的。

这是一个处理上述几点的实现。它使用包装函数向调用者隐藏记忆化的使用，并减少需要传递给 dfs:

的参数数量

def search(graph, source, target):
    # Use memoization to avoid repetitive DFS from same node, 
    #  Also used to mark a node as visited, to avoid runnning in cycles
    memo = dict()  # has routes that were already collected

    def dfs(node):
        if node not in memo:  # not been here before
            if node == target:
                memo[node] = [[target]]
            else:
                # Mark with None that this node is on the current path
                #   ...avoiding infinite recursion on a cycle
                memo[node] = None  # temporary value while not yet back from recursion
                memo[node] = [
                    [node] + route 
                        for neighbour in graph[node]
                            for route in dfs(neighbour) 
                                if route
                ]
        return memo[node]

    return dfs(source)

graph = {(0, 0): [(1, 0), (0, 1)],
    # ...etc ... 
}

routes = search(graph, (0, 0), (5, 5))

print(len(routes))
for route in routes:
    print(route)

任何人都可以解释深度优先搜索的这种实现吗？

Can anyone explain this implementation of depth first search?

python

algorithm

depth-first-search