我有一堆像下面这样的字典(有些可能很大):
V = {
0: [823, 832, 1151, 1752, 2548, 3036],
823: [832, 1151, 1752, 2548, 3036, 3551],
832: [1151, 1752, 2548, 3036, 3551],
1151: [1752, 2548, 3036, 3551],
1752: [2548, 3036, 3551, 4622],
2548: [3036, 3551, 4622],
3036: [3551, 4622, 5936, 6440],
3551: [4622, 5936, 6440],
4622: [5936, 6440, 9001],
5936: [6440, 9001],
6440: [9001],
9001: []
}
该字典表示帮助导出所有可能路径(它们是路线)的基本规则。路径是上述整数的序列。
字典值列表中的每个值也是一个键。
如何确定所有可能的路径,例如:
[3036, 4622, 9001] 是有效路径,
但是 [3036, 9001] 不是,原因是 3036 后面必须跟有 V[3036] 中的元素之一。每个组合都必须包含一个兼容的序列,并且每个序列都必须以 9001 结尾,也就是说,要到达 9001,必须经过 6440、5936 或 4622。
每个序列还必须以 V[0] 中的点之一开始。
我尝试过的两件事:
- 我首先使用 itertools.product 导出所有路径,然后过滤掉无效路径,但对于大多数字典来说,itertools.product 组合的数量太大了。
- 蒙特卡洛模拟,但循环数达数百万,无法保证捕获所有路径。
最佳答案
看起来像一个简单的 DFS。由于该图看起来是有向的(每个节点都有其数量大于该节点的后继节点),因此您甚至不需要小心避免循环。
>>> def dfs(graph, start, end):
... if start == end:
... return [[end]]
... return [[start] + result for s in graph[start] for result in dfs(graph, s, end)]
...
>>> dfs(V, 0, 9001)
[[0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 9001], [0, 823, 832, 1151, 1752, 3036, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 4622, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 9001], [0, 823, 832, 1151, 2548, 3036, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 6440, 9001], [0, 823, 832, 1151, 2548, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3551, 4622, 5936, 9001], ...]
如果上述函数在您的一个字典上永远旋转,那么是时候修改有关图有向的假设了。
关于Python 字典中元素的组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/72398649/