gpt4 book ai didi

python - 列出所有可能的 'Shortest' 路径

转载 作者:太空宇宙 更新时间:2023-11-04 06:01:20 24 4
gpt4 key购买 nike

我有一个组合问题,可以将其视为网络搜索问题。为了可视化和使用已经实现的功能,我决定使用 networkx 包(我实际上没有足够的时间以其他方式实现它)。

不幸的是,我的问题非常复杂。但是,我会尝试通过解释最简单的事情来简化理解。通常,我需要找出组合以到达树结束的节点。

下图显示了一个简单的例子:

enter image description here


在这种情况下,BDFH是终端节点,而起点是用 O 表示。因此,路径组合可以是:

OAB
OCD
OED
OEF
OH
OGH

但是,我实际上是在搜索到达终端节点的“最短”或“最有利”路径。该图(或边缘)没有提供有关路径“成本”的任何信息。成本评估将根据找到的组合结果进行。评估找到的组合的“实际”成本在计算上非常昂贵。虽然图表没有提供太多信息,但有一点很清楚:为了达到HOH 在任何时候都是比OGH 更好的选择>。因此,可以从可能的组合列表中删除组合 OGH。它本质上类似于距离度量。

还有一点,其实DF对应的是等价的点(虽然是不同的节点,但对我的应用意义相同)。然而,只有两个节点才能获得这样的信息

- see each other
- see exactly the same nodes

如果仔细看图,也可以看出CE是等价节点。因此,更具体地说:OCDOED 的组合实际上是相同的。一旦将 OCD 添加到组合列表中,就不需要添加 OED。从图中也可以看出,由于D和F是一样的,一旦将OCD添加到列表中,就不需要再添加OCF

总而言之,这种情况下的解决方案是:

OAB
anyone of OCD, OED, OCF, OEF
OH

为了绘制该图,我遵循了 networkx 的教程,然后创建了以下代码:

import networkx as nx
import matplotlib.pyplot as plt

graph = [('O', 'A'), ('O', 'C'), ('O', 'E'), ('O', 'G'), ('O', 'H'),
('A', 'B'), ('A', 'O'),
('B', 'A'),
('C', 'D'), ('C', 'E'), ('C', 'F'), ('C', 'O'),
('D', 'E'), ('D', 'C'), ('D', 'F'),
('E', 'C'), ('E', 'D'), ('E', 'F'), ('E', 'O'),
('F', 'C'), ('F', 'D'), ('F', 'E'),
('G', 'H'), ('G', 'O'),
('H', 'G'), ('H', 'O')]

G=nx.DiGraph()
for edge in graph:
G.add_edge(edge[0], edge[1])

pos=nx.graphviz_layout(G,prog='dot')
nx.draw(G, pos)
plt.show()

因此,我的问题是使用任何工具箱列出此类序列,但最好使用 networkx。要做的第一步可能是在创建图形对象之前简化(或减少)图形。获得简化图后,使用 nx.all_simple_path 命令,可以列出所有替代路径。我需要你的帮助来进行这样的图形缩减。

我的图表并不深,它们通常与示例中给出的大小大致相同。

最佳答案

我已阅读完整的模块手册并尝试了不同的搜索算法,但我找不到现有的实现,也找不到针对此类特定情况的任何解决方法。

因此,根据从评论中获得的建议,我编写了自己的简化器并在创建图形之前删除了所有“冗余”节点。我只是通过将列表转换为集合然后比较它们是否相同来做到这一点。之后,我创建了图表并使用 nx.all_simple_paths 命令列出了所有解决方案。一旦我得到了路径,这次我搜索是否有任何路径(如 OGH)当最后一个字母之前的字母(即索引 [-2])被删除时结果路径( OH) 也在 nx.all_simple_paths 列表中。如果是,那么我删除了该解决方案。

我编写的脚本非常杂乱无章,不涉及特殊技术。因此,我选择编写解决方法论。

关于python - 列出所有可能的 'Shortest' 路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24866048/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com