Jason. Cała informatyka w jednym miejscu!

Co powiecie kochani na kolejny problem algorytmiczny do przeanalizowania? Jest taki problem pokrycia zbioru, o którym nie huczy tak głośno jak o problemie komiwojażera i także nie da się rozwiązać w prosty sposób. Zainteresowani szczegółami? To zapraszam!

NA CZYM POLEGA PROBLEM POKRYCIA ZBIORU?

Termin "set cover problem" opowiada o problemie przed którym stoi człowiek, który dysponując takimi elementami (literka 'U' oznacza "uniwersum"):

U = {A, B, C, D, E}

posiada kilka różnych zbiorów, w których znajdują się poszczególne elementy:

Problem pokrycia zbioru

Rysunek graficzny prezentujący przynależność elementów do zbiorów w ramach przykładu.

a niektóre z nich znajdują się w więcej niż jednym zbiorze. Sformułowanie może wyglądać następująco:

S = {{A, B, C}, {B, C, D, E}, {C, E}}

i zagadnieniem jest znaleźć taką minimalną liczbę zbiorów, żeby uwzględnić wszystkie elementy podane w zbiorze U. Jest od groma przypadków gdzie występuje problem pokrycia zbioru. To może być chęć ustalenia które stacje telewizyjne uwzględnić, żeby przynosiły największą oglądalność przy ograniczonym budżecie. To może być proszę Ciebie, planowanie czynności marketingowych w postaci rozmieszczenia billboard'ów reklamowych w wyselekcjonowanych częściach miasta (albo publikacji reklam dla witryn internetowych), tak żeby "wisiały" jak najdłużej i ściągały na siebie jak największą uwagę w postaci szacowanej liczby zainteresowanych, i wiele innych. To już prezentuje nieco bardziej rozbudowany problem, do którego dochodzi również czynnik minimalizacji kosztów albo maksymalizacji zysków (bądź jedno i drugie), jednak takiego nie będziemy rozpatrywać. Skupmy się na istocie sprawy.

Problem: znalezienie takiego podzbioru zbiorów, żeby ich suma zawierała wszystkie elementy zbioru U

Do dzieła! Rozpracujmy to!

ZŁOŻONOŚĆ OBLICZENIOWA

Zbiory, kombinacje, funkcja celu i ograniczenia. Czy to nie daje Wam czegoś do myślenia? Problem pokrycia zbioru wymaga, aby przetrząsnąć każdy zbiór, każdy element i kombinację, zatem: 

O(2n)

Znowu kicha! O(2n) jak nic! Tak, niestety. To jest problem NP-zupełny! Tylko "brute-force" i sprawdzanie wszystkich kombinacji! Weźmy jeszcze raz te zbiory i ułóżmy w formie tabelki:

Lp {A, B, C} {B, C, D, E} {C, E}
1 0 0 0
2 0 0 1
3 0 1 0
4 1 0 0
5 1 0 1
6 1 1 0
7 0 1 1
8 1 1 1

Mamy podobną sytuację jak przy dyskretnym problemie plecakowym opisanym w poprzednim materiale. Tym razem zamiast elementów mamy podzbiory i to one stanowią pojedynczy składnik, ale zbiór potęgowy wychodzi taki sam nieubłaganie.

MAM MAŁE DEJA VU

Lipa! Przechodzimy do algorytmu zachłannego. Jak poprzednio - istnieje wiele metod optymalizacji złożoności obliczeniowej i jak zwykle pokażę tylko jedno z rozwiązań na problem pokrycia zbioru. Będzie to takie podejście, w którym dysponując tymi samymi zbiorami i elementami, oblecimy zawartości wszystkich zbiorów i będziemy dobierać "rekordzistę" pokrywającego największy fragment wymaganych elementów, których nie obejmują wcześniej wybrane zbiory. Czynimy to tak długo, aż wszystkie elementy zostaną uwzględnione, zwracamy listę zbiorów i gitara.

Dla porządku powtórzę, że zachłanność opiera się na wyniku aproksymacyjnym, zatem im większe zbiory danych do zbadania, tym bardziej narażamy się na odchylenie od rozwiązania dokładnego. Ale nie mamy innego wyjścia (co, mamy czekać kilkadziesiąt lat na rozwiązanie dokładne dla iluś tam zbiorów danych? ;) ).

KOD ŹRÓDŁOWY

Nie ma co dalej pisać trzymając się samej teorii, dlatego też macie tu kod źródłowy w kochanej Javie i popatrzcie sami jak to wygląda, uruchamiając program:

