一亩三分地论坛

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

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

算法可第三周的编程作业题讨论

[复制链接] |试试Instant~ |关注本帖
PincessR 发表于 2014-5-22 05:47:12 | 显示全部楼层 |阅读模式

[Coursera]Design and Analysis of Algorithm #3 - 2014-04-28@Stanford

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

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

x
进来问下关于第三周的编程作业题。我的答案总是20,试了一下不正确。但是用这段代码测试的小样本都是正确的,手动试了一下,也没有觉得有什么问题。不明白错在那里了。下面是结题思路:

我用java自己建的数据结构。总的来说,图的存储的方式是:使用一个map存  <顶点, 该顶点相邻的顶点>。
对于删除一个边(将两个顶点合为一个)的操作是(假设删除node1 和node2 的link,存为node1)

1. 找到node2的所有相邻点,
           a. 如果该相邻点为node1,则continue;
           b. 将其他所有相邻点 添加到node1的相邻点列表中,并且node1也会成为这些点的相邻点;
           c. 将node2从所有相邻点的邻点列表中删除;
2. 删除node2.

重复整个步骤直到图中只剩下两个点。这两个点的相邻点个数相同,返回这个个数就是min cut。

代码在下面。希望找到问题的人可以指教下 , 先谢谢了
  1. import java.io.BufferedReader;
  2. import java.io.FileNotFoundException;
  3. import java.io.FileReader;
  4. import java.io.IOException;
  5. import java.util.ArrayList;
  6. import java.util.Collections;
  7. import java.util.HashMap;
  8. import java.util.HashSet;
  9. import java.util.LinkedList;
  10. import java.util.List;
  11. import java.util.Map;
  12. import java.util.Random;
  13. import java.util.Set;


  14. public class minCut{

  15.         Graph1 graph;
  16.         
  17.         public minCut(){
  18.                 graph = new Graph1();
  19.         }
  20.                
  21.         public ArrayList<Node> findMinCut(int[][] matrix){
  22.                 graph.buildMap(matrix);
  23.                
  24.                 while(graph.getSize()>2){
  25.                         Node node1 = graph.getNode(graph.giveRandomIndex());
  26.                         Node node2 = graph.getNode(graph.giveRandomIndex());
  27.                         
  28.                         while(node2 == node1){
  29.                                 node2 = graph.getNode(graph.giveRandomIndex());
  30.                         }
  31.                         graph.cutEdge(node1, node2);
  32.                 }
  33.                 Node lastNode =graph.getNode(graph.giveRandomIndex());
  34.                 /*while(graph.getNeigbhors(lastNode).contains(lastNode)){
  35.                         graph.getNeigbhors(lastNode).remove(lastNode);
  36.                 }*/
  37.                 //return graph.getNeigbhors(lastNode).size();
  38.                 ArrayList<Node> neighbors;
  39.                 if (graph.getNeigbhors(lastNode).size() == 3){
  40.                         neighbors = graph.getNeigbhors(lastNode);
  41.                         neighbors.add(lastNode);
  42.                         return neighbors;
  43.                 }
  44.                 return null;
  45.         }
  46.         
  47.         public static void main(String[] args) throws NumberFormatException, IOException{
  48.                 /*int[][] matrix = {{1,2,6,0,0,0},{2,1,3,4,5,6},{3,2,0,0,0,0},{4,2,5,0,0,0},{5,2,4,6,0,0},{6,1,2,5,0,0}};
  49.                 minCut mincut = new minCut();
  50.                
  51.                 int number = mincut.findMinCut(matrix);
  52.                 System.out.println(number);*/

  53.         //        int[][] matrix = {{1,2,3,4,7},{2,1,3,4,0},{3,1,2,4,0},{4,1,2,3,5},{5,4,6,7,8},{6,5,7,8,0},{7,1,5,6,8},{8,5,6,7,0}};
  54.                
  55.                
  56.                 BufferedReader bf = new BufferedReader(new FileReader("data4.txt"));
  57.                 String line;
  58.                 int[][] matrix = new int[40][8];
  59.                 int i=0;
  60.                
  61.                
  62.                 while((line = bf.readLine())!=null){
  63.                         String[] chars = line.split("\\s+");
  64.                         int j=0;
  65.                         for(String integer: chars){
  66.                                 matrix[i][j] = Integer.parseInt(integer);
  67.                                 j++;
  68.                         }
  69.                         i++;
  70.                 }
  71.                
  72.                
  73.                 /*minCut mincut;
  74.                 for(int iter = 0 ;iter<1000; iter++){*/
  75.                
  76.                 int number =1000;
  77.                 for(int iter = 0 ;iter<500000; iter++){
  78.                         minCut mincut = new minCut();
  79.                         ArrayList<Node> update = mincut.findMinCut(matrix);
  80.                         if(update!= null)
  81.                                 System.out.println(update);
  82.                 }
  83. }
  84. }


  85. class Graph1{
  86.         
  87.         private static Map<Node,ArrayList<Node>> map;
  88.         
  89.         public Graph1(){
  90.                  map = new HashMap<Node,ArrayList<Node>>();
  91.         }
  92.         
  93.         public Set<Node> getAllNodes(){
  94.                 return Collections.unmodifiableSet(map.keySet());
  95.         }
  96.         
  97.         public void addNode(Node n){
  98.                 if(map.containsValue(n)) return ;
  99.                 map.put(n, new ArrayList<Node>());
  100.         }
  101.         
  102.         public static ArrayList<Node> getNeigbhors(Node n){
  103.                 return map.get(n);
  104.         }
  105.         
  106.         public static void addNeighbor(Node des, Node rcs){
  107.                 map.get(des).add(rcs);
  108.         }
  109.         
  110.         /*public static void deleteNeighbor(Node des, Node rcs){
  111.                 map.get(des).remove(rcs);
  112.         }*/
  113.         
  114.         public static void deleteNode(Node node){        
  115.                 if(!map.containsKey(node)) return ;
  116.                 for(Node neighbors:getNeigbhors(node) )
  117.                         map.get(neighbors).remove(node);
  118.                 map.get(node).clear();
  119.                 map.remove(node);
  120.         }
  121.         
  122.         public int getSize(){
  123.                 Set<Node> allNode = getAllNodes();
  124.                 return allNode.size();
  125.         }
  126.         
  127.         public int giveRandomIndex(){
  128.                 Set<Node> allNode = getAllNodes();
  129.                 int size = allNode.size();
  130.                 int item = new Random().nextInt(size);
  131.                 int i = 0;
  132.                 for(Node node:allNode){
  133.                         if(i == item)
  134.                                 return node.getNodeIndex();
  135.                         i++;
  136.                 }
  137.                 return -1;
  138.         }
  139.         
  140.         
  141.         public void buildMap(int[][] matrix){
  142.                
  143.                 List<Node> list = new LinkedList<Node>();
  144.                 for(int i =0; i<matrix.length;i++){
  145.                         Node node = new Node(matrix[i][0]);
  146.                         addNode(node);
  147.                         list.add(node);
  148.                 }
  149.                
  150.                
  151.                 int i=0;
  152.                 for(Node des:list){
  153.                         for(int j =1; j<matrix[0].length; j++){
  154.                                 if(matrix[i][j]==0) continue;
  155.                                 Node src = getNode(matrix[i][j]);
  156.                                 addNeighbor(des , src);
  157.                         }
  158.                         i++;
  159.                 }
  160.         }
  161.         
  162.         
  163.         /**
  164.          * Give parameter index x , getNode should return the corresponding Node which has this index
  165.          * @param x.
  166.          * @return
  167.          */
  168.         public Node getNode(int x){
  169.                 for(Node node:Collections.unmodifiableCollection(map.keySet())){
  170.                         if(node.getNodeIndex()==x)
  171.                                 return node;
  172.                 }
  173.                 return null;
  174.         }
  175.         
  176.         /**
  177.          * cutEdge is used to merge two Node n1 and n2 into one Node n1
  178.          * @param n1 n1 will not vanish after cutting, n2's neighbors will be added to it.
  179.          * @param n2 n2's neighbors will be added to n1. All it's neighbors will delete n2 as neighbor; And n2 is deleted afterwards;
  180.          */
  181.         public void cutEdge(Node n1, Node n2){
  182.                 for(Node node:getNeigbhors(n2)){
  183.                         if(n1 == node) // this means if n2's neighbor is n1 itself, we don't have to include it into n1's neighbor group.
  184.                                 continue;
  185.                         addNeighbor(n1, node);
  186.                         addNeighbor(node, n1);
  187.                 }
  188.                 deleteNode(n2);
  189.         }
  190. }

  191. class Node{
  192.         private int index;
  193.         //private ArrayList<Node> neighbors = new ArrayList<Node>();
  194.         
  195.         public Node(int x){ /*, ArrayList<Node> neighbors*/
  196.                 this.index = x;
  197.         //        this.neighbors = neighbors;
  198.         }
  199.         
  200.         public int getNodeIndex(){
  201.                 return index;
  202.         }
  203.         
  204.         public String toString(){
  205.                 String result = "Node: "+getNodeIndex();
  206.                 return result;
  207.         }
  208. }
