4

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.

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.

Improve this question
4
  • 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
    Commented Sep 7, 2011 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
    Commented Sep 7, 2011 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
    Commented Sep 7, 2011 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
    Commented Sep 8, 2011 at 12:26

2 Answers 2

Reset to default
4

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

Improve this answer
1
  • "It's complicated." ;) Good link, though. I spent some time researching TSP, but didn't find anything as useful as that.
    – canisrufus
    Commented Sep 7, 2011 at 13:57
4

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).

Improve this answer
3
  • 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
    Commented Sep 7, 2011 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
    Commented Sep 7, 2011 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
    Commented Sep 8, 2011 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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