1
$\begingroup$

I was told that search algorithm such as IDA* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the solution may not be optimal as the agent is too pessimistic to try out a potentially optimal path, but as least it will try some path and which could be a sub-optimal solution (i.e. the search algorithm is at least sound and complete)?

$\endgroup$

1 Answer 1

2
$\begingroup$

Beam Search can fail to find any solution even with an admissible heuristic. (Suppose the beam has width $k=1$ and the root node has two children, $a$ and $b$, with $b$ being a solution and there is no solution reachable from $a$. Let $C(v)$ be the true cost of an optimal solution via vertex $v$ and $\infty$ if no solution via $v$ exists, and $H(\cdot)$ be an admissible heuristic for $C(\cdot)$. Then it could be that $C(a) = \infty$ but $H(a) < H(b) \le C(b) < \infty$, in which case the only solution, $b$, is discarded immediately.)

IDA* will find a (possibly suboptimal) solution if an inadmissible heuristic is used.

$\endgroup$
2
  • $\begingroup$ I just read a textbook which says that IDA* will not keep all the reached states in memory. Maybe that's why it can fail to find the solution when the heuristic is inadmissible, as when it choose to ignore a node it will never expand it again? $\endgroup$
    – Sam
    Sep 19, 2022 at 16:35
  • 1
    $\begingroup$ IDA* comprises a series of DFS passes that each start from scratch and proceed until a pass-specific cost cutoff. At some point during each pass, every node below that pass's cost cutoff will be generated -- but none of them are saved in memory. The cost cutoff increases with each pass, so each pass will generate all nodes generated in all preceding passes (plus a few more). $\endgroup$ Sep 20, 2022 at 6:02

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.