Generowanie wszystkich podzbiorów

Zacznijmy od algorytmu, który jest podstawą w implementacji metod siłowychmetoda siłowametod siłowych do rozwiązywania problemów NP‑zupełnych. Zanim jednak przejdziemy do jego opisu, wprowadźmy pewnego rodzaju oznaczenie. Chcemy, aby ciąg binarny składający się z zer i jedynek reprezentował, które elementy z rozpatrywanego zbioru znajdują się w danym podzbiorze. Niech jedynki i zera oznaczają odpowiednio, że element na danej pozycji znajduje się bądź nie w rozpatrywanym podzbiorze.

Dla lepszego zrozumienia tej koncepcji przeanalizujmy, jak wyglądają reprezentacje przykładowych podzbiorów zbioru $\left\{ a, b, c, d \right\}$.

Dzięki zastosowaniu takiego oznaczenia nie musimy pisać algorytmu generującego faktyczne podzbiory. Potrzebujemy jedynie programu, który wygeneruje nam wszystkie możliwe ciągi binarne, które je reprezentują. Jest to dosyć spore ułatwienie.

Załóżmy, że chcemy wyznaczyć wszystkie podzbiory zbioru n‑elementowego. Każdy z ciągów reprezentujących pewien podzbiór to tak naprawdę zapis binarny liczby naturalnej z zakresu $\left\langle0,2^n-1\right\rangle$; przy pomocy n bitów. Wystarczy więc, aby nasz program przeiterował po każdej liczbie naturalnej z zakresu $\left\langle0,2^n-1\right\rangle$ i przekonwertował jej zapis dziesiętny na binarny przy użyciu n bitów.

Jaką złożoność ma przedstawione rozwiązanie? Załóżmy, że przekonwertowanie z zapisu dziesiętnego na binarny wymaga wykonania k operacji. Będziemy wypisywać wszystkie liczby naturalne z zakresu $\left\langle0,2^n-1\right\rangle$, których w sumie jest $2^n$. W takim razie algorytm wykona $k \cdot 2^n$ operacji, a więc ma on złożoność czasową $O(2^n)$.

Warto zastanowić się, dla jakich n nasz algorytm działa w miarę szybko. Dla $n = 40$ będzie on działał około $20$ minut, natomiast dla $n = 50$ czas potrzebny na wykonanie programu wzrasta już do $13$ dni. Dlatego właśnie algorytmy o złożoności wykładniczej to ostateczność.

Przykład zastosowania

Co tak naprawdę daje nam znajomość opisanego sposobu generowania podzbiorów? Okazuje się, że jest to bardzo dobry sposób na generowanie wszystkich możliwych rozwiązań pewnego problemu. Załóżmy, że mamy do dyspozycji po jednym z odważników o następujących wagach: $1\ \text{kg}$, $2\ \text{kg}$, $5\ \text{kg}$ i $7\ \text{kg}$. Chcemy wiedzieć, na ile sposobów jesteśmy w stanie uzyskać w sumie $8\ \text{kg}$. Możemy wykorzystać metodę siłową i wygenerować wszelkie możliwe kombinacje odważników, a następnie sprawdzić, które z zestawów dają wagę taką, jaką chcemy.

Problemy NP‑zupełne

Istnieje wiele problemów, dla których obecnie znanym optymalnym rozwiązaniem są algorytmy o złożoności wykładniczej. Bardzo często ich opis nie wskazuje na faktyczną trudność. W trakcie tego e‑materiału przedstawimy dwa z nich, lecz nie będziemy prezentować ich optymalnych rozwiązań, ponieważ mocno wykraczają one poza zakres programowy.

Problem komiwojażera

Problem komiwojażera to znany problem grafowygrafgrafowy. Tytułowy komiwojażerkomiwojażerkomiwojażer musi odwiedzić dokładnie n miast. Chce, aby jego trasa była jak najkrótsza oraz żeby kończyła się w tym samym mieście, w którym się zaczyna. Dodatkowo w trakcie swojej trasy nie chce on wchodzić do żadnego z miast więcej niż jeden raz (nie dotyczy to miasta, z którego startuje).

R1DeZX38wER5C

