Масштабируемая реализация задачи коммивояжера на Python ⇐ Python

[Anonymous]

У меня (скажем) 100 баллов. Я хочу создать путь между ними, чем короче, тем лучше. Это проблема коммивояжера. Поскольку TSP является NP-сложным, я удовлетворен тем, что не нашел глобального решения. I-метод, который быстро дает решение и хорошо масштабируется.
Создание примеров:

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

import numpy as np
points = np.random.RandomState(42).rand(100,2)

Сгенерировать матрицу расстояний, где запись i,j содержит расстояние между точкой и точкой[j]. Используя этот ответ:

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

z = np.array([[complex(*c) for c in points]]) # notice the [[ ... ]]
distance_matrix = abs(z.T-z)

Как мне продолжить поиск кратчайшего пути хотя бы с локально минимальной длиной пути?

Некоторые связанные вопросы:
Эта тема: Коммивояжер в scipy предоставляет код для поиска решения TSP. Однако он работает итеративно, поэтому, если количество точек для посещения велико, сценарий не выдаст решение за разумное время.
Эта тема: Как решить задачу кумулятивного путешествия Продавец. Проблема с использованием инструментов or в Python? не имеет кода ответа и не ориентирован на классический TSP.
Эта тема: Оптимизация алгоритма коммивояжера (алгоритм путешественника во времени) предоставляет итеративные решения проблемы (что означает плохое масштабирование )

Подробнее здесь: https://stackoverflow.com/questions/711 ... -in-python