总体来说就是构造节点和非递归搜索...
为了让代码有通用性，数码的大小可以用变量代替。
public class Node {
int size; //节点规模，n数码问题对应的size为sqrt(n+1)
int[][] board; //棋盘
int spaceX, spaceY; //空格位置
int costF, costG, costH; //f = g + h
Node parent; //父节点
LinkedList<Node> children; //子节点列表
public Node(int[][] board) {
this.size = board.length;
this.board = board;
boolean flag = false;
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
if (board[i][j] == 0) {
spaceX = i;
spaceY = j;
flag = true;
break;
}
}
if (flag) break;
}
parent = null;
children = new LinkedList<>();
}
public Node(int[][] board, int costG, int costH, int spaceX, int spaceY) {
this.size = board.length;
this.board = board;
this.costG = costG;
this.costH = costH;
this.costF = costG + costH;
this.spaceX = spaceX;
this.spaceY = spaceY;
children = new LinkedList<>();
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return size == node.size &&
Arrays.deepEquals(board, node.board);
/*注意不能是equals!*/
}
@Override
public int hashCode() {
return Arrays.deepHashCode(board);
/*同理！！！*/
}
public int getCostF() {
return costF;
}
}
然后就是Astar算法了，相信你们都会....
贴的是解决15数码的问题，8数码的简单改改就行
这里有两种估价函数还有个BFS。
public class Astar {
final int SIZE = 4; // 15数码
int step = 0; //求解步骤
int expandCount = 0; //扩展节点数
int genCount = 0; //生成节点数
//int maxDepth = 100; //深度优先搜索最大层数
final Node goal = new Node(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}});
final int[][] goalDistance = new int[][]{
{3,3}, //0
{0,0}, //1
{0,1},
{0,2},
{0,3},
{1,0}, //5
{1,2},
{1,3},
{1,4},
{2,0}, //9
{2,1},
{2,2},
{2,3},
{3,0}, //13
{3,1},
{3,2}
};//目标位置，用于h2
PriorityQueue<Node> open_table = new PriorityQueue<>(Comparator.comparing(Node::getCostF));
HashSet<Node> closed_table = new HashSet<>();
public void work (Node initial) {
initial.costH = h3(initial.board);
initial.costF = initial.costH + initial.costG;
long start = System.currentTimeMillis();
Node result = search(initial);
if (result == null) {
System.out.println("No solution.");
} else {
System.out.println("Here's the solution.");
printPath(result);
}
System.out.println("Time cost: " + (System.currentTimeMillis() - start) + " milliseconds.");
System.out.println(expandCount + " nodes have been expanded.");
System.out.println(genCount + " nodes have been generated.");
}
/**
* @return x和目标状态不对位的位数
*/
private int h1 (int[][] board) {
int count = 0;
for (int i = 0; i < SIZE; ++i)
for (int j = 0; j < SIZE; ++j)
if (board[i][j] != goal.board[i][j])
++count;
return count;
}
//节点n的每一数码与其目标位置的距离总和
private int h2 (int[][] board) {
int count = 0;
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
int N = board[i][j];
count += (Math.abs(goalDistance[N][0] - i) + Math.abs(goalDistance[N][1] - j));
}
}
return count;
}
//BFS
private int h3 (int[][] board) {
return 0;
}
/*搜索*/
private Node search (Node x) {
open_table.add(x);
while (!open_table.isEmpty()) {
Node p = open_table.peek();
if (p.equals(goal)) { //如果是目标节点,搜索结束
return p;
}
closed_table.add(open_table.poll()); // 取出节点,放到close表里
/*开始扩展p的后续节点*/
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
/*在空格的四个方向扩展*/
if ( (dx * dy) != 0 || (dx == 0 && dy == 0)) {
continue; //保证扩展方向正确
} else {
Node expandedNode = expand(p, dx, dy);
if (expandedNode == null) continue;
if (isParent(p, expandedNode)) {
++expandCount;
continue;
}
// 扩展失败或者扩展出p的父节点则不处理
++expandCount;
++genCount;
expandedNode.parent = p;
p.children.add(expandedNode);
Node retrieve = containsAndGet(open_table, expandedNode);
if (retrieve != null) {
//如果已经包含扩展出的节点
if (expandedNode.costF < retrieve.costF) {
open_table.remove(retrieve);
open_table.add(expandedNode);
}
} else if ((retrieve = containsAndGet(closed_table, expandedNode)) != null) {
closed_table.remove(retrieve);
open_table.add(expandedNode);
} else {
//如果扩展出的节点在两个表中都不在
open_table.add(expandedNode);
}
}
}
}
}
return null;
}
/*返回移动p节点的空格而生成新的单个节点*/
private Node expand (Node p, int dx, int dy) {
int spaceXofChild = p.spaceX + dx, spaceYofChild = p.spaceY + dy;
/*空格移动范围不能越界*/
if ((spaceXofChild < 0 || spaceXofChild >= SIZE) || (spaceYofChild < 0 || spaceYofChild >= SIZE))
return null;
int[][] childBoard = new int[ SIZE ][ SIZE ];
/*复制数组*/
for (int i = 0; i < SIZE; ++i) {
System.arraycopy(p.board[ i ], 0, childBoard[ i ], 0, SIZE);
}
/*复制结束之后交换空格位置*/
childBoard[ p.spaceX ][ p.spaceY ] = p.board[ spaceXofChild ][ spaceYofChild ];
childBoard[ spaceXofChild ][ spaceYofChild ] = 0;
return new Node(childBoard, p.costG + 1, h3(childBoard), spaceXofChild, spaceYofChild);
}
/*返回在堆里具有相同棋盘的结点*/
private Node containsAndGet(Collection<Node> table, Node successor) {
Iterator<Node> iterator = table.iterator();
while (iterator.hasNext()) {
Node q = iterator.next();
if (q.equals(successor))
return q;
}
return null;
}
//判断parent是否是p的祖先节点
private boolean isParent (Node p, Node parent) {
p = p.parent;
while (p != null) {
if (p.equals(parent))
return true;
p = p.parent;
}
return false;
}
private void printPath (Node p) {
if (p == null) return;
printPath(p.parent);
printNode(p);
}
private void printNode (Node p) {
System.out.println("Step " + (++step));
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
System.out.print(p.board[i][j] + " ");
}
System.out.println();
}
System.out.print("White space's coordinates: x:" + p.spaceX + ", y:" + p.spaceY + "\n");
System.out.print("Cost: f is " + p.costF + ", and h is " + p.costH + ".\n");
System.out.println("****************************");
}
}
使用姿势如下
public class Test {
public static void main (String[] args) {
int[][] initial = {{5,1,2,4},{9,6,3,8},{13,15,10,11},{14,0,7,12}};
Node node = new Node(initial);
node.costG = 1;
new Astar().work(node);
}
}
网友评论