Rysunek przedstawiający problem komiwojażera. Rysunek przedstawia graf. Mamy tu połączone ze sobą punkty od A do F. Punkty C, E, F położone są wzdłuż jednej pionowej linii w wymienionej kolejności, zaczynając od góry. Punkty B, D położone są w jednej poziomej linii znajdującej się na wysokości między C i E. Punkt A znajduje się pod B w połowie wysokości pionowej ścieżki EF. Opis ścieżek. Punkt A połączony jest tylko z jednym punktem - B pionową ścieżką o wadze 5. Punkt B połączony jest z czterema punktami: A pionową ścieżką o wadze 5, z punktem F ukośną ścieżką o wadze 2, z punktem E ukośną ścieżką o wadze 10, z punktem C ukośną ścieżką o wadze 6. Punkt C połączony jest z trzema punktami: z punktem B ukośną ścieżką o wadze 6, z punktem E pionową ścieżką o wadze 4, z punktem D ukośną ścieżką o wadze 3. Punkt D połączony jest z dwoma punktami: z punktem C ukośną ścieżką o wadze 3, z punktem E ukośną ścieżką o wadze 8. Punkt E połączony jest z z czterema punktami: z punktem D ukośną ścieżką o wadze 8, z punktem C pionową ścieżką o wadze 4, z punktem B ukośną ścieżką o wadze 10, z punktem F pionową ścieżką o wadze 2. Punkt F ma dwa połączenia: z punktem E pionową ścieżką o wadze 2 oraz z punktem B ukośną ścieżką o wadze 2. Kolorem zaznaczono trójkąt BFE, gdzie ścieżka BF ma wagę 2, ścieżka FE ma wagę 2 i ścieżka EB ma wagę 10.

Problem najdłuższej ścieżki

Mając dany graf, chcemy wiedzieć, czy istnieje ścieżka o długości większej niż pewne zadane s. Ścieżkę definiujemy jako ciąg krawędzi, po których podróżujemy. Dodatkowo zabronione jest wykorzystanie tej samej krawędzi więcej niż jeden raz. Długością ścieżki nazywamy sumę długości krawędzi wchodzącej w jej skład.

R1ci53Y433IY1

Rysunek przedstawiający problem najdłuższej ścieżki. Rysunek przedstawia graf. Mamy tu połączone ze sobą punkty od A do E. Punkty B, D położone są wzdłuż jednej pionowej linii w wymienionej kolejności, zaczynając od góry. Punkty A, C położone są w jednej poziomej linii znajdującej się w połowie wysokości BD. Punkty A, B, C, D tworzą romb. Punkt E znajduje się pod C i na wysokości D. Opis ścieżek. Punkt A połączony jest z trzema punktami: z punktem B ukośną ścieżką o wadze 5, z punktem C poziomą ścieżką o wadze 7, z punktem D ukośną ścieżką o wadze 4. Punkt B połączony jest z dwoma punktami: z punktem A ukośną ścieżką o wadze 5 oraz z punktem D pionową ścieżką o wadze 7. Punkt C połączony jest z dwoma punktami: z punktem A poziomą ścieżką o wadze 7 oraz z punktem D ukośną ścieżką o wadze 6. Punkt D połączony jest z czterema punktami: z punktem A ukośną ścieżką o wadze 4, z punktem B pionową ścieżką o wadze 7, z punktem C ukośną ścieżką o wadze 6 oraz z punktem E poziomą ścieżką o wadze 4. Punkt E ma tylko jedno połączenie - z punktem D poziomą ścieżką o wadze 4. Kolorem wyróżniono ścieżkę ABDC w kształcie litery Z obróconej o 45 stopni w lewo. Ścieżka ta jest następująca: ukośna ścieżka AB o wadze 5, pionowa ścieżka BD o wadze 7, ukośna ścieżka DC o wadze 6.

Podsumowując, algorytmy o wykładniczej złożoności czasowej są bardzo często wykorzystywane do implementacji metod siłowych. Wtedy mogą one polegać na wygenerowaniu wszystkich możliwych rozwiązań, a następnie sprawdzeniu, które z nich są poprawne. Algorytmy te są jednymi z najwolniejszych i nie powinno się ich stosować dla dużych danych wejściowych.

Słownik