public class BreadthFirstSearch extends java.lang.Object implements SearchForActions, SearchForStates
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.| Constructor and Description |
|---|
BreadthFirstSearch() |
BreadthFirstSearch(QueueSearch impl) |
| Modifier and Type | Method and Description |
|---|---|
java.util.List<Action> |
findActions(Problem p)
Returns a list of actions to the goal if the goal was found, a list
containing a single NoOp Action if already at the goal, or an empty list
if the goal could not be found.
|
java.lang.Object |
findState(Problem p)
Returns a state which is might be but not necessary is a goal state of
the problem.
|
Metrics |
getMetrics()
Returns all the metrics of the search.
|
NodeExpander |
getNodeExpander()
Returns the node expander used by the search.
|
public BreadthFirstSearch()
public BreadthFirstSearch(QueueSearch impl)
public java.util.List<Action> findActions(Problem p)
SearchForActionsfindActions in interface SearchForActionsp - the search problempublic java.lang.Object findState(Problem p)
SearchForStatesfindState in interface SearchForStatesp - the search problempublic NodeExpander getNodeExpander()
SearchForActionsgetNodeExpander in interface SearchForActionsgetNodeExpander in interface SearchForStatespublic Metrics getMetrics()
SearchForActionsgetMetrics in interface SearchForActionsgetMetrics in interface SearchForStates