Praca badawcza jest prawdopodobnie najciekawszą częścią naszego szkolenia. Pomysł jest taki, aby jeszcze na studiach spróbować swoich sił w wybranym przez siebie kierunku. Przykładowo studenci kierunków Software Engineering i Machine Learning często wyjeżdżają na badania do firm (głównie JetBrains czy Yandex, ale nie tylko).
W tym poście opowiem o moim projekcie z informatyki. W ramach swojej pracy studiowałem i wdrażałem w praktyce podejścia do rozwiązywania jednego z najbardziej znanych problemów NP-trudnych: problem pokrycia wierzchołków.
Obecnie bardzo szybko rozwija się ciekawe podejście do problemów NP-trudnych – algorytmy sparametryzowane. Postaram się Cię o tym przekonać, opowiem o kilku prostych sparametryzowanych algorytmach i opiszę jedną potężną metodę, która bardzo mi pomogła. Swoje wyniki zaprezentowałem na konkursie PACE Challenge: według wyników testów otwartych moje rozwiązanie zajmuje trzecie miejsce, a ostateczne wyniki poznamy 1 lipca.
O mnie
Nazywam się Wasilij Alferow, kończę trzeci rok w Wyższej Szkole Ekonomii Państwowego Uniwersytetu Badawczego w Petersburgu. Algorytmami interesuję się już od czasów szkolnych, kiedy to uczyłem się w moskiewskiej szkole nr 179 i z sukcesami brałem udział w olimpiadach informatycznych.
Do baru wchodzi skończona liczba specjalistów od algorytmów sparametryzowanych...
Przykład wzięty z książki
Wyobraź sobie, że jesteś ochroniarzem w barze w małym miasteczku. W każdy piątek połowa miasta przychodzi do Twojego baru, aby się zrelaksować, co sprawia Ci wiele kłopotów: musisz wyrzucić hałaśliwych klientów z baru, aby zapobiec bójkom. W końcu masz dość i decydujesz się na podjęcie środków zapobiegawczych.
Ponieważ Twoje miasto jest małe, wiesz dokładnie, które pary klientów będą ze sobą walczyć, jeśli wylądują razem w barze. Czy masz listę n ludzi, którzy przyjdą dziś wieczorem do baru. Postanawiasz trzymać niektórych mieszkańców miasta z dala od baru, tak aby nikt nie wdał się w bójkę. Jednocześnie Twoi szefowie nie chcą tracić zysków i będą niezadowoleni, jeśli nie pozwolisz im więcej niż k osób.
Niestety, problem, który przed tobą stoi, jest klasycznym problemem NP-trudnym. Być może znasz ją jako lub jako problem pokrycia wierzchołków. W przypadku takich problemów w ogólnym przypadku nie ma algorytmów, które działałyby w akceptowalnym czasie. Gwoli ścisłości, niesprawdzona i dość mocna hipoteza ETH (ang. Exponential Time Hypothesis) mówi, że problemu tego nie da się rozwiązać w czasie oznacza to, że nie można wymyślić nic zauważalnie lepszego niż pełne wyszukiwanie. Załóżmy na przykład, że ktoś przyjdzie do Twojego baru n = 1000 Człowiek. Wtedy nastąpi pełne wyszukiwanie opcji, które są w przybliżeniu - szalona ilość. Na szczęście twoje kierownictwo wyznaczyło ci limit k = 10 XNUMX XNUMX, więc liczba kombinacji, po których należy wykonać iterację, jest znacznie mniejsza: liczba podzbiorów dziesięciu elementów wynosi . To jest lepsze, ale nadal nie zostanie policzone w ciągu jednego dnia, nawet w przypadku potężnego klastra.
Aby wyeliminować możliwość bójki w tej konfiguracji napiętych relacji między gośćmi baru, musisz trzymać Boba, Daniela i Fedora z daleka. Nie ma rozwiązania, w którym pozostaną tylko dwa.
Czy to oznacza, że nadszedł czas, aby się poddać i wpuścić wszystkich? Rozważmy inne opcje. Otóż nie można wpuścić np. tylko tych, którzy najprawdopodobniej będą walczyć z bardzo dużą liczbą osób. Jeśli ktoś może chociaż powalczyć k+1 inna osoba, to zdecydowanie nie możesz go wpuścić - w przeciwnym razie będziesz musiał wszystkich trzymać z daleka k+1 mieszczan, z którymi może walczyć, co z pewnością zdenerwuje kierownictwo.
Obyś wyrzucił każdego, kogo tylko możesz, zgodnie z tą zasadą. Wtedy wszyscy inni będą mogli walczyć nie więcej niż k ludzie. Wyrzucanie ich k człowieku, nie możesz zapobiec niczemu więcej niż konflikty. Oznacza to, że jeśli jest ich więcej niż Jeśli dana osoba jest uwikłana w co najmniej jeden konflikt, z pewnością nie można zapobiec im wszystkim. Ponieważ oczywiście na pewno wpuścisz osoby całkowicie pozbawione konfliktu, musisz przejrzeć wszystkie podzbiory wielkości dziesięciu z dwustu osób. Jest ich około , a tę liczbę operacji można już posortować w klastrze.
Jeśli można bezpiecznie przyjmować osoby, które w ogóle nie są w konflikcie, to co z tymi, które uczestniczą tylko w jednym konflikcie? W rzeczywistości można ich również wpuścić, zamykając drzwi przeciwnikowi. Rzeczywiście, jeśli Alicja jest w konflikcie tylko z Bobem, to jeśli wypuścimy Alicję z nich obu, nie przegramy: Bob może mieć inne konflikty, ale Alicja z pewnością ich nie ma. Co więcej, nie ma sensu, abyśmy nie wpuścili nas obu. Po takich operacjach nie pozostaje już nic goście z nierozwiązanym losem: mamy tylko konflikty, każdy z dwoma uczestnikami i każdy zaangażowany w co najmniej dwóch. Pozostaje więc tylko uporządkować opcji, które z łatwością można uznać za pół dnia na laptopie.
Tak naprawdę prostym rozumowaniem można osiągnąć jeszcze atrakcyjniejsze warunki. Pamiętaj, że zdecydowanie musimy rozstrzygnąć wszelkie spory, czyli z każdej skłóconej pary wybrać przynajmniej jedną osobę, której nie wpuścimy. Rozważmy następujący algorytm: weźmy dowolny konflikt, z którego usuwamy jednego uczestnika i rekurencyjnie zaczynamy od reszty, następnie usuwamy drugiego i również zaczynamy rekurencyjnie. Ponieważ na każdym kroku kogoś wyrzucamy, drzewo rekurencji takiego algorytmu jest binarnym drzewem głębi k, więc w sumie algorytm działa Gdzie n jest liczbą wierzchołków, oraz m - liczba żeber. W naszym przykładzie jest to około dziesięciu milionów, które można obliczyć w ułamku sekundy nie tylko na laptopie, ale nawet na telefonie komórkowym.
Powyższy przykład jest przykładem sparametryzowany algorytm. Algorytmy sparametryzowane to algorytmy działające w czasie f(k) poli(n)Gdzie p - wielomian, f jest dowolną funkcją obliczeniową, oraz k - jakiś parametr, który prawdopodobnie będzie znacznie mniejszy niż rozmiar problemu.
Całe rozumowanie poprzedzające ten algorytm podaje przykład jądrowanie jest jedną z ogólnych technik tworzenia sparametryzowanych algorytmów. Kernelizacja to redukcja rozmiaru problemu do wartości ograniczonej funkcją parametru. Powstały problem jest często nazywany jądrem. Zatem, poprzez proste rozumowanie o stopniach wierzchołków, otrzymaliśmy jądro kwadratowe dla problemu pokrycia wierzchołków, sparametryzowane przez wielkość odpowiedzi. Istnieją inne ustawienia, które możesz wybrać dla tego zadania (takie jak Vertex Cover Above LP), ale to jest ustawienie, które omówimy.
Wyzwanie tempa
Konkurencja (The Parameterized Algorithms and Computational Experiments Challenge) powstało w 2015 roku, aby ustalić powiązanie pomiędzy sparametryzowanymi algorytmami a podejściami stosowanymi w praktyce do rozwiązywania problemów obliczeniowych. Pierwsze trzy konkursy dotyczyły znalezienia szerokości drzewa grafu (), szukając drzewa Steinera () i poszukiwanie zbioru wierzchołków przecinających cykle (). W tym roku jednym z problemów, w którym można było spróbować swoich sił, był opisany powyżej problem pokrycia wierzchołków.
Konkurs z roku na rok cieszy się coraz większą popularnością. Jeśli wierzyć wstępnym danym, w tym roku do rywalizacji o samodzielne rozwiązanie problemu pokrycia wierzchołków wzięły udział 24 drużyny. Warto zaznaczyć, że konkurs trwa nie kilka godzin czy nawet tydzień, ale kilka miesięcy. Zespoły mają okazję zapoznać się z literaturą, zaproponować własny, oryginalny pomysł i spróbować go wdrożyć. W istocie konkurs ten ma charakter projektu badawczego. Pomysły na najskuteczniejsze rozwiązania i wręczenie nagród zwycięzcom odbędzie się w połączeniu z konferencją (Międzynarodowe Sympozjum Obliczeń Parametryzowanych i Dokładnych) w ramach największego corocznego spotkania algorytmicznego w Europie . Więcej szczegółowych informacji na temat samego konkursu można znaleźć na stronie , a wyniki lat ubiegłych kłamią .
Schemat rozwiązania
Aby rozwiązać problem pokrycia wierzchołków, próbowałem użyć sparametryzowanych algorytmów. Zwykle składają się z dwóch części: zasad upraszczających (które w idealnym przypadku prowadzą do jądra) i zasad podziału. Reguły uproszczenia polegają na wstępnym przetwarzaniu danych wejściowych w czasie wielomianowym. Celem stosowania takich reguł jest zredukowanie problemu do równoważnego mniejszego problemu. Reguły upraszczające są najdroższą częścią algorytmu, a zastosowanie tej części prowadzi do całkowitego czasu działania zamiast prostego czasu wielomianowego. W naszym przypadku zasady podziału opierają się na fakcie, że dla każdego wierzchołka należy przyjąć albo ten, albo jego sąsiada jako odpowiedź.
Ogólny schemat jest taki: stosujemy zasady upraszczania, następnie wybieramy jakiś wierzchołek i wykonujemy dwa wywołania rekurencyjne: w pierwszym bierzemy go w odpowiedzi, a w drugim bierzemy wszystkich jego sąsiadów. Nazywamy to rozszczepieniem (rozgałęzieniem) wzdłuż tego wierzchołka.
Dokładnie jeden dodatek zostanie wprowadzony do tego schematu w następnym akapicie.
Pomysły na zasady podziału (brunchingu).
Omówmy, jak wybrać wierzchołek, wzdłuż którego nastąpi podział.
Główna idea jest bardzo zachłanna w sensie algorytmicznym: weźmy wierzchołek o maksymalnym stopniu i podzielmy go wzdłuż niego. Dlaczego wydaje się lepsze? Ponieważ w drugiej gałęzi wywołania rekurencyjnego usuniemy w ten sposób wiele wierzchołków. Możesz liczyć na to, że pozostał jeszcze mały wykres i możemy nad nim szybko popracować.
To podejście, wraz z omówionymi już prostymi technikami jądra, sprawdza się dobrze i rozwiązuje niektóre testy o rozmiarze kilku tysięcy wierzchołków. Ale na przykład nie działa to dobrze w przypadku grafów sześciennych (to znaczy takich, których stopień każdego wierzchołka wynosi trzy).
Istnieje inny pomysł oparty na dość prostym pomyśle: jeśli graf zostanie odłączony, problem na jego połączonych elementach można rozwiązać niezależnie, łącząc na końcu odpowiedzi. Nawiasem mówiąc, jest to mała obiecana modyfikacja w schemacie, która znacznie przyspieszy rozwiązanie: wcześniej w tym przypadku pracowaliśmy na iloczyn czasów obliczania odpowiedzi komponentów, ale teraz pracujemy dla Suma. Aby przyspieszyć rozgałęzianie, należy zamienić graf połączony w rozłączony.
Jak to zrobić? Jeśli na wykresie jest punkt artykulacji, trzeba z nim walczyć. Punkt artykulacji to wierzchołek taki, że po usunięciu wykres traci łączność. Wszystkie punkty skrzyżowania na wykresie można znaleźć za pomocą klasycznego algorytmu w czasie liniowym. Takie podejście znacznie przyspiesza rozgałęzianie.
Po usunięciu dowolnego z wybranych wierzchołków graf zostanie podzielony na połączone komponenty.
Zrobimy to, ale chcemy więcej. Na przykład poszukaj małych nacięć wierzchołków na wykresie i podziel je wzdłuż wierzchołków. Najbardziej efektywnym sposobem, jaki znam na znalezienie minimalnego globalnego cięcia wierzchołków, jest użycie drzewa Gomori-Hu, które jest zbudowane w czasie sześciennym. W wyzwaniu PACE typowy rozmiar wykresu to kilka tysięcy wierzchołków. W tej sytuacji na każdym wierzchołku drzewa rekurencji należy wykonać miliardy operacji. Okazuje się, że rozwiązanie problemu w wyznaczonym czasie jest po prostu niemożliwe.
Spróbujmy zoptymalizować rozwiązanie. Minimalne przecięcie wierzchołka między parą wierzchołków można znaleźć za pomocą dowolnego algorytmu konstruującego maksymalny przepływ. Możesz wpuścić go do takiej sieci w praktyce działa bardzo szybko. Podejrzewam, że teoretycznie możliwe jest udowodnienie oszacowania czasu pracy , co jest już całkiem akceptowalne.
Kilka razy próbowałem szukać cięć pomiędzy parami losowych wierzchołków i wybierać najbardziej zrównoważone. Niestety, dało to słabe wyniki w otwartych testach PACE Challenge. Porównałem to z algorytmem, który dzieli wierzchołki maksymalnego stopnia, uruchamiając je z ograniczeniem głębokości opadania. Algorytm próbujący znaleźć w ten sposób cięcie pozostawiał większe wykresy. Wynika to z faktu, że cięcia okazały się bardzo niezrównoważone: po usunięciu 5-10 wierzchołków udało się oddzielić tylko 15-20.
Warto zauważyć, że artykuły o teoretycznie najszybszych algorytmach wykorzystują znacznie bardziej zaawansowane techniki wybierania wierzchołków do podziału. Techniki takie mają bardzo złożoną implementację i często słabą wydajność pod względem czasu i pamięci. Nie udało mi się zidentyfikować tych, które są w pełni akceptowalne w praktyce.
Jak stosować zasady uproszczone
Mamy już pomysły na kernelizację. Pozwól, że ci przypomnę:
- Jeśli istnieje izolowany wierzchołek, usuń go.
- Jeśli istnieje wierzchołek stopnia 1, usuń go i w odpowiedzi weź jego sąsiada.
- Przynajmniej jeśli istnieje wierzchołek stopnia k+1, zabierz to z powrotem.
Z pierwszymi dwoma wszystko jest jasne, z trzecim jest jedna sztuczka. Jeśli w komiksowym problemie dotyczącym paska podano nam górną granicę k, to w PACE Challenge wystarczy znaleźć pokrycie wierzchołków o minimalnym rozmiarze. Jest to typowa transformacja problemów wyszukiwania w problemy decyzyjne; często nie ma różnicy między tymi dwoma typami problemów. W praktyce, jeśli piszemy rozwiązanie problemu pokrycia wierzchołków, może być różnica. Na przykład jak w punkcie trzecim.
Z punktu widzenia wdrożenia można postępować na dwa sposoby. Pierwsze podejście nazywa się pogłębianiem iteracyjnym. Wygląda to następująco: możemy zacząć od rozsądnego ograniczenia odpowiedzi od dołu, a następnie uruchomić nasz algorytm, używając tego ograniczenia jako ograniczenia odpowiedzi z góry, bez obniżania rekurencji niż to ograniczenie. Jeśli znaleźliśmy jakąś odpowiedź, na pewno będzie ona optymalna, w przeciwnym razie możemy zwiększyć ten limit o jeden i zacząć od nowa.
Innym podejściem jest przechowywanie aktualnej optymalnej odpowiedzi i szukanie mniejszej odpowiedzi, zmieniając ten parametr po znalezieniu k dla większego odcięcia niepotrzebnych gałęzi w poszukiwaniach.
Po przeprowadzeniu kilku nocnych eksperymentów zdecydowałem się na kombinację tych dwóch metod: po pierwsze, uruchamiam algorytm z pewnym ograniczeniem głębokości wyszukiwania (wybierając go tak, aby zajmowało to znikomo dużo czasu w porównaniu z głównym rozwiązaniem) i korzystałem z najlepszych rozwiązanie znalezione jako górna granica odpowiedzi - czyli tego samego k.
Wierzchołki stopnia 2
Zajmowaliśmy się wierzchołkami stopnia 0 i 1. Okazuje się, że można to zrobić z wierzchołkami stopnia 2, ale będzie to wymagało bardziej skomplikowanych operacji z grafu.
Aby to wyjaśnić, musimy jakoś wyznaczyć wierzchołki. Nazwijmy wierzchołek stopnia 2 wierzchołkiem v, a jego sąsiedzi - wierzchołki x и y. Następnie będziemy mieli dwa przypadki.
- Kiedy x и y - sąsiedzi. Wtedy będziesz mógł odpowiedzieć x и yI v usuwać. Rzeczywiście, z tego trójkąta trzeba w zamian wziąć co najmniej dwa wierzchołki i na pewno nie stracimy, jeśli weźmiemy x и y: prawdopodobnie mają innych sąsiadów i v Nie ma ich tu.
- Kiedy x и y - nie sąsiedzi. Następnie stwierdza się, że wszystkie trzy wierzchołki można skleić w jeden. Pomysł jest taki, że w tym przypadku istnieje optymalna odpowiedź, w której bierzemy albo vlub oba wierzchołki x и y. Co więcej, w pierwszym przypadku będziemy musieli w odpowiedzi przyjąć wszystkich sąsiadów x и y, ale w drugim nie jest to konieczne. Odpowiada to dokładnie przypadkom, kiedy w odpowiedzi nie bierzemy sklejonego wierzchołka i kiedy to robimy. Pozostaje tylko zauważyć, że w obu przypadkach odpowiedź na taką operację zmniejsza się o jeden.
Warto zauważyć, że podejście to jest dość trudne do dokładnego wdrożenia w uczciwym czasie liniowym. Sklejanie wierzchołków jest skomplikowaną operacją; należy skopiować listy sąsiadów. Jeśli zostanie to zrobione niedbale, możesz otrzymać asymptotycznie nieoptymalny czas działania (na przykład, jeśli po każdym sklejeniu będziesz kopiować wiele krawędzi). Zdecydowałem się na znalezienie całych ścieżek z wierzchołków stopnia 2 i przeanalizowanie kilku specjalnych przypadków, takich jak cykle z takich wierzchołków lub ze wszystkich takich wierzchołków z wyjątkiem jednego.
Dodatkowo konieczne jest, aby operacja ta była odwracalna, abyśmy wracając z rekurencji przywrócili graf do jego pierwotnej postaci. Aby to zapewnić, nie wyczyściłem list krawędzi połączonych wierzchołków i wtedy po prostu wiedziałem, które krawędzie muszą gdzie iść. Ta implementacja wykresów również wymaga dokładności, ale zapewnia sprawiedliwy czas liniowy. A w przypadku wykresów kilkudziesięciu tysięcy krawędzi mieści się w pamięci podręcznej procesora, co zapewnia ogromne korzyści w zakresie szybkości.
Jądro liniowe
Na koniec najciekawsza część jądra.
Na początek przypomnijmy, że w grafach dwudzielnych minimalne pokrycie wierzchołków można znaleźć za pomocą . Aby to zrobić, musisz użyć algorytmu aby znaleźć tam maksymalne dopasowanie, a następnie skorzystać z twierdzenia .
Idea jądra liniowego jest następująca: najpierw rozwidlamy graf, czyli zamiast każdego wierzchołka v dodajmy dwa piki и i zamiast każdej krawędzi ty - w dodajmy dwa żebra и . Powstały wykres będzie dwudzielny. Znajdźmy w nim minimalne pokrycie wierzchołków. Niektóre wierzchołki pierwotnego grafu dotrą tam dwukrotnie, inne tylko raz, a jeszcze inne nigdy. Twierdzenie Nemhausera-Trottera stwierdza, że w tym przypadku można usunąć wierzchołki, które nie trafiły ani razu, i cofnąć te, które trafiły dwukrotnie. Co więcej, mówi, że z pozostałych wierzchołków (tych, które trafiły raz) jako odpowiedź należy przyjąć co najmniej połowę.
Właśnie nauczyliśmy się nie zostawiać więcej niż 2k szczyty Rzeczywiście, jeśli pozostała odpowiedź to co najmniej połowa wszystkich wierzchołków, to w sumie nie ma więcej wierzchołków niż 2k.
Tutaj udało mi się zrobić mały krok do przodu. Jest oczywiste, że tak skonstruowane jądro zależy od tego, jakie minimalne pokrycie wierzchołków przyjęliśmy w grafie dwudzielnym. Chciałbym wziąć jeden, aby liczba pozostałych wierzchołków była minimalna. Wcześniej udawało im się to zrobić tylko na czas . W swoim czasie wymyśliłem implementację tego algorytmu , zatem rdzeń ten można szukać na grafach setek tysięcy wierzchołków na każdym etapie rozgałęzienia.
Doświadcz mocnych i skutecznych rezultatów
Praktyka pokazuje, że moje rozwiązanie sprawdza się dobrze na testach kilkuset wierzchołków i kilku tysięcy krawędzi. W takich testach można się spodziewać, że rozwiązanie zostanie znalezione w ciągu pół godziny. Prawdopodobieństwo znalezienia odpowiedzi w akceptowalnym czasie w zasadzie wzrasta, jeśli graf ma wystarczająco dużą liczbę wierzchołków wysokiego stopnia, na przykład stopnia 10 i wyższego.
Aby wziąć udział w konkursie, należało przesłać rozwiązania na adres . Sądząc po informacjach tam przedstawionych , moje rozwiązanie w testach otwartych zajmuje trzecie miejsce na dwadzieścia, z dużą różnicą do drugiego. Szczerze mówiąc, nie jest do końca jasne, jak rozwiązania będą oceniane w samej konkurencji: np. moje rozwiązanie przechodzi mniej testów niż rozwiązanie na czwartym miejscu, ale na tych, które przejdą, działa szybciej.
Wyniki testów zamkniętych poznamy XNUMX lipca.
Źródło: www.habr.com