Re: [Boost-users] A* heuristic

Subject: Re: [Boost-users] A* heuristic
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-12-23 22:08:53

on Wed Dec 21 2011, giridhar <giridharms-AT-gmail.com> wrote:

> Hello All,
>
> Â Â Â Â Â  I have a question about defining A* heuristic. I am trying to
> implement an algorithm in a paper using BGL. Here authors have used
> A* Dijkstra's to calculate shortest route with an additional
> constraint of route length should be no longer than a threshold value
> t.
>
> I think due to this threshold constraint they are using A* instead of
> normal Dijkstra's algorithm.

Doesn't sound like it.  The heuristic function in A* has to be an
/underestimate/ of the remaining distance to the goal.  Merely knowing
that you don't want to consider any paths more costly/longer than t
doesn't lead in any obvious way to an underestimate.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com