Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

In my transport geography class, we were asked to do a "best guess" on the route which does the following on this graph:

  1. Starts at A
  2. Visits each node
  3. Returns to A
  4. minimizes distance.

Graph

I wrote up program which calculated all of the five step paths that started from A, visited every node, and returned to A. I then calculated the cost of these paths.

My question is: how would other people solve this? My teacher gave us a "hint" that we should read about Dijkstra's algorithm, but I couldn't see how to apply that to solve this particular problem. My solution would fall apart pretty quickly as the number of steps or nodes increased.

share|improve this question
1  
Your program was lucky, because it's not guaranteed to get the best answer. For instance, if all the edges at E had costs of 1 (instead of 3,4,5,3), your program's solution would be markedly inferior to the optimum (with a cost of 8). –  whuber Sep 7 '11 at 14:09
    
@Whuber I was hoping that you would share some of your math knowledge here ;) I considered doing a range of steps, maybe between 5 and 10, to guard against that, recognizing it wouldn't provide a guarantee. Not sure how to provide that guarantee, though. –  canisrufus Sep 7 '11 at 14:22
    
A brute force solution uses recursion to solve a slightly more general problem: get from node 'v' to node 'w' while visiting a specified set of additional nodes. Thus, to visit all nodes starting at 'a', look at the solutions that start at 'v', end at 'a', and visit all other nodes, for the cases 'v' = 'b', 'v' = 'd', and 'v' = 'e'. Add the costs 3, 7, and 3 to those solutions, respectively. Pick the smallest cost. –  whuber Sep 7 '11 at 15:54
    
@whuber: That's very clear, as far as it goes. I think I can work out what the recursion would look like. I'd like to accept your response, but it's not in the "answers" section.. –  canisrufus Sep 8 '11 at 12:26

2 Answers 2

up vote 3 down vote accepted

I'd advise you to look up, research, the travelling salesman problem for some soutions.

Here's a link to a way to formulate a solution. In short, this is a tricky subject to get into/understand:

TSP solutions

share|improve this answer
    
"It's complicated." ;) Good link, though. I spent some time researching TSP, but didn't find anything as useful as that. –  canisrufus Sep 7 '11 at 13:57

Imho, "Dijkstra" is not a good hint. What you are looking at is the so-called "Travelling salesman problem".

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

Since a brute-force approach performs with O(n!), they reach their limit pretty fast (WP says 20 nodes is already the limit).

share|improve this answer
    
Thanks! I didn't find Dijkstra to be especially useful, though another student claimed to. Do TSPs also include the part where you have to return to origin? I didn't see that mentioned when I looked them up yesterday, although, of course salespeople need to drive home, too... –  canisrufus Sep 7 '11 at 14:05
    
@canis You are correct: the Dijkstra algorithm is useless for this problem. Note that your problem as stated is not the TSP, because you have not indicated that each node must be visited exactly once, only that it must be visited at some point in the route. –  whuber Sep 7 '11 at 14:14
1  
In all fairness Whuber, I think that's more of an over simplification of the problem. I actually do think the OP has been tasked with the TSP; I got the same questions in my dfegree, and I believe most people will/do –  Hairy Sep 8 '11 at 6:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.