Visits: 657

Princeton Algorithm 8 Puzzle

普林斯顿大学算法课第 4 次作业，8 Puzzle 问题。

题目链接： https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/specification.php

这道题目使用了 A* 算法，题目本身就是有点难度的，但是 Specification 里面已经把该算法的步骤都列出来了，基本就是一个优先级队列的使用。而优先级队列也可以使用提供的 MinPQ 完成，所以基本没有难度。

本题的难点依旧在于优化。

Board 的代码还是相对容易的，主要是注意 euqals 必须满足几个特性，并且距离可以做一次缓存。

Solver 我写了一个内部类来用作搜索结点，用结点之间的父亲节点来表示搜索的路径，这样当出现目标局面的时候，逐层沿着 parent 向上就可以得到整条操作路径。

注意 distance 和 priority 必须缓存，这是一个多达 25 个测试点的优化项目。

另外通过实测可以发现 Manhattan Priority 更加好，所以直接采用这个方案就可以了。

有一个 Breaking tie 的技巧：

• Using Manhattan() as a tie-breaker helped a lot.
• Using Manhattan priority, then using Manhattan() to break the tie if two boards tie, and returning 0 if both measurements tie.

Solver 可以在构造的时候直接跑出结果，然后缓存，否则没有执行过 solution() 的话，moves() 和 solvable 也拿不到。

有一个非常关键的地方在于不要添加重复的状态进入 PQ。

node.getParent() == null || !bb.equals(node.getParent().getBoard())

对于判断是不是可解的，可以将 board 和 board.twin() 一起加入 PQ，两个状态一起做 A* 搜索，要么是棋盘本身，要么是棋盘的双胞胎，总有一个会做到 isGoal()。

一旦有任何一者达到目标局面，就说明这一个情况是可解的，那么另一方就是不可解的。通过判断可解的是自己，还是自己的双胞胎，可以得到 solvable。

注意当且仅当 solvable 的时候才会有 moves() 和 solution()，所以对于不可解的状态，注意不要把它的双胞胎的 moves 和 solution 赋值过来。

// To implement the A* algorithm, you must use the MinPQ data type for the priority queue.
MinPQ<GameTreeNode> pq = new MinPQ<>();
// 把当前状态和双胞胎状态一起压入队列，做 A* 搜索
pq.insert(new GameTreeNode(initial, false));
pq.insert(new GameTreeNode(initial.twin(), true));
GameTreeNode node = pq.delMin();
Board b = node.getBoard();
//  要么是棋盘本身，要么是棋盘的双胞胎，总有一个会做到 isGoal()
while (!b.isGoal()) {
    for (Board bb : b.neighbors()) {
        // The critical optimization.
        // A* 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 in the game tree.
        if (node.getParent() == null || !bb.equals(node.getParent().getBoard())) {
            pq.insert(new GameTreeNode(bb, node));
        }
    }
    // 理论上这里 pq 永远不可能为空
    node = pq.delMin();
    b = node.getBoard();
}
// 如果是自己做出了结果，那么就是可解的，如果是双胞胎做出了结果，那么就是不可解的
solvable = !node.isTwin();

if (!solvable) {
    // 注意不可解的地图，moves 是 -1，solution 是 null
    moves = -1;
    solution = null;
} else {
    // 遍历，沿着 parent 走上去
    ArrayList<Board> list = new ArrayList<>();
    while (node != null) {
        list.add(node.getBoard());
        node = node.getParent();
    }
    // 有多少个状态，减 1 就是操作次数
    moves = list.size() - 1;
    // 做一次反转
    Collections.reverse(list);
    solution = list;
}

这段代码得了 99 分，应该已经秒杀了 Coursera 上绝大多数的提交了。

这次 Assignment 的及格线是 80 分，应该说只要正确性达标，内存和时间做的差些，90 分还是可以有的。

主要可能还是有些细节的地方没有优化到，MinPQ Operation Count 和 Board Operation Count 这两个测试有部分测试数据没过，应该是哪里还能省掉几次调用。但是在整体的运行时间上，只有 2 个测试数据超过了 1 秒，分别为 1.25 秒和 1.29 秒，其余测试点均在 0.X 秒就完成了，远小于测试规定的 5 秒以内。

Compilation:  PASSED
API:          PASSED

Spotbugs:     PASSED
PMD:          PASSED
Checkstyle:   PASSED

Correctness:  51/51 tests passed
Memory:       22/22 tests passed
Timing:       116/125 tests passed

import java.util.ArrayList;
import java.util.Arrays;

public class Board {

    private final int[][] tiles;
    private final int n;
    // 缓存每一个位置的距离，需要的时候可以不用每次都重新遍历计算
    private final int hamming;
    private final int manhattan;

