Praca badawcza to chyba najbardziej interesująca część naszej edukacji. Idea polega na tym, aby jeszcze na studiach spróbować swoich sił w wybranym kierunku. Na przykład studenci kierunków Inżynieria Oprogramowania i Uczenie Maszynowe często realizują projekty badawcze w firmach (głównie JetBrains lub Yandex, ale nie tylko).
W tym poście opowiem o swoim projekcie z dziedziny Informatyki. W ramach pracy zbadałem i wdrożyłem w praktyce podejścia do rozwiązania jednego z najbardziej znanych problemów NP-trudnych: problemu pokrycia wierzchołków.
Obecnie szybko rozwija się ciekawy sposób podejścia do problemów NP-trudnych — algorytmy parametryzowane. Postaram się wprowadzić was w temat, opowiedzieć o kilku prostych algorytmach parametryzowanych i opisać jeden skuteczny metod, który bardzo mi pomógł. O swoje wyniki zaprezentowałem na zawodach PACE Challenge: po zakończeniu testów otwartych moje rozwiązanie zajmuje trzecie miejsce, a ostateczne wyniki będą znane 1 lipca.
O mnie
Nazywam się Wasilij Alfiorow, obecnie kończę trzeci rok na Naukowej Szkole Ekonomicznej — w Petersburgu. Algorytmami interesuję się już od czasów szkolnych, kiedy uczęszczałem do moskiewskiej szkoły 179 i skutecznie brałem udział w olimpiadach informatycznych.
Koniec liczby specjalistów od algorytmów parametryzowanych wchodzi do baru...
Przykład pochodzi z książki
Wyobraź sobie, że jesteś ochroniarzem w barze w małym mieście. Każdego piątku połowa miasta przychodzi do twojego baru, aby się zrelaksować, co sprawia ci sporo kłopotów: musisz wyrzucać hałaśliwych gości, aby uniknąć bójek. W końcu to cię nuży i postanawiasz podjąć środki zapobiegawcze.
Ponieważ miasto jest małe, dokładnie wiesz, które pary gości najprawdopodobniej się pokłócą, jeśli znajdą się w barze razem. Masz listę n ludzi, którzy przyjdą dzisiaj wieczorem do baru. Postanawiasz nie wpuścić niektórych miejskich mieszkańców w taki sposób, aby nikt się nie pobił. Jednocześnie twoje kierownictwo nie chce tracić zysków i będzie niezadowolone, jeśli nie wpuszczisz do baru więcej niż k ludzi.
Niestety, problem, przed którym stoisz, jest klasycznym problemem NP-trudnym. Mogłeś znać go jako , or like the vertex cover problem. For such problems, no algorithms are known that work in a reasonable time in general. To be precise, the unproven and quite strong ETH (Exponential Time Hypothesis) suggests that this problem cannot be solved in time 
, meaning that there is nothing significantly better than brute force. For example, let’s say that approximately n = 1000 people are heading to your bar. Then brute force would involve 
combinations, which is about 
— an insane number. Fortunately, your management has imposed a restriction of k = 10, so the number of combinations you need to consider is much smaller: the number of subsets of ten elements is equal to 
. This is already better, but still cannot be calculated in a day even on a powerful cluster.
To eliminate the likelihood of fights with such a configuration of strained relationships among the bar visitors, you need to prohibit Bob, Daniel, and Fyodor from entering. There is no solution where only two remain outside.
Does this mean it's time to give up and let everyone in? Let's consider other options. For instance, you might not let only those who are likely to fight with a large number of people. If someone can start a fight with at least k + 1 other individuals, then they definitely should not be let in — otherwise, you will have to keep out all k + 1 the locals they can fight with, which would certainly upset management.
Assuming you've ejected everyone you can based on this principle. Then all remaining people can only fight with at most k others. By removing k people from them, you can prevent no more than 
conflicts. Therefore, if more than 
people are involved in at least one conflict, you certainly won't be able to prevent them all. Since, obviously, you will definitely let in the completely conflict-free people, you need to consider all subsets of ten from two hundred people. There are approximately 
, and such a number of operations can already be managed on a cluster.
Jeśli można bezpiecznie wpuścić osoby, które nie mają konfliktów, co powiedzieć o tych, którzy biorą udział w jednym konflikcie? W rzeczywistości można ich również wpuścić, zamykając drzwi przed ich przeciwnikiem. Rzeczywiście, jeśli Alicja kłóci się tylko z Bobem, to wpuszczając Alicję, nie przegramy: Bob może mieć inne konflikty, a Alicja na pewno ich nie ma. Po co w takim razie nie wpuszczać obu? Po takich operacjach zostaje nie więcej niż 
gości z nierozwiązanym losem: w sumie mamy 
konflikty, w każdym biorą udział po dwie osoby, a każda uczestniczy przynajmniej w dwóch. Oznacza to, że musimy przeanalizować tylko 
warianty, co może zająć pół dnia na laptopie.
W rzeczywistości prostymi rozważaniami można osiągnąć jeszcze bardziej korzystne warunki. Zauważmy, że konieczne jest rozwiązanie wszystkich sporów, czyli z każdej kłócącej się pary wybrać przynajmniej jedną osobę, którą nie wpuszczimy. Rozważmy taki algorytm: weźmiemy dowolny konflikt, usuniemy jednego uczestnika i uruchomimy rekurencyjnie z resztą, następnie usuniemy drugiego i również uruchomimy rekurencyjnie. Ponieważ w każdym kroku kogoś wykluczamy, drzewo rekurencji tego algorytmu to drzewo binarne o głębokości k, dlatego algorytm działa w czasie 
, gdzie n -- liczba wierzchołków, a m -- liczba krawędzi. W naszym przykładzie to około dziesięciu milionów, co w ciągu ułamka sekundy można obliczyć nie tylko na laptopie, ale nawet na telefonie komórkowym.
Podany powyżej przykład to przykład algorytmu parametryzowanego. Algorytmy parametryzowane to algorytmy, które działają w czasie f(k) poly(n), gdzie p -- wielomian, f -- dowolna funkcja obliczalna, a k -- jakiś parametr, który może być znacznie mniejszy od rozmiaru zadania.
Wszystkie rozważania do tego algorytmu prowadzą do przykładu kernelizacji jedną z powszechnych technik tworzenia algorytmów parametryzowanych. Kernelizacja polega na redukcji rozmiaru zadania do wartości ograniczonej funkcją od parametru. Otrzymane zadanie często nazywa się rdzeniem. Tak, prostymi rozważaniami na temat stopni wierzchołków uzyskaliśmy kwadratowy rdzeń dla zadania Vertex Cover, parametryzowanego według wielkości odpowiedzi. Istnieją również inne parametry, które można wybrać dla tego zadania (na przykład Vertex Cover Above LP), ale będziemy omawiać właśnie ten parametr.
Pace Challenge
Zawody (The Parameterized Algorithms and Computational Experiments Challenge) powstało w 2015 roku, aby stworzyć połączenie między algorytmami parametryzowanymi a podejściami wykorzystywanymi w praktyce do rozwiązywania zadań obliczeniowych. Pierwsze trzy zawody dotyczyły znalezienia szerokości drzewa grafu (), znalezienia drzewa Steinera (), oraz znalezienia zbioru wierzchołków, który przecina cykle (). W tym roku jednym z zadań, w którym można było spróbować swoich sił, było opisane powyżej zadanie o pokryciu wierzchołków.
Zawody z każdym rokiem zyskują na popularności. Jeśli wierzyć wstępnym danym, w tym roku w zawodach dotyczących rozwiązania zadania pokrycia wierzchołków uczestniczyło 24 zespoły. Warto zauważyć, że zawody trwają nie kilka godzin, a nawet nie tydzień, lecz kilka miesięcy. Zespoły mają możliwość przestudiowania literatury, pomyślenia o własnym oryginalnym pomyśle i próby jego realizacji. W zasadzie te zawody stanowią pracę badawczą. Pomysły najefektywniejszych rozwiązań oraz nagrodzenie zwycięzców odbędzie się wspólnie z konferencją (International Symposium on Parameterized and Exact Computation) w ramach największego corocznego spotkania algorytmicznego w Europie . Bardziej szczegółowe informacje na temat samych zawodów można znaleźć na , a wyniki z lat ubiegłych można znaleźć .
Schemat rozwiązania
Aby poradzić sobie z zadaniem pokrycia wierzchołków, spróbowałem zastosować algorytmy parametryzowane. Z reguły składają się one z dwóch części: reguł uproszczenia (które w idealnym przypadku prowadzą do kernelizacji) oraz reguł rozgałęziania. Reguły uproszczenia to wstępne przetwarzanie wejścia w czasie wielomianowym. Celem zastosowania takich reguł jest sprowadzenie zadania do równoważnego zadania mniejszego rozmiaru. Reguły uproszczenia to najbardziej kosztowna część algorytmu, a zastosowanie tej części prowadzi do ogólnego czasu pracy. 
Zamiast prostego czasu wielomianowego. W naszym przypadku reguły rozgałęziania opierają się na tym, że dla każdego wierzchołka musimy wziąć w odpowiedzi albo jego, albo jego sąsiada.
Ogólny schemat jest taki: stosujemy reguły uproszczenia, następnie wybieramy jakiś wierzchołek i wykonujemy dwa rekurencyjne wywołania: w pierwszym bierzemy go w odpowiedzi, a w drugim bierzemy wszystkich jego sąsiadów. Nazywamy to rozgałęzieniem (branżowaniem) wzdłuż tego wierzchołka.
Do tego schematu wprowadzimy dokładnie jedno uzupełnienie w następnym akapicie.
Pomysły na reguły rozgałęzania (branżowania)
Porozmawiajmy o tym, jak wybrać wierzchołek, przy którym będzie się odbywać rozgałęzienie.
Podstawowa idea jest bardzo chciwa w sensie algorytmicznym: weźmy wierzchołek o maksymalnym stopniu i rozgałęźmy się właśnie przy nim. Dlaczego wydaje się, że to lepsze? Ponieważ w drugim gałęzi wywołania rekurencyjnego w ten sposób usuniemy bardzo wiele wierzchołków. Można się spodziewać, że zostanie mały graf, a na nim szybko zrealizujemy działanie.
To podejście z wcześniej omówionymi prostymi technikami kernelizacji sprawdza się całkiem nieźle, rozwiązując pewne testy o rozmiarze kilku tysięcy wierzchołków. Jednak na przykład słabo działa dla grafów kubicznych (to znaczy grafów, w których stopień każdego wierzchołka wynosi trzy).
Jest jeszcze jeden pomysł oparty na dość prostym myśleniu: jeśli graf jest niespójny, zadanie na jego komponentach spójności można rozwiązywać niezależnie, łącząc odpowiedzi na końcu. To zresztą jest niewielka obiecana modyfikacja w schemacie, która znacznie przyspieszy rozwiązanie: wcześniej w takim przypadku pracowaliśmy za iloczyn czasów liczenia odpowiedzi komponentów, a teraz pracujemy za sumę. A dla przyspieszenia rozgałęziania trzeba przekształcić graf spójny w niespójny.
Jak to zrobić? Jeśli w grafie jest węzeł krytyczny, należy podzielić według niego. Węzeł krytyczny to taki węzeł, którego usunięcie powoduje utratę spójności grafu. Wszystkie węzły krytyczne w grafie można znaleźć klasycznym algorytmem w czasie liniowym. Takie podejście znacząco przyspiesza proces dzielenia.
Przy usunięciu dowolnego z wyróżnionych węzłów graf rozpadnie się na komponenty spójne.
Zrobimy to, ale oczekujemy więcej. Na przykład, możemy szukać w grafie małych cięć wierzchołkowych i przeprowadzać podział przez wierzchołki z nich. Najbardziej efektywny znany mi sposób na znalezienie minimalnego globalnego cięcia wierzchołkowego to wykorzystanie drzewa Gomoriego-Hu, które buduje się w czasie kubicznym. W PACE Challenge typowy rozmiar grafu to kilka tysięcy węzłów. W takim przypadku w każdym węźle rekurencji trzeba wykonać miliardy operacji. Tak więc rozwiązanie zadania w ramach zadanego czasu jest po prostu niemożliwe.
Spróbujmy zoptymalizować rozwiązanie. Minimalne cięcie wierzchołkowe między parą węzłów można znaleźć dowolnym algorytmem, który buduje maksymalny przepływ. Można zastosować do tego , w praktyce działa on bardzo szybko. Mam podejrzenie, że teoretycznie można udowodnić ocenę na czas działania 
, co jest już całkiem akceptowalne.
Próbowałem kilka razy szukać cięć między parami losowych węzłów i wybierać z nich najbardziej zrównoważone. Niestety, na otwartych testach PACE Challenge dało to słabe wyniki. Porównywałem z algorytmem, który dzielił się przez wierzchołki o maksymalnym stopniu, uruchamiając go z ograniczeniem na głębokość spadku. Po algorytmie próbującym znaleźć cięcie w ten sposób pozostawały grafy większego rozmiaru. Dzieje się tak, ponieważ cięcia były bardzo niezbalansowane: usuwając 5-10 węzłów, udawało się odłączyć zaledwie 15-20.
Warto zauważyć, że w artykułach na temat teoretycznie najszybszych algorytmów stosowane są znacznie bardziej zaawansowane techniki wyboru węzłów do podziału. Takie techniki mają bardzo skomplikowaną implementację i często złe wyniki pod względem czasu i pamięci. Nie udało mi się wydzielić z nich w pełni akceptowalnych dla praktyki.
Jak stosować zasady uproszczenia
Mamy już pomysły na kernelizację. Przypomnę:
- Jeśli istnieje izolowany węzeł, usuń go.
- Jeśli istnieje wierzchołek o stopniu 1, usuń go i weź jego sąsiada w odpowiedzi.
- Jeśli istnieje wierzchołek o stopniu przynajmniej k + 1, weź go w odpowiedzi.
Z pierwszymi dwoma wszystko jasne, z trzecim jest jeden trik. Jeśli w żartobliwej zagadce o barze mieliśmy ograniczenie górne na k, to w wyzwaniu PACE musimy po prostu znaleźć wierzchołkowe pokrycie minimalnego rozmiaru. To typowa transformacja zadań wyszukiwania (Search Problem) w zadania rozwiązania (Decision Problem), często między tymi dwoma rodzajami zadań nie robi się różnicy. W praktyce, gdy piszemy rozwiązanie dla zadania o wierzchołkowym pokryciu, różnica może być. Na przykład, jak w trzecim punkcie.
Z punktu widzenia realizacji można postąpić na dwa sposoby. Pierwsze podejście nazywa się Iterative Deepening. Polega ono na tym, że zaczynamy od jakiegoś rozsądnego ograniczenia dolnego na odpowiedź i następnie uruchamiamy nasz algorytm, używając tego ograniczenia jako górnego ograniczenia na odpowiedź, nie schodząc w rekurencji głębiej niż to ograniczenie. Jeśli znajdziemy jakąś odpowiedź, jest ona gwarantowanie optymalna, w przeciwnym razie możemy zwiększyć to ograniczenie o jeden i ponownie uruchomić algorytm.
Inne podejście polega na przechowywaniu jakiejś aktualnej optymalnej odpowiedzi i poszukiwaniu odpowiedzi mniejszego rozmiaru, przy jej znalezieniu zmieniając ten parametr k aby lepiej odciąć zbędne gałęzie w wyszukiwaniu.
Po przeprowadzeniu kilku nocnych eksperymentów, zdecydowałem się na kombinację tych dwóch sposobów: najpierw uruchamiam swój algorytm z jakimś ograniczeniem na głębokość wyszukiwania (dobierając je tak, aby zajmowało to znikomy czas w porównaniu z głównym rozwiązaniem) i używam najlepiej znalezionej odpowiedzi jako górnego ograniczenia na odpowiedź — to znaczy na to same k.
Wierzchoły o stopniu 2
Z wierzchołkami o stopniu 0 i 1 się uporaliśmy. Okazuje się, że można to zrobić także z wierzchołkami o stopniu 2, ale do tego od grafu są potrzebne bardziej skomplikowane operacje.
Aby to wyjaśnić, musimy jakoś oznaczyć wierzchołki. Nazwijmy wierzchołek o stopniu 2 wierzchołkiem v, a jego sąsiadów — wierzchołkami x i y. Następnie będziemy mieli dwa przypadki.
- Kiedy x i y — sąsiedzi. Wtedy można wziąć w odpowiedzi x i y, a v usunąć. I naprawdę, z tego trójkąta przynajmniej dwa wierzchołki musimy wziąć w odpowiedzi, i na pewno nie przegramy, jeśli weźmiemy x i y: prawdopodobnie mają jeszcze sąsiadów, a v oni nie mają.
- Kiedy x i y — nie sąsiedzi. W takim razie twierdzi się, że wszystkie trzy wierzchołki można połączyć w jeden. Idea polega na tym, że w takim przypadku istnieje optymalne rozwiązanie, które obejmie albo v, albo oba wierzchołki x i y. Przy czym w pierwszym przypadku będziemy musieli wziąć w odpowiedzi wszystkich sąsiadów x i y, a w drugim nie jest to konieczne. To dokładnie odpowiada przypadkom, gdy nie bierzemy połączonego wierzchołka w odpowiedzi i gdy go bierzemy. pozostało jedynie zauważyć, że w obu przypadkach odpowiedź z tej operacji zmniejsza się o jeden.
Warto zauważyć, że takie podejście w uczciwy sposób w czasie liniowym jest dość trudne do realizacji. Łączenie wierzchołków to złożona operacja, trzeba skopiować listy sąsiadów. Jeśli zrobimy to nieostrożnie, możemy otrzymać asymptotycznie nieoptymalny czas działania (na przykład, jeśli po każdym połączeniu skopiujemy wiele krawędzi). Skupiłem się na poszukiwaniu całkowitych ścieżek z wierzchołków stopnia 2 i rozważaniu mnóstwa szczególnych przypadków, takich jak cykle z takich wierzchołków lub z wszystkimi takimi wierzchołkami z wyjątkiem jednego.
Ponadto, ta operacja musi być odwracalna, aby podczas powrotu z rekursji przywrócić graf do pierwotnego stanu. Aby to zapewnić, nie czyściłem list krawędzi połączonych wierzchołków, po czym po prostu wiedziałem, które krawędzie dokąd skierować. Taka realizacja grafów również wymaga ostrożności, ale zapewnia uczciwy czas liniowy. A dla grafów z kilkudziesięcioma tysiącami krawędzi mieści się to w pamięci podręcznej procesora, co daje duże przewagi w prędkości.
Liniowe jądro
Na koniec, najbardziej interesująca część jądra.
Na początku przypomnijmy, że w grafach dwudzielnych minimalne pokrycie wierzchołkowe można znaleźć w 
. W tym celu należy skorzystać z algorytmu aby znaleźć tam maksymalne skojarzenie, a następnie skorzystać z twierdzenia .
Idea liniowego jądra jest taka: najpierw rozdzielamy graf, to znaczy zamiast każdego wierzchołka v wprowadzamy dwa wierzchołki 
i 
, a zamiast każdej krawędzi u — v wprowadzamy dwie krawędzie 
i 
Otrzymany graf będzie dwudzielny. Znajdziemy w nim minimalne pokrycie wierzchołków. Niektóre wierzchołki oryginalnego grafu znajdą się tam dwa razy, niektóre tylko raz, a inne - ani razu. Twierdzenie Nemhausera-Trottera stwierdza, że w takim przypadku można usunąć wierzchołki, które nie znalazły się ani razu, a w odpowiedzi wziąć te, które znalazły się dwa razy. Co więcej, mówi, że z pozostałych wierzchołków (tych, które znalazły się raz) należy wziąć w odpowiedzi przynajmniej połowę.
Właśnie nauczyliśmy się pozostawiać w grafie nie więcej niż 2k wierzchołków. I rzeczywiście, jeśli w odpowiedzi zostaje przynajmniej połowa wszystkich wierzchołków, to w sumie jest ich nie więcej niż 2k.
Tutaj udało mi się zrobić mały krok naprzód. Oczywiste jest, że zbudowane w ten sposób jądro zależy od tego, jakie dokładnie minimalne pokrycie wierzchołków w grafie dwudzielnym przyjęliśmy. Chciałbym wziąć takie, aby liczba pozostałych wierzchołków była minimalna. Wcześniej robić to można było tylko w czasie 
. Ja jednak wymyśliłem realizację tego algorytmu w czasie 
, dzięki czemu to jądro można szukać w grafach liczących setki tysięcy wierzchołków na każdym etapie branżingu.
Wynik
Praktyka pokazuje, że moje rozwiązanie dobrze działa na testach liczących kilka setek wierzchołków i kilka tysięcy krawędzi. Na takich testach można spodziewać się, że rozwiązanie znajdzie się w pół godziny. Prawdopodobieństwo znalezienia odpowiedzi w rozsądnym czasie ogólnie wzrasta, jeśli w grafie jest wystarczająco dużo wierzchołków o dużym stopniu, na przykład stopnia 10 i wyżej.
Aby wziąć udział w zawodach, rozwiązania należało wysłać na . Z danych przedstawionych tam , moje rozwiązanie na otwartych testach zajmuje trzecie miejsce spośród dwudziestu, z dużą przewagą nad drugim. Jeśli być całkowicie szczerym, to nie do końca wiadomo, jak będą oceniane rozwiązania w samych zawodach: na przykład moje rozwiązanie przechodzi mniej testów niż rozwiązanie na czwartym miejscu, ale te, które przechodzi, działa szybciej.
Wyniki z zamkniętych testów będą znane pierwszego lipca.
Źródło: habr.com
