Graph Traversal – Finding an A* Heuristic for a Directed Graph

graph-traversalheuristicslanguage-agnostic

In a previous question, I asked about finding a route (or path if you will) in a city. That is all dandy. The solution I chose was with the A* algorithm, which really seems to suit my needs. What I find puzzling is heuristic. How do I find one in an environment without constant distance between 2 nodes? Meaning, not every 2 nodes have the same distance between them.

What I have is nodes (junctures), streets with weight (which may also be one-way), a start/finish node (since the start and end is always in the same place) and a goal node. In an ordinary case, I would just use the same way I got to goal to go back, but since one of the streets could have been a one-way, that may not be possible.

The main question

How do I find a heuristic in a directed graph?

Best Answer

Let h(x) be your heuristic for node x and h*(x) the perfect heuristic (where you know the EXACT distance to your goal from x), if 0 < h(x) <= h*(x) for every node of the graph then the heuristic is admissible.

  • If h(x) = 0 you have no information and A* degenerates into Dijkstra's algorithm.
  • If h(x) = h*(x) you do know the answer and therefore there is no problem to solve.
  • The closer h(x) is to h*(x), the shorter A* will take to find the shortest path.
  • If h(x) > h*(x) then your solution is not guaranteed to be optimal (i.e. found path might not be the least cost path.)

Some well known heuristics that meet this criteria are Euclidean distance and Manhattan distance.

If h(x) <= d(x,y) + h(y) for every edge x, y of the graph, where d(x,y) is the actual distance between the nodes, the heuristic is said to be monotone (or consistent) and no nodes need to be processed more than once.

Said that, any heuristic that doesn't overestimate the distance will do fine. It doesn't matter if your nodes have different weights, that's part of d(x) (the actual distance of your walked path), not h(x) which is just a roughly estimate to favor some paths before others. As long as h(x) (remember, it's just an estimate) is < h*(x) you'll get the optimal route.

In an ordinary case, I would just use the same way I got to goal to go back, but since one of the streets could have been a one-way, that may not be possible.

It doesn't really matter if you have one-way streets. Your graph can be directed and you just don't let your algorithm generate that route. You don't need to go back while executing A*, because it would become a longer route that if you didn't take that path in the first place. If you want to go back from GOAL to NODE that's just a new search in your search space, not a single problem.

Regarding MSalters' notice, I don't think you can derive a heuristic in a graph with just weights. You need a problem that meets some kind of criteria that offers extra information to guess from. If you only have weights, then you can't to it better than Dijkstra's because you lack any more information. It depends entirely on the problem domain, so a broad answer that fits any graph can't be given.

Related Topic