8 puzzle 算法
算法根据Coursera上的算法课程实现
8 puzzle问题在18世纪70年代由Noyes Palmer提出，并逐渐流行起来。它由8个方块和一共空格组成3X3的格子。8个方块随机放置1-8个数字，目标是移动方块使得8个方块按顺序排放。具体如下：
1 3 1 3 1 2 3 1 2 3 1 2 3
4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6
7 8 6 7 8 6 7 8 6 7 8 6 7 8
initial 1 left 2 up 5 left goal
算法实现
下面具体介绍了Java实现8 puzzle的过程。算法也可以用在4X4的解决中，但是如果问题需要40步以上才能解决时，会有内存溢出的情况，这需要算法进一步优化。
解决问题使用了A*搜索算法，首先定义了一个Board对象，用来描述NxN的一个数据结构。将初始节点放priority queue中，然后得到优先级最高的节点，并计算其相邻的节点，放入priority queue中，持续最高过程，直到节点与目标节点相同为止。
首先定义一个优先级函数：
- Hamming priority function：NxN格子中与预期位置不同的方块的数量。一般来说，具有错误数量方块越少的节点越接近预期的节点。
- Manhattan priority function：所有方块当前与预期位置距离的和。
举例：
8 1 3 1 2 3 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
4 2 4 5 6 ---------------------- ----------------------
7 6 5 7 8 1 1 0 0 1 1 0 1 1 2 0 0 2 2 0 3
initial goal Hamming = 5 + 0 Manhattan = 10 + 0
算法实现：
public Board(int[][] blocks) {
this.blocks = blocks;
}
public int hamming() {
if (hamming >= 0) {
return hamming;
}
hamming = 0;
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks.length; j++) {
if (blocks[i][j] != 0)
hamming += i * blocks.length + j + 1 == blocks[i][j] ? 0 : 1;
}
}
return hamming;
}
public int manhattan() {
if (manhattan >= 0)
return manhattan;
manhattan = 0;
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks.length; j++) {
if (blocks[i][j] != 0 && i * blocks.length + j + 1 != blocks[i][j]) {
int ii = (blocks[i][j] - 1) / blocks.length;
int jj = blocks[i][j] - ii * blocks.length - 1;
manhattan += Math.abs(ii - i) + Math.abs(jj - j);
}
}
}
return manhattan;
}
// all neighboring boards
public Iterable<Board> neighbors() {
if (neighbors != null) {
return neighbors;
}
List<Board> boards = new ArrayList<>();
int[][] newBolcks;
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks.length; j++) {
if (blocks[i][j] == 0) {
if (i > 0) {
newBolcks = exchange(i, j, i - 1, j);
boards.add(new Board(newBolcks));
}
if (i < blocks.length - 1) {
newBolcks = exchange(i, j, i + 1, j);
boards.add(new Board(newBolcks));
}
if (j > 0) {
newBolcks = exchange(i, j, i, j - 1);
boards.add(new Board(newBolcks));
}
if (j < blocks.length - 1) {
newBolcks = exchange(i, j, i, j + 1);
boards.add(new Board(newBolcks));
}
break;
}
}
}
neighbors = boards;
return neighbors;
}
private int[][] exchange(int i1, int j1, int i2, int j2) {
int[][] newBlocks = new int[blocks.length][blocks.length];
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks.length; j++) {
newBlocks[i][j] = blocks[i][j];
}
}
int temp = newBlocks[i1][j1];
newBlocks[i1][j1] = newBlocks[i2][j2];
newBlocks[i2][j2] = temp;
return newBlocks;
}在priority queue中可以使用 hamming 或者 manhattan 函数。
关键的优化：
在搜索树中寻找相邻节点（neighbors()函数得到的节点）的时候需要抛弃当前节点的父节点，否则让同一个节点不断地重复计算。
8 1 3 8 1 3 8 1 8 1 3 8 1 3
4 2 4 2 4 2 3 4 2 4 2 5
7 6 5 7 6 5 7 6 5 7 6 5 7 6
previous search node neighbor neighbor neighbor
(disallow)
游戏树
将计算过程看作一共游戏决策树，每一个搜索节点都所谓树上的一个节点，树的孩子对应该节点的相邻搜索节点。内部的节点都已经北处理过，叶子节点则会被放入优先队列中，每一步都会从队列中拿出优先级最高的节点，并将它相邻节点放入游戏树和优先队列中。
定义游戏树节点：
class GameTreeNode implements Comparable<GameTreeNode> {
private Board board;
private GameTreeNode father;
private int moves;
private int priority;
private GameTreeNode(Board b, GameTreeNode father) {
this.board = b;
this.father = father;
if (father != null) {
this.moves = father.moves + 1;
this.priority = this.board.manhattan() + this.moves;
}
}
public GameTreeNode getFather() {
return father;
}
public int getMoves() {
return moves;
}
public void setMoves(int moves) {
this.moves = moves;
this.priority = this.board.manhattan() + this.moves;
}
public int getPriority() {
return priority;
}
@Override
public int compareTo(GameTreeNode o) {
if (this.priority == o.priority) {
return this.board.manhattan() - o.board.manhattan();
}
return this.priority - o.priority;
}
}求解过程：
public Solver(Board initial) {
if (initial == null)
throw new NullPointerException();
int move = 0;
GameTreeNode root = new GameTreeNode(initial, null);
MinPQ<GameTreeNode> mp = new MinPQ<>();
mp.insert(root);
GameTreeNode currNode = mp.delMin();
while (!currNode.board.isGoal()) {
for (Board b : currNode.board.neighbors()) {
// don't enqueue a neighbor if its board is the same as the
// board of the previous search node
if (currNode.getFather() == null || !b.equals(currNode.getFather().board)) {
GameTreeNode node = new GameTreeNode(b, currNode);
mp.insert(node);
}
}
}
}无解的情况
并不是所有的情况都是可以解决的：
1 2 3 1 2 3 4
4 5 6 5 6 7 8
8 7 9 10 11 12
13 15 14
unsolvable unsolvable
对于不可解的Board，交换其中任意两个方块便可以得到有解的Board（不包括空格）。具体证明不懂。因此在世纪算法中需要同时解两个Board，一个是需要求解的，另一个是交换任意两个方块的Board，如果其中一个得到了求解的最终结果，那么另一个则是无解的。
结果
下面列出了4X4的求解过程：
3 2 4 1
5 6 8 7
9 11 10 12
13 14 15 0
3 2 4 1
5 6 8 7
9 11 10 0
13 14 15 12
3 2 4 1
5 6 8 7
9 11 0 10
13 14 15 12
3 2 4 1
5 6 0 7
9 11 8 10
13 14 15 12
3 2 4 1
5 6 7 0
9 11 8 10
13 14 15 12
3 2 4 0
5 6 7 1
9 11 8 10
13 14 15 12
3 2 0 4
5 6 7 1
9 11 8 10
13 14 15 12
3 2 7 4
5 6 0 1
9 11 8 10
13 14 15 12
3 2 7 4
5 6 1 0
9 11 8 10
13 14 15 12
3 2 7 4
5 6 1 10
9 11 8 0
13 14 15 12
3 2 7 4
5 6 1 10
9 11 0 8
13 14 15 12
3 2 7 4
5 6 1 10
9 0 11 8
13 14 15 12
3 2 7 4
5 0 1 10
9 6 11 8
13 14 15 12
3 0 7 4
5 2 1 10
9 6 11 8
13 14 15 12
0 3 7 4
5 2 1 10
9 6 11 8
13 14 15 12
5 3 7 4
0 2 1 10
9 6 11 8
13 14 15 12
5 3 7 4
2 0 1 10
9 6 11 8
13 14 15 12
5 3 7 4
2 1 0 10
9 6 11 8
13 14 15 12
5 3 7 4
2 1 10 0
9 6 11 8
13 14 15 12
5 3 7 4
2 1 10 8
9 6 11 0
13 14 15 12
5 3 7 4
2 1 10 8
9 6 0 11
13 14 15 12
5 3 7 4
2 1 0 8
9 6 10 11
13 14 15 12
5 3 0 4
2 1 7 8
9 6 10 11
13 14 15 12
5 0 3 4
2 1 7 8
9 6 10 11
13 14 15 12
5 1 3 4
2 0 7 8
9 6 10 11
13 14 15 12
5 1 3 4
0 2 7 8
9 6 10 11
13 14 15 12
0 1 3 4
5 2 7 8
9 6 10 11
13 14 15 12
1 0 3 4
5 2 7 8
9 6 10 11
13 14 15 12
1 2 3 4
5 0 7 8
9 6 10 11
13 14 15 12
1 2 3 4
5 6 7 8
9 0 10 11
13 14 15 12
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
转载自原文链接, 如需删除请联系管理员。
原文链接：8 Puzzle 算法原理和源码，转载请注明来源！