    // create a board from an n-by-n array of tiles,
    // where tiles[row][col] = tile at (row, col)
    public Board(int[][] tiles) {
        n = tiles.length;
        this.tiles = new int[n][n];
        int hammingSum = 0;
        int manhattanSum = 0;
        // 复制值，而不是令 this.tiles = tiles，确保 Immutable
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                this.tiles[i][j] = tiles[i][j];
                // 反正这里都是要遍历一遍的，不如直接把空格位置记录下来，方便后面查找，就不需要再遍历去找那个 0 了
                if (tiles[i][j] != 0) {
                    // 这里根据定义，空位 0 是不需要再加到距离上的
                    // 顺便也一起做了 cache
                    // 这是 hamming 的，计算 shouldAt 和 nowAt 是不是相等
                    // 应该在的位置就是自己的数值（由于下标从 0 开始，减 1），如果是空位，就在最后
                    int targetAt = tiles[i][j] - 1;
                    // 这是现在在的位置，把二维的转化为一维的
                    int nowAt = i * n + j;
                    hammingSum += targetAt != nowAt ? 1 : 0;
                    // 这是 manhattan 的，计算横纵坐标距离差的绝对值的和
                    int vertical = Math.abs(i - targetAt / n);
                    int horizontal = Math.abs(j - targetAt % n);
                    manhattanSum += vertical + horizontal;
                }
            }
        }
        hamming = hammingSum;
        manhattan = manhattanSum;
    }

    // string representation of this board
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(n).append("\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(tiles[i][j]).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    // board dimension n
    public int dimension() {
        return n;
    }

    // number of tiles out of place
    public int hamming() {
        return hamming;
    }

    // sum of Manhattan distances between tiles and goal
    public int manhattan() {
        return manhattan;
    }

    // is this board the goal board?
    public boolean isGoal() {
        return hamming() == 0;
    }

    // does this board equal y?
    @Override
    public boolean equals(Object y) {
        // The equals() method is inherited from java.lang.Object, so it must obey all of Java’s requirements.
        if (y == null) {
            return false;
        }
        if (this == y) {
            return true;
        }
        if (y.getClass() != this.getClass()) {
            return false;
        }
        Board board = (Board) y;
        // 这里二维数组的相等做 deepEquals
        return Arrays.deepEquals(tiles, board.tiles);
    }

    // 本题不允许重写 hashCode()

    // all neighboring boards
    public Iterable<Board> neighbors() {
        ArrayList<Board> neighbors = new ArrayList<>();
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (tiles[i][j] == 0) {
                    x = i;
                    y = j;
                }
            }
        }
        int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        for (int[] direction : directions) {
            int xx = x + direction[0];
            int yy = y + direction[1];
            if (isValid(xx, yy)) {
                neighbors.add(new Board(swap(x, y, xx, yy)));
            }
        }
        return neighbors;
    }

    // 判断是否越界
    private boolean isValid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }

    // 复制数组并交换指定位置
    private int[][] swap(int x, int y, int xx, int yy) {
        int[][] newTiles = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(tiles[i], 0, newTiles[i], 0, n);
        }
        int tmp = newTiles[x][y];
        newTiles[x][y] = newTiles[xx][yy];
        newTiles[xx][yy] = tmp;
        return newTiles;
    }

    // a board that is obtained by exchanging any pair of tiles
    public Board twin() {
        Board b = null;
        // 随便找两个相邻的位置就可以了，只要不越界，只要不是 0，就可以交换
        for (int i = 0; i < n * n - 1; i++) {
            int x = i / n;
            int y = i % n;
            int xx = (i + 1) / n;
            int yy = (i + 1) % n;
            if (tiles[x][y] != 0 && tiles[xx][yy] != 0) {
                b = new Board(swap(x, y, xx, yy));
                break;
            }
        }
        return b;
    }

    // unit testing (not graded)
    public static void main(String[] args) {
        int[][] t = {{1, 2, 3}, {4, 5, 0}, {8, 7, 6}};
        Board b = new Board(t);
//        System.out.println(b.dimension());
//        System.out.println(b);
//        System.out.println(b.hamming());
//        System.out.println(b.manhattan());
//        System.out.println(b.isGoal());
//        System.out.println(b.twin());
//        System.out.println(b.equals(b.twin()));
        for (Board bb : b.neighbors()) {
            System.out.println(bb);
        }
    }

}

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;
import java.util.Collections;


public class Solver {

