一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2173|回复: 12
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
sanguine 发表于 2014-2-23 01:33:38 | 显示全部楼层 |阅读模式

[Coursera]Algorithms #4 - 2014-01-31@princeton

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 sanguine 于 2014-3-19 17:06 编辑

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.


bitcpf 发表于 2014-3-10 22:13:26 | 显示全部楼层
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)

折腾了好久,求指导。。。
回复 支持 反对

使用道具 举报

wsmjmiisme 发表于 2014-3-17 14:54:03 | 显示全部楼层
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-22 07:06:05 | 显示全部楼层
谁能简单介绍下,这个算法到底是怎么实现的吗?看英文不能理解。
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-2-23 05:16:33 | 显示全部楼层
czbnlzd920706 发表于 2015-2-22 07:06
谁能简单介绍下,这个算法到底是怎么实现的吗?看英文不能理解。

搞懂了,写完了。如果有同学对这个没思路的,可以给我留言。
回复 支持 反对

使用道具 举报

totoSalad 发表于 2015-3-11 22:32:40 | 显示全部楼层
czbnlzd920706 发表于 2015-2-23 05:16
搞懂了,写完了。如果有同学对这个没思路的,可以给我留言。

木有思路啊 亲。。我是菜菜,救命
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-3-12 00:38:18 | 显示全部楼层
totoSalad 发表于 2015-3-11 22:32
木有思路啊 亲。。我是菜菜,救命

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

使用道具 举报

totoSalad 发表于 2015-3-12 15:13:54 | 显示全部楼层
czbnlzd920706 发表于 2015-3-12 00:38
九个格子.8个写数字,一个空的。移动成序。把空的当作可移动的格子。每次可以朝不同方向移动一格,以与所 ...

谢谢!之前其实看是看明白了,就在一个地方卡壳了,多谢帮助!
回复 支持 反对

使用道具 举报

totoSalad 发表于 2015-3-12 16:53:01 | 显示全部楼层
czbnlzd920706 发表于 2015-3-12 00:38
九个格子.8个写数字,一个空的。移动成序。把空的当作可移动的格子。每次可以朝不同方向移动一格,以与所 ...

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

使用道具 举报

czbnlzd920706 发表于 2015-3-13 19:18:39 | 显示全部楼层
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.很多都讲的很详细。
祝好。
回复 支持 反对

使用道具 举报

tonyabracadabra 发表于 2015-7-23 20:02:33 | 显示全部楼层
algs4.jar中给的MinPQ.java要求Key inplement Iterable<Key>,可加入的不是Board元素么?为何是Iterable的?难道每次加入的都是一个Board元素的全部邻居(ArrayList)?那该怎么取优先啊?以及,是否需要在Board中额外实现两个comparator?
回复 支持 反对

使用道具 举报

大成若缺 发表于 2015-8-4 23:08:47 | 显示全部楼层
本帖最后由 大成若缺 于 2015-8-4 23:11 编辑

老夫遇到了一个老问题百思不得其解:就是当从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

求问各位是怎么解决这个问题的呀?很困惑很困惑很困惑,请各位高手指点!
回复 支持 反对

使用道具 举报

oumizx 发表于 2016-6-19 02:32:44 | 显示全部楼层
大成若缺 发表于 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.      * Initializes an empty priority queue using the given comparator.
  8.      *
  9.      * @param  comparator the order to use when comparing keys
  10.      */
  11.     public MinPQ(Comparator<Key> comparator) {
  12.         this(1, comparator);
  13.     }
复制代码
和比较大小时的判断方法
  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.     }
复制代码
当出现priority相等的情况时,即代码中的difference = 0时,当这个Node中manhattan小,move大时,这个Node的判定越小,即delMin时的优先级越高。

建立inference
  1. private final Comparator<SearchNode> byPriority = new ByPriority();
复制代码
初始化MinPQ
  1. pq = new MinPQ<>(byPriority);
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 11:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表