Коммивояжер по всем источникам ⇐ Python

[Anonymous]

У меня есть «мелкомасштабная» задача TSP, точное решение которой можно тривиально вычислить следующим образом. Я пытаюсь заставить это работать, выдавая пути TSP «всех источников». Мне не обязательно начинать с фиксированного узла. Я могу начать с любого места и хочу знать все возможные оптимальные пути из каждой вершины. Как это можно сделать, кроме необходимости генерировать несколько матриц расстояний, каждый раз перемаркируя вершины, что было бы весьма раздражающе.

Код: Выделить всё

import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming

distance_matrix = np.array([
[0,437,23,21,41,300,142,187,81,171,98],
[545,0,10,19,54,339,142,201,78,170,143],
[95,147,0,186,273,93,29,55,731,76,164],
[45,60,930,0,518,28,10,13,298,31,71],
[74,111,495,490,0,62,25,21,407,87,143],
[122,126,2,1,13,0,2057,241,17,45,26],
[328,313,5,20,34,527,0,560,70,107,76],
[208,200,5,9,24,442,159,0,41,61,41],
[122,174,53,44,110,98,25,40,0,878,798],
[214,340,12,37,66,162,54,96,199,0,789],
[265,423,12,27,90,173,73,86,312,701,0]])

distance_matrix = distance_matrix * -1
solve_tsp_dynamic_programming(distance_matrix)
([0, 5, 6, 7, 4, 3, 2, 8, 9, 10, 1], np.int64(-7727))

ПРИМЕЧАНИЕ. Мне нужны только точные решения, а не приближения.

Подробнее здесь: https://stackoverflow.com/questions/790 ... les-person