典型的8 puzzle如下：
image
算法设计参照A搜索算法，即使不了解A搜索算法，题目也已经将解法解释的很具体了。
Best-first search：设计参照A* 搜索算法。定义一个 search node类，包含board，从初始状态到达当前board状态的移动权重moves，和previous search node。
- 插入初始的search node，其board设为初始board，moves设为0，previous search node设置为0
- 将初始化的search node置于MinPQ类型的优先级队列中
- 删除优先级队列中的min节点，再将该节点的邻居节点放入优先级队列中。
- 重复2和3操作直至从优先级队列中删除的min节点是目标board
A* 搜索算法的优先级判定依据是f(n) = g(n) + h(n)，g(n)是从初始节点到达当前节点的代价，h(n)是当前节点到目标节点的预估代价。
在本题中search node中的moves就是g(n)，而关于h(n)题目给出了两种候选：
Hamming priority function: 处于错误位置的block的个数（空白处不算block）
Manhatten priority function: 处于错误位置的block距离其各自目标位置的横向和纵向距离之和
h(n)采用这两者均可，根据题目中的图示，显然发现题目推荐采用manhatten方法。
至此优先级队列中的优先级判断依据就是当前search node的moves+manhatten value
A critical optimization: 上述Best-first search中可能会存在刚出队列的节点又被当成其邻居节点的邻居而被放回优先级队列的情况，这种情况会造成很大的性能损失。为了阻止这种情况的发生，可以在Best-first search的第3步“将该节点的邻居节点放入优先级队列”时比较下这个邻居节点的board是否与本节点的board相同。
image
例如此时{{8，1，3}，{4，0，2}，{7，6，5}}就不应该放入优先级队列中。
A second optimization: 建议在search node的构造函数中计算其manhattan值，也就是在search node的构造函数中确定其优先级。
Detecting unsolvable puzzles：如果一个board是不可解的，那么随便在该board中选择一对block互换位置，就能将其变为可解的。为此采用同时对board和其互换了一对block的twindboard进行求解，如果board先实现目标解，那么其就是可解的，相反，如果twinboard先实现目标节，那么该board就不可解。
import java.util.ArrayList;
public class Board {
private final int [][]blocks;
private static final int BLANK = 0;
private final int N;
public Board(int[][] blocks) // 创建n*n的棋盘
{
if (blocks == null)
throw new java.lang.IllegalArgumentException("the blocks is null");
N = blocks.length;
this.blocks = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
this.blocks[i][j] = blocks[i][j];
}
}
}
public int dimension() // 棋盘维度n
{
return N; // 返回列数
}
private int getIndex(int i, int j) // 二维变一维坐标
{
return i * N + j + 1;
}
private int getRow(int value) // 在目标结果中，值所对应的行数
{
return (value - 1) / N;
}
private int getCol(int value) // 在目标结果中，值所对应的列数
{
return (value -1) % N;
}
public int hamming() // hamming优先级=错的位置个数+已移动次数
{
int wrongNum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]位置上的元素放错
wrongNum++;
return wrongNum;
}
public int manhattan() // manhattan优先级=距离目标距离+已移动次数
{
int wrongNum = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]位置上的元素放错
{
int righti = getRow(blocks[i][j]); // blocks[i][j]位置上的元素正确的i坐标
int rightj = getCol(blocks[i][j]); // blocks[i][j]位置上的元素正确的j坐标
wrongNum = wrongNum + Math.abs(righti - i) + Math.abs(rightj -j);
}
}
return wrongNum;
}
public boolean isGoal() // 棋盘是否为目标位置
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]位置上的元素放错
return false;
return true;
}
private int[][] copy() // 拷贝棋盘元素
{
int [][]newblocks = new int[N][N];
for (int i1 = 0; i1 < N; i1++)
for (int j1 = 0; j1 < N; j1++)
newblocks[i1][j1] = this.blocks[i1][j1];
return newblocks;
}
private Board swap(int i1, int j1, int i2, int j2) // 交换两个棋盘元素位置
{
int [][]newblocks = copy();
int temp = newblocks[i1][j1];
newblocks[i1][j1] = newblocks[i2][j2];
newblocks[i2][j2] = temp;
return new Board(newblocks);
}
public Board twin() // 通过交换任何一对块而获得的板。
{
int i1 = 0, j1 = 0, i2 = 1, j2 = 1;
if (blocks[i1][j1] == BLANK)
{
i1 = 1;
j1 = 0;
}
if (blocks[i2][j2] == BLANK)
{
i2 = 1;
j2 = 0;
}
Board newBoard = swap(i1, j1, i2, j2);
return newBoard;
}
public boolean equals(Object y) // 判断两个棋盘是否相等
{
if (y == null)
return false;
if (y == this)
return true;
if (y.getClass().isInstance(this)) // y和this属于同一类型
{
Board boardY = (Board) y;
if (boardY.N != this.N)
return false;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (this.blocks[i][j] != boardY.blocks[i][j])
return false;
}
else // y和this不属于同一类型
{
return false;
}
return true;
}
public Iterable<Board> neighbors() // 所有的邻居棋盘
{
ArrayList<Board> boards = new ArrayList<>();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (blocks[i][j] == BLANK) // 找到空格位置
{
// 上
if (i > 0)
{
Board upBoard = swap(i, j, i-1, j);
boards.add(upBoard);
}
// 下
if (i < N-1)
{
Board lowBoard = swap(i, j, i+1, j);
boards.add(lowBoard);
}
// 左
if (j > 0)
{
Board leftBoard = swap(i, j, i, j-1);
boards.add(leftBoard);
}
// 右
if (j < N-1)
{
Board rightBoard = swap(i, j, i, j+1);
boards.add(rightBoard);
}
}
}
}
return boards;
}
public String toString() // 此板的字符串表示形式（以下面指定的输出格式）
{
StringBuilder sBuilder = new StringBuilder();
sBuilder.append(N + "\n");
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
sBuilder.append(blocks[i][j] +"\t");
}
sBuilder.append("\n");
}
String string = sBuilder.toString();
return string;
}
public static void main(String[] args) // unit tests (not graded)
{
int [][]blocks = new int[3][3];
blocks[0][0] = 8;
blocks[0][1] = 1;
blocks[0][2] = 3;
blocks[1][0] = 4;
blocks[1][1] = 0;
blocks[1][2] = 2;
blocks[2][0] = 7;
blocks[2][1] = 6;
blocks[2][2] = 5;
Board board = new Board(blocks);
System.out.println(board.manhattan());
System.out.println(board.toString());
for (Board it : board.neighbors()) {
System.out.println(it.toString());
}
System.out.println(board.twin().toString());
}
}
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Stack;
public class Solver {
private SearchNode currentNode;
private SearchNode currentTwinNode;
private Stack<Board> stackBoard;
private class SearchNode implements Comparable<SearchNode>
{
private final Board board; // 当前棋盘情况
private final int moves; // 当前棋盘移动步数
private SearchNode preSearcchNode = null; // 当前棋盘前身
private final int priority; // 当前状态优先级
public SearchNode(Board board, SearchNode pNode)
{
this.board = board;
this.preSearcchNode = pNode;
if (preSearcchNode == null)
moves = 0;
else
moves = preSearcchNode.getMoves() + 1;
priority = board.manhattan() + getMoves();
}
public int compareTo(SearchNode otherNode)
{
return Integer.compare(this.getPriority(), otherNode.getPriority());
}
public int getPriority() {
return priority;
}
public Board getBoard()
{
return board;
}
public int getMoves()
{
return moves;
}
public SearchNode getPreNode()
{
return preSearcchNode;
}
}
public Solver(Board initial) // 找到初始板的解决方案（使用A*算法）
{
if (initial == null)
throw new java.lang.IllegalArgumentException("The intial Board is null");
currentNode = new SearchNode(initial, null); // 初始
MinPQ<SearchNode> minInitialPQ = new MinPQ<>();
minInitialPQ.insert(currentNode);
currentTwinNode = new SearchNode(initial.twin(), null); // 交换两个位置后的
MinPQ<SearchNode> minTwinNode = new MinPQ<>();
minTwinNode.insert(currentTwinNode);
boolean flag = false;
while (flag != true)
{
// 对原始棋盘进行操作
currentNode = minInitialPQ.delMin(); // 取树中优先级最小的值
if (currentNode.getBoard().isGoal()) // 有解
flag = true;
else
putNeighborsBoardToPQ(currentNode, minInitialPQ); // 将邻居步骤放入树中
// 对调整顺序的棋盘进行操作
currentTwinNode = minTwinNode.delMin(); // 取树中优先级最小的树
if (currentTwinNode.getBoard().isGoal())
flag = true;
else
putNeighborsBoardToPQ(currentTwinNode, minTwinNode); // 将邻居步骤放入树中
}
}
// 将邻居情况插入到树中
private void putNeighborsBoardToPQ(SearchNode currentNode, MinPQ<SearchNode> pMinPQ)
{
Iterable<Board> boards = currentNode.getBoard().neighbors(); // 所有邻居情况
for (Board neighborsBoard : boards) {
if (currentNode.getPreNode() == null ||
neighborsBoard.equals(currentNode.getPreNode().getBoard()) != true) // 防止回退现象
pMinPQ.insert(new SearchNode(neighborsBoard, currentNode)); // 将邻居情况插入树中
}
}
public boolean isSolvable() // 初始板是可解的吗？
{
return currentNode.getBoard().isGoal();
}
public int moves() // 求解初始板的最小移动数；如果不可解，则为-1
{
if (isSolvable())
return currentNode.getMoves();
else
return -1;
}
public Iterable<Board> solution() // 最短解中的板序列；若不可解则为空
{
if (isSolvable() != true)
return null;
stackBoard = new Stack<>();
SearchNode nowNode = currentNode;
while (nowNode != null) {
stackBoard.push(nowNode.getBoard());
nowNode = nowNode.getPreNode();
}
return stackBoard;
}
public static void main(String[] args) // solve a slider puzzle (given below)
{
int [][]blocks = new int[3][3];
blocks[0][0] = 8;
blocks[0][1] = 1;
blocks[0][2] = 3;
blocks[1][0] = 4;
blocks[1][1] = 0;
blocks[1][2] = 2;
blocks[2][0] = 7;
blocks[2][1] = 6;
blocks[2][2] = 5;
Board board = new Board(blocks);
Solver solver = new Solver(board);
System.out.println(solver.currentNode.getPreNode() == null);
System.out.println(solver.currentNode.getPreNode());
if (solver.isSolvable() != false) {
System.out.println("this board is can't resolve");
}
Iterable<Board> bIterable = solver.solution();
System.out.println(bIterable.toString());
System.out.println("444");
for (Board it : bIterable) {
System.out.println(it.toString());
}
}
}
网友评论