作业|学习资料|算法

8 Puzzle

jxtxzzw · 3月22日 · 2020年 · · · · 298次已读

Princeton Algorithm 8 Puzzle

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

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

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

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

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

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

注意 distancepriority 必须缓存,这是一个多达 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())

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

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

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

// 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 CountBoard 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

以下代码获得 99 分

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

}

查看其它 Assignment 题解

Percolation

2017-11-7 0

Collinear Points

2020-3-16 0

说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
  订阅评论动态  
提醒