# Are there graphs for which A* cannot be admissible?

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!

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: $$$$h(v) = \begin{cases} 3 & \text{if } v = q_1 \\ 0 & \text{else}\end{cases}$$$$ 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$$).

• 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. – iaskdumbstuff Apr 30 '20 at 17:26
• 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. – Pedro Juan Soto May 1 '20 at 14:10