Maski bitowe

03.10.2009 - Damian Rusak

Pomocna w rozwiązaniu wielu problemów algorytmicznych z gatunku programowania dynamicznego bywa umiejętność zwięzłego zapisu wszystkich możliwych do osiągnięcia stanów. Spotykamy problemy, w których te stany to pewne podzbiory. Co to oznacza? W jaki sposób reprezentować podzbiory i czy faktycznie jest to dobry i skuteczny sposób rozwiązywania problemów algorytmicznych? Odpowiedzi na te pytania znajdziesz w tym artykule.

Poniższy artykuł prezentuje rozwiązania trzech zadań programistycznych. Czytelnik może sprawdzić po lekturze artykułu swoją wiedzę, wysyłając rozwiązania tych zadań na naszą sprawdzaczkę. Ponadto do rozwiązania są dwa dodatkowe zadania, o których nie ma mowy w treści artykułu. Zachęcam do zmierzenia się z nimi!

Problem Komiwojażera

Za przykład wykorzystania tej idei posłużyć nam może znany Problem Komiwojażera (TSP - Travelling Salesman Problem). Dla ustalenia uwagi, sprecyzujemy tu jeden z wariantów TSP :

W ważonym grafie pełnym należy znaleźć najlżejszą spośród ścieżek, przechodzących przez każdy wierzchołek dokładnie raz i kończących się w tym samym wierzchołku, w którym się rozpoczęły.

Ten problem jest trudny i nie jest znany algorytm, który rozwiązywałby go i działał w czasie wielomianowym. Wobec tego zaatakujemy problem, znajdując w miarę dobre rozwiązanie w czasie wykładniczym.

Oczywiście nietrudno znaleźć rozwiązanie w czasie $O\left(n!\right)$ , bazujące na przejrzeniu wszystkich możliwych ścieżek, poprzez ustawienie wierzchołków na ścieżce za pomocą permutacji zbioru wierzchołków. Istnieje jednak sposób rozwiązania tego problemu, działający w czasie $O\left(n^{2}\cdot 2^{n}\right)$ .

Rozważmy na potrzeby przykładu poniższy graf:

Dobrą praktyką, towarzyszącą wymyśleniu algorytmu programowania dynamicznego, jest próba wyszczególnienia pewnych stanów i konstrukcja rozwiązania dla każdego z nich z wykorzystaniem uprzednio obliczonych rozwiązań dla stanów poprzedzających. Tutaj naturalne jest zasymulowanie „podróży” komiwojażera przez wierzchołki grafu. Naszym stanem może być pewien fragment przebytej drogi. Moglibyśmy przyjąć, że stan to fragment drogi od pierwszego wierzchołka na jej trasie.

Jednak taki pomysł nie różni się od brutalnego sprawdzania wszystkich permutacji. Tu pojawia się ważna obserwacja - jeśli rozpatrujemy pewien fragment ścieżki komiwojażera oraz wiemy w jakim miejscu się rozpoczął i w jakim zakończył, to nie jest dla nas istotne, w jakiej kolejności zostały odwiedzone pozostałe wierzchołki na ścieżce - istotne jest jedynie, które wierzchołki zostały już odwiedzone, szukamy wszak najlepszej spośród wszystkich tych możliwości i interesuje nas koszt, a nie kolejność. To odpowiada pomysłowi z wykorzystaniem nieuporządkowanych podzbiorów jako stanów - określmy stan (fragment ścieżki) jako podzbiór zbioru wszystkich wierzchołków, z wyszczególnionym początkiem i końcem.

Szybko dochodzimy też do pomysłu na optymalizację tego podejścia - skoro (w naszym wariancie) ścieżka komiwojażera ma być cyklem, i przechodzić przez wszystkie wierzchołki, to bez straty ogólności możemy założyć, że zawsze zaczyna się ona w pewnym wyszczególnionym wierzchołku (nazwijmy go wierzchołkiem początkowym). W ten sposób przestrzeń stanów można ograniczyć do podzbiorów zbioru wierzchołków, wraz z wyszczególnionym wierzchołkiem końcowym. Teraz, szacując złożoność pamięciową, otrzymujemy $O\left(n\cdot 2^{n}\right)$ możliwych stanów.

Dalsza część rozwiązania to programowanie dynamiczne. Przeglądamy wszystkie stany, w kolejności zadanej przez liczbę wierzchołków, należących do odwiedzonego podzbioru. Daje nam to pewność, że przy obliczaniu najkrótszej ścieżki dla danego stanu, mamy już obliczone wartości dla wszystkich podzbiorów zawierających się w rozpatrywanym podzbiorze. Wprowadźmy oznaczenia:

$l\left[w\right]\left[v\right]$ - waga ścieżki od wierzchołka $w$ do wierzchołka $v$

$d\left[K\right]\left[v\right]$ - waga najkrótszej ścieżki, rozpoczynającej się w wierzchołku nr 1, przechodzącej przez wszystkie wierzchołki z podzbioru $K$ dokładnie raz i kończącej się w wierzchołku $v$ .

Teraz, skoro przebyliśmy drogę jedynie poprzez wierzchołki z podzbioru $K$ , to wystarczy rozpatrzeć przejście przez ostatnią krawędź na ścieżce i wybrać najmniejszą możliwą wartość, korzystając z wcześniej wyliczonych wielkości w tablicy $d$ :

$d\left[1\right]\left[1\right] = 0$
$d\left[\left\{1,w\right\}\right] = l\left[1\right]\left[w\right]$
$d\left[K\right]\left[w\right] = min\left\{d\left[K/\left\{w\right\}\right]\left[v\right]+l\left[v\right]\left[w\right]\left|\:v\in K/\left\{w,1\right\} \right\} \:dla\:w\neq1$

Gdy dokonamy tych obliczeń dla wszystkich podzbiorów, otrzymamy najmniejsze wartości ścieżek, przebiegających wszystkie wierzchołki grafu, i kończących się w pewnym jego wierzchołku, różnym od 1. Teraz należy zamknąć cykl komiwojażera, powracając do wierzchołka nr 1. Stąd rozwiązanie to:

$min\left\{d\left[\left\{1,2,...,n\right\}\right]\left[v\right]+l\left[v\right]\left[1\right]\left|\:v\in\left\{2,3,...,n\right\}\right\}$