Archive

Posts Tagged ‘Breadth-first search’

Iterative Deepening Search

September 4th, 2010 2 comments

Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.

Breadth First Search Vs Depth First Search

September 4th, 2010 1 comment
Breadth First Search Depth First Search
Advantages
Optimal solutions are always found

Multiple solutions found early

May arrive at solutions without examining much of search space
Will not go down blind alley for solution Needs little memory (only node in current path needs to be stored)
Disadvantages
If solution path is long, the whole tree must be searched up to that depth May settle for non-optimal solution
All of the tree generated must be stored in memory May explore single unfruitful path for a long time (forever if loop exists!)

Breadth First Search

September 4th, 2010 No comments
An animation to visualize the Breadth-First-Se...

Image via Wikipedia

BFS is an uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it. It does not use a heuristic algorithm.

From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO (i.e., First In, First Out) queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called “open” and then once examined are placed in the container “closed”.