当绘制出这个简单图形后,上面的代码将返回路径中的答案为[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 NoneThe 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更多推荐
发布评论