1

グラフの最大独立集合を見つけるアルゴリズムをコーディングしました。定義によると、独立集合は「グラフのすべての辺が S にない少なくとも 1 つの端点を持ち、S にないすべての頂点が S に少なくとも 1 つの隣接点を持つような集合 S」です。

以下に示すように、グラフは無向グラフです。

ノード: 1,2,3,4,5,6,7 エッジ: 1-2,2-3,3-4,4-5,5-6,6-7,1-5

そして、ここに私の実装があります：

FindMIS fms= new FindMIS(network);


public class FindMIS {

INetwork network;

public FindMIS(INetwork network) {

    this.network = network;
    ArrayList<INode> nodes = new ArrayList<>();
    nodes.addAll(network.getNodesList());
    Iterator<INode> iter = nodes.iterator();
    ArrayList<INode> IS = new ArrayList<>();
    while (iter.hasNext()) {
        INode node=iter.next();
        visitNode(node, IS, nodes);

    }


}

private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode>   

previousCandidates) {


    ArrayList<INode> IS=new ArrayList<>();
     IS.addAll(previousIS);
    ArrayList<INode> candidates = new ArrayList<>();

    candidates.addAll(previousCandidates);
    //System.out.println(node);
    ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node);
    for (INode n : previousCandidates) {
        if (neighbor.contains(n)) {
            candidates.remove(n);
        }

    }
    IS.add(node);

    candidates.remove(node);
    Iterator<INode> iter = candidates.iterator();
    while (iter.hasNext()) {
        visitNode(iter.next(), IS, candidates);
    }
    if (candidates.size()==0){
         Iterator<INode> iter2=IS.iterator();
    System.out.print("output:{" );
    while(iter2.hasNext()){
        System.out.print(iter2.next().getid());
    }
        System.out.println("}");
    }




   }
}

出力は以下のとおりです。

output:{1 3 6 }
output:{1 4 6 }
output:{1 6 3 }
output:{1 6 4 }
output:{2 4 6 }
output:{2 4 7 }
output:{2 5 7 }
output:{2 6 4 }
output:{2 7 4 }
output:{2 7 5 }
output:{3 1 6 }
output:{3 5 7 }
output:{3 6 1 }
output:{3 7 5 }
output:{4 1 6 }
output:{4 2 6 }
output:{4 2 7 }
output:{4 6 1 }
output:{4 6 2 }
output:{4 7 2 }
output:{5 2 7 }
output:{5 3 7 }
output:{5 7 2 }
output:{5 7 3 }
output:{6 1 3 }
output:{6 1 4 }
output:{6 2 4 }
output:{6 3 1 }
output:{6 4 1 }
output:{6 4 2 }
output:{7 2 4 }
output:{7 2 5 }
output:{7 3 5 }
output:{7 4 2 }
output:{7 5 2 }
output:{7 5 3 }

You can realize that there are some redundant sets like {1,3,6} and {1,6,3}. The final result must be:

output:{1 3 6}
output:{1 4 6}
output:{2 4 6}
output:{2 4 7}
output:{2 5 7}
output:{3 5 7}

I am trying to figure out a way to avoid unnecessary computation. 
I appreciate for any idea.

UPDATE :1 : Darryl Gerrow の返信の後、次のように visitNode メソッドを変更しました。アルゴリズムを読みやすく、移植しやすくするために、アルゴリズムにはまだいくつかの問題があります。完成したらいつでも最終版を投稿します。すべてのコミュニティに感謝します。すべてのノードを探すだけでなく、グラフ内の最大独立集合を見つける方法を誰かが知っている場合は、読んでいただければ幸いです。

private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode>    

previousCandidates) {


    ArrayList<INode> IS=new ArrayList<>();
     IS.addAll(previousIS);
    ArrayList<INode> candidates = new ArrayList<>();

    candidates.addAll(previousCandidates);
    //System.out.println(node);
    ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node);
    for (INode n : previousCandidates) {
        if (neighbor.contains(n)) {
            candidates.remove(n);
        }

    }
    IS.add(node);

    candidates.remove(node);


    Iterator<INode> iter = candidates.iterator();
    while (iter.hasNext()) {
       INode nextnode=iter.next();
       if (node.getid() < nextnode.getid())
        visitNode(nextnode, IS, candidates);
    }
    if (candidates.size()==0){
         Iterator<INode> iter2=IS.iterator();
    System.out.print("output:{" );
    while(iter2.hasNext()){
        System.out.print(iter2.next().getid() +" ");
    }
        System.out.println("}");
    }




}

}

4

1 に答える 1

0

n 乗反復を行っているように見えるため、{1, 3, 6}、{1, 6, 3}、{3, 6, 1}、....基本的にすべて許容可能なセットの可能な組み合わせ。

現在のノードよりも大きなノードのみにアクセスするように、反復を書き直す必要があると思います。

すなわち。{1, 3, 6} が得られますが、6 > 3 であるため、{1, 6, 3} は受け入れられません。

Iterator を削除して、ArrayList のインデックス メソッドを使用する必要がある場合があります。

于 2013-09-04T17:16:32.853 に答える