Java 程序解决集合覆盖问题
集合覆盖是组合优化技术中一个众所周知的 NP-hard 问题。我们将集合覆盖问题称为 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 程序通过使用过滤器类解决子集中最多两个元素的集合覆盖问题
Java 程序通过贪婪方法解决子集中最多两个元素的集合覆盖问题。使用贪婪方法在子集中找到两个元素
在此特定的 Java 代码中,我们尝试向您展示如何使用贪婪方法解决子集中有两个最大元素的集合覆盖问题。
示例 1
// 将一些输入输出类作为声明导入
import java.io.*;
// 从 java.util 包导入一些实用程序类
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;
// 这里的主类是 ARBRDD,正如我们在此处声明的那样
public class ARBRDD {
// 过程的接口声明
// 通过采用一些抽象方法来操作接口类来声明接口类
interface Filter<T> {
boolean matches(T t);
}
// 集合覆盖求解的方法 1 的声明
// 声明组合方法。该方法是 -'shortcombo'
// 以集合的形式声明输出。还返回特定集合作为输出
private static <T> Set<T>
shortcombo(Filter<Set<T> > filter, List<T> sets){
// 将特定范围设置为工作集的大小
final int size = sets.size();
// 检查条件以运行该方法
// 如果内容的大小大于 25,则--->
// 我们将抛出一个异常,弹出此处存在太多组合的窗口
if (size > 20)
throw new IllegalArgumentException(
"此处存在太多组合 ---->");
// 现在组合将留在这里,总共移动 1 个进程时间 size
int comb = 1 << size;
// 尽快引用另一个集合
// 此 Arraylist 组合将包含此过程中存在的所有可能解决方案
List<Set<T> > possible = new ArrayList<Set<T> >();
// 声明一个 for 循环,迭代所有逻辑直到组合
for (int i = 0; i < comb; i++) {
// 引用声明的 lInkedHashSet
// 组合我们正确运行此代码
Set<T> 组合 = new LinkedHashSet<T>();
// 循环并迭代直到该组合中存在的大小
for (int j = 0; j < size; j++) {
// 如果我们执行右移 i 和 j,然后以 1 结束 - 这将是过程
// 这个可能的逻辑将告诉我们在这个过程中至少现在有多少种组合是可能的
if (((i >> j) & 1) != 0)
// 现在将集合组合添加到
// 数组列表中
combinations.add(sets.get(j));
}
// 现在添加到此处的特定可能引用
possible.add(combination);
}
// 使用 Collections 类上的 sort() 方法,我们至少可以对集合进行排序
Collections.sort(
possible, new Comparator<Set<T> >() {
// 通过采取以下措施找到此过程的最小长度
// 此处可能的字符总大小之间的差异
// 此处列出的列表
public int compare(Set<T> a1, Set<T> a2)
{
return a1.size() - a2.size();
}
});
// 现在我们可以采取特定的迭代过程,直到我们能够达到可能的
for (Set<T> possibleSol : possible) {
// 然后我们检查当前可能的解决方案是否匹配
// 如果匹配
// 从流程中返回解决方案
// 如果不匹配
// 返回空值
if (filter.matches(possibleSol))
return possibleSol;
}
return null;
}
//引入方法2用于流程代码
//这里是声明的main方法
public static void main(String[] args){
// 获取数组中存在的一些自定义条目的所有可能组合
Integer[][] all = {
{ 1, 2 }, { 3, 4 }, { 8, 9 },
{ 16, 7 }, { 5, 8 }, { 11, 6 },
{ 4, 5 }, { 6, 7 }, { 10, 11 },
};
// 列表中的一些数字 从列表中选择
// 再次,在数组中进行自定义条目
Integer[] solution
= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
// 在这里让我们取一个集合来运行逻辑以再次传递代码
List<Set<Integer> > sets
= new ArrayList<Set<Integer> >();
// 现在,取一个函数 all 的数组来表示数组
for (Integer[] array : all)
// 现在取这些元素并将它们添加到
// 在 LinkedHashSet 本身中
sets.add(new LinkedHashSet<Integer>(Arrays.asList(array)));
// 现在取存在的整数 sol 的集合并
// 将其设置为列表的解决方案
final Set<Integer> sol = 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-each 循环来迭代整个方法
for (Set<Integer> ints : integers)
union.addAll(ints);
return union.equals(sol);
}
};
// 现在,下面的集合将调用此处的特定短组合
// 此函数将用于从此处的组合中对最短的组合进行排序
Set<Set<Integer> > firstSol= shortcombo(filter, sets);
// 打印并显示该过程的相同逻辑
System.out.println("此处的短组合 ---> : "+ firstSol);
}
}
输出
此处呈现的简短组合 ---> : [[1, 2], [3, 4], [8, 9], [5, 8], [6, 7], [10, 11]]
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);
}
// 按大小顺序排列的可能解决方案。
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("最短组合如下: -----> " + firstSolution);
}
}
输出
最短组合如下:-----> [[1, 2], [3, 8], [9, 10], [5, 6], [4, 7]]
结论
在本文中,我们详细了解了集合覆盖问题。今天,我们在这里使用贪婪方法通过上述语法和算法解决了这个问题。希望通过本文,您已经对如何在 Java 环境中使用各种方法解决集合覆盖问题有了广泛的了解。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

