Алгоритм перечисления гамильтоновых циклов полного графа (перестановки, в которых циклы, обращения, циклические преобразования или повторы не учитываются)
Я хочу сгенерировать все гамильтоновы циклы полного неориентированного графа (перестановки множества, где циклы и обратные отсчеты считаются дубликатами и не учитываются).
Например, перестановки {1,2,3}
Стандартные перестановки:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
Что я хочу, чтобы программа / алгоритм печатали для меня:
1,2,3
Поскольку 321 — это всего 123 назад, 312 — это всего лишь 123, повернутых на одно место и т. Д.
Я вижу много дискуссий о количестве этих циклов, которые имеет данный набор, и алгоритмах, чтобы найти, имеет ли граф гамильтонов цикл или нет, но ничего о том, как перечислить их в полном, неориентированном графе (то есть наборе чисел этому может предшествовать или следовать любой другой номер в наборе).
Я действительно хотел бы, чтобы алгоритм или код C ++ выполняли эту задачу, или если бы вы могли направить меня туда, где есть материал по этой теме. Спасибо!
Решение
Вы можете наложить некоторые ограничения на вывод, чтобы исключить нежелательные перестановки. Допустим, мы хотим переставить числа 1, …, N. Чтобы избежать некоторых особых случаев, предположим, что N> 2.
Чтобы исключить простые повороты, мы можем потребовать, чтобы первое место было 1. Это правда, потому что произвольная перестановка всегда может быть повернута в эту форму.
Для устранения реверсов мы можем потребовать, чтобы число на втором месте было меньше, чем число на последнем месте. Это верно, потому что из двух перестановок, начинающихся с 1, которые обращены друг к другу, именно одна обладает этим свойством.
Таким образом, очень простой алгоритм может перечислять все перестановки и исключать недопустимые. Конечно, возможны оптимизации. Например, можно легко избежать перестановок, которые не начинаются с 1, на этапе генерации.
Другие решения
Очень ленивый способ проверить, является ли путь тем же самым, который начинается в другой точке цикла (IE, тот же цикл или обратный цикл того же цикла:
1: Решите, что по соглашению все циклы начнутся с наименьшего номера вершины и продолжатся в направлении нижнего из двух соседних ординалов.
Следовательно, все вышеперечисленные пути будут описаны одинаково.
Вторая, другая полезная информация здесь:
Если вы хотите проверить, что два пути совпадают, вы можете объединить один с самим собой и проверить, содержит ли он второй путь или обратный путь второго пути.
То есть,
1 2 3 1 2 3
содержит все вышеперечисленные пути или их обратные. Так как процесс нахождения всех гамильтоновых циклов кажется намного, намного медленнее, чем небольшая неэффективность этого алгоритма, я чувствовал, что мог бы добавить его 🙂