java - Karger MinCut Java Large Input Error 的 Minimum Cut

Question

一段时间以来，我一直在努力解决这个问题。实际上已经好几个星期了，但我已经用尽了可能的解决方案或修改。所以该算法是随机 Karger 最小切割算法，下面提供了我的实现:

算法:

用于无向图。每个顶点都作为键存储在 hashmap 中，其相邻顶点作为 arraylist 存储在 hashmap 的值中，例如

如果测试用例是:

1   2   6
2   1   3   4   5
3   2   4
4   2   3   5
5   2   4   6
6   1   5

其中第一列是键，与它们相邻的数字是它的值(数组列表)。

我的算法是

1. 选择一个名为“i”的第一个出现的顶点，该顶点具有 2 个以上的相邻顶点(在本例中为 2 个)
2. 虽然“i”的列表中有两个以上的数字
3. 随机选择一个称为“U”的相邻顶点
4. 将“U”与“i”合并(将它与另一个称为“V”的顶点合并不会给出正确答案)
5. 现在检查新“i”的列表是否包含“i”本身并将其删除。 (自循环)
6. 将新“i”的列表交叉引用到其他顶点

7. 删除“U”(键)，例如，如果“U”为 6，更新后的顶点将如下所示:

   1   2   6   2
   2   1   3   4   5   1   5
   3   2   4
   4   2   3   5
   5   2   4   6   2
   

8. 因此，当“i”将具有唯一编号时，算法将终止(通过将“i”的列表添加到 Set 来完成)。例如:

   2   6   6
   
   6   2   2
   

所以对于给定的图，这是 2 个最小切割。

代码:

我在java中对上述算法的代码如下:

