在深度优先搜索中跟踪和返回路径

Question

所以我有一个问题,我想使用深度优先搜索来解决,返回DFS找到的第一个路径.这是我的(不完整的)DFS功能:

    start = problem.getStartState()
    stack = Stack()
    visited = []
    stack.push(start)
    if problem.isGoalState(problem.getStartState):
        return something
    while stack:
        parent = stack.pop()
        if parent in visited: continue
        if problem.isGoalState(parent):
            return something
        visited.append(parent)
        children = problem.getSuccessors(parent)
        for child in children:
            stack.push(child[0])

startState和goalState变量只是x,y坐标的元组.问题是一个有各种方法的类.这里重要的是getSuccessors(它以3项元组的列表的形式返回给定状态的子节点.虽然这部分问题只是元组的第一个元素,(child [0]),返回x,y坐标中的子状态,重要)和isGoalState(提供目标状态的x,y坐标).

所以我认为(在这一点上难以测试),这个功能,如果适当实现其他一切,将在它达到目标状态后返回.如果我错过了什么,请告诉我.不过,我最大的问题是什么回归.我希望它按照从开始到结束的顺序输出到达目标状态所需的所有状态的列表.它似乎不是简单地返回我的堆栈将做的技巧,因为堆栈将包括许多未访问的孩子.我访问过的列表也不会产生任何有用的东西,因为可以想象我可以达到死胡同,不得不回溯,但仍然有访问列表中的死胡同.我如何获得我想要的清单？

Answer 1

你是对的 - 你不能简单地返回堆栈,它确实包含很多未访问的节点.

但是,通过维护一个地图(字典):map:Vertex->Vertex这样parentMap[v] = the vertex we used to discover v,你可以得到你的路径.

您需要做的修改几乎在for循环中:

    for child in children:
        stack.push(child[0])
        parentMap[child] = parent #this line was added

稍后,当您找到目标时,您可以获得从源到目标的路径(伪代码):

curr = target
while (curr != None):
  print curr
  curr = parentMap[curr]

请注意,顺序将颠倒,可以通过将所有元素推送到堆栈然后打印来解决.

我曾经回答了一个类似的(虽然不完全相同的IMO)关于在这个帖子中找到BFS中的实际路径的问题

另一个解决方案是使用递归版本的DFS而不是迭代+堆栈,一旦找到目标,就会打印current递归中的所有节点 - 但是这个解决方案需要将算法重新设计为递归算法.

PS请注意,visited如果图形包含无限分支,则DFS可能无法找到目标路径(即使维护集合).
如果你想要一个完整的(总是找到一个解决方案,如果存在)和最优(找到最短路径)算法 - 如果你有一些启发式函数,你可能想要使用BFS或Iterative Deepening DFS甚至A*算法

Answer 2

不是特定于您的问题,但您可以调整此代码并将其应用于不同的场景,事实上,您可以使堆栈也保持路径.

例:

     A
   /    \
  C      B
  \     / \
   \    D E
    \    /
       F


graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}




def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                stack.append((neighbor, path + [neighbor]))

print (dfs_paths(graph, 'A', 'F'))   #['A', 'B', 'E', 'F']

Answer 3

这个链接应该对你有很大帮助...这是一篇很长的文章，广泛讨论了返回路径的 DFS 搜索...我觉得它比我或其他任何人可以发布的任何答案都要好

http://www.python.org/doc/essays/graphs/