[HomeWork] Algorithms, Part I (week 1)

第一周的作业Percolation。难点在于“backwash”也就是在percolate的时候，不能有“孤立”的virtual bottom与virtual top连在连在一起（变蓝），注意一下isFull。大家可以自己想明白的，可以多多讨论~顺便求米求学分~
Ps:coursera的评价系统好屌，各种style错误，还有一些小问题，不过既然是算法，大头对了就差不多了，不是完美主义者~

rilegoule.....终于过了bonus test....

解决backwash的两种方法：
1. 一个UF object 控制percolate()，另一个UF object控制isFull()
前者有virtual bottom和virtual top, 后者只有virtual top;
fields：UF object1 (N * N + 2); UF object2 (N * N + 1); boolean array (N * N) 控制isOpen()
2. 一个UF object控制isFull(), percolates()是每次open()的最后做一个DFS找所有unfilled sites，(找到一个fill一个)，如果找到深度为N的的说明percolates了.
只有virtual top;
fields: UF obejct (N * N + 1)控制isFull(); boolean array1 (N * N) 控制isOpen(); boolean array2 (N * N)作为isFull的矩阵标记; boolean percolates单一布尔值做percolates与否的标记

只有方法2可以避免backwash的同时通过bonus memory test

为什么方法2可以通过timing test？
因为虽然对某个site来说, open它之后做的DFS最坏需要O(N^2)的时间，但是amortized running time一定是O(1) 的：
证明：
从sites全部blocked开始，进行M次open；每个open()最后都有一个DFS，所以一共是M次DFS；
DFS的时间取决于它经过的sites的个数；
每个DFS经过的sites都会fill掉；
设第i个open()中的DFS，经过了T(i)个sites，那么它一定也fill了T(i)个sites；
DFS只找unfilled sites，所以任意两次DFS fill的sites是没有重叠的，因而前M次fill的总数是它们直接相加: 一共fill了 T(1) + T(2) + ... + T(M)个site
而filled sites的总数不会超过当前open sites的总数，每次只open一个sites，所以第M次open()的最后open sites总数为M; 从而T(1) + T(2) + ... + T(M) ≤ M
这是M次DFS的总和，那平均每次DFS就 ≤ M/M ＝ 1了


故平均每次open花的时间为O(1) (除了union()等UF操作之外)

人蠢只能多模仿了╰(￣▽￣)╭课件里老师也就随口提一句virtual top和bottom完全理解不来，看了解释才明白过来：

virtual top连通了棋盘top row中所有的open site，也就是为什么生成的UF对象数量+2/ +1。

一个UFobject 控制percolate()， percolated条件即virtual top和bottom连通，体现在UF的结构上，就是两棵树连通了~

另一个UFobject控制isFull()，full的条件就是给定的site和virtual top所在的component连通了~

boolean array(N * N) 控制isOpen()

为什么需要两棵树？

如果用一个UF的话，假如用Perco需要的UF，该UF中既有virtualtop和bottom，在grid被击穿的事件中，virtual top和virtual bottom就连通了，也就等于与virtual bottom连通的所有bottom行的open site也会变为full open site

PS.~style这种东西下次作业再注意吧~

Style还是挂了....不过好像不算分

zj45499 发表于 2015-1-25 21:14
Style还是挂了....不过好像不算分

哈哈，一开始Style出来吓了我一跳，不过移动format就好了。。

要避免 backwash，还不能用自己写的 Union-Find，还不能用多个 Union-Find Object，真是纠结了好一会儿。

还是那个老问题，怎么添加那几个jar啊？我的市Mac OX搞半天，按照去年的讨论贴看了，放到default，eclipse还是显示"WeightedQuickUnionUF can not be resolved to a type".难道是我理解错了放到哪一个default里？或者我还缺少别的操作？

交作业了

有加学分么？没有完美...

交作业了

birdor 发表于 2015-1-26 06:27
要避免 backwash，还不能用自己写的 Union-Find，还不能用多个 Union-Find Object，真是纠结了好一会儿。 ...

你用一个Union-Find Object是怎么实现的？我只能用两个么

New613Life 发表于 2015-1-30 00:17
你用一个Union-Find Object是怎么实现的？我只能用两个么

我也是用两个~请教大神