Я играюсь с проблемой коммивояжера. Я понял, как использовать алгоритм кучи для создания всех перестановок, но когда я увеличил масштаб местоположений, это заняло слишком много времени, поэтому я использовал алгоритм ближайшего соседа для вычисления кратчайшего маршрута, но это не точно. Итак, я сгруппировал свои местоположения, затем вычислил центроиды кластеров, а затем использовал алгоритм моего ближайшего соседа, чтобы получить кратчайший путь между центроидами. Итак, теперь у меня есть порядок, как перемещаться между центроидами, например:
Кластеры:
clusters = [[0],[1,2],[3,5,6],[4,7]]
Порядок кластеров:
orderOfClusters = [0, 1, 3, 2]
Затем я вычислил все перестановки местоположения внутри кластеров:
permutationClusters = [
[[0]],
[[1,2],[2,1]],
[[3,5,6],[3,6,5],[5,3,6],[5,6,3],[6,3,5],[6,5,3]],
[[4,7],[7,4]]
]
Теперь я хочу объединить как перестановки местоположений внутри кластеров, так и порядок кластеров, например:
permutationOfRoutes = [
[0,1,2,4,7,3,5,6],
[0,2,1,4,7,3,5,6],
[0,1,2,7,4,3,5,6],
[...]
]
моя идея заключалась в том, чтобы l oop над permutationClusters и l oop внутри этого l oop для подмассивов, но эта доза дает мне все перестановки, которые я должен получить. Может быть, дадут мне немного sh в правильном направлении.