复制代码
breezet 发表于 2014-5-22 10:00:25 | 显示全部楼层
我感觉问题可能出在把其他点的连接也由node2改成node1的部分,如果其他点之前已经跟node1相连的话这样似乎会有不必要的删边?不过你的答案比正确答案大。。。
我是用Python搞的数据结构,结果是17,是一个list里分两部分,前一部分为点list,后一部分为跟点连接的边list大体思路是这样的:
1.随机抽一个点,挑跟它相连的第一个点
2.将这两个点的第二部分拼在一起,第一部分也拼在一起
3.循环这个超点的连接部分,如果里面出现了连接到自身的边就删除
4.重复直到只有两个点
  1. import random
  2. import time

  3. f = open('kargerMinCut.txt', 'r')
  4. lines = f.readlines()
  5. graph = []
  6. f.close()

  7. for i in lines:
  8.     s = i.split('\t')
  9.     vertex = [int(s[0])]
  10.     adjacent = []
  11.     for node in s[1:-1]:
  12.         adjacent.append(int(node))
  13.     graph.append([vertex, adjacent])

  14. def Merge(A, B):
  15.     newvertex = [A[0] + B[0], A[1] + B[1]]
  16.     i = 0
  17.     while i < len(newvertex[1]):
  18.         if newvertex[1][i] in newvertex[0]:
  19.             newvertex[1].remove(newvertex[1][i])
  20.         else:
  21.             i += 1
  22.     return newvertex

  23.    
  24. def RContraction(graph):
  25.     if len(graph) == 2:
  26.         return graph
  27.     else:
  28.         random.shuffle(graph)
  29.         vertex = graph.pop()
  30.         random.shuffle(vertex[1])
  31.         tomerge = vertex[1][0]
  32.         for i in range(len(graph)):
  33.             if tomerge in graph[i][0]:
  34.                 graph[i] = Merge(vertex, graph[i])
  35.                 break
  36.         return graph

  37. #graph = [[[1], [2, 3]], [[2], [1, 3, 4]], [[3], [1, 2, 4]], [[4], [2, 3]]]
  38. minimum = 40000
  39. for i in range(0, 40):
  40.     newgraph = graph[:]
  41.     random.shuffle(newgraph)
  42.     while len(newgraph) > 2:
  43.         newgraph = RContraction(newgraph)
  44. #    print min(len(newgraph[0][1]), len(newgraph[1][1]))
  45.     if min(len(newgraph[0][1]), len(newgraph[1][1])) < minimum:
  46.         minimum = min(len(newgraph[0][1]), len(newgraph[1][1]))

  47. print 'minimum = ' + str(minimum)
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-24 10:23:28 | 显示全部楼层
我能够在这边讨论一下选择题么?关于第二题我第一次attempt选错了第二道多项选择题然后它给了我四个对一个错,可是我觉得那些comment有点不对啊,那四个真的是真正答案吗?
另外的是四道选择题答案是log(n)/log(a)吗?
第一道是n-1是吧?
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-24 11:42:49 | 显示全部楼层
麻倉枼 发表于 2014-5-24 10:23
我能够在这边讨论一下选择题么?关于第二题我第一次attempt选错了第二道多项选择题然后它给了我四个对一个 ...

