New answers tagged


I believe you can use any algorithm for heuristic search. On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.


I suspect they probably mean $$ub_d = \max_i x_i^d$$ where $x_i^d$ is the $d$h coordinate of $x_i$; and similarly for $lb_d$, but using $\min$ instead of $\max$. But I don't know -- I am just speculating based on context.


No. Assume towards contradiction that it is true, then ignore $f$ completely (choose some $f$ which is constant) Then, what your statement would say is that $h,g$ are admissible $\implies h+g$ is admissible. In particular, for any admissible function $g$, choose $h=g$, and your statement implies $2g$ is admissible. Apply the statement again to get that $3g$ ...

Top 50 recent answers are included