Использование циклических перестановок для уменьшения сложности Traveling Salesman

Я пытаюсь найти множество различных алгоритмов для поиска оптимальных решений Проблема с продавцом, и одним из методов является подход грубой силы - проверяя все возможные пути между русскими городами и просто возвращая лучший. Это алгоритм O (n!), Поэтому для большого количества городов требуется очень много времени.

Я хочу повысить эффективность моей реализации грубой силы, и одна из вещей, которую я заметил, - это то, что вам не нужно проверять каждую перестановку городов. Например, если у вас есть города 1, 2, 3 и 4, путь (1-2-3-4) будет такой же длины, как и путь (2-3-4-1). То же самое касается путей (3-4-1-2) и (4-1-2-3). Используя этот факт, мы должны иметь возможность уменьшить сложность алгоритма грубой силы от O (n!) До O ((n-1)!) Или даже O ((n-1)!/2), если мы что все пути могут быть отменены, не затрагивая их длины.

В принципе, я ищу алгоритм, способный генерировать круговые перестановки из набора различных целых чисел. Было бы также здорово, если бы алгоритм обрабатывал "зеркальные" перестановки как эквивалентные (например, 1-2-3 и 3-2-1 одинаковы, поэтому нужен только один из них). Кто-нибудь знает, как это сделать? Реализация Java была бы замечательной, но я возьму что-нибудь!

Ответ 1

Если вы всегда начинаете с того же node (например, "1" ), вы не должны сталкиваться с этой проблемой. Затем вы можете легко добавить проверку на зеркала, потому что это просто работает от node 0 до N-1 N-2, пока вы снова не достигнете нуля.

Например, 1,2,3,4 имеет следующие перестановки:

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

Теперь, если мы заставим 1 в качестве первого node, вы получите эти уникальные решения:

1234 1243 1324 1342 1423 1432

Далее мы можем устранить "зеркальные" решения:

normal => reverse => rotated by 1
1234 => 4321 => 1432
1243 => 3421 => 1342
1324 => 4231 => 1423

Вам нужно будет только проверить:

1234 1243 1324

Update:

Самый простой способ сгенерировать эту последовательность - перечислить все возможности 1... N-1, где 1 до 2 (форсирование направления) и добавление N.

Например, для N = 4 мы сначала генерируем все перестановки 1... N-1:

123 132 213 231 312 321

Теперь мы фильтруем, где 1 до 2:

123 132 312

И добавьте N (4):

1234 1324 3124

Это, вероятно, проще и эффективнее для программирования. Это также доказывает, что верхняя граница, необходимая для грубой силы TSP, равна: (N - 1)!/2

Ответ 1

Ответ 2