KLASA "MAIN"
public class Main {
	public static void main(String[] args) {
		new SetCoverProblem();
	}
}
KLASA "SET"
import java. util.List;
import java. util.LinkedHashSet;

public class Set {
	private final StringBuilder name = new StringBuilder();
	private final LinkedHashSet<String> elements = new LinkedHashSet<>();

	public Set() {}

	public Set(String name, List<String> elements) {
		setName(name);
		this.elements.addAll(elements);
	}

	public void setName(String name) {
		this.name.replace(0, this.name.length(), name);
	}

	public String getName() {
		return name.toString();
	}

	public LinkedHashSet<String> getElements() {
		return elements;
	}
}
KLASA "SETS"
import java. util.*;

public class Sets extends LinkedHashSet<Set> {
	private final Set bestSet = new Set();

	public Sets(HashSet<String> universe) {
		add(new Set("A", Arrays.asList("A", "B", "C")));
		add(new Set("B", Arrays.asList("B", "C", "D", "E")));
		add(new Set("C", Arrays.asList("C", "E")));
		findMostCoveringSet(universe);
	}

	public Set getBestSet() {
		return bestSet;
	}

	private void findMostCoveringSet(HashSet<String> universe) {
		HashSet<String> coveredElements = new HashSet<>();

		for (Set s : this) {
			HashSet<String> intersection = elementsIntersection(universe, s.getElements());

			if(foundMoreCoveredElements(intersection, coveredElements)) {
				bestSet.setName(s.getName());

				coveredElements = intersection;
			}
		}

		bestSet.setElements(coveredElements.stream().toList());
	}

	private HashSet<String> elementsIntersection(HashSet<String> universe, HashSet<String> elements) {
		HashSet<String> setElements = new HashSet<>(universe);

		setElements.retainAll(elements);

		return setElements;
	}

	private boolean foundMoreCoveredElements(HashSet<String> intersection, HashSet<String> coveredElements) {
		return intersection.size() > coveredElements.size();
	}
}
KLASA "SETCOVERPROBLEM"
import java. io.PrintStream;
import java. util.*;

public class SetCoverProblem {
	private final LinkedHashSet<String> universe = new LinkedHashSet<>(Arrays.asList("A", "B", "C", "D", "E"));
	private final HashSet<String> selectedSets = new HashSet<>();
	private final PrintStream printStream = System.out;

	public SetCoverProblem() {
		findSubsets();
		printStream.println("Wybrane zbiory: " + selectedSets);
	}

	private void findSubsets() {
		while (!universe.isEmpty()) {
			findAnotherBestSet();
		}
	}

	private void findAnotherBestSet() {
		Sets sets = new Sets(universe);
		String bestSetName = sets.getBestSet().getName();
		HashSet<String> coveredElements = sets.getBestSet().getElements();

		universe.removeAll(coveredElements);
		selectedSets.add(bestSetName);

		printStream.println("Zbiór pokrywający największą część elementów: " + bestSetName);
		printStream.println("Elementy w danym zbiorze: " + coveredElements);
		printStream.println("Pozostałe brakujące elementy: " + universe);
	}
}

Starałem się jak mogłem, żeby jakoś ładnie podzielić ten kod, aby instrukcje były zrozumiałe. Klasa "Set" to nasz pojedynczy zbiór, do którego wrzucamy sobie w konstruktorze elementy w postaci listy i wprowadzamy nazwę. Użyłem obiektu "StringBuilder", ponieważ wielokrotnie modyfikujemy ten sam obiekt łańcucha, a tych którzy nie wiedzą dlaczego zmiana samego "String" byłaby niebezpieczna, zapraszam do osobnego wpisu. Dodałem też konstruktor bezparametrowy, bo jak pisałem o tym fragmentowaniu kodu, jest w klasie "Sets" zależność w postaci przechowywania najlepszego zbioru w ramach wyszukiwania lokalnie optymalnego rozwiązania (ten "rekordzista"). Reszta to tylko "gettery" i "settery", więc idziemy dalej do...

