Brute-Force

The Algorithm

  1. List of all possible hamilton circuits,

  2. Calculate the weight of each circuit found in Step 1

  3. Pick the circuit that has the smallest weight.

List of Circuits by the Brute-Force Method

This method is inefficient, i.e., takes a lot of time. The reason is that if we have a complete graph, K-N, with N vertecies then there are (N-1)! circuits to list, calculate the weight, and then select the smallest from. Even if we cut this huge number of (N-1)! by half, still for N as small as 28, the time it takes even the fastest computers of our day by Brute-Force is longer than the age of our universe. I don't know of others, but as far as I am concerned, I don't have that much time in my hands. Even if that was possible, I rather do some other mathematics than listing circuits by Brute-Force.

Here is the list of (5-1)! = 24 circuits.

Note that the circuit listed on the right is the circuit on the left, traced in the opposite direction. This was why we said above we can cut the number of circuits by half. 

A-B-C-D-E-A <=> 500 + 305 + 320 + 302 + 205 = 1632 <=> A-E-D-C-B-A


A-B-C-E-D-A <=> 500 + 305 + 165 + 302 + 185 = 1457 <=> A-D-E-C-B-A


A-B-D-C-E-A <=> 500 + 360 + 320 + 165 + 205 = 1550 <=> A-E-C-D-B-A


A-B-D-E-C-A <=> 500 + 360 + 302 + 165 + 200 = 1527 <=> A-C-E-D-B-A


A-B-E-C-D-A <=> 500 + 340 + 165 + 320 + 185 = 1510 <=> A-D-C-E-B-A


A-B-E-D-C-A <=> 500 + 340 + 302 + 320 + 200 = 1622 <=> A-C-D-E-B-A


A-C-B-D-E-A <=> 200 + 305 + 360 + 302 + 205 = 1372 <=> A-E-D-B-C-A


A-C-B-E-D-A <=> 200 + 305 + 340 + 302 + 185 = 1332 <=> A-D-E-B-C-A


A-C-D-B-E-A <=> 200 + 320 + 360 + 340 + 205 = 1425 <=> A-E-B-D-C-A


A-C-E-B-D-A <=> 200 + 165 + 340 + 360 + 185 = 1250 <=> A-D-B-E-C-A


A-D-B-C-E-A <=> 185 + 360 + 305 + 165 + 205 = 1220 <=> A-E-C-B-D-A


A-D-C-B-E-A <=> 185 + 320 + 305 + 340 + 205 = 1355 <=> A-E-B-C-D-A

The Optimal Solution is shown below.


Pros and Cons

Nearest Neighbour Algorithm