第一题是n-1
第二题应该是选3个
第四题是−log(n)/log(α)呀
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-24 19:06:27 | 显示全部楼层
breezet 发表于 2014-5-23 22:42
第一题是n-1
第二题应该是选3个
第四题是−log(n)/log(α)呀

选三个?哪三个啊,差点被骗了。。至于第四题我第一次attempt是错了,但是第二次不敢选这个的原因是搞不清楚是alpha还是log(a),因为那货说道每次Loop的话至少都有75%长的array n,而我一直找不到log是怎么来的,毕竟这个是O(n)。。。反正我也不知道自己在说神马,请教一下Big O是怎么换算成Log的。。
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-24 20:08:41 | 显示全部楼层
麻倉枼 发表于 2014-5-24 19:06
选三个?哪三个啊,差点被骗了。。至于第四题我第一次attempt是错了,但是第二次不敢选这个的原因是搞不 ...

课上的结论。。选对于每个图大于的两项和存在一个图小于的一项。
第四题就直观理解。。。每次问题的规模都变成原来的\alpha倍,所以n*\alpha^k = 1,解出来就行了
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-24 20:51:34 | 显示全部楼层
breezet 发表于 2014-5-24 07:08
课上的结论。。选对于每个图大于的两项和存在一个图小于的一项。
第四题就直观理解。。。每次问题的规模 ...

