資料結構
網路
關係資料庫管理系統 (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
廣告