I'm trying to develop a Travelling Salesman-type program (in Java) and am trying to figure out the logic for a certain part, a brute-force approach for calculating the most efficient route between a set of nodes (Cities) where each node is touched only once.
I've defined a City class with the x/y co-ords and have an array of City instances, and a grid class to draw the grid. Cities are visible on a grid, and numbered 0-i for their index in the City array
(In the sample grid there are 4 cities defined):
· · · · · · · · · · · · · · · ·
· · · · · · · · · 1 · · · · · ·
· · 0 · · · · · · · · · · · · ·
· · · · · · · · · · · 3 · · · ·
· · · · · · 2 · · · · · · · · ·
· · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · ·
There are many routes visible already (I believe 4! = 24):
- 0-1-2-3
- 0-2-1-3
- 2-0-1-3
- 2-3-1-0
- etc..
Is there a simple iterative/recursive method to obtain every possible path, given an array of cities and their co-ordinates, which I can use to determine the distance and list the most efficient route(s)?