Results 1 to 2 of 2

Math Help - A* heuristic estimate question

  1. #1
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1

    A* heuristic estimate question

    Hi! I recently read the wikipedia article about the A* search algorithm, which is basically a generalization of Dijkstra's algorithm, which also takes a heuristic function (called h) to evaluate the distance from a node to the goal (in Dijkstra's this heuristic would always be 0). However the algorithm requires the heuristic function to be admissible, i.e. the estimated cost of getting to the goal may never be greater than the actual cost of getting to the goal.

    What I wonder about, doesn't the heuristic function have to be consistent as well? I.e. the decrease in the heuristic estimate when moving one step cannot be greater than the actual cost of taking that step. However, it says on wikipedia that the heuristic just has to be admissible for the algorithm to return an optimal path.

    Burt what about this example?



    Here, the heuristic function is admissible, since it never overestimates the cost of getting to the goal (although it's not consistent). Yet, i my opinion, the A* algorithm would take the suboptimal path here (the lower path), since it thinks the heuristic evaluation there (that in node C) is much more optimistic than in the upper path given in node B.

    Am I right or wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    I'm not claiming any expertise here, never having wanted to solve this type of problem in a real program. Clearly, if the algorithm fails for your example, which it certainly looks like it might, then either the claim that the heuristic only needs to be admissible is wrong, or you understanding of what it means to be admissible is not correct, or possibly you are not meant to have 0 cost paths. The wikipedia article you link to seems to imply there is more to both the algorithm and the function f(x) than just your heuristic. If I were you I would take the trouble to implement the algorithm - the Wikipedia pseudo-code looks like a good basis, and there look to be links to C++ implementations.

    In my experience one gets a much better understanding of a complex algorithm by really implementing it and tracing through the decisions made by the computer than by trying to work through an example in one's head, because it is all too easy to make a mistake that way. Often you will find the computer does something you did not expect, and when you come to study it you will find there was a flaw in your understanding.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Heuristic method
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: August 18th 2011, 08:38 PM
  2. Find a lower estimate and an upper estimate
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 17th 2010, 03:28 AM
  3. Another Area Estimate Question
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 26th 2010, 09:30 PM
  4. Area Estimate Question
    Posted in the Calculus Forum
    Replies: 0
    Last Post: April 26th 2010, 06:56 AM
  5. Flag and flagpoles multi sets heuristic help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 29th 2010, 11:22 PM

Search Tags


/mathhelpforum @mathhelpforum