A brute-force algorithm for this problem generates all possible orderings of the n nodes and checks whether each ordering yields a Hamiltonian circuit. That is, if we list all possible combinations without repetition for the prior example, we need to examine 7x6x5x4x3x2x1 = 5040 cases:
A B C D E F G A C D E F G B A D E F G B C A E F G B C D A F G B C D E A G B C D E F ...
There are n! (n factorial) possible orderings.
Hence the time complexity of the brute-force algorithm is at least
O(n!) in the worst case.
** What kind of problem solving method is this?
CS1104 Main Page
Last Updated 2002/01/02
© L.Heath, 2000, upgraded by J.A.N. Lee on the date above.