Решение грубой силы для нахождения гамильтонова цикла требует O (n!) Работы (которая действительно является O (n ^ n), но O (n ^ n) не будет жесткой верхней границей).
Гамильтонов цикл в графе G с n узлами имеет вид H = v_1,v_2,v_3,...,v_n,v_1.
Поскольку H включает каждый узел в G, мыможет начать наш поиск с любого произвольно выбранного узла, скажем, v_1.Впоследствии существует n-1 узлов-кандидатов, которые будут вторым узлом v_2 (т. Е. Все узлы, кроме самого v_1);есть n-2 выбор для третьего узла v_3 (т. е. все узлы, кроме выбранных кандидатов на v_1 и v_2) и т. д .;в конце с фиксированными кандидатами на v_1 - v_n-1 остается ровно один оставшийся кандидат на v_n.
(i) В результате получается максимум (n-1)(n-2)...(2)(1) = (n-1)! комбинаций.
(ii) В наивной реализации проверка каждой комбинации требует O (n) работы;т. е. для проверки, является ли данная комбинация гамильтоновым циклом, мы просматриваем всю последовательность данной комбинации и проверяем, имеет ли она требуемые свойства гамильтонова пути.
Следовательно,
Общая сложность составляет O(n) x (n-1)! = O(n!)
Конечно, мы можем сократить требуемую работу, используя различные методы, например, подходы ветвления и ограничения.