Jump to content

Talk:Iterative deepening depth-first search

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Lead sentence: "depth-first" vs. "breadth-first"

[edit]

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)[reply]

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)[reply]
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)[reply]
...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)[reply]
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)[reply]
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)[reply]

Space complexity

[edit]

I just reverted the space complexity of IDDFS back to O(bd) after it was changed to O(bd) 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)[reply]

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)[reply]
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)[reply]

actual quotes

[edit]

"In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known."

Is a citation really enough? This appears to be an __exact__ quote from the Norvig book. Shouldn't there be quotes or something around it, or shouldn't it be rewritten? Seems to be borderline plagiarism still otherwise. (FYI, I originally quoted it, but it was later changed to a regular Wikipedia style citation.) -- Solberg (talk) 03:08, 24 December 2007 (UTC)Solberg[reply]

IDA*

[edit]

Why is IDA* (iteratively deepening A*) a redirect here? It seems to have next to nothing to do with IDDFS. --SLi (talk) 14:58, 17 April 2008 (UTC)[reply]

I agree. iIeratively deepening A* is not the same thing. This should have it's own article. - Mike —Preceding unsigned comment added by 137.205.112.19 (talk) 10:23, 20 June 2008 (UTC)[reply]

Thirded 64.252.22.20 (talk) 13:27, 9 July 2008 (UTC)[reply]

This page looks to have been copied without attribution

[edit]

Check out the copy here: http://www.onlinemca.com/mca_course/kurukshetra_university/semester4/artificialintelligence/iterative_depthfirst_search.php — Preceding unsigned comment added by 74.198.87.67 (talk) 20:45, 15 September 2011 (UTC)[reply]

Code won't end

[edit]

The code simply won't end if the node doesn't exist. It should be a condition for the DLS to inform the iddfs that it have reached the deepest. Timothychen1019 (talk) 13:03, 23 October 2017 (UTC)[reply]

Second example for unknown depth, proposal

[edit]

Agreed, but in order to keep code simple as it is now I would maintain the current example with a big "if depth or goal membership is known" notice (changing ∞ for known depth), but add another example returning a sentinel element to denote some elements remain (a mismatch), different from "null" which would mean the current level has 0 children. --2bam (talk) 17:38, 16 July 2018 (UTC)[reply] 

remaining_levels ← new node
no_more_levels ← null

function IDDFS(root)
    found ← null
    for depth from 0 to ∞
        found ← DLS(root, depth)
        if found = null
            break
    return found

function DLS(node, depth)
    if depth = 0
        node is a goal
            return node
        else if node has children
            return remaining_levels
        else
            return no_more_levels

    else if depth > 0
        any_remaining ← false
        foreach child of node
            found ← DLS(child, depth−1)
            if found = remaining_levels
                any_remaining = true
            else if node ≠ no_more_levels
                return found
        
        if any_remaining
            return remaining_levels
        else
            return no_more_levels

Also, a functional-ish approach (return collected children list, stop if no children were collected, check outside if matching goal) would be the clearest, although maybe more difficult to imperative-only programmers. It should have a notice for performance issues of collecting and concatenation of lists (time and memory-wise, feasibility for infinite trees, etc.): --2bam (talk) 17:38, 16 July 2018 (UTC)[reply] 

function IDDFS(root)
    for depth from 0 to ∞
        level ← DLS(root, depth)

        if level is empty
            break

        for each node in level
            if node is goal
                return goal


function DLS(node, depth)
    if depth = 0
        return [node]

    else if depth > 0
        collected ← empty list
        for each child of node
            level ← DLS(child, depth−1)
            collected += level

        return collected

Could also return a tuple with "children left" and the element or null. --2bam (talk) 17:55, 16 July 2018 (UTC)[reply] 


function IDDFS(root)
   for depth from 0 to ∞
       found, remaining ← DLS(root, depth)
       if found ≠ null
           return found
       else if not remaining
           return null

function DLS(node, depth)
   if depth = 0
       if node is a goal
           return (node, true)
       else
           return (null, true)    (Not found, but may have children)

   else if depth > 0
       any_remaining ← false
       foreach child of node
           found, remaining ← DLS(child, depth−1)
           if found ≠ null
               return (found, true)   
           if remaining
               any_remaining ← true    (At least one node found at depth, let IDDFS deepen)
       return (null, any_remaining)

Updated to match article. --2bam (talk) 01:02, 22 July 2018 (UTC)[reply]

Pseudocode for bidirectional IDDFS: yes or no?

[edit]

I have managed to write (possibly) correct pseudocode implementation of the bidirectional IDDFS (see Richard E. Korf's 1985 paper, pages 102 - 103). The code is backed up by a Java implementation that seems to work correctly as compared to a couple of other algorithms. Now, is it O.K. to add that pseudocode to its own subsection, or should I create a separate Wikipedia article for it? — Preceding unsigned comment added by Rodion.Efremov (talk • contribs) 10:44, 20 June 2019 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Iterative_deepening_depth-first_search&oldid=1207758666"