    // 定义一个搜索树，方便进行 A* 搜索
    // 搜索树的结点，递归的定义
    private static class GameTreeNode implements Comparable<GameTreeNode> {
        private final Board board; // 结点
        private final GameTreeNode parent; // 父亲
        private final boolean twin;
        private final int moves;
        // Caching the Hamming and Manhattan priorities.
        // To avoid recomputing the Manhattan priority of a search node from scratch each time during various priority queue operations, pre-compute its value when you construct the search node;
        // save it in an instance variable; and return the saved value as needed.
        // This caching technique is broadly applicable:
        // consider using it in any situation where you are recomputing the same quantity many times and for which computing that quantity is a bottleneck operation.
        //
        // rejecting if doesn't adhere to stricter caching limits
        private final int distance;
        // The efficacy of this approach hinges on the choice of priority function for a search node.
        // We consider two priority functions:
        //
        // The Hamming priority function is the Hamming distance of a board plus the number of moves made so far to get to the search node.
        // Intuitively, a search node with a small number of tiles in the wrong position is close to the goal, and we prefer a search node if has been reached using a small number of moves.
        //
        // The Manhattan priority function is the Manhattan distance of a board plus the number of moves made so far to get to the search node.
        private final int priority;

        // 初始节点，parent 为 null，需要区分是不是双胞胎
        public GameTreeNode(Board board, boolean twin) {
            this.board = board;
            parent = null;
            this.twin = twin;
            moves = 0;
            distance = board.manhattan();
            priority = distance + moves;
        }

        // 之后的结点，twin 状态跟从 parent
        public GameTreeNode(Board board, GameTreeNode parent) {
            this.board = board;
            this.parent = parent;
            twin = parent.twin;
            moves = parent.moves + 1;
            distance = board.manhattan();
            priority = distance + moves;
        }

        public Board getBoard() {
            return board;
        }

        public GameTreeNode getParent() {
            return parent;
        }

        public boolean isTwin() {
            return twin;
        }

        @Override
        public int compareTo(GameTreeNode node) {
            // Using Manhattan() as a tie-breaker helped a lot.
            // Using Manhattan priority, then using Manhattan() to break the tie if two boards tie, and returning 0 if both measurements tie
            if (priority == node.priority) {
                return Integer.compare(distance, distance);
            } else {
                return Integer.compare(priority, node.priority);
            }
        }

        @Override
        public boolean equals(Object node) {
            if (node == null) {
                return false;
            }
            if (this == node) {
                return true;
            }
            if (node.getClass() != this.getClass()) {
                return false;
            }
            GameTreeNode that = (GameTreeNode) node;
            return getBoard().equals(that.getBoard());
        }

        @Override
        public int hashCode() {
            return 1;
        }
    }

    private int moves;
    private boolean solvable;
    private Iterable<Board> solution;
    private final Board initial;

    // find a solution to the initial board (using the A* algorithm)
    public Solver(Board initial) {
        if (initial == null) {
            throw new IllegalArgumentException();
        }
        this.initial = initial;
        cache();
    }

    // is the initial board solvable? (see below)
    public boolean isSolvable() {
        return solvable;
    }

    // min number of moves to solve initial board
    public int moves() {
        return moves;
    }

    // sequence of boards in a shortest solution
    public Iterable<Board> solution() {
        return this.solution;
    }

    // 构造的时候直接跑出结果，然后缓存，否则没有 solution 的话，moves 和 solvable 也拿不到
    private void cache() {
        // To implement the A* algorithm, you must use the MinPQ data type for the priority queue.
        MinPQ<GameTreeNode> pq = new MinPQ<>();
        // 把当前状态和双胞胎状态一起压入队列，做 A* 搜索
        pq.insert(new GameTreeNode(initial, false));
        pq.insert(new GameTreeNode(initial.twin(), true));
        GameTreeNode node = pq.delMin();
        Board b = node.getBoard();
        //  要么是棋盘本身，要么是棋盘的双胞胎，总有一个会做到 isGoal()
        while (!b.isGoal()) {
            for (Board bb : b.neighbors()) {
                // The critical optimization.
                // A* 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 in the game tree.
                if (node.getParent() == null || !bb.equals(node.getParent().getBoard())) {
                    pq.insert(new GameTreeNode(bb, node));
                }
            }
            // 理论上这里 pq 永远不可能为空
            node = pq.delMin();
            b = node.getBoard();
        }
        // 如果是自己做出了结果，那么就是可解的，如果是双胞胎做出了结果，那么就是不可解的
        solvable = !node.isTwin();

        if (!solvable) {
            // 注意不可解的地图，moves 是 -1，solution 是 null
            moves = -1;
            solution = null;
        } else {
            // 遍历，沿着 parent 走上去
            ArrayList<Board> list = new ArrayList<>();
            while (node != null) {
                list.add(node.getBoard());
                node = node.getParent();
            }
            // 有多少个状态，减 1 就是操作次数
            moves = list.size() - 1;
            // 做一次反转
            Collections.reverse(list);
            solution = list;
        }
    }

    // test client (see below)
    public static void main(String[] args) {

        // create initial board from file
        In in = new In(args[0]);
        int n = in.readInt();
        int[][] tiles = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tiles[i][j] = in.readInt();
            }
        }
        Board initial = new Board(tiles);

        // 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);
            }
        }
    }

}