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

Honor code.   All students in the course must agree to abide by the Coursera honor code. In particular, do not post solutions or partial solutions to programming assignments; however, you are permitted to discuss general ideas and problem-solving approaches. You are also permitted to discuss solutions to exercises and job interview questions.
assignments不可以share code，但是exercise和job interview questions是可以的

讨论帖(该贴仅为week4讨论帖，加分贴请点这里)

课程汇总 && 介绍：http://www.1point3acres.com/bbs/thread-78774-1-1.html


Week 4

This week we are going to introduce two fundamental data types, address the challenges of developing algorithms and data structures that can serve as the basis of efficient implementations, and try to convince you that such implementations enable solution of a broad range of applications problems that could not be solved without them.

Lecture: Priority Queues. We introduce the priority queue data type and an efficient implementation using the binary heap data structure. This implementation also leads to an efficient sorting algorithm known as heapsort. We conclude with an applications of priority queues where we simulate the motion of N particles subject to the laws of elastic collision.

Lecture: Elementary Symbol Tables. We define an API for symbol tables (also known as associative arrays) and describe two elementary implementations using a sorted array (binary search) and an unordered list (sequential search). When the keys are Comparable, we define an extended API that includes the additional methods min, max floor, ceiling, rank, and select. To develop an efficient implementation of this API, we study the binary search tree data structure and analyze its performance.

Exercise. Drill exercises on the lecture material.

Programming Assignment: 8-Puzzle. Your programming assignment is to implement the famous A* search algorithm to solve a combinatorial problem, and to substantially speed it up with an efficient priority queue implementation.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 2.4, 3.1, and 3.2 in Algorithms, 4th edition.

大成若缺 发表于 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);

复制代码

czbnlzd920706 发表于 2015-2-22 07:06
谁能简单介绍下，这个算法到底是怎么实现的吗？看英文不能理解。

搞懂了，写完了。如果有同学对这个没思路的，可以给我留言。

谁能简单介绍下，这个算法到底是怎么实现的吗？看英文不能理解。

Solver 的 solution测试过不去

Test 2: Call solution() with file inputs to ensure that the correct sequence of moves is followed
  *  puzzle00.txt
  *  puzzle01.txt
    wrong initial board
     - student   solution() initial board = 2
1  2
3  0

     - reference solution() initial board = 2
1  0
3  2

  *  puzzle02.txt
    wrong initial board
     - student   solution() initial board = 9
1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54
55 56 57 58 59 60 61 62 63
64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80  0

     - reference solution() initial board = 9
1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54
55 56 57 58 59 60 61 62 63
64 65 66 67 68 69 70  0 71
73 74 75 76 77 78 79 80 72

代码片段：
        public Iterable<Board> solution()       // sequence of boards in a shortest solution; null if no solution
        {
        if (result == null)
            return null;
        Stack<Board> s = new Stack<Board>();
        Node temp = result;
        while(temp!=null)
        {
                s.push(temp.board);
                temp = temp.previous;
        }
        
        
        
        
        return s;
        }


另外比较挫，一直没搞清楚怎么在Eclipse下调试，都是写了之后上传，根据反馈改
这次把jar导入之后依然是有错误
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
        at edu.princeton.cs.algs4.AcyclicLP.main(AcyclicLP.java:122)

折腾了好久，求指导。。。

taxicab问题，有人关心吗？

我搜到这个解法，应该是空间为O(N)的解法
http://algs4.cs.princeton.edu/24pq/Taxicab.java.html

可是我觉得有点问题：
这个算法并不能保证(i,j)是按照立方和从小到大的顺序被push进queue的

这样，从queue里面pop出最小的，然后拿相邻的两个被pop的进行比较，是有风险的：

比如先push了一个大数a进去，然后push一个小一点的数b进去
但是很可能在b还没被push进去的时候，跟b一样大小的数先被pop出来了

这样不就漏了么？

czbnlzd920706 发表于 2015-2-23 05:16
搞懂了，写完了。如果有同学对这个没思路的，可以给我留言。

木有思路啊 亲。。我是菜菜，救命

totoSalad 发表于 2015-3-11 22:32
木有思路啊 亲。。我是菜菜，救命

九个格子.8个写数字，一个空的。移动成序。把空的当作可移动的格子。每次可以朝不同方向移动一格，以与所需结果的相似度作为优先级压入PQ。然后取出优先级最低的，继续按照不同情况往下走，把此时新情况压入PQ，不断重复。直到最后空格移动到9，并且1-8成序排列。
http://blog.csdn.net/liuweiran900217/article/details/19818289
这个链接里有解释，可以看看。如果还有问题请留言。只解决思路上的问题，不负责帮你debug。

czbnlzd920706 发表于 2015-3-12 00:38
九个格子.8个写数字，一个空的。移动成序。把空的当作可移动的格子。每次可以朝不同方向移动一格，以与所 ...

谢谢！之前其实看是看明白了，就在一个地方卡壳了，多谢帮助！

czbnlzd920706 发表于 2015-3-12 00:38
九个格子.8个写数字，一个空的。移动成序。把空的当作可移动的格子。每次可以朝不同方向移动一格，以与所 ...

public Board twin()                    // a boadr that is obtained by exchanging two adjacent blocks in the same row 这个方法是干什么用的，不太清楚可以解释一下吗

totoSalad 发表于 2015-3-12 16:53
public Board twin()                    // a boadr that is obtained by exchanging two adjacent blo ...

不好意思，这么久才回复。意思是，有些九宫格是走不成的，那这样的话如果你只跑一个模板，计算机会一直跑，一直压入优先级队列，然后CPU的占有率会冲到100%，死机。所以会有一个twinBoard，数学证明，调换一下位置后，如果原模板不会成功，这个twinBoard一定可以走出来。所以每次测试都是两个模板一起测试。详细的信息可以看coursera里面，有一个 Frequently Asked Question.很多都讲的很详细。
祝好。