Java 求解集合覆盖问题

集合覆盖问题是组合优化技术中一个著名的NP困难问题。我们将集合覆盖问题称为NP-Hard，因为针对这个特定问题没有多项式实时解决方案可用。贪心启发式算法是一种针对集合覆盖问题的著名算法。

以下是一个示例：

Let U be the universe of elements, {S1, S2,.....Sm} be collection of subsets of the set, U and Cost(S1), C(S2),......Cost(Sm) be costs of subsets.
1)Let I is the set of elements included so far.  
  Initialize the process I = {}
2) Do following while I is not same as U.
   a) Find the set Si = {S1, S2, ... Sm} whose cost effectiveness is 
      smallest, i.e., the ratio of cost C(Si) and number of newly added 
      elements is minimum. 
      Basically we pick the particular set for which following value is minimum.
      Cost(Si) / |Si - I| - is the possible equation here. 
   b) Add elements of above picked the Si to I, i.e.,  I = I U Si

解决一组覆盖问题的算法

在这个特定的算法中，我们试图向您展示如何使用Java虚拟机来解决一组覆盖问题。

• 步骤1 – 开始。

• 步骤2 – 声明可能的集合和数值组合作为输入。

• 步骤3 – 将它们都放入一个数组中。

• 步骤4 – 创建一个列表。

• 步骤5 – 将数据存储在其中。

• 步骤6 – 调用最短组合作为函数。

• 步骤7 – 该函数将该集合作为输入。

• 步骤8 – 它抛出异常。

• 步骤9 – 如果大小超过20。

• 步骤10 – 否则，过程向前移动并进入下一个。

• 步骤11 – 迭代所有可能组合的大小。

• 步骤12 – 为此我们需要一个新的集合。

• 步骤13 – 运行操作后，将值向右移动。

• 步骤14 – 将其结束为1。

• 步骤15 – 将所有解决方案添加到该数组中。

• 步骤16 – 从数组中消除重复值。

• 步骤17 – 终止进程。

解决一组覆盖问题的语法

Set i / i1*i6 / ;
Set k / k1*k6 / ;
Table d(i,k)
k1 k2 k3 k4 k5 k6

i1 1 1 0 1 0 0

i2 1 1 1 0 0 0

i3 0 1 1 0 0 1

i4 1 0 0 1 1 0

i5 0 0 0 1 1 1

i6 0 0 1 0 1 1 ;


Binary Variable Y(k);
Variables
z "Set Covering"
Equation AgebtoPtoEnc , Def_obj ;
AgebtoPtoEnc..
sum(k, Y(k)*d[i,k)) =g= 1 ;
Def_obj..
z =e= sum(k, Y(k));
Model setcovering / all / ;
Solve setcovering using mip minimizing z;
Display z.l, y.l ;

这里是使用Java环境解决集合覆盖问题可能的语法。在这个语法中，我们使用了一些可能的方法，这些方法将帮助你理解下面提到的Java代码。

可采取的方法

• 方法1−使用贪心算法解决集合覆盖问题的Java程序，其中一个子集中最多包含两个元素的值

• 方法2−使用一个过滤器类解决集合覆盖问题的Java程序，其中一个子集中最多包含两个元素的值

方法1：使用贪心算法解决集合覆盖问题的Java程序，其中一个子集中最多包含两个元素的值

在这个特定的Java代码中，我们尝试展示如何使用贪心算法解决一个集合覆盖问题，其中一个子集中最多包含两个最大元素。

示例1

// Importing some of the input output classes as declaration
import java.io.*;
// Importing some utility classes from the java.util package
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

// Main class here is ARBRDD, as we declared here
public class ARBRDD {

    // Interface Declaration Of The Process
    // Declaring the interface class by taking some abstract methods to operate the interface class
    interface Filter<T> {
      boolean matches(T t);
    }

    // Method 1's declaration for the Set Cover Solving
    // Declaring a combo method. The method is a -'shortcombo'
    // Declaring in a form of set the outputs. A also returning a particular set as an output
    private static <T> Set<T>
    shortcombo(Filter<Set<T> > filter, List<T> sets){
      // Set a particular range as the size of the working set 
      final int size = sets.size();

      // Condition check to run the method 
      // If the size of the content is greater than 25 then--->
      // We will throw an exception a pop up of too many combinations present here 
      if (size > 20)
        throw new IllegalArgumentException(
            "Too many Combinations present here ---->");

      // Now the combination will left here shift 1 process time of size in total
      int comb = 1 << size;

      // Taking an another set with reference as soon possible
      // this Arraylist combination will contain all of the possible solution present here in the process
      List<Set<T> > possible = new ArrayList<Set<T> >();

      // Declaring a for loop which iterates all the logics till combination
      for (int i = 0; i < comb; i++) {

        // lInkedHashSet of reference declaration
        // combination we run this code properly
        Set<T> combination = new LinkedHashSet<T>();

        // Taking a loop and iterating till the size present in that combination  
        for (int j = 0; j < size; j++) {

            // If we perforn the right shift i and j, and then ending it with 1 - it will be the process

            // This possible logic will give us how many combinations are possible at least now in this process
            if (((i >> j) & 1) != 0)

                // Now set combinations are added to the
                // array list
                combination.add(sets.get(j));
        }

        // Now add to the particular possible reference here
        possible.add(combination);
      }
      // using the sort() method over Collections class, we can sort the collection at least
      Collections.sort(
        possible, new Comparator<Set<T> >() {

            // Find the minimum length of this process by taking
            // the difference is here between the total sizes of possible characters
            // present here list
            public int compare(Set<T> a1, Set<T> a2)
            {
                return a1.size() - a2.size();
            }
        });

      // Now we can take the particular iteration process till we can streach possible
      for (Set<T> possibleSol : possible) {

        // Then we check about the matching of the present possible solution

        // If it does
        //return the solution from the process
        // If it doesnot 
        //return the null value
        if (filter.matches(possibleSol))
            return possibleSol;
      }
      return null;
    }

