首页 文章

列出所有TSP路径组合（5个顶点）

提问于
浏览 次
3

我想列出所有TSP路线组合 .

有5个顶点，因此有10个边：

所有边缘如下：

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')]

注意： ('A', 'B') 与 ('B', 'A') 相同，其他边也一样 . 我想列出从A开始的所有路线组合，并访问彼此的号码并在A结束 .

这是我到目前为止所得到的：

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')]
x = list(itertools.permutations(['A','B','C','D','E', 'A'], 6))

b = 1
for i in x:
    if i[-1] == 'A' and i[0] == 'A':
        print(i, b)
        b += 1

但是，我不想要重复的路线 . 我该如何解决这些问题？例如 . A-> B-> C-> A与A-> C-> B-> A相同，不应计数/列出两次 .

python sorting graph combinations traveling-salesman

1 回答

  • 0

    您可以使用生成器的递归：

    edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')]
def all_paths(graph, start, end=None, _flag = None, _pool = [], _seen= []):
   if start == end:
      yield _pool
   else:
      for a, b in graph:
        if a == start and a not in _seen:
          yield from all_paths(graph, b, end=_flag, _flag=_flag, _pool = _pool+[b], _seen =_seen+[a])


results = list(all_paths(edges+[(b, a) for a, b in edges], 'A', _flag = 'A'))
filtered = [a for i, a in enumerate(results) if not any(len(c) == len(a) and all(h in c for h in a) for c in results[:i])]

    输出：

    [['B', 'C', 'D', 'E', 'A'], ['B', 'C', 'D', 'A'], ['B', 'C', 'E', 'A'], ['B', 'C', 'A'], ['B', 'D', 'E', 'A'], ['B', 'D', 'A'], ['B', 'E', 'A'], ['B', 'A'], ['C', 'D', 'E', 'A'], ['C', 'D', 'A'], ['C', 'E', 'A'], ['C', 'A'], ['D', 'E', 'A'], ['D', 'A'], ['E', 'A']]
    回复于

相关问题