Алгоритм генерации решений TSP случайным образом

Question

Наиболее распространенная эвристика для решения проблемы TSP (в частности, эвристика Кернигана-Линя) требует работы со случайно сгенерированным туром и улучшения решения, начиная с этого.Тем не менее, единственный способ, которым я придумал, - это генерировать случайную перестановку вершин и проверять, является ли это решением или нет.

Для больших случаев проблемы (например, 1000 вершин) этот процесс может занять некоторое время.Есть ли другой умный способ быстрее создать случайный тур для проблемы TSP ??Обратите внимание, что я ищу тур, независимо от его стоимости, а не оптимальное решение.

Заранее спасибо

Answer 1

Если вы просто ищете какой-либо тур, вы можете использовать поиск по ширине или глубине, чтобы сгенерировать путь, отмечая посещенные узлы.

Answer 2

Вы можете просто создать массив, содержащий города этой проблемы, а затем случайным образом перемешать этот массив (есть методы, которые могут это сделать).Полученный массив фактически является случайной перестановкой.

Answer 3

Вы хотите использовать кривую заполнения пространства.