Python 在深度优先搜索中跟踪和返回路径
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12864004/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Tracing and Returning a Path in Depth First Search
提问by user1427661
So I have a problem that I want to use depth first search to solve, returning the first path that DFS finds. Here is my (incomplete) DFS function:
所以我有一个问题，我想使用深度优先搜索来解决，返回 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])
The startState and goalState variables are simply a tuple of x, y coordinates. problem is a class with a variety of methods. The important ones here are getSuccessors (which returns the children of a given state in the form of a list of 3 item tuples. for this part of the problem though, only the first element of the tuple, (child[0]), which returns the state of the child in x, y coordinates, is important) and isGoalState (which provides the x, y coordinates of the goal state).
startState 和目标状态变量只是 x, y 坐标的元组。问题是一个有多种方法的类。这里重要的是 getSuccessors（它以 3 个项元组列表的形式返回给定状态的子项。不过，对于这部分问题，只有元组的第一个元素 (child[0])，即在 x, y 坐标中返回孩子的状态，很重要）和 isGoalState（提供目标状态的 x, y 坐标）。
So I THINK (difficult to test at this point), that this function, given proper implementation of everything else, will return once it has reached a goal state. Please let me know if I am missing something. My biggest issue, though, is WHAT to return. I want it to output a list of all of the states it takes to get to the goal state, in order from the beginning to the end. It doesn't seem like simply returning my stack will do the trick, since the stack will include many unvisited children. Nor will my visited list yield anything useful, since it is conceivable I could reach dead ends, have to backtrack, but still have the dead-end tuples in the visited list. How would I go about getting the list I desire?
所以我认为（此时很难测试），这个函数在正确实现其他一切的情况下，一旦达到目标状态就会返回。如果我遗漏了什么，请告诉我。不过，我最大的问题是返回什么。我希望它按从开始到结束的顺序输出到达目标状态所需的所有状态的列表。似乎简单地返回我的堆栈并不能解决问题，因为堆栈将包含许多未访问的子项。我的访问列表也不会产生任何有用的东西，因为可以想象我可能会到达死胡同，不得不回溯，但访问列表中仍然有死胡同。我将如何获得我想要的清单？
采纳答案by amit
You are right - you cannot simply return the stack, it indeed contains a lot of unvisited nodes.
您是对的 - 您不能简单地返回堆栈，它确实包含许多未访问的节点。
However, by maintaining a map (dictionary): map:Vertex->Vertexsuch that parentMap[v] = the vertex we used to discover v, you can get your path.
但是，通过维护地图（字典）：map:Vertex->Vertex这样parentMap[v] = the vertex we used to discover v，您可以获得您的路径。
The modification you will need to do is pretty much in the for loop:
您需要做的修改几乎在 for 循环中：
for child in children:
stack.push(child[0])
parentMap[child] = parent #this line was added
Later on, when you found your target, you can get the path from the source to the target (pseudo code):
稍后，当您找到目标时，您可以获取从源到目标的路径（伪代码）：
curr = target
while (curr != None):
print curr
curr = parentMap[curr]
Note that the order will be reversed, it can be solved by pushing all elements to a stack and then print.
注意顺序会颠倒，可以通过将所有元素压入堆栈然后打印来解决。
I once answered a similar (though not identical IMO) question regarding finding the actual path in BFS in this thread
我曾经在这个线程中回答了一个关于在 BFS 中找到实际路径的类似（虽然不是相同的 IMO）问题
Another solution is to use a recursive version of DFS rather then iterative+stack, and once a target is found, print all currentnodes in the recursion back up - but this solution requires a redesign of the algorithm to a recursive one.
另一种解决方案是使用 DFS 的递归版本而不是迭代 + 堆栈，一旦找到目标current，将递归中的所有节点打印备份 - 但该解决方案需要将算法重新设计为递归算法。
P.S. Note that DFS might fail to find a path to the target (even if maintaining a visitedset) if the graph contains an infinite branch.
If you want a complete (always finds a solution if one exists) and optimal (finds shortest path) algorithm - you might want to use BFSor Iterative Deepening DFSor even A* Algorithmif you have some heuristic function
PS 请注意，visited如果图形包含无限分支，DFS 可能无法找到到达目标的路径（即使维护一个集合）。
如果您想要一个完整的（如果存在，则始终找到解决方案）和最佳（找到最短路径）算法 -如果您有一些启发式函数，您可能想要使用BFS或迭代深化 DFS甚至A* 算法
回答by Joran Beasley
this link should help you alot ... It is a lengthy article that talks extensively about a DFS search that returns a path... and I feel it is better than any answer I or anyone else can post
这个链接应该对你有很大帮助......这是一篇冗长的文章，广泛讨论了返回路径的 DFS 搜索......我觉得它比我或其他任何人可以发布的任何答案都要好
回答by user2555221
I just implemented something similar in PHP.
我刚刚在PHP.
The basic idea behind follows as: Why should I maintain another stack, when there is the call stack, which in every point of the execution reflects the path taken from the entry point. When the algorithm reaches the goal, you simply need to travel back on the current call stack, which results in reading the path taken in backwards. Here is the modified algorithm. Note the return immediatelysections.
背后的基本思想如下：为什么我要维护另一个堆栈，当有调用堆栈时，它在执行的每个点都反映了从入口点采取的路径。当算法达到目标时，您只需返回当前调用堆栈，这将导致向后读取路径。这是修改后的算法。注意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;
}
回答by XueYu
Not specific to your problem, but you can tweak this code and apply it to different scenarios, in fact, you can make the stack also hold the path.
不是针对您的问题，但您可以调整此代码并将其应用于不同的场景，实际上，您可以使堆栈也包含路径。
Example:
例子：
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']
