/
BreadthFirstSearch.java
50 lines (46 loc) · 1.74 KB
/
BreadthFirstSearch.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package aima.core.search.uninformed;
import aima.core.search.framework.*;
import aima.core.search.framework.qsearch.GraphSearch;
import aima.core.search.framework.qsearch.QueueSearch;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.11, page
* 82.<br>
* <br>
*
* <pre>
* 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)
* </pre>
*
* Figure 3.11 Breadth-first search on a graph.<br>
* <br>
* <b>Note:</b> Supports TreeSearch, GraphSearch, and BidirectionalSearch. Just
* provide an instance of the desired QueueSearch implementation to the
* constructor!
*
* @author Ruediger Lunde
* @author Ciaran O'Reilly
*/
public class BreadthFirstSearch<S, A> extends QueueBasedSearch<S, A> {
public BreadthFirstSearch() {
this(new GraphSearch<>());
}
public BreadthFirstSearch(QueueSearch<S, A> impl) {
super(impl, QueueFactory.createFifoQueue());
// Goal test is to be applied to each node when it is generated
// rather than when it is selected for expansion.
impl.setEarlyGoalTest(true);
}
}