http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html
Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
The problem. The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board (left) to the goal board (right).
A critical optimization. Best-first search has one annoying feature: search nodes corresponding to the same board are enqueued on the priority queue many times. To reduce unnecessary exploration of useless search nodes, when considering the neighbors of a search node, don't enqueue a neighbor if its board is the same as the board of the previous search node.
Detecting unsolvable puzzles. Not all initial boards can lead to the goal board by a sequence of legal moves, including the two below:
Board and Solver data types. Organize your program by creating an immutable data type Board with the following API:
Performance requirements. Your implementation should support all Board methods in time proportional to N2 (or better) in the worst case.
Also, create an immutable data type Solver with the following API:
Corner cases. The constructor should throw a java.lang.NullPointerException if passed a null argument.
Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
The problem. The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board (left) to the goal board (right).
Best-first search. Now, we describe a solution to the problem that illustrates a general artificial intelligence methodology known as the A* search algorithm. We define a search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the minimum priority, and insert onto the priority queue all neighboring search nodes (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeued corresponds to a goal board. The success of this approach hinges on the choice of priority function for a search node. We consider two priority functions: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
- Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intuitively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node that have been reached using a small number of moves.
- Manhattan priority function. The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the search node.
We make a key observation: To solve the puzzle from a given search node on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank square when computing the Hamming or Manhattan priorities.) Consequently, when the goal board is dequeued, we have discovered not only a sequence of moves from the initial board to the goal board, but one that makes the fewest number of moves. (Challenge for the mathematically inclined: prove this fact.)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
A critical optimization. Best-first search has one annoying feature: search nodes corresponding to the same board are enqueued on the priority queue many times. To reduce unnecessary exploration of useless search nodes, when considering the neighbors of a search node, don't enqueue a neighbor if its board is the same as the board of the previous search node.
Game tree. One way to view the computation is as a game tree, where each search node is a node in the game tree and the children of a node correspond to its neighboring search nodes. The root of the game tree is the initial search node; the internal nodes have already been processed; the leaf nodes are maintained in a priority queue; at each step, the A* algorithm removes the node with the smallest priority from the priority queue and processes it (by adding its children to both the game tree and the priority queue).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)
To detect such situations, use the fact that boards are divided into two equivalence classes with respect to reachability: (i) those that lead to the goal board and (ii) those that lead to the goal board if we modify the initial board by swapping any pair of blocks (the blank square is not a block). (Difficult challenge for the mathematically inclined: prove this fact.) To apply the fact, run the A* algorithm on two puzzle instances—one with the initial board and one with the initial board modified by swapping a pair of blocks—in lockstep (alternating back and forth between exploring search nodes in each of the two game trees). Exactly one of the two will lead to the goal board.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 and Solver data types. Organize your program by creating an immutable data type Board with the following API:
public class Board {
public Board(int[][] blocks) // construct a board from an N-by-N array of blocks
// (where blocks[i][j] = block in row i, column j)
public int dimension() // board dimension N
public int hamming() // number of blocks out of place
public int manhattan() // sum of Manhattan distances between blocks and goal
public boolean isGoal() // is this board the goal board?
public Board twin() // a board that is obtained by exchanging any pair of blocks
public boolean equals(Object y) // does this board equal y?
public Iterable<Board> neighbors() // all neighboring boards
public String toString() // string representation of this board (in the output format specified below)
public static void main(String[] args) // unit tests (not graded)
}
Corner cases. You may assume that the constructor receives an N-by-N array containing the N2 integers between 0 and N2 − 1, where 0 represents the blank square.Performance requirements. Your implementation should support all Board methods in time proportional to N2 (or better) in the worst case.
Also, create an immutable data type Solver with the following API:
public class Solver {
public Solver(Board initial) // find a solution to the initial board (using the A* algorithm)
public boolean isSolvable() // is the initial board solvable?
public int moves() // min number of moves to solve initial board; -1 if unsolvable
public Iterable<Board> solution() // sequence of boards in a shortest solution; null if unsolvable
public static void main(String[] args) // solve a slider puzzle (given below)
}
To implement the A* algorithm, you must use MinPQ from algs4.jar for the priority queue(s).Corner cases. The constructor should throw a java.lang.NullPointerException if passed a null argument.
I'm a bit confused about the purpose of the twin() method. You will use it to determine whether a puzzle is solvable: exactly one of a board and its twin are solvable. A twin is obtained by swapping any pair of blocks (the blank square is not a block). For example, here is a board and several possible twins. Your solver will use only one twin.
Can I terminate the search as soon as a goal search node is enqueued (instead of dequeued)? No, even though it does lead to a correct solution for the slider puzzle problem using the Hamming and Manhattan priority functions, it's not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).
I noticed that the priorities of the search nodes dequeued from the priority queue never decrease. Is this a property of the A* algorithm? Yes. In the language of the A* algorithm, the Hamming and Manhattan distances (before adding in the number of moves so far) are known as heuristics. If a heuristic is both admissible (never overestimates the number of moves to the goal search node) and consistent (satisfies a certain triangle inequality), then this noticed property is guaranteed. The Hamming and Manhattan heuristics are both admissible and consistent. You may use this noticed property as a debugging clue: if the priority of the search node dequeued from the priority queue decreases, then you know you did something wrong.
Even with the critical optimization, the priority queue may contain two or more search nodes corresponding to the same board. Should I try to eliminate these? In principle, you could do so with a set data type such as SET in algs4.jar or java.util.TreeSet or java.util.HashSet (provided that the Board data type were either Comparable or had a hashCode() method). However, almost all of the benefit from avoiding duplicate boards is already extracted from the critical optimization and the cost of identifying other duplicate boards will be more than the remaining benefit from doing so.
Can I put the logic for detecting whether a puzzle is infeasible in Board instead of Solver? There is a elegant algorithm for determining whether a board is solvable that relies on a parity argument (and occasionally we change our API to require this solution). However, the current API requires you to detect infeasiblity in Solver by using two synchronized A* searches (e.g., using two priority queues).
How do I reconstruct the solution once I've dequeued the goal search node? Since each search node records the previous search node to get there, you can chase the pointers all the way back to the initial search node (and consider them in reverse order).1 3 3 1 1 3 1 3 1 3 6 3 4 2 5 4 2 5 2 4 5 4 5 2 4 2 5 4 2 5 7 8 6 7 8 6 7 8 6 7 8 6 8 7 6 7 8 1 board twin twin twin twin twin
Can I terminate the search as soon as a goal search node is enqueued (instead of dequeued)? No, even though it does lead to a correct solution for the slider puzzle problem using the Hamming and Manhattan priority functions, it's not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).
I noticed that the priorities of the search nodes dequeued from the priority queue never decrease. Is this a property of the A* algorithm? Yes. In the language of the A* algorithm, the Hamming and Manhattan distances (before adding in the number of moves so far) are known as heuristics. If a heuristic is both admissible (never overestimates the number of moves to the goal search node) and consistent (satisfies a certain triangle inequality), then this noticed property is guaranteed. The Hamming and Manhattan heuristics are both admissible and consistent. You may use this noticed property as a debugging clue: if the priority of the search node dequeued from the priority queue decreases, then you know you did something wrong.
Even with the critical optimization, the priority queue may contain two or more search nodes corresponding to the same board. Should I try to eliminate these? In principle, you could do so with a set data type such as SET in algs4.jar or java.util.TreeSet or java.util.HashSet (provided that the Board data type were either Comparable or had a hashCode() method). However, almost all of the benefit from avoiding duplicate boards is already extracted from the critical optimization and the cost of identifying other duplicate boards will be more than the remaining benefit from doing so.
Can I put the logic for detecting whether a puzzle is infeasible in Board instead of Solver? There is a elegant algorithm for determining whether a board is solvable that relies on a parity argument (and occasionally we change our API to require this solution). However, the current API requires you to detect infeasiblity in Solver by using two synchronized A* searches (e.g., using two priority queues).
随着学习的深入，这次作业的复杂度有了一个明显的上升，但这门课最美妙的地方之一也就在这里：面临的问题越来越复杂，而导师给出的指导思路依然保持最大程度的简洁优雅，每一步骤的设定都直指问题核心，并在实现功能基础上提供非常丰富的优化选择，以及每个优化会带来的影响分析
整个问题相对比较复杂，但经过给定API的划分和给定的限制后，问题变成了实现一个个目标明确的小方法而已，其中最复杂的不过是A*的实现，而周到合理的封装和PQ的使用也使得这个过程无比自然，在此之前我从未意识到我可以将A*在如此短小清晰的代码中实现：（源码如此，仅省略了声明过程）
while (!pq.min().board.isGoal()) {
cur = pq.delMin();
for (Board nb : cur.board.neighbors()) {
if (cur.prev != null && nb.equals(cur.prev.board)) continue;
pq.insert(new Node(nb, cur.moves+1, cur));
}
}
PQ使用了Manhattan Priority作为Comparator，Node为封装Board的单链表节点，结束后获取最短路径只需取PQ中最小Node，利用prev指针遍历。
解决8 Puzzle这一NP难问题的核心代码便完成了。
当然，在其余部分还是有不少值得提到的点：
解决8 Puzzle这一NP难问题的核心代码便完成了。
当然，在其余部分还是有不少值得提到的点：
- 用char[]存储一个Board的状态比用int[][]好太多，但使用前需要详细测试将char做数字使用与直接用int的区别；
- Board的equals()方法只需比较char[]构成的String即可，早期因图省事直接比较了toString()的返回值（one-liner），造成了很大的性能损失，最后寻找问题来源也费了不少功夫（教训：看似再简单的部分也要在脑袋里多转一转再下手，devil in the details，…，you name it）；
- Solvability: 这篇文章描述的解决方案应为checklist所述方案，但需要脆弱地依赖
toString()反推Board内容，在本期课程的API设定中已被明确禁止，要求使用两个同步A*的方案解决（最好使用一个PQ），但未来session可能会在两方案对应API设定间切换，所以我都实现了一遍，上面出现的A*代码来自文章所述方案； - 实现Priority的cache时需要稍多做思考，直觉想到的第一方案是储存在Node中与A*过程配合，而这将使A*代码迅速肿胀，且没有很好地利用更多规律：如checklist所指出，对相邻Board每次重新计算Priority其实也有很多重复工作，我的做法是将cache过程作为Board类一个私有构造函数，构造相邻Priority只需做对应增量操作即可，以最简洁的手段达到了目的。
public class Board {
private static final int SPACE = 0;
private int[][] blocks;
public Board(int[][] blocks) {
this.blocks = copy(blocks);
}
private int[][] copy(int[][] blocks) {
int[][] copy = new int[blocks.length][blocks.length];
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
copy[row][col] = blocks[row][col];
return copy;
}
public int dimension() {
return blocks.length;
}
public int hamming() {
int count = 0;
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (blockIsNotInPlace(row, col)) count++;
return count;
}
private boolean blockIsNotInPlace(int row, int col) {
int block = block(row, col);
return !isSpace(block) && block != goalFor(row, col);
}
private int goalFor(int row, int col) {
return row*dimension() + col + 1;
}
private boolean isSpace(int block) {
return block == SPACE;
}
public int manhattan() {
int sum = 0;
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
sum += calculateDistances(row, col);
return sum;
}
private int calculateDistances(int row, int col) {
int block = block(row, col);
return (isSpace(block)) ? 0 : Math.abs(row - row(block)) + Math.abs(col - col(block));
}
private int block(int row, int col) {
return blocks[row][col];
}
private int row (int block) {
return (block - 1) / dimension();
}
private int col (int block) {
return (block - 1) % dimension();
}
public boolean isGoal() {
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (blockIsInPlace(row, col)) return false;
return true;
}
private boolean blockIsInPlace(int row, int col) {
int block = block(row, col);
return !isSpace(block) && block != goalFor(row, col);
}
public Board twin() {
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length - 1; col++)
if (!isSpace(block(row, col)) && !isSpace(block(row, col + 1)))
return new Board(swap(row, col, row, col + 1));
throw new RuntimeException();
}
private int[][] swap(int row1, int col1, int row2, int col2) {
int[][] copy = copy(blocks);
int tmp = copy[row1][col1];
copy[row1][col1] = copy[row2][col2];
copy[row2][col2] = tmp;
return copy;
}
public boolean equals(Object y) {
if (y==this) return true;
if (y==null || !(y instanceof Board) || ((Board)y).blocks.length != blocks.length) return false;
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (((Board) y).blocks[row][col] != block(row, col)) return false;
return true;
}
public Iterable<Board> neighbors() {
LinkedList<Board> neighbors = new LinkedList<Board>();
int[] location = spaceLocation();
int spaceRow = location[0];
int spaceCol = location[1];
if (spaceRow > 0) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow - 1, spaceCol)));
if (spaceRow < dimension() - 1) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow + 1, spaceCol)));
if (spaceCol > 0) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow, spaceCol - 1)));
if (spaceCol < dimension() - 1) neighbors.add(new Board(swap(spaceRow, spaceCol, spaceRow, spaceCol + 1)));
return neighbors;
}
private int[] spaceLocation() {
for (int row = 0; row < blocks.length; row++)
for (int col = 0; col < blocks.length; col++)
if (isSpace(block(row, col))) {
int[] location = new int[2];
location[0] = row;
location[1] = col;
return location;
}
throw new RuntimeException();
}
public String toString() {
StringBuilder str = new StringBuilder();
str.append(dimension() + "\n");
for (int row = 0; row < blocks.length; row++) {
for (int col = 0; col < blocks.length; col++)
str.append(String.format("%2d ", block(row, col)));
str.append("\n");
}
return str.toString();
}
}
public class Solver {
private class Move implements Comparable<Move> {
private Move previous;
private Board board;
private int numMoves = 0;
public Move(Board board) {
this.board = board;
}
public Move(Board board, Move previous) {
this.board = board;
this.previous = previous;
this.numMoves = previous.numMoves + 1;
}
public int compareTo(Move move) {
return (this.board.manhattan() - move.board.manhattan()) + (this.numMoves - move.numMoves);
}
}
private Move lastMove;
public Solver(Board initial) {
MinPQ<Move> moves = new MinPQ<Move>();
moves.insert(new Move(initial));
MinPQ<Move> twinMoves = new MinPQ<Move>();
twinMoves.insert(new Move(initial.twin()));
while(true) {
lastMove = expand(moves);
if (lastMove != null || expand(twinMoves) != null) return;
}
}
private Move expand(MinPQ<Move> moves) {
if(moves.isEmpty()) return null;
Move bestMove = moves.delMin();
if (bestMove.board.isGoal()) return bestMove;
for (Board neighbor : bestMove.board.neighbors()) {
if (bestMove.previous == null || !neighbor.equals(bestMove.previous.board)) {
moves.insert(new Move(neighbor, bestMove));
}
}
return null;
}
public boolean isSolvable() {
return (lastMove != null);
}
public int moves() {
return isSolvable() ? lastMove.numMoves : -1;
}
public Iterable<Board> solution() {
if (!isSolvable()) return null;
Stack<Board> moves = new Stack<Board>();
while(lastMove != null) {
moves.push(lastMove.board);
lastMove = lastMove.previous;
}
return moves;
}
}
http://blog.csdn.net/liuweiran900217/article/details/19818289
Is there an efficient way to solve the 8-puzzle and its generalizations?Finding a shortest solution to an N-by-N slider puzzle isNP-hard,so it's unlikely that an efficient solution exists.
如果这是一个NP-hard问题，我们只有两种思路：一种是找出概率解，也就是说在多项式时间内做出一个解，这个解有很大的概率是正确的；另一种就是用搜索树等方法来搜索到精确解，但是搜索解本身可能是一个时间复杂度或者空间复杂度为指数复杂度的算法。
Princeton的《Algorithm》给出了一个使用A*搜索的方式来进行解决。其思路和Coursera中另一个公开课《Generic Game Playing》的搜索树算法很像，大致思路是：对于每一个中间解，计算一个这个解是“正确的”大概期望，按照每一个中间解的期望对搜索树进行排序，优先搜索期望大的解。在本题中，所谓的“期望”就是Hamming priority和Manhattan priority。对搜索树排序的方法就是Week4中的优先队列。
上述算法一定能够搜索到正确的解，因为搜索树最极限的情况也就是把所有的可能移动方法都搜索一遍嘛，所以在最糟糕情况下，算法的时间复杂度和空间复杂度都将会是指数级的。
但是，能否搜索到解还有一个情况，就是能否判断8 Puzzle的这个实例是否确实存在解。但是，是否存在解这个确定问题也是一个NP-hard问题，至今没有一个多项式时间算法能在多项式空间复杂度内回答一个8 Puzzle实例是否存在解。针对此问题，《Algorithm》给出了一种判断方法。8 Puzzle问题可分为两类：给定实例存在解，或给定实例的“Twin”实例存在解。因此，整个算法要求构造一个给定实例的Twin实例，然后同时在两个实例中运行搜索算法：如果给定实例找到了解，那么就输出解；如果Twin实例找到了解，那么说明给定实例不存在解，输出null。
http://www.1point3acres.com/bbs/thread-84775-1-1.html