Talk:Iterative deepening depth-first search

From Wikipedia, the free encyclopedia

[edit] Lead sentence: "depth-first" vs. "breadth-first"

There seems to be a minor dispute involving the first sentence of the article, which used to say:

Iterative deepening depth-first search is a state space search strategy, that visits each node in the search tree in the same order as depth-first search but does so by gradually increasing the maximum depth limit of the search iteratively.

I noticed what I believe to be a mistake in that description a while ago, and corrected it to say:

Iterative deepening depth-first search is a state space search strategy, that visits each node in the search tree in the same order as breadth-first search but does so by gradually increasing the maximum depth limit of the search iteratively.

Today, 84.92.184.91 reverted my change, providing no edit summary. Since I still believe my version to be correct, I have reverted to it again, but will not do so again until the apparent dispute has been settled.

As far as I can tell from the article (and from what other sources I'm familiar with), a iterative deepening depth-first search is essentially a way to simulate a breadth-first search by repeatedly doing a depth-limited depth-first search with successively increasing limits. As such, the order in which the nodes are (first) visited is the same as for a real breadth-first search — and indeed that is the entire point of the whole thing. Or am I just really confused? —Ilmari Karonen (talk) 16:20, 25 January 2006 (UTC)

As I understand it, your form is not correct. Whilst breadth first and depth first theoretically give the same results for a fixed search depth, the order of evaluation of the nodes is different. The main point of iterative deepening is that it improves alpha-beta pruning, killer heuristic tables and other heuristics by giving a better initial evaluation order. A breadth first seach doesn't work quite the same way for these heuristics, and it isn't used. A depth first search tends to evaluate the best move first, or earlier in the search, and the heuristics then hold onto the best move throughout the evaluation, causing large parts of the tree to be pruned.WolfKeeper 19:07, 25 January 2006 (UTC)

I agree with WolfKeeper here. Also, I'd like to point out that it's "iterative deepening depth-first search". :) --Arabani (Talk ∞ Contribs) 20:02, 25 January 2006 (UTC)

...which is precisely what made it sound redundant to me. But I do see WolfKeeper's point now. In think, in a way, we're both right, and the lead sentence is simply confusing. One one hand, an IDDFS consists of repeated depth-limited searches, and each DLS certainly visits the nodes in depth-first order. On the other, since each iteration only visits one new layer of nodes, the order in which the entire IDDFS first visits each node, assuming no pruning, is breadth-first. The latter property is significant since it guarantees completeness,

Huh? Are you saying that fixed depth-depth first searches aren't complete? Why is the order that new nodes are evaluated at all important?WolfKeeper 15:46, 26 January 2006 (UTC)

Yes I am, and I believe Depth-limited search#Completeness agrees with me. If the order didn't matter, surely a simple unlimited depth-first search would be complete, and there would be no point in iterating it. —Ilmari Karonen (talk) 19:28, 26 January 2006 (UTC)

but I suppose that for pruned searches it's the former property that matters more. In any case, the lead section should probably be clarified in some. I'll try and see if I can come up with something less ambiguous. —Ilmari Karonen (talk) 13:20, 26 January 2006 (UTC)

[edit] Space complexity

I just reverted the space complexity of IDDFS back to O(bd) after it was changed to O(b^d) by 84.49.100.52 (talk • contribs). I do believe this is correct (and, in fact, it seems to me only O(d) space is needed if the children of each node are traversed in a predetermined order), but I'd welcome any comments. —Ilmari Karonen (talk) 15:14, 20 June 2006 (UTC)

In it's simplest form surely space complexity is just O(d), where d is the maximum depth? You don't have to generate a child of a node, except when you evaluate it, and you can destroy it immediately after. It's the same as fixed depth-first search.WolfKeeper 15:52, 20 June 2006 (UTC)

Right. The O(bd) applies if you are choosing the descent path heuristically (or randomly), in which case you have to keep track of all the branches you've already taken at each level to know when you're done. —Ilmari Karonen (talk) 20:38, 20 June 2006 (UTC)