python - 找到解决方案/返回后如何停止递归
问题描述
我的递归函数有问题,希望在这里得到帮助。
我想编写一个函数,在其中找到两个节点之间的所有路径,该函数应该在找到解决方案后停止并输出第一个路径。如果已经找到该路径,则该函数应继续执行,直到找到下一条路径并再次停止并输出找到的路径。
为此,我编写了一个函数(或我打算这样做),它从起始节点开始,然后到它的邻居节点,然后到邻居节点的邻居节点等,直到到达结束节点。然后它应该输出路径。如果没有到达结束节点,它应该删除最后一个节点并继续在那里。所以是一种带回溯的DFS算法。
我的问题是该函数在找到结束节点后并没有停止。我认为这是因为仍有“打开”的功能需要关闭。如果我在代码底部写“return pathfind(nknots)”而不是“pathfind(nkots)”,那么我的代码会在到达结束节点时停止,但如果尚未到达结束节点,则不会继续回溯. 所以在这两种情况下我都有问题。
有谁知道我如何解决这个问题?最好以一种我不必过多更改自己的代码/想法的方式?
def pathfind(x):
visited.add(x)
if neighbours[x] != {}:
for nknots in neighbours[x]:
if nknots == n:
print("final node is found")
augpath.append(n)
return augpath
elif nknots in augpath or nknots not in neighbours or nknots in visited:
print("Node already in augpath, visited or has no neighbours: ")
continue
else:
augpath.append(nknots)
pathfind(nknots) # pathfind on new node
visited.remove(nknots)
augpath.pop()
解决方案
如果您希望函数在遇到结束节点时立即停止并返回路径,那么您应该使用以下return
语句告诉它停止:
def onepath(start, end, neighbours, path=[], visited=None):
if visited is None:
visited = {start}
if start == end:
return path + [start]
else:
for n in neighbours[start]:
if n not in visited:
visited.add(n)
p = onepath(n, end, neighbours, path + [start], visited)
if p:
return p
return None
如果要查找所有路径,则应返回由所有递归调用找到的所有路径组成的列表:
def allpaths1(start, end, neighbours, path=[], visited=set()):
if start == end:
return [path + [start]]
else:
return [p
for n in neighbours[start]
if n not in visited
for p in allpaths1(n, end, neighbours, path + [start], visited | {start})
]
请注意,使用 double 进行列表推导的语法for
有点尴尬。对于这些类型的函数,我认为最 Pythonic 的方式是使用生成器,而不是列表:
def allpaths2(start, end, neighbours, path=[], visited=set()):
if start == end:
yield path + [start]
else:
for n in neighbours[start]:
if n not in visited:
yield from allpaths2(n, end, neighbours, path + [start], visited | {start})
neighbours = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2, 4], 4: [1, 3]}
# 1 - 2
# | \ |
# 4 - 3
print(onepath(1, 3, neighbours))
# [1, 2, 3]
print(allpaths1(1, 3, neighbours))
# [[1, 2, 3], [1, 3], [1, 4, 3]]
print(list(allpaths2(1, 3, neighbours)))
# [[1, 2, 3], [1, 3], [1, 4, 3]]
推荐阅读
- sql - 如何查询缺少的字段和关联并返回 PostgreSQL 中缺少的内容?
- c# - 如何将选定的下拉列表值与 MVC 中的模型属性进行比较
- javascript - 警告:无法对未安装的组件执行 React 状态更新,方法只需要运行一次
- string - 如何在 Golang 中将 time.Now() 对象转换为字符串,反之亦然?
- ios - iOS 应用程序无法在 iOS 14.7.1 上通过 LTE 网络连接到服务器
- .net-core - 为什么 observable 不产生任何元素
- embedded-linux - 在 u-boot SPL 中设置环境
- cygwin - 酒 + Cygwin 乱码 argv
- r - 如何将ggarrange(ggplotGrob + ggplot图)的大小自动调整为R中的pdf?
- amazon-web-services - 与禁用 CIS 基准相关的 Security Hub 日志