    //Introduction of the Method 2 for the process code
    //Here it is the main method as declared
    public static void main(String[] args){

      // Taking all the possible combinations with some custom entries present in an array
      Integer[][] all = {
         { 1, 2 },  { 3, 4 }, { 8, 9 },
         { 16, 7 }, { 5, 8 }, { 11, 6 },
         { 4, 5 },  { 6, 7 }, { 10, 11 },
      };

      // Some Numbers From The List Choose From The List
      // Again, custom entries making in an array
      Integer[] solution
        = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };

      // Here let us take a set to run the logic to pass the code again
      List<Set<Integer> > sets
        = new ArrayList<Set<Integer> >();

      // Now, take an array of the function all to represent the array
      for (Integer[] array : all)

        // Now taking those elements to add them 
        // in an LinkedHashSet itself
        sets.add(new LinkedHashSet<Integer>(Arrays.asList(array)));

      // Now taking the set of the integer sol present and
      // setting it as a solution for the list
      final Set<Integer> sol = new LinkedHashSet<Integer>(Arrays.asList(solution));

      // Now taking funnel filter for checking the particular values
      Filter<Set<Set<Integer> > > filter
        = new Filter<Set<Set<Integer> > >() {
            // Now taking a boolean function which matches
            // The function helps to iterate all the values
            // over those integers we have a variable which adds
            // up all that to an union set which will give
            // us the new desired result based on logic
            public boolean matches(
                Set<Set<Integer> > integers) {
                Set<Integer> union = new LinkedHashSet<Integer>();

                // Iterating the whole method by using for-each loop instead
                for (Set<Integer> ints : integers)
                  union.addAll(ints);

                return union.equals(sol);
            }
        };

      // Now the below set present here, will call the particular short combo here
      // This function wil used to sort the shortest from a
      // combo present here
      Set<Set<Integer> > firstSol= shortcombo(filter, sets);

      // Print and display out the same logic for the process
      System.out.println("The short combination present here ---> : "+ firstSol);
    }
}

输出

The short combination present here ---> : [[1, 2], [3, 4], [8, 9], [5, 8], [6, 7], [10, 11]]

方法2：Java程序解决集合覆盖问题，通过使用过滤器类来确定子集中最大两个元素的值

在这个特定的Java构建代码中，我们使用了预定义的过滤器类接口来解决集合覆盖问题，该问题的最大值为最大两个元素的值。

示例2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class SetCoverMax2Elem {
   interface Filter<T>{
      boolean matches(T t);
   }

   private static <T> Set<T> shortestCombination(Filter<Set<T>> filter,List<T> listOfSets){
      final int size = listOfSets.size();
      if (size > 20)
         throw new IllegalArgumentException("Too many combinations");
      int combinations = 1 << size;
      List<Set<T>> possibleSolutions = new ArrayList<Set<T>>();
      for (int l = 0; l < combinations; l++){
         Set<T> combination = new LinkedHashSet<T>();
         for (int j = 0; j < size; j++){
            if (((l >> j) & 1) != 0)
            combination.add(listOfSets.get(j));
         }
         possibleSolutions.add(combination);
      }
      // the possible solutions in order of size.
      Collections.sort(possibleSolutions, new Comparator<Set<T>>(){
         public int compare(Set<T> o1, Set<T> o2){
            return o1.size() - o2.size();
         }
      });
      for (Set<T> possibleSolution : possibleSolutions){
         if (filter.matches(possibleSolution))
         return possibleSolution;
      }
      return null;
   }
   public static void main(String[] args){
      Integer[][] arrayOfSets = { { 1, 2 }, { 3, 8 }, { 9, 10 }, { 1, 10 },
         { 2, 3 }, { 4, 5 }, { 5, 7 }, { 5, 6 }, { 4, 7 }, { 6, 7 },
         { 8, 9 }, };
      Integer[] solution = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
      List<Set<Integer>> listOfSets = new ArrayList<Set<Integer>>();
      for (Integer[] array : arrayOfSets)
         listOfSets.add(new LinkedHashSet<Integer>(Arrays.asList(array)));
      final Set<Integer> solutionSet = new LinkedHashSet<Integer>(
         Arrays.asList(solution));
      Filter<Set<Set<Integer>>> filter = new Filter<Set<Set<Integer>>>(){
         public boolean matches(Set<Set<Integer>> integers) {
            Set<Integer> union = new LinkedHashSet<Integer>();
            for (Set<Integer> ints : integers)
            union.addAll(ints);
            return union.equals(solutionSet);
         }
      };
        Set<Set<Integer>> firstSolution = shortestCombination(filter,listOfSets);
        System.out.println("The shortest combination was as per the input: -----> " + firstSolution);
   }
}

输出

The shortest combination was as per the input: -----> [[1, 2], [3, 8], [9, 10], [5, 6], [4, 7]]

结论

在本文中，我们详细学习了集合覆盖问题。今天我们使用贪婪法来解决这个问题，采用了上述语法和算法。希望通过本文，你能在Java环境中使用不同方法解决集合覆盖问题，获得广泛的视野。