[Coursera] Algorithms (princeton) (week4) 讨论帖

algs4.jar中给的MinPQ.java要求Key inplement Iterable<Key>，可加入的不是Board元素么？为何是Iterable的？难道每次加入的都是一个Board元素的全部邻居（ArrayList）？那该怎么取优先啊？以及，是否需要在Board中额外实现两个comparator?

老夫遇到了一个老问题百思不得其解：就是当从MinPQ当中选择元素输出的时候，如果有两个节点的曼哈顿优先级（manhattan() + moves）相同，那么该取哪一个？

题目的描述中是说随便取一个，原话是这样的：
When two search nodes have the same Manhattan priority, you can break ties however you want, e.g., by comparing either the Hamming or Manhattan distances of the two boards.

按照这句话，我在Node类的compareTo函数重写时，用moves来break ties。我的方法是当优先队列中有两个Node的优先级相同并且最小时，取moves更大的那个，如此可以避免走弯路——回到一个moves更少的节点。这种方法在大多数情况下work了，满足solution中的元素个数刚好等于moves + 1。但是对于一部分复杂的board，会出现这种情况：即从MinPQ中调用delMin()的时候，MinPQ中priority最小的节点，其moves比上次delMin的节点moves还小。

由题意，一个节点的moves变量就等于它在Game Tree中的深度。对于一些比较复杂的Board，会在某一次调用delMin()的时候，发现其中拥有最小Priority的节点，其moves不是最大或并列最大的，比上次从MinPQ中取出来的Node的moves要小。也就是说，比上一次delMin()产生的节点在游戏树中的深度更浅了，也就是之前的solution数据结构构建的时候是走了弯路的，之前到上一次那个深度之前的节点，不是达到goal的必经路径。在多次这样走弯路，然后回头继续加深深度的查找和插入soution后，得到的solution中的元素数量和最终得到goalBoard的moves显然是不匹配的。但是autograder要求solution中元素的个数必须等于moves + 1。复杂的txt文件就无法满足这一点。对于维度越高的init，可能走的弯路越多，可能造成solution中元素个数太大。
autograder是这么说的：
Test 12b: Call solution() with 3-by-3 file inputs  *  puzzle3x3-00.txt  *  puzzle3x3-01.txt  *  puzzle3x3-02.txt  *  puzzle3x3-03.txt  *  puzzle3x3-04.txt  *  puzzle3x3-05.txt  *  puzzle3x3-06.txt  *  puzzle3x3-07.txt  *  puzzle3x3-08.txt  *  puzzle3x3-09.txt  *  puzzle3x3-10.txt  *  puzzle3x3-11.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 18     -  moves()              = 11  *  puzzle3x3-12.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 17     -  moves()              = 12  *  puzzle3x3-13.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 46     -  moves()              = 13  *  puzzle3x3-14.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 21     -  moves()              = 14  *  puzzle3x3-15.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 27     -  moves()              = 15  *  puzzle3x3-16.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 87     -  moves()              = 16  *  puzzle3x3-17.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 277     -  moves()              = 17  *  puzzle3x3-18.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 327     -  moves()              = 18  *  puzzle3x3-19.txt  *  puzzle3x3-20.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 345     -  moves()              = 20  *  puzzle3x3-21.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 330     -  moves()              = 21  *  puzzle3x3-22.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 594     -  moves()              = 22  *  puzzle3x3-23.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 423     -  moves()              = 23  *  puzzle3x3-24.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 1142     -  moves()              = 24  *  puzzle3x3-25.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 1353     -  moves()              = 25  *  puzzle3x3-26.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 694     -  moves()              = 26  *  puzzle3x3-27.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 3841     -  moves()              = 27  *  puzzle3x3-28.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 3921     -  moves()              = 28  *  puzzle3x3-29.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 6066     -  moves()              = 29  *  puzzle3x3-30.txt     -  number of boards in solution() does not equal to 1 + moves()        (it should be 1 greater because solution() starts with the inital board)     -  length of solution() = 4490     -  moves()              = 30==> FAILED

