В настоящее время я работаю над кодом Python для решения задачи коммивояжера. По сути, вам нужно найти кратчайшее возможное расстояние при посещении нескольких точек на карте и возвращении к исходной точке.
Часть моего кода, которая вычисляет расстояние, работает очень хорошо, но в настоящее время она занимает слишком много времени, чтобы перебрать все возможные перестановки и вычислить соответствующие расстояния.
В настоящее время Я использую itertools.permutations, чтобы сгенерировать все возможные пути для посещения этих точек.
Однако, поскольку я возвращаюсь к исходной точке, мне не нужно вычислять решения, при которых исходная точка изменяется, поскольку они будут возвращать одинаковые расстояния. , В общем, я просто хочу переставить все записи, которые идут после первой записи в моем списке.
Кроме того, [0, 1, 2, 3] дает то же расстояние, что и [0, 3, 2, 1], поэтому я хочу избавиться и от этих обратных дубликатов. ,
Вот часть кода, которая отвечает за перестановки:
import itertools
import random
max_x = 510
max_y = 510
number_points = int(input("Enter number of points: "))
print("")
coords_list = []
i = 0
while i < number_points:
a = [random.randint(10, max_x), random.randint(10, max_y)]
coords_list.append(a)
print("Point", i, "has coords", a)
i = i + 1
print("")
# All possible permutations
b = list(itertools.permutations(coords_list, number_points))
print(b)
print("")
print(len(b))