3
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 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$ – iaskdumbstuff Apr 30 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$ – Pedro Juan Soto May 1 at 14:10

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.