/
Node.java
137 lines (122 loc) · 4.11 KB
/
Node.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package aima.core.search.framework;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.10, page
* 79.<br>
*
* Figure 3.10 Nodes are the data structures from which the search tree is
* constructed. Each has a parent, a state, and various bookkeeping fields.
* Arrows point from child to parent.<br>
* <br>
* Search algorithms require a data structure to keep track of the search tree
* that is being constructed. For each node n of the tree, we have a structure
* that contains four components:
* <ul>
* <li>n.STATE: the state in the state space to which the node corresponds;</li>
* <li>n.PARENT: the node in the search tree that generated this node;</li>
* <li>n.ACTION: the action that was applied to the parent to generate the node;
* </li>
* <li>n.PATH-COST: the cost, traditionally denoted by g(n), of the path from
* the initial state to the node, as indicated by the parent pointers.</li>
* </ul>
*
* @param <S> The type used to represent states
* @param <A> The type of the actions to be used to navigate through the state space
*
* @author Ravi Mohan
* @author Ciaran O'Reilly
* @author Mike Stampone
* @author Ruediger Lunde
*/
public class Node<S, A> {
// n.STATE: the state in the state space to which the node corresponds;
private final S state;
// n.PARENT: the node in the search tree that generated this node;
private final Node<S, A> parent;
// n.ACTION: the action that was applied to the parent to generate the node;
private final A action;
// n.PATH-COST: the cost, traditionally denoted by g(n), of the path from
// the initial state to the node, as indicated by the parent pointers.
private final double pathCost;
private final int depth;
/**
* Constructs a root node for the specified state.
*
* @param state
* the state in the state space to which the node corresponds.
*/
public Node(S state) {
this(state, null, null, 0.0);
}
/**
* Constructs a node with the specified state, parent, action, and path
* cost.
*
* @param state
* the state in the state space to which the node corresponds.
* @param parent
* the node in the search tree that generated the node.
* @param action
* the action that was applied to the parent to generate the
* node.
* @param pathCost
* full pathCost from the root node to here, typically
* the root's path costs plus the step costs for executing
* the the specified action.
*/
public Node(S state, Node<S, A> parent, A action, double pathCost) {
this.state = state;
this.parent = parent;
this.action = action;
this.pathCost = pathCost;
depth = parent != null ? parent.getDepth()+1 : 0;
}
/**
* Returns the state in the state space to which the node corresponds.
*
* @return the state in the state space to which the node corresponds.
*/
public S getState() {
return state;
}
/**
* Returns this node's parent node, from which this node was generated.
*
* @return the node's parenet node, from which this node was generated.
*/
public Node<S, A> getParent() {
return parent;
}
/**
* Returns the action that was applied to the parent to generate the node.
*
* @return the action that was applied to the parent to generate the node.
*/
public A getAction() {
return action;
}
/**
* Returns the cost of the path from the initial state to this node as
* indicated by the parent pointers.
*
* @return the cost of the path from the initial state to this node as
* indicated by the parent pointers.
*/
public double getPathCost() {
return pathCost;
}
/**
* Returns <code>true</code> if the node has no parent.
*
* @return <code>true</code> if the node has no parent.
*/
public boolean isRootNode() {
return parent == null;
}
public int getDepth() {
return depth;
}
@Override
public String toString() {
return "[parent=" + parent + ", action=" + action + ", state=" + getState() + ", pathCost=" + pathCost + "]";
}
}