package practice;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class MinCut {
static Map <Integer,ArrayList <Integer>> vertices=new HashMap <Integer,ArrayList <Integer>>() ;
static Random random= new Random ();
static int SIZE=0;
static TreeSet <Integer> minSize= new TreeSet <Integer> ();
static int reps=0;
static ArrayList <Integer> uTracker= new ArrayList <Integer> ();
public static void main(String[] args) {

    int reps2=0;
    for (int i=0;i<=10;i++){
        minCutCalc();
        TreeSet <Integer> trackSet= new TreeSet <Integer> ();
        if (!uTracker.isEmpty()){
            Collections.sort(uTracker);
            for (int o=0;o<uTracker.size();o++){
                System.out.println("uTracker: "+uTracker.get(o));
                if (!trackSet.add(uTracker.get(o))){
                    reps2++;
                }
            }
            //to check "U"s in every run
            uTracker.clear();
        }
    }

    //prints the lowest number in the set hence the minimum cut
    System.out.println("The attempted minimum cut is: "+minSize.first());
    System.out.println("FINAL REPS: "+reps2);

}
private static void minCutCalc() {

    readMap();
    int i=0;

    i=selectVertex(1);

    //for testing purposes
    System.out.println(" \"i\" is: "+i);

    if (vertices.get(i) != null){
        Set <Integer> tempSet= new LinkedHashSet <Integer> ();


        while (vertices.get(i).size()>2){
            /*to remove any instances of "i" copied into list from other vertices
             * to avoid getting "i" selected as "U" in random numbers as then "U"
             * will be deleted hence showing result as "null"
             */
            for (int l=0;l<vertices.get(i).size();l++){
                for (int c=0;c<vertices.get(i).size();c++){
                    if (vertices.get(i).get(c)==i){
                        int index=vertices.get(i).indexOf(i);
                        System.out.println("Yes it contains "+i+": "+vertices.get(i).get(index));
                        vertices.get(i).remove(index);
                    }
                }

            }

            //for testing purposes
            System.out.println("\"i\" is: "+i);
            for (int j=0;j<vertices.get(i).size();j++){
                System.out.println("\n"+"LIST DISPLAY: "+vertices.get(i).get(j));
            }

            if (!tempSet.isEmpty()){
                tempSet.clear();
            }
            tempSet.addAll(vertices.get(i));

            //if there is only one occurrence of a number in the list
            if (tempSet.size()==1){
                break;
            }

            int U=selectRandom(i,vertices);

            //for testing purposes
            System.out.println("PRINT u: "+U);
            //to check if unique "U"s are selected each time
            uTracker.add(U);
            for (int n=0;n<vertices.get(U).size();n++){
                System.out.println("\"U\" List: "+vertices.get(U).get(n));
            }

            //merging "U"'s vertices to "i"
            if (vertices.containsKey(U)){
                vertices.get(i).addAll(vertices.get(U));
                for (int y=0;y<vertices.get(U).size();y++){
                    System.out.println(vertices.get(U).get(y));

                    //cross referencing "i" to rest of the vertices in "U"'s list
                    if (vertices.get(U).get(y)!=i){
                        vertices.get(vertices.get(U).get(y)).add(i);
                    }

                }
            }

            vertices.remove(U);

            //if any of the vertices consists of "U" as its edge it will be deleted
            for (int t=1;t<=SIZE;t++){
                if (vertices.containsKey(t)){
                    for (int y=0;y<vertices.get(t).size();y++){
                        for (int z=0;z<vertices.get(t).size();z++){
                            if (vertices.get(t).get(z)==U){
                                int index=vertices.get(t).indexOf(U);
                                vertices.get(t).remove(index);
                            }

                        }
                    }
                }
            }

            //for testing purposes
            System.out.println("\"i\" is: "+i);
            for (int j=0;j<vertices.get(i).size();j++){
                System.out.println("LIST \"AFTER\" DISPLAY: "+vertices.get(i).get(j));
            }

            //null check
            if (vertices.get(i)==null){
                System.out.println("This is null: "+i);
                break;
            }
        }
    }

    //to check the final result
    for (int o=1;o<=SIZE;o++){
        System.out.println(" SHOW at "+o+" index: "+vertices.get(o));
        if (vertices.get(o)!=null){
            //minimum cuts (size of current list) are added to a set
            minSize.add(vertices.get(o).size());
        }
    }

    System.out.println("Total Number of Repititions: "+reps);
}

private static void readMap() {
    try {
        FileReader file= new FileReader("C:\\xyz\\Desktop\\testMinCut.txt");
        BufferedReader reader= new BufferedReader(file);
        String line="";

        while ((line=reader.readLine())!=null){
            String [] lineArr;
            lineArr=line.split("\t");

            int vert1=Integer.parseInt(lineArr[0]);

            vertices.put(vert1,new ArrayList <Integer> ());

            for (int p=1;p<lineArr.length;p++){
                int vert2=Integer.parseInt(lineArr[p]);
                vertices.get(vert1).add(vert2);
            }
        }
        SIZE=vertices.size();
    } catch (FileNotFoundException e) {
        System.err.println(e.toString());
    } catch (IOException e) {
        System.err.println(e.toString());
    }

}
private static int selectVertex(int i) {
    LinkedHashSet <Integer> storer= new LinkedHashSet <Integer> ();

    for (int s=1;s<=SIZE;s++){
        if (vertices.get(s)!=null){
            if (!storer.isEmpty()){
                storer.clear();
            }
            storer.addAll(vertices.get(s));
            if (storer.size()>2){
                i=s;
                break;
            }
            else {
                i=0;
            }
        }

    }

    return i;
}

private static int selectRandom(int i, Map<Integer, ArrayList<Integer>> vertices) {

    int u;
    int U = 0;

    LinkedHashSet <Integer> tempSet2= new LinkedHashSet <Integer> ();
    tempSet2.addAll(vertices.get(i));

    u=random.nextInt(tempSet2.size());

    Set <Integer> uSet=new HashSet <Integer> ();
    Set <Integer> uSet2=new HashSet <Integer> ();

    //to reassure unique "u" is selected each time
    if (!uSet.isEmpty() && uSet.contains(u)){
        u=random.nextInt(tempSet2.size());
        reps++;
    }

    uSet.add(u);

    U=vertices.get(i).get(u);
    //ensuring unique "U" is selected
    if (uSet2.contains(U)){
        u=random.nextInt(tempSet2.size());
        U=vertices.get(i).get(u);
        reps++;
    }

    uSet2.add(U);

    tempSet2.clear();

    return U;
}

}

问题:

我面临的问题是，除了一个由 200 个顶点组成的非常大的测试用例之外，该算法对我遇到的几乎所有测试用例都运行良好。正确答案应该是 17，但我一直得到的答案是“20”。我跟踪了所有选择的“U”。显然它们都是独一无二的，没有任何重复，我不断得到答案“20”。有什么建议吗？再次感谢。测试用例的链接是:

http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt

注意:

这不是家庭作业，而是我在 coursera 的在线类(class)(算法设计和分析)中看到的我正在研究的练习题。现在类(class)结束了。非常感谢你提前。我再次问这个问题，因为我第一次无法得到答案。如果我能提供任何帮助，我将不胜感激，因为我已经研究了很长一段时间，所以这个问题对我造成了伤害。

Answer 1

所以我设法让它工作并得到正确答案。问题在于随机边缘选择。因为我首先选择一个顶点(它有超过 2 条边)然后从那个顶点选择一条边，这是错误的方法，因为并非所有边都均匀分布在顶点之间。所以这是我改进的算法:

为集合中的所有边保留一个列表

1. 当边列表中还剩2条以上的边时
2. 从边列表中随机选择一条边并将其命名为 V
3. 然后从 V 中选择另一个随机边(因为我的实现是 HashMap，所以获取值，它是键值“V”的数组列表)列表并称之为“U”
4. 合并 U 和 V 以形成合并边
5. 从边缘列表中删除 U(因为我合并了 U 的列表，这意味着它 到 V 的边因此组合边只是 V，所以在合并 U 和 V 之后成为一个 super 边，称为“V”)

希望这对某人有帮助。