import java.util.*;
/**
* This abstract class represents a Node of the A* algorithm.
*/
public abstract class Node {
/**
* nodeCount is the counter for all instances of this class. It is used to
* assign each instance a unique identifier used in the
* {@link #distinguishCompare(Node)} method.
*/
private static long nodeCount = 0;
/**
* nodeNum is the "serial number" of this instance, initialized in the
* constructor using the {@link #nodeCount} value.
*/
private long nodeNum;
/**
* Simple constructor that takes the parent node and the g-value as
* parameters. It automatically initializes the "serial number" also.
*/
protected Node(Node parent, double gValue) {
this.parent = parent;
this.gValue = gValue;
nodeNum = nodeCount++;
}
/**
* The parent node. It represents the search state from which we generated
* the current state.
*/
private Node parent;
/**
* The g-value.
*/
private double gValue;
/**
* This is the cached g+h value, for better performance.
*
* Whenever we need to find the g+h value of this search node, and
* {@link #useCachedGPlusH} is set to true, we'll read the g+h
* value from this field instead of calculating it.
*/
private double cachedGPlusH = 0;
/**
* This boolean flag will be "true" if g+h has already been evaluated.
*/
private boolean useCachedGPlusH = false;
/**
* Returns the parent node.
*/
public Node getParent() {
return parent;
}
/**
* Returns the g-value.
*/
public double getGValue() {
return gValue;
}
/**
* Evaluates and returns the g+h value for this node.
*/
public double evaluateGPlusH() {
if (useCachedGPlusH) {
return cachedGPlusH;
} else {
cachedGPlusH = evaluateHeuristic() + getGValue();
useCachedGPlusH = true;
return cachedGPlusH;
}
}
/**
* Returns a comparator used to compare nodes when deciding on which to
* expand next. If one of the nodes has smaller g+h value, it gets expanded
* first. If both nodes have the same g+h value, the one with bigger g value
* will get expanded first. If both nodes have the same g value and the same
* h value, then we need to call {@link #distinguishCompare(Node)} so that
* we never return 0 for different nodes.
*/
public Comparator getComparator() {
return new Comparator() {
/**
* Returns -1 if the first node should be expanded first, 1 if the
* second node should be expanded first. 0 is returned if and only
* if both nodes refer to the same search state, that is, the same
* instance of {@link Node}.
*
* @param n1
* @param n2
* @return
*/
public int compare(Node n1, Node n2) {
// TODO: your code here.
/*
* Implementation notes:
* See the getComparator method comment.
* Useful functions:
*
* node.evaluateGPlusH() returns the g+h value of the node
*
* node.getGValue() returns the g value of the node.
*
* IMPORTANT: if both nodes have the same g and h values, call
* return n1.distinguishCompare(n2)
*/
}
/**
* Returns "true" if both pointers refer to the same instance.
*
* @param n1
* @param n2
* @return
*/
public boolean equals(Node n1, Node n2) {
return n1 == n2;
}
};
}
/**
* This abstract method generates the successor states.
*
* @return
*/
public abstract List extends Node> generateChildren();
/**
* This abstract method decided whether this search state is the goal state.
*
* @return
*/
public abstract boolean isGoal();
/**
* Evaluates the h-value for this search state.
*
* @return
*/
public abstract double evaluateHeuristic();
/**
* Used to compare nodes with the same g and h values. Should not return 0
* if the provided node refers to a different search state.
*/
public int distinguishCompare(Node n) {
if (nodeNum > n.nodeNum)
return 1;
if (nodeNum < n.nodeNum)
return -1;
return 0;
}
/**
* Prints out the solution, assuming that this node is the goal node. This
* default implementation prints all the states from the root one to the
* goal one and returns the number of states.
*/
public int printSolution() {
List nodes = new ArrayList();
Node p = this;
while (p != null) {
nodes.add(p);
p = p.getParent();
}
for (int i = nodes.size() - 1; i >= 0; i--) {
System.out.println(nodes.size() - i - 1 + ":");
System.out.println(nodes.get(i).toString());
}
return nodes.size();
}
}