我还是不懂你多项题的解释。。

第四题我不知道怎么解可是正如你所说就直观理解的确是这样的。。
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-24 21:03:27 | 显示全部楼层
麻倉枼 发表于 2014-5-24 20:51
我还是不懂你多项题的解释。。

第四题我不知道怎么解可是正如你所说就直观理解的确是这样的。。

课上有结论对于任意一个图的任意一个mincut 都有Pr[] > p,所以肯定选这个
然后还有一个选项是对于任意一个图存在一个mincut都有Pr[] > p,这个比上一个还要弱,肯定选
另外一个是存在一个图和一个mincut 有Pr[] < p,因为特例很容易举

第四题这不就是解法么,它不就是问的递归的数量
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-24 21:14:43 | 显示全部楼层
breezet 发表于 2014-5-24 08:03
课上有结论对于任意一个图的任意一个mincut 都有Pr[] > p,所以肯定选这个
然后还有一个选项是对于任意 ...

呼~~~终于全对了。。
看完你的解释我终于找对了答案,看了至少四遍count min cut。。。可能我不懂的原因是中文太差了。。
第四题我的意思是说我在做题的时候并没有想到你那条equation/ formula。。。完全只在脑中模拟randomized select recrusion
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-24 21:43:05 | 显示全部楼层
麻倉枼 发表于 2014-5-24 21:14
呼~~~终于全对了。。
看完你的解释我终于找对了答案,看了至少四遍count min cut。。。可能我不懂的原因 ...

好吧,我那个所谓的equation大概只相当于对问题建模
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-24 23:24:20 | 显示全部楼层
breezet 发表于 2014-5-24 08:43
好吧,我那个所谓的equation大概只相当于对问题建模

这种技能我是很难驾驭啊
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-25 08:46:10 | 显示全部楼层
麻倉枼 发表于 2014-5-24 23:24
这种技能我是很难驾驭啊

感觉这个还是跟数学关系比较大。。。
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-25 13:14:38 | 显示全部楼层
breezet 发表于 2014-5-24 19:46
感觉这个还是跟数学关系比较大。。。

是的,周一开始攻略程序,话说我已经忘记上这堂课的初衷了,记得一开始是为了以后工作面试而准备的。。可是现在不记得了
回复 支持 反对

使用道具 举报

jlsqsd 发表于 2014-5-26 11:54:27 | 显示全部楼层
我第一个版本也是20,看了半天不知道哪里错,一气之下换个思路从头写,得出正确答案,回头看第一个版本,至今不知道哪里错
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-29 17:48:09 | 显示全部楼层
本帖最后由 麻倉枼 于 2014-5-29 05:23 编辑
breezet 发表于 2014-5-21 21:00
我感觉问题可能出在把其他点的连接也由node2改成node1的部分,如果其他点之前已经跟node1相连的话这样似乎 ...

关于编程题真心跪了,目前答案最少的可以得到1。。可是答案还是错呀。。我都不知道debug了多少次,请问你能给点建议吗?

目前状况是:0. randomly create mainVertex and subVertex; if they are not the same, proceed the following:

1. 把subVertex 的Edge 全加进mainVertex Edge List;

2. remove duplicate mainVertex from the mainVertex Edge List;

3. remove all subVertex from every Edge List in the graph;

4. validate if duplicate mainVertex is removed and all subVertecies are removed;

5. if yes, then count each subVertex from the mainVertex EdgeList and count the number of mainVertecies from each subVertex's Edge List, and then modify each subVertex Edge List until it got the same number of mainVertex as the number of subVertex in the mainVertex Edge List;

6. repeat until the graph contains only two Vertecies.
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-29 18:16:15 | 显示全部楼层
麻倉枼 发表于 2014-5-29 17:48
关于编程题真心跪了,目前答案最少的可以得到1。。可是答案还是错呀。。我都不知道debug了多少次,请问你 ...

I think your ideas are not so clear, maybe it should not be so complicated. I run it as follows.

