Homework 4: 8 Puzzle

CS61B

Important Guide video

Best-First Search

Optimizations

卡在了如何计算Hamming priority里的the number of moves made so far to get to the search node.

打开了之前做Algorithm Part 1的week4的作业，发现现在在写的Board.java没有达到题目immutable的要求，遂改之：

• 成员变量写成private final……
• constructor里面构造board的时候，不能直接把参数的2Darray赋给成员变量，而是通过复制Darray里面的内容来构建，防止2Darray被改动时你的board也被改动

同时，也发现Board.java里的Hamming priority和Manhattan priority function都还不需要计入moves made to reach the current position.要在Solver.java里面计算priority的时候再加上moves.

写Solver.java的时候，要从MinPQ里delMin,但现在卡子MinPQ里如何compare two SearchNode的priority.

在网上看到了这个帖子正是讨论该问题：
Algorithms (princeton) (week4) 讨论帖

于是按照大神的建议，重写了MinPQ里的comparator, 同时在new MinPQ的时候采用有一个comparator参数的构造函数来构造，就可以new出采用你自己重写的comparator的MinPQ了。

新写一个private class，就是你自己要定义的comparator, which implements Comparator <SearchNode>:

private class ByPriority implements Comparator<SearchNode> {
        @Override
        public int compare(SearchNode node1, SearchNode node2) {
            int difference = node1.priority - node2.priority;
            if(difference > 0){
                return 1;
            }else if(difference < 0){
                return -1;
            }else{
                if(node1.currentState.manhattan() < node2.currentState.manhattan()){
                    return -1;
                }else{
                    return 1;
                }
            }
        }
    }

new一个你自己定义的comparator类的对象：

private final Comparator<SearchNode> byPriority = new ByPriority();

用含有Comparator参数的构造方法new出你需要的MinPQ:

this.searchNodes = new MinPQ<>(byPriority);

做了好一会儿，得到的运行结果不正确:

图中的1是solutionBoard的size(),也就是要到到goal state需要依次到达的状态个数，明显是错的，说明我的solutionBoard肯定弄错了，没有循环递增。

查了下之前的作业，发现多了这么一段codes:

    node = pq.delMin();
    solved = node.getBoard().isGoal();
    solutionBoards.add(node.getBoard());
    while((node = node.getPreviousNode()) != null) {
          solutionBoards.add(0,node.getBoard());
    }

But why, 怎么看怎么觉得现在代码没毛病啊~

晚上看了一下Week4的assignment,发现我今天写的有一段代码肯定有问题，就是防止重复的解board被加入到solutionBoards里面

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.

我写的只是满足每一次delMin, 再insert它的childNodes到MinPQ时，确保不会insert跟上一步有重复的Board，但不能保证跟上上一级，上上上一级没有重复的。

之后又根据week4的作业更正了往solutionBoards里面add board的代码，最后是运行成功了，但还不明白为什么自己先前写的会导致错误的结果：

改正后的代码：

public Solver(Board initial){
        this.initialBoard = initial;
        this.searchNodes = new MinPQ<>(byPriority);
        SearchNode rootNode = new SearchNode(initial, 0, null);
        searchNodes.insert(rootNode);
        SearchNode nodeToDelete;
        while(!searchNodes.min().currentState.isGoal()) {
            nodeToDelete = searchNodes.delMin();
            for(Board neighbor : Board.neighbors(nodeToDelete.getState())){
                if(!alreadyExisted(nodeToDelete, neighbor)){
                    searchNodes.insert(new SearchNode(neighbor, nodeToDelete.getMoves() + 1, nodeToDelete ));
                }
            }
        }
        nodeToDelete = searchNodes.delMin();
        this.solutionBoards.add(nodeToDelete.getState());
        while((nodeToDelete = nodeToDelete.getPreviousNode()) != null ){
            this.solutionBoards.add(0, nodeToDelete.getState());
        }
    }

下面这个为什么错了：

  public Solver(Board initial){
        this.initialBoard = initial;
        this.searchNodes = new MinPQ<>(byPriority);
        SearchNode rootNode = new SearchNode(initial, 0, null);
        searchNodes.insert(rootNode);
        SearchNode nodeToDelete;
        while(!searchNodes.min().currentState.isGoal()) {
            nodeToDelete = searchNodes.delMin();
            solutionBoards.add(nodeToDelete.getState());
            for(Board neighbor : Board.neighbors(nodeToDelete.getState())){
                if(!alreadyExisted(nodeToDelete, neighbor)){
                    searchNodes.insert(new SearchNode(neighbor, nodeToDelete.getMoves() + 1, nodeToDelete ));
                }
            }
        }
}

通过测试，发现我的moves()有问题，

   /**
     * Returns the minimum number of moves to solve the
     * initial board.
     *
     * 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.
     *
     */
    public int moves(){
        return initialBoard.manhattan();
    }

本来manhattan()就是省略了movesMadesofar的，所以这里肯定出错了；
参考week4 assignment,更正：

  public int moves(){
        return this.solutionBoards.size() - 1;
    }