0
$\begingroup$

I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes.

Am I correct in thinking the way to see which one is admissible is add up all the values of the h(n) and compare it to the total real cost of the graph?

Example:

enter image description here

h1 total = 681 h2 total = 732

Total cost of graph = 704

Does this mean h1 is admissible as it doesn't overestimate?

$\endgroup$
5
$\begingroup$

A heuristic function $h$ is admissible, if it never overestimates the cost for any given node. Formally speaking, let $h^{*}$ map each node to its true cost of reaching the goal. The heuristic function $h$ is admissible, if for all nodes $n$ in the search tree the following inequality holds: \begin{align} h(n) \leq h^*(n). \tag{$\star$} \end{align}

That means for checking whether a given heuristic function $h$ is admissible, we have to verify that the inequality $(\star)$ holds by either
  (a) calculating the real cost $h^{*}$ for each node and comparing the values, or
  (b) proving it by using additional information available of the heuristic.

For example, we know that the eucledian distance is admissible for searching the shortest path (in terms of actual distance, not path cost). Note also that any consistent heuristic is admissible (but not always vice-versa).

For your example, there is no additional information available regarding the two heuristics. Thus you have to calculate the real cost $h^*$ for each node, and then check whether the inequality $(\star)$ holds (I leave this task to you).

By checking the total cost you can neither prove that a heuristic is admissible nor that a heuristic is not admissible. The problem with this idea is that on the one hand you sum up the costs of the edges, but on the other hand you sum up the path cost (the heuristic values). For example, consider the following search tree with start node $A$ and goal node $C$

enter image description here

and the following heuristic functions $h_1$ and $h_2$:

\begin{align} h_1(A) = 20; &\quad h_2(A) = 8 \\ h_1(B) = 10; &\quad h_2(B) = 11 \\ h_1(C) = 0; &\quad h_2(B) = 0 \\ \end{align}

The sum of the total cost of the search graph is $10 + 10 = 20$. The sum of the heuristic values of $h_1$ is equal to $20 + 10 + 0 = 30$, which is larger than $20$ although $h_1$ is admissible. The sum of the heuristic values of $h_2$ is equal to $8 + 11 + 0 = 19$, which is smaller than $20$, but $h_2$ is not admissible, since $h_2(B) = 11 \nleq h^{*}(B) = 10$.

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