[Coursera] Standford Algorithm Design & Analysis II

两次一起贴

bmbdl 发表于 2012-12-23 15:33
再求学分  赶在deadline之前做完第二周的。。

可以求问一下楼上的方法么

kinslover 发表于 2012-12-24 13:49
可以求问一下楼上的方法么

好像不好公开讨论。。我白色一下吧。。反正你已经做对了。

是说第二题吧，公开课的论坛里有不少讨论，可以看看。我用的办法很暴力，主要是基于这个想法: 题目只要求考虑差别小于3的情况，所以，对每个元素只需要考虑三种配对: 跟它相同的 label，差别为1的，和差别为2的，个数是1 + C(24,1) + C(24, 2) ~= 300，暴力列举就行，ruby/python的话可以直接用标准库里的permutation。

bmbdl 发表于 2012-12-24 14:49
好像不好公开讨论。。我白色一下吧。。反正你已经做对了。

是说第二题吧，公开课的论坛里有不少讨论， ...

我是保留了图中边权<=2的边，然后一遍DFS求出连通分量个数…………

kinslover 发表于 2012-12-25 01:07
我是保留了图中边权

对了问一下，你是用什么方法计算hamming距离的？论坛里有人说不用每个节点之间都比较，但我实在不明白他们怎么做的。用brute-force计算距离的话确实有点慢，得花10s左右的时间。

kinslover 发表于 2012-12-25 01:07
我是保留了图中边权

嗯，DFS或BFS搜索一遍也行，本质上是一样的。主要问题在于怎么把图构建出来，也就是怎么找到这些边权<=2的边。如果是所有节点两两配对的话，跟暴力算汉明距离一样。你是怎么做的？

moophis 发表于 2012-12-25 08:55
对了问一下，你是用什么方法计算hamming距离的？论坛里有人说不用每个节点之间都比较，但我实在不明白他们 ...

不用每个节点之间都比较 <= 看我上边的，每个节点只可能有300个节点与它的的距离不超过2.

moophis 发表于 2012-12-25 08:55
对了问一下，你是用什么方法计算hamming距离的？论坛里有人说不用每个节点之间都比较，但我实在不明白他们 ...

hamming的话我没做什么优化，就是O(N^2)的算一遍，保留<=2的边构图。目前能拍脑门想到的优化就是：位运算加速，虽然还是O(N^2)的，但是比对任意一对hamming code中元素挨个比较速度是快多了

bmbdl 发表于 2012-12-25 09:50
嗯，DFS或BFS搜索一遍也行，本质上是一样的。主要问题在于怎么把图构建出来，也就是怎么找到这些边权

初步就是暴戾20000x20000个边，保留<=2的边，用来构图，然后DFS求树的个数。然后算hamming distance的过程中我感觉可以用位运算加速比较水的做法T__T

kinslover 发表于 2012-12-25 09:54
初步就是暴戾20000x20000个边，保留

嗯。。暴力的话，用find-union就好了，遍历20k*20k个边，同时就可以find-union做完了。代码比BFS/DFS简单。