Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed to terminate only if there exists a solution."

Does this mean that, if I have such a graph, then there is no admissible A* which exists for this graph? When one says that A* is not admissible, this means that its heuristic is not admissible, right?

Furthermore, is it correct to say that a heuristic is only admissible with respect to a graph - not generally admissible?

For example, if I have a infinite graph which has a finite branching factor, and the cost of each edge is half of the cost of the edge preceding it (something like this: $goal\leftarrow_{_{c=2}} start \rightarrow_{_{c=1}}q1 \rightarrow_{_{c=1/2}} q_2 \rightarrow ...$), the heuristic and therefore the A* is necessarily inadmissible as there exists no fixed $\epsilon>0$ that is less than the cost of any edge?

To generalize, the $epsilon$ constraint is to make sure that there is no infinite path who's total cost converges, thereby assuring termination?

Any clarification is appreciated. Thanks!


1 Answer 1


The heuristic function $h:V \longrightarrow \mathbb{R}_{\geq 0}$ is *an input to the $A^*$ algorithm. If the function is admissible then $A^*$ algorithm gives you the solution; however as you have noted for infinite graphs the edge weights must have a positive lower bound.

The point of the heuristic function is to find the shortest path in the least amount of time, i.e. lower the computational complexity; because you are making informed decisions based on a heuristic (hence the name).

Recall the heuristic function is admissible if $h(v)$ is always less than (or equal to) the true path cost to the goal node.

There is always an admissable $h$ namely $h(v)= 0$ for all $v$. In this extreme case it becomes Dijkstra's algorithm.

Returning to the example you gave if you plug in the input $A^*(G,h)$ where $G$ is a description of $G$ and $h = 0$ then $A^*$ won't halt (geometric series $r = 2 \implies \sum_i r^i = \frac{1-r^{n+1}}{1-r} \leq 2$ for all finite partial sums). But lets see if we can bypass that; lets try: \begin{equation} h(v) = \begin{cases} 3 & \text{if } v = q_1 \\ 0 & \text{else}\end{cases} \end{equation} as you can see $h$ is admissible (because $d(q_1 , \text{goal}) = 3$ on the nose) and $A^*$ will pick "goal" as its first node (because its two choices are $f(q_1) = 4$ or $f(\text{goal}) = 2$).

  • 1
    $\begingroup$ Thanks for your answer; it's cleared everything up. Quick last question: does it make sense to ask that a BFS or a DFS algorithm is admissible. BFS algorithms return the optimal solution (I believe), but it doesn't have a heuristic, right? But since it doesn't have a heuristic, would that be equivalent to having a heuristic $h(n) = 0 \forall n$ - which is an admissible heuristic? Thanks. $\endgroup$ Commented Apr 30, 2020 at 17:26
  • $\begingroup$ Yea, exactly; BFS doesn't have a heuristic. The point of the heuristic is that you have given/"taught" the computer some "extra knowledge." The computer can use this knowledge to make "more informed decisions." The better the heuristic the faster the computer finds the solution; in other words, $h$ reduces the computational complexity of the problem. $\endgroup$ Commented May 1, 2020 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.