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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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