...klasy "Sets", w której jest duża część implementacji! "Sets" dziedziczy po "LinkedHashSet", gdyż zależy nam na zapewnieniu unikatowości elementów (w tym przypadku pominąłem tworzenie osobnej klasy dla elementów ze względu na uniknięcie wstawiania referencji instancji elementów, a tak to wystarczy wpisać ten sam łańcuch znaków i po sprawie), a "Linked" sprawi że zostanie zapamiętana kolejność wprowadzanych elementów. Mamy jedną daną składową, o której wspomniałem przed sekundą będącą naszą przechowalnią aktualnego zbioru, który podczas przeprowadzanych operacji zostanie uznany za ten "the best". W konstruktorze wprowadziłem wstawienie naszych zbiorów z obrazka powyżej oraz wywołanie metody wyszukującej naszego kandydata na podstawie naszego "uniwersum" (podawanego jako parametr). Zostało to zrobione w taki sposób, gdyż po każdym wybraniu najlepszego zbioru, nasz zbiór "wszechświata" będzie każdorazowo ucinany z tych elementów jakie posiada ten zbiór wybrany. Wobec tego, przepływ programu nie zostanie zaburzony.

Problem pokrycia zbioru redukujemy w metodzie "findMostCoveringSet". Zmienna lokalna typu "HashSet" będzie przechowywać elementy odnalezione w zbiorze, przez który przejdzie pętla "for-each" występująca dwie linijki niżej. W środku niej, wywołujemy kolejną odrębną metodę odpowiadająca za znalezienie części wspólnej pomiędzy zbiorem wszystkich elementów (uniwersum), a zbiorem z elementami wyodrębnionymi. Tu sięgamy bardzo ważnego kroku jakim jest wywołanie metody "retainAll". "retainAll" oznacza dosłowne wykonanie operacji iloczynu zbiorów. Żeby kod zadziałał poprawnie, zwracamy część wspólną zbioru A (jakim jest uniwersum) i zbioru B (jakim jest aktualny zbiór zbioru S - sięgnij wyżej kolego, jeśli nie wiesz co to za literka). Kiedy takowy zbiór zostanie zwrócony, program natrafia na instrukcję warunkową porównującą moce obu zbiorów. Kiedy część wspólna ma więcej elementów niż nasza tymczasowa zmienna lokalna, dochodzi do uznania danego zbioru za "ten najlepszy". Przypisuje się jego nazwę, a także referencję do zbioru powstałego z iloczynu zbiorów. Program wykonuje te same instrukcje dla każdego zbioru, po czym do referencji naszego "rekordzisty" wprowadza się elementy zbioru uznanego za ten najlepszy.

Tak doszliśmy do ostatniej klasy "SetCoverProblem", w której następuje "odpalenie" algorytmu. Finalne dane składowe to jest zbiór (już w sensie struktury danych, a nie matematyki) naszego uniwersum (wszystkie elementy, które uznajemy za konieczne do posiadania), kolejny zbiór dla wybranych zbiorów, które zostają uwzględnione jako części rozwiązania ostatecznego oraz "PrintStream" dla skrócenia sobie wywołań "println". W konstruktorze wywołujemy sobie metodę, która rozwiązuje problem pokrycia zbioru aproksymacyjnie (korzystamy jak zawsze z pętelki "while"). Pętla wykonuje się tak długo, aż wszystkie niezbędne elementy będą pokrywane przez wybrane zbiory (innymi słowy, wyczerpujemy nasz zbiór elementów po wybraniu każdego kolejnego zbioru, aż suma wszystkich zbiorów będzie równa naszemu uniwersum):

A ∪ B = U = {A, B, C, D, E}

Bardzo uproszczony zapis, żebyście wiedzieli do czego to się sprowadza. Wywołuje się tylko jedna metoda, "findAnotherBestSet". Blok treści wygląda tak: tworzymy sobie instancję "zbiorów" podstawiając parametr jako nasz zbiór wszystkich elementów (a tak naprawdę, to aktualny stan elementów, których żaden wybrany zbiór jeszcze nie posiada). Już wiemy co się dzieje w środku, zatem idąc dalej natrafiamy na pobranie nazwy i elementów "rekordzisty". I teraz uwaga! Usuwamy WSZYSTKIE elementy z naszego zbioru robiącego za uniwersum, które zostaną znalezione w zbiorze pokrywającym największą część elementów. Stosujemy taką "metodę eliminacji". I oczywiście dodajemy do osobnej kolekcji łańcuch znaków w postaci nazwy tego samego zbioru, przyczyniając się do otrzymania rozwiązania częściowego. A dalej to są już tylko wypisy wyników na terminal, żebyście mieli podgląd ustaleń programu.


Gotowe! Pokazane, wytłumaczone i rozwiązane na własnym przykładzie (banalnym, jeśli chodzi o ścisłość). Problem pokrycia zbioru zamykam na cztery spusty.

PODOBNE ARTYKUŁY