/
SearchUtils.java
104 lines (91 loc) · 3.19 KB
/
SearchUtils.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package aima.core.search.framework;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import aima.core.agent.Action;
import aima.core.agent.impl.NoOpAction;
/**
* Provides several useful static methods for implementing search.
*
* @author Ravi Mohan
* @author Ruediger Lunde
*
*/
public class SearchUtils {
public static interface NodeListener {
void onNodeExpanded(Node node);
}
/**
* All node listeners added to this list get informed whenever a node is
* expanded. This is for demonstration and debugging purposes only. Handle
* with care!
*/
public static List<NodeListener> nodeListeners = new ArrayList<NodeListener>();
/**
* Returns the children obtained from expanding the specified node in the
* specified problem.
*
* @param node
* the node to expand
* @param problem
* the problem the specified node is within.
*
* @return the children obtained from expanding the specified node in the
* specified problem.
*/
public static List<Node> expandNode(Node node, Problem problem) {
List<Node> successors = new ArrayList<Node>();
for (NodeListener listener : nodeListeners)
listener.onNodeExpanded(node);
ActionsFunction actionsFunction = problem.getActionsFunction();
ResultFunction resultFunction = problem.getResultFunction();
StepCostFunction stepCostFunction = problem.getStepCostFunction();
for (Action action : actionsFunction.actions(node.getState())) {
Object successorState = resultFunction.result(node.getState(), action);
double stepCost = stepCostFunction.c(node.getState(), action, successorState);
successors.add(new Node(successorState, node, action, stepCost));
}
return successors;
}
/**
* Returns the list of actions corresponding to the complete path to the
* given node or NoOp if path length is one.
*/
public static List<Action> getSequenceOfActions(Node node) {
List<Node> nodes = node.getPathFromRoot();
List<Action> actions = new ArrayList<Action>();
if (nodes.size() == 1) {
// I'm at the root node, this indicates I started at the
// Goal node, therefore just return a NoOp
actions.add(NoOpAction.NO_OP);
} else {
// ignore the root node this has no action
// hence index starts from 1 not zero
for (int i = 1; i < nodes.size(); i++)
actions.add(nodes.get(i).getAction());
}
return actions;
}
/** Returns an empty action list. */
public static List<Action> failure() {
return Collections.emptyList();
}
/**
* Calls the goal test of the problem and - if the goal test is effectively
* a {@link SolutionChecker} - additionally checks, whether the solution is
* acceptable. Solution checkers can be used to analyze several or all
* solutions with only one search run.
*/
public static boolean isGoalState(Problem p, Node n) {
boolean isGoal = false;
GoalTest gt = p.getGoalTest();
if (gt.isGoalState(n.getState())) {
if (gt instanceof SolutionChecker) {
isGoal = ((SolutionChecker) gt).isAcceptableSolution(getSequenceOfActions(n), n.getState());
} else {
isGoal = true;
}
}
return isGoal;
}
}