<p>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 <strong>ALT</strong> (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: <a href="https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/">https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/</a></p>

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

<p>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): <a href="http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5372/5180">http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5372/5180</a></p>

CC BY-SA 3.0
2016-09-09T16:26:24.167Z
2016-09-09T16:26:24.167Z
Michael N. Rice
<p>I'm exploring heuristics in <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow">A*</a> and apparently all heuristics require coordinates of all the locations to calculate a <em>h-cost</em>. This is fine if you are working on grids, but what if you need to work <strong>solely</strong> on graphs where "<em>traveling in a straight line</em>" doesn't make sense at all?</p>

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

CC BY-SA 3.0
2016-07-19T13:19:09.263Z
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.
pdexter
CC BY-SA 3.0
2016-07-19T13:33:22.957Z
@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!
Bora M. Alper
<graph-theory><shortest-path><heuristics>
Are there any heuristics that works solely on graphs?
Bora M. Alper
# Are there any heuristics that works solely on graphs?

(Asked by: username_0 on 2016-07-19)

I'm exploring heuristics in [A\*](https://en.wikipedia.org/wiki/A*_search_algorithm) 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)?

**Tags:** graph-theory, shortest-path, heuristics
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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!  

---

## 1 answers

### Answer by username_2 on 2016-09-09. Score: 5 | Accepted answer

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>


---

