数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Java程序解决集合覆盖问题
集合覆盖是一个著名的NP难问题，属于组合优化技术。我们称集合覆盖问题为NP难问题，是因为目前还没有针对这个问题的多项式实时解法。一种称为贪婪启发式算法是解决集合覆盖问题的常用方法。
这里有一个例子：
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
解决集合覆盖问题的语法
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代码。
遵循的方法
-
使用贪婪算法
-
使用Filter类
使用贪婪算法
在这段特定的Java代码中，我们尝试向你展示如何使用贪婪算法解决一个集合覆盖问题，该问题子集中的最大元素个数为两个。
- 导入java.io用于输入/输出操作和`java.util.*`用于数据结构，例如ArrayList、`Set`和List。
- 定义主类`ARBRDD`，其中包含Filter接口、主方法和shortcombo方法来解决子集组合问题。
- 在主类中定义`Filter`接口，包括`matches(T t)`方法来检查子集组合是否覆盖所有必需的元素。
- 实现shortcombo方法，该方法接受Filter和子集列表作为输入，使用循环迭代组合。
- 在`shortcombo`中使用if条件来检查每个组合是否满足过滤条件，并存储最短的有效解。
- 定义主方法来初始化数据，设置所需的集合，并调用shortcombo来查找结果。
示例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]]
使用Filter类
在这段特定的Java构建代码中，我们使用了预定义的Filter类接口来解决集合覆盖问题，最大元素值为两个。
- 从java.util包导入所有类，以使用诸如`ArrayList`、Set和Map之类的类进行数据处理。
- 定义`SubsetFinder`类，其中包含`shortestSubset`方法，用于识别覆盖所需元素的最小子集。
- 在`shortestSubset`中，使用参数`requiredSet`和`availableSets`来处理所需元素和可用子集。
- 在`shortestSubset`中初始化变量以跟踪最短组合，使用循环迭代子集组合。
- 使用`嵌套循环`和if条件来检查每个组合是否覆盖`requiredSet`中的所有元素。
- 如果组合满足条件，则比较其大小以查找和存储最短组合。
- 定义主方法来创建测试数据，设置`requiredSet`和`availableSets`，并调用`shortestSubset`来查找结果。
示例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环境中使用各种方法解决集合覆盖问题有一个全面的了解。
更新于：2024年11月11日
浏览量：455
广告