Hi Steven:
Note though that I would now have implemented it
slightly differently: I would have made 'State' an
interface, rather than an abstract class. There were
rumors that in the current java VM's, use of interfaces is
inefficient since it involves a linear search where they
should have used a hashtable. I did not check this, but
anyway, if it is true it will no doubt be fixed soon in
upcoming versions.
In the case of my A* implementation, an interface for
'State' makes code using th A* class much more beautiful:
for example, I'm now working on an A* solver for my Rubik
cube applet (the problem space is huge though, I dont have
good enough heuristics yet) and I had to subclass 'State' and
give it an instance variable pointing to the corresponding Cube.
If State was an interface, I could have subclassed the Cube and
made sure it was a State as well. When I have time I'll make
this change, if you want to I'll let you know when this new
version is available.
Java A* Algorithm
=================
// -*- mode: java; folded-file: t -*-
/*
* Author Geert-Jan van Opdorp
*
* Copyright (c) 1995 AI Engineering.
*
*/
package aie.astar;
// {{{ import
import java.awt.*;
import java.awt.image.*;
import java.net.*;
import java.applet.*;
import java.lang.*;
import java.util.*;
// }}}
// {{{ final class node
final class node {
State state;
int costs;
int distance;
int total;
node parent;
node(State theState, node theParent, int theCosts, int theDistance) {
state = theState;
parent = theParent;
costs = theCosts;
distance = theDistance;
total = theCosts + theDistance;
};
}
// }}}
// {{{ public final class AStar
public final class AStar {
// {{{ Variables
private final Hashtable open = new Hashtable(500);
private final Hashtable closed = new Hashtable(500);
public int evaluated = 0;
public int expanded = 0;
public int bestTotal = 0;
public boolean ready = false;
private boolean newBest = false;
private final Vector nodes = new Vector(); //sorted open node
// }}}
private synchronized void setBest (int value) {
bestTotal = value;
newBest = true;
notify(); // All?
Thread.currentThread().yield(); //for getNewBest
}
public synchronized int getNewBest() {
while(!newBest) {
try {
wait();
} catch (InterruptedException e) {
}
}
newBest = false;
return bestTotal;
}
// {{{ private node search()
private node search() {
node best;
Vector childStates;
int childCosts;
Vector children = new Vector();
while (!(nodes.isEmpty())) {
best = (node) nodes.firstElement();
if(closed.get(best.state) != null) { //to avoid having to remove
nodes.removeElementAt(0); // improved nodes from nodes
continue;
}
if (!(best.total == bestTotal)) {
setBest(best.total);
}
if ((best.state).goalp()) return best;
children.removeAllElements();
childStates = (best.state).generateChildren();
childCosts = 1 + best.costs;
expanded++;
for (int i = 0; i < childStates.size(); i++) {
State childState = (State) childStates.elementAt(i);
node closedNode = null;
node openNode = null;
node theNode = null;
if ((closedNode = (node) closed.get(childState)) == null)
openNode = (node) open.get(childState);
theNode = (openNode != null) ? openNode : closedNode;
if (theNode != null) {
if (childCosts < theNode.costs) {
if (closedNode != null) {
open.put(childState, theNode);
closed.remove(childState);
} else {
int dist = theNode.distance;
theNode = new node(childState, best, childCosts, dist);
open.put(childState, theNode);
//nodes.removeElement(theNode); //get rid of this
}
theNode.costs = childCosts;
theNode.total = theNode.costs + theNode.distance;
theNode.parent = best;
children.addElement(theNode);
}
} else {
int estimation;
node newNode;
estimation = childState.estimate();
newNode = new node(childState, best, childCosts, estimation);
open.put(childState, newNode);
evaluated++;
children.addElement(newNode);
}
}
open.remove(best.state);
closed.put(best.state, best);
nodes.removeElementAt(0);
addToNodes(children); // update nodes
}
return null; //no open nodes and no solution
}
// }}}
private int rbsearch(int l, int h, int tot, int costs){
if(l>h) return l; //insert before l
int cur = (l+h)/2;
int ot = ((node) nodes.elementAt(cur)).total;
if((tot < ot) ||
(tot == ot && costs >= ((node) nodes.elementAt(cur)).costs))
return rbsearch(l, cur-1, tot, costs);
return rbsearch(cur+1, h, tot, costs);
}
private int bsearch(int l, int h, int tot, int costs){
int lo = l;
int hi = h;
while(lo<=hi) {
int cur = (lo+hi)/2;
int ot = ((node) nodes.elementAt(cur)).total;
if((tot < ot) ||
(tot == ot && costs >= ((node) nodes.elementAt(cur)).costs))
hi = cur - 1;
else
lo = cur + 1;
}
return lo; //insert before lo
}
// {{{ private void addToNodes(Vector children)
private void addToNodes(Vector children) {
for (int i = 0; i < children.size(); i++) {
node newNode = (node) children.elementAt(i);
int newTotal = newNode.total;
int newCosts = newNode.costs;
boolean done = false;
int idx = bsearch(0, nodes.size()-1, newTotal, newCosts);
nodes.insertElementAt(newNode, idx);
// for (int j = 0; j < nodes.size(); j++) {
// int ot = ((node) nodes.elementAt(j)).total;
// if (newTotal < ot) {
// nodes.insertElementAt(newNode, j);
// done = true;
// break;
// }
// if (newTotal == ot) {
// if (newNode.costs >= ((node) nodes.elementAt(j)).costs) {
// nodes.insertElementAt(newNode, j);
// done = true;
// break;
// }}
// }
// if (!done) nodes.addElement(newNode);
}
}
// }}}
// {{{ public final Vector solve (State initialState)
public final Vector solve (State initialState) {
node solution;
node firstNode;
int estimation;
expanded = 0;
evaluated = 1;
estimation = initialState.estimate();
firstNode = new node(initialState, null, 0, estimation);
open.put(initialState, firstNode);
nodes.addElement(firstNode);
solution = search();
nodes.removeAllElements();
open.clear();
closed.clear();
ready = true;
setBest(bestTotal);
return getSequence(solution);
}
// }}}
// {{{ private Vector getSequence(node n)
private Vector getSequence(node n) {
Vector result;
if (n == null) {
result = new Vector();
} else {
result = getSequence (n.parent);
result.addElement(n.state);
}
return result;
}
// }}}
}
// }}}
State package
=============
// -*- mode: java; folded-file: t -*-
package aie.astar;
import java.util.Vector;
// {{{ abstract class state
public abstract class State {
public abstract Vector generateChildren();
public abstract boolean goalp();
public abstract int estimate();
}
// }}}