📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5068| 回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

[入门|算法|数据结构] 算法可第三周的编程作业题讨论

全局:
公开课
学校名称: Stanford
Unit号: 3
开课时间: 2014-04-28
课程全名: Design and Analysis of Algorithm
平台: Coursera

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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. }
复制代码

上一篇:求推荐MFE的公开课
下一篇:[Coursera]程序设计实习 / Practice on Programming (week12) 加分&amp;讨论帖
推荐
麻倉枼 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。。。
回复

使用道具 举报

推荐
麻倉枼 2014-5-30 10:08:43 | 只看该作者
全局:
breezet 发表于 2014-5-29 20:21
其实我觉得你在15楼提到的整体思路不是很清楚,容易带来问题。。。如果单纯的看这一部分,倒没有什么问题 ...

我的结构是用hashmap的,
其实我也有key list,
然后就是bug让我找到了,压根不是逻辑问题而是别的,
另外就是现在解决这个bug发现Min cut 数字很大啊,最低极限是20,无法突破到17。。

我举个例子吧。。
V       E
1        2        3        4        7       
2        1        3        4       
3        1        2        4       
4        1        2        3        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7       

Round 1:
mainVertex = 2
subVertex = 3

step 1: add all subV EdgeList to mainV
V       E
1        2        3        4        7       
2        1        3        4        1        2        4
3        1        2        4       
4        1        2        3        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

step 2: remove subV from the graph
V       E
1        2        4        7       
2        1        4        1        2        4
4        1        2        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

step3: removed self loop from each edgeList, current mainV = 2
V       E
1        2        4        7       
2        1        4        1        4
4        1        2        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

IMPORTANT STEP: modify each subV that is in the mainV edgeList, count how many of each, and then modify its edge list; EX: 1 在 2的edgeList 出现两次,所以我们跳到1的edge list 数有多少个2, 如果少过两次的话,加2直到有两次为止;然后如此类推

V       E
1        2        4        7        2
2        1        4        1        4
4        1        2        5        2
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

End of Round 1
回复

使用道具 举报

推荐
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大米 +10 收起 理由
sanguine + 10

查看全部评分

回复

使用道具 举报

🔗
麻倉枼 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大概只相当于对问题建模
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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