Search Tree

[strokebow]

Hi I have a quick question. I have a tree structure and I want to implement breadth search first and Iterative deepening depth-first search on the tree.

Rather than having a goal node, however, I have a goal sequence (a certain order of characters I want to obtain). I want to obtain as many of the 6 different sequences from this tree from my data set as I can.

......P
......|
......P
......|
......C
..../.....\
...G.......P
...|.........|
...G........G
....|........|
....P.......P
....|........|
....A........A
.../ |\ ...../ | \
...A C G...A C G
...| | |....| | |
...G G G...G G G
...| | |.....| | |
..G G G.....G G G

My question is this:

How will the Iterative deepening depth-first search be carried out on such a tree? How will it differ from the Depth First Search? If at all?

Thank you very much for reading. Your help is much appreciated.



edit: ahhh! the white space didnt stay!
(ignore the dots '.')

[itCbitC]

Is this a sorted b-tree data structure?

[strokebow]

Please ask me for more info if it is required or if I have explained poorly.

[strokebow]

Is this a sorted b-tree data structure?

Hi,

yes.

This tree structure represents the 6 different motif sequences I desire from a dataset.

I am just wondering for this hypothetical tree how one would implement the two search strategies and how/if they would differ?

[iMalc]

Iterative deepening differs from breadth-first search thusly:

• It requires less memory during the process.
• It traverses parts of the data structure multiple times instead of just once.
• It generally takes more time, due to the second difference having greater impact that the first difference.

Both should generate the same results. You perform Iterative deepening on this type of tree which has 1..n children, in the same way you do it on a binary or n-ary tree:

1. Start with k=0
2. Iterate over the tree depth-first, searching for all nodes at depth k
3. increase k
4. repeat until no nodes are found at depth k

Your diagram will preserve the spaces AND use a fixed width font (as desired) if you enclose it inside [code][/code] tags rather than [quote][/quote] tags

[Adak]

Iterative deepening DFS works just like regular DFS except, after it has finished some n number of plys (levels in the tree), it will come back and give the calling function a "best number so far" value.

In chess programming for instance, it quickly gives your program a "best move so far" index number, from the moves array. It causes shallow depth moves in the search tree, to be looked at again, (thus wasting a tiny bit of time), but the huge benefit is that your program will *always* have a best move it can play from a previous ply in the search tree, if time expires (and a move must be made right now).

Iterative deepening was one of the big improvements in chess programming, starting with the World Champion CHESS program from Northwestern, and the (also World Champion), Russian KAISSA program.