1
$\begingroup$

I'm trying to understand the A$^*$ search algorithm. I read in wikipedia that A$^*$ chooses nodes based on their cost, calculated as $f(n)=g(n)+h(n)$, where $h(n)$ is a heuristic estimation of the cost to reach the target from node $n$. But I don't understand how to determine its value.

Thanks for your help.

$\endgroup$
  • 1
    $\begingroup$ Do you mean "how do I design the function h" or literally "how do I evaluate it for a particular input"? $\endgroup$ – harold Sep 11 '16 at 12:04
  • $\begingroup$ wiki doesn't mention any think about h, so I hope to know the two: $\endgroup$ – aName Sep 11 '16 at 14:37
  • 1
    $\begingroup$ Start by reading more than Wikipedia. Have you read a description in a textbook? Or checked out any of the many online courses? $\endgroup$ – D.W. Sep 11 '16 at 17:01
4
$\begingroup$

Let's try to walk together through the $f$ function!

The intuition here is that we want to choose nodes in our exploration frontier which are:

  1. Close to the start state
  2. Close to a goal state

The shortest distance to the start state can be calculated recursively for every node in the search space pretty much as we do in uniform cost search.

However, the distance of a node to a goal state cannot be precisely calculated (for that we would need to know the shortest path to a goal, which would mean we have already solved the problem).

Thus the best we can do is try estimating it, using a heuristic function $h$. Obviously, we want this estimation to be as precise as possible, but we also want some other properties to hold:

  • (admissibility) we want $h$ to never overestimate the cost to the goal from any given node.
  • (consistency) we want $h(n)$ to not be greater than $h(n')+c(n,n')$ for any successor $n'$ of $n$, where $c(n,n')$ is the cost of the path that joins both states. In other words, the true cost of going from any given node to another must be less than the difference between the heuristic value of both nodes.

If we impose the restriction that $h(n)=0$ if $n$ is a goal state, then it is easy to see that consistency implies admissibility.

These properties guarantee that the algorithm is sound, complete and optimal for tree-search (admissibility) and graph-search (consistency).

Now, there are many heuristics out there for each problem.

One example is the trivial heuristic which assigns $h(n)=0$ for every $n$. This heuristic is indeed consistent. In this case, $A^*$ behaves as uniform cost search.

We can find heuristics better suited to solve a problem. One way to do so is by relaxing the conditions to solve the problem, and calculating the exact solution of the relaxed problem from the state we are in.

For example, we can take the $n$-queens problem, where each step consists in moving one queen, and take as a heuristic the number of queens under attack minus one (or zero if no queen is under attack).

$\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.