42

所以我有一个问题想用深度优先搜索来解决，返回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 坐标）。

所以我认为（在这一点上很难测试），这个函数，如果正确实现了其他一切，一旦达到目标状态，它就会返回。如果我遗漏了什么，请告诉我。不过，我最大的问题是返回什么。我希望它按从头到尾的顺序输出到达目标状态所需的所有状态的列表。似乎简单地返回我的堆栈并不能解决问题，因为堆栈将包含许多未访问的孩子。我的访问列表也不会产生任何有用的信息，因为可以想象我可能会到达死胡同，不得不回溯，但访问列表中仍然有死胡同。我将如何获得我想要的列表？

4

4 回答 4

52

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

但是，通过维护一个地图（字典）：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将递归中的所有节点打印备份 - 但此解决方案需要将算法重新设计为递归算法。

visitedPS 请注意，如果图包含无限分支 ，DFS 可能无法找到到目标的路径（即使维护一个集合）。如果您想要一个完整的（如果存在，总是找到解决方案）和最佳（找到最短路径）算法 -如果您有一些启发式函数
，您可能想要使用BFS或迭代深化 DFS甚至A* 算法

于 2012-10-12T17:25:32.843 回答
26

不是针对您的问题，但是您可以调整此代码并将其应用于不同的场景，实际上，您可以使堆栈也保持路径。

例子：

     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']
于 2016-09-07T17:40:42.403 回答
4

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

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

于 2012-10-12T17:17:06.467 回答
1

我刚刚在PHP.

背后的基本思想如下：为什么要维护另一个堆栈，当有调用堆栈时，它在执行的每个点都反映了从入口点获取的路径。当算法达到目标时，您只需要返回当前调用堆栈，这会导致读取向后的路径。这是修改后的算法。注意return immediately部分。

/**
 * Depth-first path
 * 
 * @param Node $node        Currently evaluated node of the graph
 * @param Node $goal        The node we want to find
 *
 * @return The path as an array of Nodes, or false if there was no mach.
 */
function depthFirstPath (Node $node, Node $goal)
{
    // mark node as visited
    $node->visited = true;

    // If the goal is found, return immediately
    if ($node == $goal) {
        return array($node);
    }

    foreach ($node->outgoing as $edge) {

        // We inspect the neighbours which are not yet visited
        if (!$edge->outgoing->visited) {

            $result = $this->depthFirstPath($edge->outgoing, $goal);

            // If the goal is found, return immediately
            if ($result) {
                // Insert the current node to the beginning of the result set
                array_unshift($result, $node);
                return $result;
            }
        }
    }

    return false;
}
于 2013-07-05T23:26:06.680 回答