python - BFS 输出图的最短路径

Question

我正在尝试创建一个回溯函数，它将返回从根到 GOAL

的最短路径顺序列表

我的路径持有人:

path_holder = {
   'node1':['node2','node3','node5'],  
   'node2':['node1','node8','node10'],
   'node3':['node4','node6']},
   'node4':['node2','node1','node3'],
   'node5':['DEADEND'],
   'node6':['GOAL']
    ....
    }

在我的 path_holder 输入中，它是 BFS 的输出，因此第一个节点是根节点，最后一个节点是目标节点。因为 path_holder 输入是 BFS 的输出，它会在找到 GOAL 时停止，因此所有作为先前节点分支的节点都需要搜索 GOAL 也被添加到 path_holder 中。

目前我陷入了发生无限循环的 while 循环。我的一般策略是从 GOAL 节点开始，使用该节点的键查找该键在另一个键(节点)列表中的位置。一旦找到该节点(它的列表中包含 key )，我就将该节点的 key 设置为新目标。 (混淆句抱歉)

这张图可能包含循环，这可能就是我得到无限循环的原因。

我的回溯函数:

def backtrace(path_holder, root, goal):
    dct = {}
    for d in path_holder:
            dct.update(d)
    rootnode = root.keys()[0]
    goal = goal.keys()[0]
    #x = len(path_holder)
    path = []
    path.append(goal)
    #for i in reversed(xrange(x):
    #   path_holder[i].keys()
    while goal != rootnode: 
        # find key that contains goal in list
        for i in dct:
            #print i
            for j in dct[i] :
                if j not in path:
                    if j == goal:
                        path.append(i)
                        goal = i
        # append key that has goal in the list
        # set goal to be the key that was appended
        # repeat
    return path

例如:输出

path = ['node1','node3','node6']

Answer 1

1。错误

1. 当我运行您的代码时出现以下错误:

   >>> backtrace(path_holder, 'node1', 'GOAL')
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "q20349609.py", line 13, in backtrace
       dct.update(d)
   ValueError: dictionary update sequence element #0 has length 1; 2 is required
   

   那是因为当你像这样遍历字典时:

   for d in path_holder:
   

   您得到的是字典的键。所以 d 取值 'node1'、'node2' 等等，你不能将这些传递给 dict。更新方法。

   但是你到底想在这里做什么？如果你试图将 path_holder 复制到 dct 中，你可以这样写:

   dct = dict(path_holder)
   

   但为什么要复制呢？为什么不直接使用 path_holder？

2. 修复错误 #1 后，程序运行但陷入无限循环。那是因为这些行:

   if j not in path:
       if j == goal:
           path.append(i)
   

   这些行意味着你只添加一个节点到路径，如果它有一个邻居 j 还没有在路径中，但等于目标。但是请稍等，此时 goal 已经在路径中。所以这两个条件不能同时满足。因此，没有任何东西被添加到路径中!

   清楚的是:

   if j not in path:
   

   应该是:

   if i not in path:
   

   因为 i 是我们考虑添加到路径中的节点。

3. 修复错误 #1 和 #2 后，程序取得了一些进展，但仍然陷入无限循环。如果我们在 path.append(i) 之后添加 print(path) 行，那么我们会得到以下输出，直到它卡住为止:

   >>> backtrace(path_holder, 'node1', 'GOAL')
   ['GOAL', 'node6']
   ['GOAL', 'node6', 'node3']
   ['GOAL', 'node6', 'node3', 'node4']
   

   可以看到搜索出错了:从node3到了node4，但是没有从node4的路由到 GOAL 除了通过 node3 的那个。并且搜索永远不会考虑将 node3 添加到路径中，因为它已经存在。

2。该怎么做

当你找到一个像node4这样的节点的路径时，你无法知道该节点是否在从GOAL到的最短路径上节点 1。此时你所能知道的是如果 node4 位于从GOAL 到node1 的最短路径上，< em>然后您将通过 node3 到达那里。这就是您必须记录的全部内容。

我是这样实现的，使用字典 visited 为每个节点记录从 start 到该节点的最短路径上的前一个节点，以及 collections.deque维护一个节点队列，我们​​可能还没有访问过其邻居。

from collections import deque

class NotFound(Exception): pass

def search(graph, start, goal):
    """Find the shortest path from start to goal in graph (which must be a
    map from a node to an iterable of adjacent nodes), using
    breadth-first search.

        >>> graph = {
        ...     1: [2, 4, 5],  
        ...     2: [1],
        ...     3: [4, 6],
        ...     4: [2, 1, 3],
        ...     5: [],
        ...     6: [7],
        ...     7: [],
        ... }
        >>> search(graph, 1, 7)
        [1, 4, 3, 6, 7]
        >>> search(graph, 1, 1)
        [1]
        >>> search(graph, 5, 1) # doctest: +IGNORE_EXCEPTION_DETAIL
        Traceback (most recent call last):
            ...
        NotFound: No path from 5 to 1

    """
    visited = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = visited[node]
            return path[::-1]
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited[neighbour] = node
                queue.append(neighbour)
    raise NotFound('No path from {} to {}'.format(start, goal))

注意事项:

1. 您的变量 path_holder 包含一个称为 graph in adjacency list representation 的数据结构。所以我将此变量称为 graph。

2. 我已经编写了一个文档字符串来解释该函数的作用以及如何调用它。文档字符串还包含可以使用 doctest 模块运行的嵌入式代码示例。

3. 您的函数从目标向后搜索到起点。但这与从开始到目标的所有边都反转的向前搜索是一样的。所以我通过向前搜索让事情变得简单。