Breadth-First-Search.md

BREADTH-FIRST-SEARCH

AIMA4e

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
 if problem's initial state is a goal then return empty path to initial state
 frontier ← a FIFO queue initially containing one path, for the problem's initial state
 reached ← a set of states; initially empty
 solution ← failure
 while frontier is not empty do
   parent ← the first node in frontier
   for child in successors(parent) do
     s ← child.state
     if s is a goal then
       return child
     if s is not in reached then
       add s to reached
       add child to the end of frontier
 return solution

---

Figure 3.9 Breadth-first search algorithm.

AIMA3e

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
 node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
 if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
 frontier ← a FIFO queue with node as the only element
 explored ← an empty set
 loop do
   if EMPTY?(frontier) then return failure
   node ← POP(frontier) /* chooses the shallowest node in frontier */
   add node.STATE to explored
   for each action in problem.ACTIONS(node.STATE) do
      child ← CHILD-NODE(problem,node,action)
      if child.STATE is not in explored or frontier then
         if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)
         frontier ← INSERT(child,frontier)

---

Figure ?? Breadth-first search on a graph.