单源最短路径的完整代码及其迭代过程

单源最短路径的完整代码及其迭代过程
单源最短路径的完整代码及其迭代过程

单源最短路径的完整代码及其迭代过程
一本书上的练习题,刚编的.注释用的日文字体,看不懂记得提问.
import java.util.*;
public class Search {
Node node[];
Node start;
Node goal;
Search() {
makeStateSpace();
}
private void makeStateSpace() {
node = new Node[10];
// 状态空间の生成
node[0] = new Node("L.A.Airport", 0);
start = node[0];
node[1] = new Node("UCLA", 7);
node[2] = new Node("Hollywood", 4);
node[3] = new Node("Anaheim", 6);
node[4] = new Node("Grand Canyon", 1);
node[5] = new Node("SanDiego", 2);
node[6] = new Node("Downtown", 3);
node[7] = new Node("Pasadena", 4);
node[8] = new Node("DisneyLand", 2);
node[9] = new Node("Las Vegas", 0);
goal = node[9];
node[0].addChild(node[1], 1);
node[0].addChild(node[2], 3);
node[1].addChild(node[2], 1);
node[1].addChild(node[6], 6);
node[2].addChild(node[3], 6);
node[2].addChild(node[6], 6);
node[2].addChild(node[7], 3);
node[3].addChild(node[4], 5);
node[3].addChild(node[7], 2);
node[3].addChild(node[8], 4);
node[4].addChild(node[8], 2);
node[4].addChild(node[9], 1);
node[5].addChild(node[1], 1);
node[6].addChild(node[5], 7);
node[6].addChild(node[7], 2);
node[7].addChild(node[8], 1);
node[7].addChild(node[9], 7);
node[8].addChild(node[9], 5);
}
/***
* 幅优先探索
*/
public void breadthFirst() {
List open = new ArrayList();
open.add(start);
List closed = new ArrayList();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か?
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか?
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ArrayList children = node.getChildren();
// node を closed に入れる．
closed.add(node);
// 子节点 m が open にも closed にも含まれていなければ,
for (int i = 0; i < children.size(); i++) {
Node m = (Node) children.get(i);
if (!open.contains(m) && !closed.contains(m)) {
// m から node へのポインタを付ける．
m.setPointer(node);
if (m == goal) {
open.add(0, m);
} else {
open.add(m);
}
}
}
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 深さ优先探索
*/
public void depthFirst() {
List open = new ArrayList();
open.add(start);
List closed = new ArrayList();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か?
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか?
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ArrayList children = node.getChildren();
// node を closed に入れる．
closed.add(node);
// 子节点 m が open にも closed にも含まれていなければ,
// 以下を実行．幅优先探索と异なるのはこの部分である．
// j は复数の子节点を适切にopenの先头に置くために位置
// を调整する変数であり,一般には展开したときの子节点
// の位置は任意でかまわない．
int j = 0;
for (int i = 0; i < children.size(); i++) {
Node m = (Node) children.get(i);
if (!open.contains(m) && !closed.contains(m)) {
// m から node へのポインタを付ける
m.setPointer(node);
if (m == goal) {
open.add(0, m);
} else {
open.add(j, m);
}
j++;
}
}
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 分岐限定法
*/
public void branchAndBound() {
List open = new ArrayList();
open.add(start);
start.setGValue(0);
List closed = new ArrayList();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か?
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか?
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
List children = node.getChildren();
// node を closed に入れる．
closed.add(node);
for (int i = 0; i < children.size(); i++) {
Node m = (Node) children.get(i);
// 子节点mがopenにもclosedにも含まれていなければ,
if (!open.contains(m) && !closed.contains(m)) {
// m から node へのポインタを付ける．
m.setPointer(node);
// nodeまでの评価値とnode->mのコストを
// 足したものをmの评価値とする
int gmn = node.getGValue() + node.getCost(m);
m.setGValue(gmn);
open.add(m);
}
// 子节点mがopenに含まれているならば,
if (open.contains(m)) {
int gmn = node.getGValue() + node.getCost(m);
if (gmn < m.getGValue()) {
m.setGValue(gmn);
m.setPointer(node);
}
}
}
}
}
open = sortUpperByGValue(open);
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 山登り法
*/
public void hillClimbing() {
start.setGValue(0);
boolean success = false;
// Start を node とする．
Node node = start;
for (;;) {
// node は ゴールか?
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ArrayList children = node.getChildren();
System.out.println(children.toString());
for (int i = 0; i < children.size(); i++) {
Node m = children.get(i);
// m から node へのポインタを付ける．
m.setPointer(node);
}
// 子节点の中に goal があれば goal を node とする．
// なければ,最小の hValue を持つ子节点 m を node
// とする．
boolean goalp = false;
Node min = children.get(0);
for (int i = 0; i < children.size(); i++) {
Node a = children.get(i);
if (a == goal) {
goalp = true;
} else if (min.getHValue() > a.getHValue()) {
min = a;
}
}
if (goalp) {
node = goal;
} else {
node = min;
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 最良优先探索
*/
public void bestFirst() {
List open = new ArrayList();
open.add(start);
List closed = new ArrayList();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か?
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか?
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
List children = node.getChildren();
// node を closed に入れる．
closed.add(node);
for (int i = 0; i < children.size(); i++) {
Node m = (Node) children.get(i);
// 子节点mがopenにもclosedにも含まれていなければ,
if (!open.contains(m) && !closed.contains(m)) {
// m から node へのポインタを付ける．
m.setPointer(node);
open.add(m);
}
}
}
}
open = sortUpperByHValue(open);
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* A* アルゴリズム
*/
public void aStar() {
List open = new ArrayList();
open.add(start);
start.setGValue(0);
start.setFValue(0);
List closed = new ArrayList();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か?
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか?
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
List children = node.getChildren();
// node を closed に入れる．
closed.add(node);
for (int i = 0; i < children.size(); i++) {
Node m = children.get(i);
int gmn = node.getGValue() + node.getCost(m);
int fmn = gmn + m.getHValue();
// 各子节点mの评価値とポインタを设定する
if (!open.contains(m) && !closed.contains(m)) {
// 子节点mがopenにもclosedにも含まれていない场合
// m から node へのポインタを付ける．
m.setGValue(gmn);
m.setFValue(fmn);
m.setPointer(node);
// mをopenに追加
open.add(m);
} else if (open.contains(m)) {
// 子节点mがopenに含まれている场合
if (gmn < m.getGValue()) {
// 评価値を更新し,m から node へのポインタを付け替える
m.setGValue(gmn);
m.setFValue(fmn);
m.setPointer(node);
}
} else if (closed.contains(m)) {
if (gmn < m.getGValue()) {
// 子节点mがclosedに含まれていて fmn < fm となる场合
// 评価値を更新し,mからnodeへのポインタを付け替える
m.setGValue(gmn);
m.setFValue(fmn);
m.setPointer(node);
// 子节点mをclosedからopenに移动
closed.remove(m);
open.add(m);
}
}
}
}
}
open = sortUpperByFValue(open);
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 解の表示
*/
public void printSolution(Node theNode) {
if (theNode == start) {
System.out.println(theNode.toString());
} else {
System.out.print(theNode.toString() + "