求问各位是怎么解决这个问题的呀？很困惑很困惑很困惑，请各位高手指点！

大成若缺 发表于 2015-8-4 23:08
老夫遇到了一个老问题百思不得其解：就是当从MinPQ当中选择元素输出的时候，如果有两个节点的曼哈顿优先级 ...

这个break tie的问题我也思考了很长时间。解决的方法是这样的。Override MinPQ中的compare方法，即改变MinPQ中比较大小的方法。
根据MinPQ源码中的初始化方法

1. public MinPQ(int initCapacity, Comparator<Key> comparator) {
   
2.         this.comparator = comparator;
   
3.         pq = (Key[]) new Object[initCapacity + 1];
   
4.         N = 0;
   
5.     }
   
6. 
   
7.     /**
   
8.      * Initializes an empty priority queue using the given comparator.
   
9.      *
   
10.      * @param  comparator the order to use when comparing keys
    
11.      */
    
12.     public MinPQ(Comparator<Key> comparator) {
    
13.         this(1, comparator);
    
14.     }

复制代码

和比较大小时的判断方法

1. private boolean greater(int i, int j) {
   
2.         if (comparator == null) {
   
3.             return ((Comparable<Key>) pq[i]).compareTo(pq[j]) > 0;
   
4.         }
   
5.         else {
   
6.             return comparator.compare(pq[i], pq[j]) > 0;
   
7.         }
   
8.     }

复制代码

可以知道在初始化数组的时候我们可以自定义一个comparator，让他来衡量MinPQ中的大小。

Override Comparator的代码

1. private class ByPriority implements Comparator<SearchNode> {
   
2.         public int compare(SearchNode searchNode1, SearchNode searchNode2) {
   
3.             int difference = searchNode1.priority - searchNode2.priority;
   
4.             if (difference > 0) {
   
5.                 return 1;
   
6.             } else if (difference < 0) {
   
7.                 return -1;
   
8.             } else {
   
9.                 if (searchNode1.board.manhattan() < searchNode2.board.manhattan()) {
   
10.                     return -1;
    
11.                 } else {
    
12.                     return 1;
    
13.                 }
    
14.             }
    
15. 
    
16.         }
    
17.     }

复制代码

当出现priority相等的情况时，即代码中的difference = 0时，当这个Node中manhattan小，move大时，这个Node的判定越小，即delMin时的优先级越高。

建立inference

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

复制代码

初始化MinPQ

1. pq = new MinPQ<>(byPriority);

复制代码

oumizx 发表于 2016-6-19 02:32
这个break tie的问题我也思考了很长时间。解决的方法是这样的。Override MinPQ中的compare方法，即改变Mi ...

你好，我感觉我的问题是这个问题好像压根就不需要考虑进去步长，因为算法里面从来不可能有调整，每次都是从这一searchnode的neighbor中选取下一步要走的，还有一个问题是如果第一步要走的时候就出现两个neighbor的曼哈顿数一样，然后他们步长也都是1，那怎么判断到底走哪个。。。

FslHoly 发表于 2017-3-25 17:48
你好，我感觉我的问题是这个问题好像压根就不需要考虑进去步长，因为算法里面从来不可能有调整，每次都是 ...

难得找到进度差不多的小伙伴！

FslHoly 发表于 2017-3-25 17:48
你好，我感觉我的问题是这个问题好像压根就不需要考虑进去步长，因为算法里面从来不可能有调整，每次都是 ...

我觉得可以比较hamming（）

criszz 发表于 2017-4-17 08:59
我觉得可以比较hamming（）

我已经刷完了part1了，当时这个问题问的挺傻的。。。思路完全想错了

FslHoly 发表于 2017-4-18 17:09
我已经刷完了part1了，当时这个问题问的挺傻的。。。思路完全想错了

找到错就好了~现在我都找不到相同进度的小伙伴了只能挖老坟