2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

After some consideration, this appears to be an alternative formulation of the depth-first variant of the Branch-and-Bound algorithm.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Carlos Linares López
    Feb 1, 2016 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.