/
BestFirstSearch.java
50 lines (44 loc) · 1.8 KB
/
BestFirstSearch.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.informed;
import aima.core.search.framework.Node;
import aima.core.search.framework.QueueBasedSearch;
import aima.core.search.framework.QueueFactory;
import aima.core.search.framework.qsearch.QueueSearch;
import java.util.Comparator;
import java.util.function.ToDoubleFunction;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): page 92.<br>
* <br>
* Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH
* algorithm in which a node is selected for expansion based on an evaluation
* function, f(n). The evaluation function is construed as a cost estimate, so
* the node with the lowest evaluation is expanded first. The implementation of
* best-first graph search is identical to that for uniform-cost search (Figure
* 3.14), except for the use of f instead of g to order the priority queue.
*
* @author Ruediger Lunde
* @author Ciaran O'Reilly
* @author Mike Stampone
*/
public class BestFirstSearch<S, A> extends QueueBasedSearch<S, A> implements Informed<S, A> {
private final EvaluationFunction<S, A> evalFn;
/**
* Constructs a best first search from a specified search execution strategy and an
* evaluation function.
*
* @param impl
* A search execution strategy.
* @param evalFn
* An evaluation function, which returns a number purporting to
* describe the desirability (or lack thereof) of expanding a
* node.
*/
public BestFirstSearch(QueueSearch<S, A> impl, final EvaluationFunction<S, A> evalFn) {
super(impl, QueueFactory.createPriorityQueue(Comparator.comparing(evalFn::applyAsDouble)));
this.evalFn = evalFn;
}
/** Modifies the evaluation function. */
@Override
public void setHeuristicFunction(ToDoubleFunction<Node<S, A>> h) {
evalFn.setHeuristicFunction(h);
}
}