search - Iterative Deepening Without Specified Depth Limit -
i have question regarding search technique iterative deepening. question is, difference between normal depth-first search , iterative deepening without specified depth limit? have tree goal node have no specified limit in iterative deepening search. output same traversal sequence if regular depth-first search?
suppose goal @ depth level of 3 (with root being @ depth = 0), , it's not way on "left" side of tree (where found depth-first search (dfs)).
a normal dfs may spend lot of time search @ depth levels of 4, 5, 6, etc., beforing moving "up" tree, "to right", , finding goal @ depth 3. iterative deepening, if there goal @ depth = 3, never waste time looking @ nodes @ depth = 4. because iterative deepening first dfs depth limit of 1, dfs depth limit of 2, , dfs depth limit of 3 (which find goal , therefore terminate search).
note in example situation, breadth-first search (brfs) not waste time @ depth of 4, , bit faster due not re-doing work done previously. take lot more memory though.
another advantage of iterative deepening cannot stuck in infinitely long path. in practical situations infinitely long path unlikely anyway, it's possible. dfs stuck in such infinite path.
finally, iterative deepening has advantage compared dfs in can provide more useful results when terminating due running out of processing time. important in search algorithms game-playing (think of chess engine). since explicitly specified there goal node in situation, don't think relevant you, let me know if you're interested , can write explanation advantage well.
Comments
Post a Comment