python - 列出所有 TSP 路由组合（5 个顶点）

Question

我想列出所有 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 相同，不应计算/列出两次。

标签： pythonsortinggraphcombinationstraveling-salesman

Answer 1

您可以将递归与生成器一起使用：

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']]