package aima.core.search.uninformed;
import java.util.List;
import aima.core.agent.Action;
import aima.core.search.framework.GraphSearch;
import aima.core.search.framework.Metrics;
import aima.core.search.framework.Node;
import aima.core.search.framework.Problem;
import aima.core.search.framework.QueueSearch;
import aima.core.search.framework.Search;
import aima.core.util.datastructure.FIFOQueue;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.11, page
* 82.
*
*
*
* 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 3.11 Breadth-first search on a graph.