python - 用 Python 实现了广度优先搜索算法。不知道如何返回解决方案

Question

我设法做了一个像广度优先一样扩展的寻路算法，避免重新访问节点，并检测是否找到目标节点。然而，我正在努力解决的主要问题是找到解决方案，即从起始节点到目标节点的实际路径。基本上一切正常，但我不知道如何返回从起始节点到目标节点的实际路径。

顺便说一下，如果您想知道，这不是作业。我正在自学寻路算法(以及一般的 AI)，并试图重新创建广度优先搜索算法。因此，我欢迎 psuedocode(因为它会告诉我我应该做什么，我可以自己想出代码来从中学到很多东西。)

是否可以用我的算法返回一个解决方案(从起始节点到结束节点的路径)？我是否必须重写我的整个算法，或者是否有一段代码从我的广度优先搜索算法返回路径

import collections

def bfs(graph,start, end):
    path = collections.deque()
    trail = collections.deque()
    solution = collections.deque()


    path.append(start)

    # A series of visited nodes
    trail.append(start)

    if start == end:
        return path
    while True:
        for node in graph[start]:
            print node

            # Adds node to path if it is not visited already
            if node not in trail:
                path.append(node)
                trail.append(node)
                print path        

        #Removes parent node after all children added to path (by removing the left of the path)
        path.popleft()
        start = path.popleft()
        path.appendleft(start)
        print "****Node Scan Completed:****"
        print path

        # If goal node is reached
        if start == end:
            print "----------------------Final Results:----------------------"
            print trail
            print path
            return solution
    print "Final Results:"
    print trail
    print path
    return None


graph = { "a" : [],
          "b" : ["a"],
          "c" : ["a"],
          "d" : ["b","c","e"],
          "e" : ["h","r"],
          "f" : ["c","g"],
          "g" : [],
          "h" : ["p","q"],
          "p" : ["q"],
          "q" : [],
          "r" : ["f"],
          "s" : ["d","e","p"]
        }

print bfs(graph,'s','g')

Answer 1

首先，感谢您花时间自学。

您的算法遗漏了一个非常重要的部分:正如您已经意识到的那样，您没有保存有关从起始节点到结束节点的路径的信息。您只存储访问过的节点(在 trail 变量中)和要访问的节点(在 path 中)变量。解决方法很简单。只需添加一个父节点的 map，这样无论何时访问一个节点，您都知道您来自哪个节点。到达结束节点后，您可以检查此父节点图，构建解决方案路径，直到到达起始节点。

在代码中，只需在最顶部添加一个新的 parents 映射:

path = collections.deque()
trail = collections.deque()
parents = {} # New line

接下来，添加代码以在循环中填充此 map :

        # Adds node to path if it is not visited already
        if node not in trail:
            parents[node] = start # New line
            path.append(node)
            trail.append(node)

最后添加代码以在函数底部构建和返回解决方案:

    # If goal node is reached
    if start == end:
        print "----------------------Final Results:----------------------"
        print trail
        print path

        solution = [end] # New code from here down
        n = end
        while n in parents and parents[n]:
            solution.append(parents[n])
            n = parents[n]

        return solution[::-1]

您可以找到 entire code here .