Finding an A* heuristic for a directed graph

Question

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?

Answer 1

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.

Answer 2

The heuristic doesn't have to be perfect. Whilst A* would run in ridiculously short time if h(node) was equal to the optimum path from that node to the goal, that's obviously unrealistic. However, for reasonable heuristics, they only have to be the minimum possible distance- that is, there can be no path which reaches the goal from x of less weight than h(x), but it can most assuredly be greater. Common heuristics are Euclidean distance, and Manhattan distance. Neither of these is perfect, but they both fit the requirements of A*.

Answer 3

The case of one-way streets doesn't necessarily change the heuristic. You should just not generate invalid routes in the A* algorithm itself. I.e., in terms of the Wikipedia pseudocode,

neighbor_nodes(current)

should only generate nodes (junctions) that can actually be reached by one step from current and not try to traverse a one-way street in the wrong direction.

The A* heuristic function, however, should be an underestimate of the distance to the goal, and assuming that one-way streets can be traversed both ways will give you exactly that.

(You might be able to take one-way streets into account in a smarter heuristic, but you don't need to.)

Answer 4

Finding the longest cycle is a novel concept in biochemical feedback loop analysis in systems biology. Biochemical networks are often represented as directed graphs in which vertices represent chemical compounds and edges represent chemical reactions between compounds. Therefore, a biochemical longest feedback loop can be formulated as the longest cycle in a directed graph. Because finding the longest cycle in a directed graph is NP-hard, in this paper, we proposed an intelligent heuristic algorithm to find the longest cycle in a directed graph. We tested the algorithm on both randomly generated complex networks and real biochemical networks extracted from the KEGG database. The results showed that our algorithm is able to find more than 70% of the real longest cycles in the 200 randomly generated complex networks and also can find the feedback loop in the longest pathway. Compared with the traditional breadth first search pathway finding algorithm, the search efficiency of the proposed algorithm has been improved dramatically. Among the feedbacks found from the KEGG database using the proposed algorithm, the longest feedback includes 8 compounds, 9 reactions, and 6 pathways across different modules.

Answer 5

The heuristic is based on the direct bird's flight cost of travelling to your goal with the lowest possible weight (e..g running into a super highway without speed limits, if those exist in your context).

It has not much to do with your graph apart from the minimal weight per distance unit it could contain.