Brute-Force algorithm

Hamiltonian Circuit Problem: Given a graph G having n nodes, find a Hamiltonian circuit in G.

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?

[Prev][TOC][Next]

CS1104 Main Page
Last Updated 2002/01/02
© L.Heath, 2000, upgraded by J.A.N. Lee on the date above.