Set Cover問題のブランチとバインドされたアルゴリズム？

Question

Set Coverの問題を解決するためにブランチとバインドされたメソッドを使用するJavaプログラムを誰かと共有できますか？ 以下は私がこれまで持っていたものです。したがって、各段階で、アルゴリズムは1組をとり、問題の2つのインスタンスを取得することになっています。1.配列リストから最初のセットを選択します。2. arraylistから最初のセットを取りません。 この時点では、ブランチを開始してバインドする方法について固執しています。

import java.util。*;

public class BranchAndBound { 
    static int bestSoFar=100; 
    static int count=0; 
    public static void main(String args[]){ 

    //create the universe 
    int numU = 10; 
    MySets universe = new MySets(); 
    for(int i=1;i<=numU;i++){ 
      universe.add(i); 
    } 

    //create each set 
    MySets s1 = new MySets(); 
    MySets s2 = new MySets(); 
    MySets s3 = new MySets(); 
    MySets s4 = new MySets(); 
    MySets s5 = new MySets(); 

    ArrayList<MySets> s=new ArrayList<MySets>(); 
    //elements 
    s1.add(1);s1.add(2);s1.add(3);s1.add(8);s1.add(9);s1.add(10); 
    s2.add(1);s2.add(2);s2.add(3);s2.add(4);s2.add(5); 
    s3.add(4);s3.add(5);s3.add(7); 
    s4.add(5);s4.add(6);s4.add(7); 
    s5.add(6);s5.add(7);s5.add(8);s5.add(9);s5.add(10); 

    s.add(s1);s.add(s2);s.add(s3);s.add(s4);s.add(s5); 
    branchAndBound(universe,s,0); 

    } 

    public static void branchAndBound(MySets U,ArrayList<MySets> listSets,int countSelected){ 
     MySets universe = new MySets(); 
     universe.addAll(U); 

     ArrayList<MySets> s=new ArrayList<MySets>(); 
     s.addAll(listSets); 

     MySets selectedSet= new MySets(); 

     selectedSet.addAll(listSets.get(0)); 
     count++; 

     universe.removeAll(selectedSet);//the universe now contains the elements still need to be covered 
     listSets.remove(0);//remove the first elemeent from the list 

     displaySet(selectedSet, "selected set"); 
     displaySet(universe, "universe"); 

     while(!universe.isEmpty() && !listSets.isEmpty()){ 
      branchAndBound(universe,listSets,count); 
     } 
    } 




public static void displaySet(MySets s, String name){ 
    System.out.print(name+"==>"); 
    Iterator it=s.iterator(); 
    while(it.hasNext()){ 
     Integer value=(Integer)it.next(); 
     System.out.print(+value+" "); 
    }//while 
    System.out.println(); 
}//displaySet 
} 

Answer 1

私は以前同様の質問と関連する質問をしたと思いますhere。そこに指摘されているように、Set CoveringはNP困難です。したがって、多項式アルゴリズムは存在しないことが知られている。あなたが問題の詳細を抽象化するとき、それは整数プログラム（IP）です。したがって、MS-Excelで提供されているような汎用IPソルバを使用できます。すべての一般的な整数計画問題は、分岐と結合方法を使って解決されます。つまり、Set Coveringだけでは特に必要はありません。あなたがする必要があるのは、集合の問題を整数計画として定式化し、それを残りのものを処理するソルバーに提供することだけです。 SOの従業員は、あなたと共有できる既製のコードを持つことはまずありません。 （整数プログラミングの基礎をなす）整数プログラミング/線形プログラミングは非常に詳細で特殊化されています。