Showing posts with label Breadth. Show all posts
Showing posts with label Breadth. Show all posts

Sunday, 18 January 2009

breadth first search algorithm

procedure breadth_first_search;
begin
OPEN:=[START];
CLOSED:=[ ];

while OPEN<>[ ] do
begin
X := dequeue (OPEN);
if final(X)
then return(success);
else
begin
add X to CLOSED
find successors of X
kill the successors of X that are in CLOSED or OPEN;
enqueue the surviving successors of X into OPEN;
end; {else}
end; {while}

return(failure);
end; {breadth_first_search}

Classification of Strategies for State Space Search

Blind (exhaustive, uninformed, naive) – explore the state space systematically without any “suspicion” where the final state might be and direction of the search to it.
Breadth-first search;
Depth-first search (depth-first search with leap-frogging (or just depth-first search), depth-first search with backtracking (or just Backtracking)
Uniform-cost search;
Iterative deepening;
Etc.
Heuristic (informed)- exploit state descriptions to select the “most promising” node