# Informed search with a lower-bound heuristic?

I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state.

However, what about when one only has a heuristic that never underestimates the minimum cost from a node to any goal state? (Also: is there a name for such a heuristic?)

What I am currently doing is as follows. I first find some path to a goal state (luckily in my case this is relatively trivial) and record its cost and path as the best cost and path. Then I do a depth-first search, with two modifications. One, I do not stop when I reach a goal state, instead updating the best cost found so far and record the path to get here. Two, anytime I find myself at a node where the sum of the cost to get here and the heuristic is greater than or equal to the best cost found so far, I backtrack. Then at the end I output the best path found.

(Two nice things about this: 1) it's guaranteed to return an optimal solution, 2) if interrupted it has a solution, albeit a suboptimal one)

I've been calling this "iterative shallowing" (as opposed to iterative deepening), but I have no clue as to the actual name.

So: is there a name for this? If so, what is it? Is there a name for a lower-bound heuristic? Is there a name for informed search algorithms using only a lower-bound heuristic?

• Regarding your question about whether that algorithm has a name or not, you're right and that's known as DFBnB: Depth First Branch and Bound. Regarding whether we have names for heuristics that never underestimate the minimum cost (ie., $h(n)\geq h^*(n)$) the answer is no because they can not be used for optimally solving minimization problems. Feb 1, 2016 at 7:36