我怎样才能让这个Python路径搜索找到正确的路径？(How can I make it so that this python path search finds the correct path?

我怎样才能让这个Python路径搜索找到正确的路径？(How can I make it so that this python path search finds the correct path?) def rightMostPath(graph, root, target, path = None): if path == None: path = [] path.append(root) if root == target: return path if root not in graph.keys(): return None for v in graph[root]: if v not in path: ep = rightMostPath(graph, v, target, path) if ep: return ep return None if __name__ == '__main__': graph = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1]} R = rightMostPath(graph, 0, 3) print(R)

当绘制出这个简单图形后，上面的代码将返回路径中的答案为[0,1,2,3]，显然路径应该是[0,1,3]。 我想知道是什么会导致这种情况发生，因为我看到的每个地方都指向Python中这种类型的图结构路径搜索。

def rightMostPath(graph, root, target, path = None): if path == None: path = [] path.append(root) if root == target: return path if root not in graph.keys(): return None for v in graph[root]: if v not in path: ep = rightMostPath(graph, v, target, path) if ep: return ep return None if __name__ == '__main__': graph = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1]} R = rightMostPath(graph, 0, 3) print(R)

The above code will return with the answer in path as [0,1,2,3] when after drawing out this simple graph it is obvious that the path should be [0,1,3]. I wanted to know what would be causing this to happen because everywhere I look points to this type of path search for graph structures in Python.

最满意答案

主要的问题是，在你知道它会工作之前，你将根追加到解决方案路径 ; 如果失败，你不会删除它。 由于路径遍布各处，这就是您要更新的主副本 - 失败的节点仍在路径中。 您访问的每个节点，无论它是否有助于解决方案，都会出现在最终副本中。

在失败时删除根 路径 ，或者在成功返回之前不要追加它（这需要对逻辑进行一些其他更改）。

快速解决方案：添加该行

path.remove(root)

在每个返回None的地点之前。 我现在得到了这种情况下的预期输出，而且这些老化的眼睛看起来像逻辑流程似乎是DFS。

def rightMostPath(graph, root, target, path = None): if path == None: path = [] path.append(root) if root == target: return path if root not in graph.keys(): path.remove(root) # Restore path return None for v in graph[root]: if v not in path: ep = rightMostPath(graph, v, target, path) if ep: return ep path.remove(root) # Restore path return None

The main problem is that you append root to the solution path before you know it will work; if it fails, you don't remove it. Since path is passed around everywhere, that's the master copy you're updating -- the failed node is still in the path. Every node you visit, whether or not it contributes to a solution, appears in your final copy.

Either remove root from path on failure, or don't append it until you return successfully (which requires a few other changes in your logic).

Quick solution: add the line

path.remove(root)

just before each spot where you return None. I now get the expected output for that case, and the logical flow looks like a DFS to these aging eyes.

def rightMostPath(graph, root, target, path = None): if path == None: path = [] path.append(root) if root == target: return path if root not in graph.keys(): path.remove(root) # Restore path return None for v in graph[root]: if v not in path: ep = rightMostPath(graph, v, target, path) if ep: return ep path.remove(root) # Restore path return None