0. Create a Vertex structure which contains vertex list and edge list, originally every Vertex contains 1 vertex and some edges
1. Randomly choose a vertex A to merge, and randomly choose a vertex B in its edge list
2. Merge the vertex B into A, so A's vertex list now contains A and B, and merge B's edge list into A's, delete B
3. Loop around A's new edge list, find the edge connected to A or B and delete
4. Repeat until the graph contains only 2 vertices
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-29 18:25:51 | 显示全部楼层
breezet 发表于 2014-5-29 05:16
I think your ideas are not so clear, maybe it should not be so complicated. I run it as follows.
...

一个问题,刚刚看文档发现的,就是A这个点每一次loop都会换么?我意思说目前我的想法是每一次Loop
A和B都会randomized generated,而我看到的好像A is a pivot? only B will be randomized generated every loop?
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-29 20:45:43 | 显示全部楼层
麻倉枼 发表于 2014-5-29 18:25
一个问题,刚刚看文档发现的,就是A这个点每一次loop都会换么?我意思说目前我的想法是每一次Loop
A和B ...

是的,是每一次都会换的
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-5-30 00:15:44 | 显示全部楼层
本帖最后由 麻倉枼 于 2014-5-29 20:57 编辑
breezet 发表于 2014-5-29 07:45
是的,是每一次都会换的

我的程序好像跪了,一个小graph的话还是OK的,但是要运行很多遍才能找到min cut (在知道真正答案的情况下),

但是作业上面那个真心各种不解。。现在一个很大的bug实在找不出原因来。。while loop 和 for loop各种测试了都还是不行,这个bug是这样的:

在程序某部分我要把mainVertex的edge list整理一下,整理的内容为查看里面是否存在self loop,意思说list里面会有mainVertex出现,如果出现的话就把它删掉。。

然后bug就是如果我运行作业的文件的话,最后的两个vertex 的size不一致,原因就是self loop出现了。。

于是我干脆就写了一个Loop,把graph里面每一个edge list和每一个vertex分别检查一遍,反正无伤大雅。。
实在不知道怎么查bug了,其中最有可能出现问题是这部分可以看看吗?逻辑上的问题。。

前提:
1. graph是用 hashMap的;
2. Long currentVertex = 0L;
3. ArrayList<Long> currentEdgeList = null;

// remove every duplicate vertex from this current vertex edge list;
                                while(i < graph.size()){
                                       
                                        currentVertex = keyList.get(i);
                                        currentEdgeList = graph.get(currentVertex);

                                        int w = 0;
                                        while(w < currentEdgeList.size()){      //这里进去后      *** 有时候这里连进去都没进去,但出来后能查到size的确存在的,list还是有内容
                                                if(currentEdgeList.get(w) == currentVertex){    //这里压根没检查     ***然后这里压根没跑
                                                        graph.get(currentVertex).remove(w);
                                                        
                                                        System.out.println("CurrentVertex = " + currentVertex);
                                                        System.out.println("CurrentVertex Edge List = " + graph.get(currentVertex) + "\n");
                                                        
                                                        w = 0;
                                                        currentEdgeList = graph.get(currentVertex);
                                                }
                                                else{
                                                        w++;                    ***  这里却一直有Loop
                                                }
                                        }
                                       
                                        //System.out.println("In duplicte vertex while loop!!!! "  + "\n");
                                        i++;                 ***这里也有loop,最终数字和graph.size()一致
                                }


真心被压倒了,两天没睡觉了。。今天无论如何都睡一下,反正您都给了答案了。。


/***********************  更新 ***************************/
终于找到这个逆天的bug了!!
低级错误但是很有杀伤力,基础不好的人基本上就是要像我一样熬夜去吧。。。
答案就是Long, 不是long。。。。@~@
然后。。。让有缘人去解读这个bug。。。
回复 支持 反对

使用道具 举报

breezet 发表于 2014-5-30 09:21:01 | 显示全部楼层
麻倉枼 发表于 2014-5-30 00:15
我的程序好像跪了,一个小graph的话还是OK的,但是要运行很多遍才能找到min cut (在知道真正答案的情况 ...

其实我觉得你在15楼提到的整体思路不是很清楚,容易带来问题。。。如果单纯的看这一部分,倒没有什么问题。运行很多遍才找到也是正常的,我的一般运行40遍。

我觉得你的思路问题出在3和5上,先删掉了所有subVertex后面又modify each subVertex Edge List,虽然我不能很清楚的假设一种情况,但是直观上看这样会改变graph的结构,而且这种方法有点不“美”,我还是建议你不要删掉subVertex再modify而是直接用我提到的merge的办法,这样不需要改其他vertex的Edge
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 22:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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