Find shortest distance between X number of places

Mutant_Fruit

Have this college assignment to find the shortest and longest route between 7 different places while only visiting each place once. I've got it finished, but i'm wondering is there a better way of doing it other than checking each possibility.

For 7 different possibilities theres 7! ways of visiting the places, which is 5040 routes to check. Is there a technique for cutting down that computation so i could check the shortest distance between 70 places, or 700?

Nalz

What alogrithm did you use? dijsktras?

daymobrew

This sounds like the Travelling Salesman problem. IIRC there is a well established algorithm for solving it.

I recall the name, but not he solution, from hearing Computer Applications students mention it when I was in DCU (back around 1990). The book they used was "Algorithms".

Nalz

dijsktra's is the way to go. Google it there is some very helpful sites out there...with code from vb to C++ syntax

Mutant_Fruit

What alogrithm did you use? dijsktras?

I have no idea what dijsktras is :P I wrote a recursive algorithm that calls itself in order to loop through all 5040 possible routes. I just thought it was a bit inefficient, but i can't think of a better way of doing it.

Bit of backround info... I made a Town structure which contains the X/Y coordinates of each town, the town name, and an ID for the town (which i use for referencing each town).

Algorithm:
My route contains 8 stops (i start in Arklow and finish in arklow).
'routeposition' increments by 1 each time i visit another town. This is == 7 when i have visited everything.
'currenttown' contains the ID of the town that i'm currently in.
Calling MakeRoute with a 'currenttown' supplied means i'm going to that town.

void MakeRoute(int currenttown, int routeposition)
{
  int i=0;
  for(i=0; i<max_towns; i++)
    {
       // Global array used to store the towns i've visited so far. As i 'visit' a town, i store the town ID in the corresponding 'position' so as to not accidently go to the same town twice.
      CurrentRoute[routeposition] = currenttown;

      if(TownFree(i) == 1) //TownFree checks the CurrentRoute array to make sure that i don't go to a town already in the Route. If the town is free, i go to that town next.
	{
	  MakeRoute(i, (routeposition + 1));
	}
      if(GoneEverywhere() == 1) // just a sanity check to make sure my route contains each town. Once it does, i calculatethe distance and break out of the loop.
	{
	  CalculateDistance();
	  break;
	}
    }
// Once i've tried one complete "route" i hop back into the previous call of MakeRoute and keep recursing til i've tried all 5040 possibilities
}

I hope that makes sense to ye

EDIT: In this loop, 'i' is the townID. So everywhere you see 'i' just think "townid".

Nalz

http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html

pH

Is this not the Traveling Salesman Problem

How about you keep a store of the shortest path and only keep evaluating paths that are still shorter than this.

For example:

If the path 1-2-3-4-5-6-7-1 has a length of 1,083 (and its the shortest you've currently found)

You're currently evaluating other paths ...

If the path 1-5-7 *already* has a length > 1,083 then there's no need to evaluate any full paths starting 1-5-7 as they all have to be longer, in this way you can prune the tree to make the search space more efficient.

Just a a matter of curiousity how does townfree() work in a recursive situation?

[Edited because i was taliking nonsense!]

Mutant_Fruit

Just a a matter of curiousity how does townfree() work in a recursive situation?

Well, i had two options:
1) I could just pass an array through each recursion to store what towns i have visited in the current route i'm creating, or i could use a global variable that could be seen by all the recursions. I went with global variable cos i was lazy

int CurrentRoute[max_towns]; // Array which will store the townID as i enter each town.

//I start my recursion sequence by calling: MakeRoute(0,0);
// first 0 is townID (arklow is townid: 0), second 0 means its the first town i visit

So now, my recursion sequence starts. The first thing MakeRoute does is store Arklows ID into my CurrentRoute array in position 0 as it is the first town i'm in.

Next, a for loop starts looping from 0. TownFree() checks if 0 is in the global array, if it isn't, it goes there as the next hop in the route. If it is, we just continue the for loop and check if the townid 1 is in my global array, which it isn't. So i now go to 1. The next recursion then stores townid 1 in position 1 of the array etc etc, and it just loops around like that. That way i can call TownFree() no matter where in the recursion loop i'm in and it'll be able to tell me if that particular townID is already plotted in my route or not.

Once i "fill" my route, i.e. i have plotted 0,1,2,3,4,5,6,7 (gone to everywhere) it drops back a recursion level, increments what used to be 6 and tries 0,1,2,3,4,5,7,6. Then it tries 0,1,2,3,4,6,5,7 etc etc.

MrPinK

Mutant_Fruit wrote:

For 7 different possibilities theres 7! ways of visiting the places, which is 5040 routes to check. Is there a technique for cutting down that computation so i could check the shortest distance between 70 places, or 700?

There are faster algorithms, but they are still of exponential time complexity. Advanced algorithms for solving the travelling salesman problem are the sort of thing people write their thesises (plural of thesis?) on. But if you do come up with anything better than that you'll get $1m from the Cray institute.