3

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework.

Route creator

I have a task, where a company has to create a route for a given data set. The data set can be input for every operation and in the end, it should print out the optimum route. The conditions are like this:

  • Streets can only be directed North-South or East-West, effectively making every angle between 2 streets in 90 degrees.
  • The data set includes streets, junctions and places to pick client and where to drop him off, as well as the starting place for the car.

My problem is, that I'm having trouble thinking of the correct data structure way to do this. What came up first from the top of my head was a directional graph. In theory, it should fit perfectly

  • Streets are input up front with numeric identificators
  • A node represents junction and is represented by the id's of the streets
  • An edge between 2 nodes represents a piece of street and has length
  • Places of interest are effectively a sub-class of Junction nodes therefore they have distance from the one node to another.

Best route would then be calculated by finding the shortest path from the starting place of the car to the starting place of the client + shortest path from the starting place of the client to the ending place of the client + shortest path from the ending place of the client to the starting place of the car.

Is my thinking in this matter even remotely correct? I am finding this quite difficult to image with any other data structure than a directed graph, but maybe I'm just limiting my options with this thinking.

4 Answers 4

4

It strikes me that knowing that all streets run N_S or E_W will allow you to easily compute an excellent heuristic for the A* algorithm, which on first thought would seem to be the best general purpose algorithm to solve this.

With such a great heuristic you should be able to use an extremely sparse structure due to the ability to do extensive pruning.

EDIT - In response for the request to elaborate on the heuristic: With the A* algorithm one requires an admissible heuristic, {h(x)} that is an estimate of the distance from the current node to the target. To be "admissible" the heuristic, or estimate of the distance from the current point (x) to the goal must be less than or equal to the true distance. Normally one might use the straight line distance ("as the crow flies") between the two points, since no actual road could be shorter than a straight line.

In your problem you are told that all roads run north-south or east-west, thus no diagonal roads. Lets take a specific example: Suppose one wants to estimate the minimum distance, h(x), for starting at the point (0,0) and traveling to (10,10). Now this is a square with a side of length 10, so ordinarily one would estimate that there could be a road that went straight from (0,0) to (10,10) so the straight line distance would be the square root of 200 or approx 14.14. But in your case, since all roads run N-S or E-W we know that the minimum possible distance is 20. Of course the true distance might be more depending what roads are available.

Since you have an admissible heuristic for two points (x1,y1), (x2,y2) being h(x) = (abs(x2-x1) + abs(y2-y1)); this h(x) is always greater than or equal to the straight line distance, and thus is a "better" heuristic in that it will lead to a smaller solution space which will need to be explored. In other words greater tree pruning.

5
  • Could you please elaborate on the heuristic part? Dec 26, 2011 at 11:35
  • Thanks for the edit, but I do not know what are the absolute coordinates of any of the nodes (points) since in my task that doesn't matter. The only thing that matters is the distance from one point to another. I can think of no way to get these coordinates. What I can think of though, is doing a depth-wise search before path-finding, and upon encountering the goal node, retracing my way strait back to the start, while counting the nodes, summing their weight and in the end getting the average weight, which should be a goo heuristic. Could this work? Dec 26, 2011 at 13:44
  • Janis: You must be able to compute the coordinates. Assign (0,0) to the starting point. Then don't you know a direction and distance along some possible road? If you go east for 5 units you will end up at (5,0) etc.
    – JonnyBoats
    Dec 26, 2011 at 13:47
  • Hmm. When thinking about file inputs, I didn't think about assigning the N_S or E_W to the street, thus my system doesn't know about this. Upon reviewing it though, it seems, that I may need to do this just for the sake of finding the heuristic. Thanks! Dec 26, 2011 at 13:54
  • @JanisPeisenieks you can always use a heuristic of 0, which gives you dijkstra's algorithm, but given a better heuristic is easily calculatable (the manhattan distance to target node) this would be better
    – jk.
    Jan 16, 2012 at 17:28
2

There is no doubt that a road network and routefinding algorithm is best modeled with a graph and using A*, Dijkstra's algorithm, or some variation of those for searching.

In your case, no doubt the intersections should be modeled as nodes and the roads as edges. As the author of a commercial GPS package, I model the starting point of each road as a node (so a junction of three roads has three nodes); this more complex model allows you to count turn costs (especially, making U-turns expensive) and turn restrictions.

If all roads have the same speed limit or you want to find the shortest distance, A* is a good algorithm, but if h(x) isn't close enough to the actual path cost, A* routing may offer no speed advantage over the simpler Dijkstra algorithm. I used A* originally, but these days I use a modified bidirectional Dijkstra algorithm, which you can think of as A* without the extra overhead of computing h(x).

The fact that all roads are located on a grid may affect the data structure you choose, but you could divide your code into two parts, one is a generic A* or Dijkstra algorithm that supports any graph regardless of how it's stored, and the other takes care of the implementation details of your data structure.

1
  • You might be interested in answering the follow-up question: click here. Maybe you know a good answer. :)
    – Skalli
    Jun 4, 2012 at 7:13
1

A directed graph should be the best approach in your case. It is probably true that some more optimal structure could perhaps be devised taking into consideration the given constraint that streets can only be directed North-South or East-West, but I would not even waste any time thinking about this possibility: it would tie your solution to an artificial constraint and it would result in a data structure that would be more hacky and less academic. You might want to take this constraint into account if you are ever asked to draw the map of your domain, but that's all.

2
  • 2
    I disagree with some things you said. There is a whole field called Computational Geometry which is intersection of algorithms and geometry - the algorithms take advantage of the fact that nodes have to be arranged in some sort of (usually physical) space. This would generally mean, for instance, that a triangular inequality holds. The algorithms that are specific to C.G. are not more hacky or less academic. They are a different way of thinking about things. I am not sure if C.G. has advantage over regular graph-based algorithms here, but I think it is unwise to discard a bunch of techniques.
    – Job
    Dec 24, 2011 at 16:47
  • @Job Sure, you are right, I stand corrected. I hope whoever reads my answer will also read your comment.
    – Mike Nakis
    Dec 24, 2011 at 16:57
1

Make a grid (two dimensional array) of Junctions. Each Junction may have a south bound and an east bound exit (the north and west ones are exits from the neighbor cell). Each exit may have a name and a number interval. This allows you to navigate.

For easier lookup a given street name is a list of Junction references.

2
  • Does this also stand true for a case, where there are e.g. 5 paralel streets, and there is a street in-between them going form the 2. to the 4.th street? Also, I cant think of a way to keep the hierarchy between the streets in this case. E.g, if looking from top, which street would be on top (more north) and which more south. Dec 24, 2011 at 17:30
  • It should, but if it does not come natural to you it is most likely not a structure you should use. Note that you may use several datastructures representing the same data if you have several types of answers you need.
    – user1249
    Dec 24, 2011 at 17:48

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.