Перечислите все комбинации маршрутов TSP (5 вершин) - PullRequest
Новая
       38

Перечислите все комбинации маршрутов TSP (5 вершин)

0 голосов
/ 09 декабря 2018

Я хочу перечислить все комбинации маршрутов TSP.

Существует 5 вершин и, следовательно, 10 ребер: enter image description here

Все ребра имеют следующий вид: 

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'), то же самое относится и к другим краям.Я хочу перечислить все комбинации маршрутов, где вы начинаете с А и посещаете номера друг друга и заканчиваете в А.

Это то, что я получил до сих пор: 

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, и не должно учитываться / перечисляться дважды.

1 Ответ

0 голосов
/ 09 декабря 2018

Вы можете использовать рекурсию с генератором: 

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