Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
3  
See answer in previous question. –  JonnyBoats Dec 26 '11 at 13:00
    
@MSalters I don't think that's what he intended to ask (although it's a great question, yup.) In the question he mentions streets so there' probably a way to figure a rough distance there. Also: he seems to be only concerned about one-way streets and the fact that d(x,y) is not constant. Posted my answer anyways. Would the asker care to clarify? –  kaoD May 29 '12 at 1:17
    
MSalters is kind of right. I really enjoyed @kaoD's answer, which is what I ended up doing, but I think that my half-baked atempt of determining a heuristic using a depth-search was what ended up not geting me the max points. –  Janis Peisenieks May 29 '12 at 6:06
add comment

5 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
I'd say that A* always is a best-first search - it degenerates to dijkstra's algorithm for h = 0 –  jk. May 28 '12 at 12:19
    
minor adjustment: i.e. found path might not be the shortest should be ie. found path might not be the least cost path –  Steve Evers May 28 '12 at 13:55
    
@jk. you're completely right, thanks, I'm fixing it :) –  kaoD May 29 '12 at 0:45
    
@SnOrfus thank you too, fixed that aswell. –  kaoD May 29 '12 at 0:48
    
I thought this answer looked promising, in particular the h(x) <= d(x,y) + h(y) (monotone heuristic) statement. This directly relates d(x,y) which is known and the heuristic which is sought. –  MSalters May 29 '12 at 8:06
show 3 more comments

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

share|improve this answer
1  
and of course in the limit that h(node) = 0, A* = dijkstra's algorithm –  jk. May 28 '12 at 12:08
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.