1
$\begingroup$

I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work solely on graphs where "traveling in a straight line" doesn't make sense at all?

Are there any heuristics that works solely on graphs (i.e. without requiring coordinates of the locations)?

$\endgroup$
  • 1
    $\begingroup$ What information do you have available for the heuristic? If you don't have any other information then you're out of luck I think. $\endgroup$ – pdexter Jul 19 '16 at 13:19
  • $\begingroup$ @pdexter I don't have any other information (more precisely, at each step, I only know which vertices I have visited and their neighbors.) I was just doing a research for my high school homework, so I think I'll change my problem to work on grids. Thanks! $\endgroup$ – Bora M. Alper Jul 19 '16 at 13:33
5
$\begingroup$

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known example in recent research is called ALT (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/

There has since been much further research on expanding and improving upon the heuristics used by the ALT technique. A simple search on this topic should turn up plenty of more-recent and relevant results (I tried posting links to some of them here, but the system has unfortunately limited the number of links I can provide in my response).

Aside from ALT, there has also been subsequent research on alternative techniques for constructing other similar heuristics purely from the graph representation (which is directly compared to ALT as well): http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5372/5180

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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