首页 > 代码库 > Programming Assignment 4: 8 Puzzle
Programming Assignment 4: 8 Puzzle
The Problem. 求解8数码问题。用最少的移动次数能使8数码还原.
Best-first search.使用A*算法来解决，我们定义一个Seach Node，它是当前搜索局面的一种状态，记录了从初始到达当前状态的移动次数和上一个状态。初始化时候，当前状态移动次数为0，上一个状态为null，将其放入优先级队列，通过不断的从优先级队列中取出Seach Node去扩展下一级的状态，直到找到目标状态。对于优先级队列中优先级的定义我们可以采用：Hamming priority function 和 Manhattan priority function，第一个表示有多少个块不在目标位置，第二个表示每一个块到他所在目标位置曼哈顿距离之和。
对于解决8数码来说，为了寻求最少步数，那么当前状态移动步数优先级需要考虑，同时选择Hamming或者Manhattan进行启发式的搜索。当目标状态出现时，我们就是使用了最少的步数。怎么证明？
A critical optimization.在搜索的过程中会遇到重复出现的状态，所以我们在进行下一个状态搜索的时候，判断不要将它相邻已经出现的状态加入到优先级队列中。
Game Tree. 搜索是一个博弈树的形式展开，每一个节点对应一个状态，树根是初始状态，在每一步中，A*算法删除优先级对联中priority最小的那个节点，然后进行处理
Detecting infeasible puzzles. 有些初始状态是无法通过移动来得到目标状态的，比如：
但是我们通过交换任意行不为空白的相邻的两个，如果按照这个初始状态来进行搜索，我们就可以得到目标状态。对于可行性的判断，可以根据初始状态和目标状态逆序数的奇偶性来进行判断，在进行移动后，应该奇偶性保持一致。但在这次Assignment中，不要求这么做，而是通过加入两个初始节点，一个是原有的，一个是进行相邻交换一次的，同时进行A*的搜索，如果原有的找到了目标解，那么就是可行，否则另一个找到了可行解，原有的就是不可行状态。
同一个初始状态到目标状态的最小移动次数是存在多解。其他还有IDA*,双向BFS等解法。
一些优化的地方，使用char[][] 比int[][]的空间更小。在进行曼哈顿距离求解的时候，我们可以用空间换时间，预存每个数字的曼哈顿距离，然后直接返回。
8数码是一个NP-Hard问题，没有有效的解存在。
完整的代码如下：
Board.java
public class Board { private int[][] matrix; // blocks private int N; // deimension private int posX, posY; // 0‘ position // construct a board from an N-by-N array of blocks // (where blocks[i][j] = block in row i, column j) public Board(int[][] blocks) { N = blocks.length; matrix = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = blocks[i][j]; if (matrix[i][j] == 0) { posX = i; posY = j; } } } } // board dimension N public int dimension() { return N; } // number of blocks out of place public int hamming() { int hammingDis = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (matrix[i][j] == 0) continue; if (i*N+j+1 != matrix[i][j]) hammingDis++; } } return hammingDis; } // sum of Manhattan distances between blocks and goal public int manhattan() { int manhattanDis = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (matrix[i][j] == 0) continue; int x, y; if (matrix[i][j] % N == 0) { x = matrix[i][j] / N - 1; y = N - 1; } else { x = matrix[i][j] / N; y = matrix[i][j] % N - 1; } manhattanDis += Math.abs(i-x) + Math.abs(j-y); } } return manhattanDis; } // is this board the goal board? public boolean isGoal() { if (posX != N-1 || posY != N-1) return false; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (matrix[i][j] == 0) continue; if (i*N+j+1 != matrix[i][j]) return false; } } return true; } // a board obtained by exchanging two adjacent blocks in the same row public Board twin() { int x = -1, y = -1; int[][] tmpBlock = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (j < N-1 && matrix[i][j] != 0 && matrix[i][j+1] != 0) { x = i; y = j; } tmpBlock[i][j] = matrix[i][j]; } } if (x == -1 && y == -1) throw new IllegalArgumentException(); int t = tmpBlock[x][y]; tmpBlock[x][y] = tmpBlock[x][y+1]; tmpBlock[x][y+1] = t; return new Board(tmpBlock); } // does this board equal y? public boolean equals(Object y) { if (y == this) return true; if (y == null) return false; if (y.getClass() != this.getClass()) return false; Board that = (Board) y; if (this.dimension() != that.dimension()) return false; int sz = this.dimension(); for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { if (this.matrix[i][j] != that.matrix[i][j]) return false; } } return true; } // all neighboring boards public Iterable<Board> neighbors() { Queue<Board> queue = new Queue<Board>(); int[] dx = {0, 0, -1, 1}; int[] dy = {1, -1, 0, 0}; for (int i = 0; i < 4; i++) { int x = posX + dx[i]; int y = posY + dy[i]; if (x < N && x >= 0 && y < N && y >= 0) { int tmp = matrix[posX][posY]; matrix[posX][posY] = matrix[x][y]; matrix[x][y] = tmp; queue.enqueue(new Board(matrix)); tmp = matrix[posX][posY]; matrix[posX][posY] = matrix[x][y]; matrix[x][y] = tmp; } } return queue; } // string representation of the board (in the output format specified below) public String toString() { StringBuilder s = new StringBuilder(); s.append(N + "\n"); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { s.append(String.format("%2d ", matrix[i][j])); } s.append("\n"); } return s.toString(); } public static void main(String[] args) { int[][] mat = { {1, 2, 3}, {4, 6, 0}, {7, 8, 5} }; //hamming //manhattan Board b = new Board(mat); Board c = b.twin().twin(); StdOut.println(b.equals(c)); StdOut.print(b.toString()); for (Board it : b.neighbors()) { StdOut.print(it.toString()); StdOut.println("hamming: " + it.hamming()); StdOut.println("manhattan: " + it.manhattan()); } } }
Solver.java
public class Solver { private BoardNode targetBoardNode; // record targetBoardNode private class BoardNode implements Comparable<BoardNode> { private Board item; private BoardNode prev; private int move; private boolean isTwin; // compare by priority public int compareTo(BoardNode that) { if (that == null) throw new NullPointerException("Input argument is null"); int thisPriority = this.move + this.item.manhattan(); int thatPriority = that.move + that.item.manhattan(); if (thisPriority < thatPriority) return -1; else if (thisPriority == thatPriority) return 0; else return 1; } } // find a solution to the initial board (using the A* algorithm) public Solver(Board initial) { targetBoardNode = null; // priority queue maintain the minimum elements MinPQ<BoardNode> minpq = new MinPQ<BoardNode>(); // initial boardnode BoardNode bn = new BoardNode(); bn.item = initial; bn.prev = null; bn.move = 0; bn.isTwin = false; minpq.insert(bn); // initial twin boardnode BoardNode twinbn = new BoardNode(); twinbn.item = initial.twin(); twinbn.prev = null; twinbn.move = 0; twinbn.isTwin = true; minpq.insert(twinbn); while (!minpq.isEmpty()) { BoardNode curbn = minpq.delMin(); if (curbn.item.isGoal()) { if (curbn.isTwin) targetBoardNode = null; else targetBoardNode = curbn; break; } for (Board it : curbn.item.neighbors()) { if (curbn.prev == null || !curbn.prev.item.equals(it)) { bn = new BoardNode(); bn.item = it; bn.prev = curbn; bn.move = curbn.move+1; if (curbn.isTwin) bn.isTwin = true; else bn.isTwin = false; minpq.insert(bn); } } } } // is the initial board solvable? public boolean isSolvable() { return targetBoardNode != null; } // min number of moves to solve initial board; -1 if no solution public int moves() { if (isSolvable()) return targetBoardNode.move; else return -1; } // sequence of boards in a shortest solution; null if no solution public Iterable<Board> solution() { Stack<Board> stack = new Stack<Board>(); BoardNode tmpbn = targetBoardNode; while (tmpbn != null) { stack.push(tmpbn.item); tmpbn = tmpbn.prev; } if (stack.isEmpty()) return null; else return stack; } // solve a slider puzzle (given below) public static void main(String[] args) { // create initial board from file In in = new In(args[0]); int N = in.readInt(); int[][] blocks = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) blocks[i][j] = in.readInt(); Board initial = new Board(blocks); // solve the puzzle Solver solver = new Solver(initial); // print solution to standard output if (!solver.isSolvable()) StdOut.println("No solution possible"); else { StdOut.println("Minimum number of moves = " + solver.moves()); for (Board board : solver.solution()) StdOut.println(board); } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。