Wikiって使ったことないからわかんないです。
518のPDFファイルのほぼコピペでとりあえず動くもの作ったが、PDFファイルに誤字ありまくりなので当ってるかどうかはわからん。何をしてるプログラムなのかもよく分からん。だもんで責任は持てません。
//================================================== // Node.java //================================================== import java.util.Hashtable; import java.util.Vector; public class Node { private String name; private Vector children; private Node pointer; private Hashtable childrenCosts; private int gValue; private int hValue; private int fValue; private boolean hasGValue; public Node(String theName, int theValue) { this.name = theName; children = new Vector(); childrenCosts = new Hashtable(); this.hValue = theValue; } public String getName() { return name; } public void setPointer(Node theNode) { this.pointer = theNode; } public Node getPointer() { return pointer; } public int getGValue() { return gValue; } public void setGValue(int theGValue) { this.gValue = theGValue; } public int getHValue() { return hValue; } public int getFValue() { return fValue; } public void setFValue(int theFValue) { this.fValue = theFValue; } /** * 子ノード追加 * * @param theChild そのノードの子ノード * @param theCost その子ノードまでのコスト */ public void addChild(Node theChild, int theCost) { children.addElement(theChild); childrenCosts.put(theChild, new Integer(theCost)); } public Vector getChildren() { return children; } public int getCost(Node theChild) { return ((Integer) (childrenCosts.get(theChild))).intValue(); } }
//================================================== // Search.java //================================================== import java.util.Vector; public class Search { private Node[] nodes; private Node goal; private Node start; public Search() { makeStateSpace(); } private void makeStateSpace() { // nodes(Node[])を定義 nodes = new Node[10]; // PDFのままノードを定義した。「theValue」はテキトー nodes[0] = new Node( "L.A.Airport", 0 ); nodes[1] = new Node( "UCLA", 1 ); nodes[2] = new Node( "Hollywood", 2 ); nodes[3] = new Node( "Anaheim", 3 ); nodes[4] = new Node( "Grand canyon", 4 ); nodes[5] = new Node( "San Diego", 5 ); nodes[6] = new Node( "Downtown", 6 ); nodes[7] = new Node( "Pasadena", 7 ); nodes[8] = new Node( "Disneyland", 8 ); nodes[9] = new Node( "Las Vegas", 9 ); // PDFのまま子ノードを定義した。「コスト」はテキトー nodes[0].addChild( nodes[1], 1 ); nodes[0].addChild( nodes[2], 2 ); nodes[1].addChild( nodes[2], 1 ); nodes[1].addChild( nodes[6], 2 ); nodes[2].addChild( nodes[3], 1 ); nodes[2].addChild( nodes[6], 2 ); nodes[2].addChild( nodes[7], 3 ); nodes[3].addChild( nodes[4], 1 ); nodes[3].addChild( nodes[7], 2 ); nodes[3].addChild( nodes[8], 3 ); nodes[4].addChild( nodes[8], 1 ); nodes[4].addChild( nodes[9], 2 ); nodes[5].addChild( nodes[1], 1 ); nodes[6].addChild( nodes[5], 1 ); nodes[6].addChild( nodes[7], 2 ); nodes[7].addChild( nodes[8], 1 ); nodes[7].addChild( nodes[9], 2 ); nodes[8].addChild( nodes[9], 1 ); // PDFのままスタートとゴールを定義した。 start = nodes[0]; goal = nodes[9]; } /** * 幅優先 * */ public void breadthFirst() { System.out.println( "<< 幅優先 >>" ); Vector open = new Vector(); open.addElement(nodes[0]); Vector closed = new Vector(); boolean success = false; int step = 0; while( true ) { // openが空のとき if( open.size() == 0 ) { success = false; break; // openが空でないとき } else { // openの先頭を取り出しnodeとする。 Node node = (Node)open.elementAt(0); open.removeElementAt(0); // nodeがゴールの時 if( node.equals(goal) ) { success = true; break; // nodeがゴールでないとき } else { // nodeを展開して子ノードをすべて求める。 Vector children = node.getChildren(); // nodeをclosedリストに入れる。 closed.addElement(node); for( int i=0; i<children.size(); i++ ) { Node m = (Node)children.elementAt(i); // 子ノードmがopenにもcloseにも含まれていなければ if( !open.contains(m) && !closed.contains(m) ) { // mからnodeへのポインタをつける。このポインタをたどることで解を表示することが出来る。 m.setPointer(node); // mがgoalであれば、openリストの先頭に挿入 if( m.equals(goal) ) { open.insertElementAt(m, 0); // mがgoalでなければ、未展開の子ノードmをopenリストの最後に置く。 } else { open.addElement(m); } } } } } } if( success ) { System.out.println( "*** Solution ***" ); printSolution(goal); } } /** * 深さ優先 * */ public void depthFirst() { System.out.println( "<< 深さ優先 >>" ); Vector open = new Vector(); open.addElement(nodes[0]); Vector closed = new Vector(); boolean success = false; int step = 0; while( true ) { // openが空のとき if( open.size() == 0 ) { success = false; break; // openが空でないとき } else { // openの先頭を取り出しnodeとする。 Node node = (Node)open.elementAt(0); open.removeElementAt(0); // nodeがゴールの時 if( node.equals(goal) ) { success = true; break; // nodeがゴールでないとき } else { // nodeを展開して子ノードをすべて求める。 Vector children = node.getChildren(); // nodeをclosedリストに入れる。 closed.addElement(node); // jは複数の子節点を適切にopenの先頭に置くために位置を調整する変数 int j=0; for( int i=0; i<children.size(); i++ ) { Node m = (Node)children.elementAt(i); // 子ノードmがopenにもcloseにも含まれていなければ if( !open.contains(m) && !closed.contains(m) ) { // mからnodeへのポインタをつける。このポインタをたどることで解を表示することが出来る。 m.setPointer(node); // mがgoalであれば、openリストの先頭に挿入 if( m.equals(goal) ) { open.insertElementAt(m, 0); // mがgoalでなければ、未展開の子ノードmをopenリストの最初に置く。 } else { open.insertElementAt(m, j); j++; } } } } } } if( success ) { System.out.println( "*** Solution ***" ); printSolution(goal); } } /** * @param goal */ private void printSolution(Node goal) { do { System.out.print( goal.getName() + " <- " ); goal = goal.getPointer(); }while( !goal.equals(start) ); System.out.println( goal.getName() ); } public static void main(String[] args) { Search obj = new Search(); if( args.length != 1 ) { System.out.println( "コマンドライン引数は1か2を入力してください。" ); System.exit(1); } // 1:幅優先 if( args[0].equals("1") ) { obj.breadthFirst(); // 2:深さ優先 } else if( args[0].equals("2") ) { obj.depthFirst(); } else { System.out.println( "コマンドライン引数は1か2を入力してください。" ); } } }