Hacker News new | past | comments | ask | show | jobs | submit login

I recently implemented depth-first iterative deepening in an Artificial Intelligence class project to solve the classic missionaries and cannibals problem [0]. The professor remarked that while there have been some optimizations over the last few decades, using them can be quite messy – to the point where the combination of A* and iterative deepening is still commonly used in the field.

I'm fairly certain that the claim in the introduction – "Unfortunately, current AI texts either fail to mention this algorithm or refer to it only in the context of two-person game searches" – is no longer true.

From my current textbook (Artificial Intelligence: A Modern Approach [1]):

"Iterative deepening search (or iterative deepening depth-first search) is a general strategy, often used in combination with depth-first tree search, that finds the best depth limit. It does this by gradually increasing the limit — first 0, then 1, then 2, and so on — until a goal is found... In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known."

[0] http://en.wikipedia.org/wiki/Missionaries_and_cannibals_prob...

[1] http://www.amazon.com/Artificial-Intelligence-Modern-Approac...

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact