1

私はしばらくの間、これを修正しようと取り組んでいます。実際にはかなりの数週間が経ちましたが、可能な解決策や修正を使い果たしました。したがって、アルゴリズムは Randomized Karger Minimum Cut Algorithm であり、私の実装は以下のとおりです。

アルゴリズム:

無向グラフ用です。各頂点はハッシュマップのキーとして保存され、隣接する頂点はハッシュマップの値の配列リストとして保存されるため、たとえば

テスト ケースが次の場合:

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

ここで、最初の列はキーであり、それらに隣接する数字はその値 (arraylist) です。

私のアルゴリズムは

  1. 2 つ以上の隣接する頂点 (この場合は 2 つ) を持つ "i" と呼ばれる最初に発生する頂点を選択します。
  2. 「i」のリストに2つ以上の数字がある間
  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 個の頂点からなる 1 つの非常に大きなテスト ケースを除いて、私が遭遇したほぼすべてのテスト ケースで完全に機能することです。正解は 17 のはずですが、「20」と答え続けます。選択したすべての「U」を追跡しました。どうやらそれらはすべて重複せずに一意であり、「20」という答えが得られ続けています。アドバイスをお願いします。もう一度ありがとう。テストケースへのリンクは次のとおりです。

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

注意:

これは宿題ではなく、coursera のオンライン コース (アルゴリズムの設計と分析) で見た練習問題です。これでコースは終了です。事前にどうもありがとうございました。最初に答えを得ることができなかったので、この質問をもう一度します。私はかなり長い間それに取り組んできたので、この質問が私に負担をかけていると言ったので、提供された助けに感謝します.

4

1 に答える 1

2

だから私はそれを機能させて正しい答えを得ることができました。問題は、ランダムなエッジ選択にありました。最初に頂点 (2 つ以上のエッジを持つ) を選択し、次にその頂点からのエッジを選択していたため、すべてのエッジが頂点間で均等に分散されているわけではないため、間違ったアプローチでした。だからここに私の改善されたアルゴリズムがあります:

Set 内のすべてのエッジのリストを保持する

  1. エッジ リストに 2 つ以上のエッジが残っていますか?
  2. エッジ リストからランダムなエッジを選択し、それを V と呼びます
  3. 次に、V から別のランダムなエッジを選択します (私の実装は HashMap であるため、キー値の配列リストである値を取得します (「V」) リスト & それを「U」と呼びます)。
  4. U と V を組み合わせて結合エッジを作成する
  5. エッジ リストから U を削除します (U のリストを結合したため、そのエッジを V に意味するため、結合されたエッジはちょうど V でした。したがって、U と V をマージした後、単に「V」と呼ばれるスーパー エッジになりました)

うまくいけば、それは誰かに役立つでしょう。

于 2013-09-21T16:22:36.190 に答える