Istraživački rad je možda najzanimljiviji dio našeg usavršavanja. Ideja je okušati se u odabranom smjeru još na fakultetu. Na primjer, studenti iz područja softverskog inženjerstva i strojnog učenja često odlaze istraživati u tvrtke (uglavnom JetBrains ili Yandex, ali ne samo).
U ovom postu govorit ću o svom projektu iz informatike. U sklopu svog rada proučavao sam i u praksi primjenjivao pristupe rješavanju jednog od najpoznatijih NP-teških problema: problem pokrivanja vrhova.
Danas se vrlo brzo razvija zanimljiv pristup NP-teškim problemima - parametrizirani algoritmi. Pokušat ću vas upoznati, reći ću vam neke jednostavne parametrizirane algoritme i opisati jednu moćnu metodu koja mi je puno pomogla. Na natjecanju PACE Challenge prezentirao sam svoje rezultate: prema rezultatima otvorenih testova moje rješenje zauzima treće mjesto, a konačni rezultati bit će poznati 1. srpnja.
O meni
Moje ime je Vasily Alferov, sada završavam treću godinu na Nacionalnom istraživačkom sveučilištu Visoka škola ekonomije - St. Petersburg. Algoritmi su me zanimali još od školskih dana, kada sam studirao u moskovskoj školi br. 179 i uspješno sudjelovao na informatičkim olimpijadama.
Konačan broj stručnjaka za parametrizirane algoritme ulazi u bar...
Primjer preuzet iz knjige
Zamislite da ste zaštitar bara u malom gradu. Svakog petka pola grada dolazi u vaš bar da se opusti, što vam zadaje dosta problema: morate izbaciti razularene mušterije iz lokala kako biste spriječili tučnjave. Na kraju vam dosadi i odlučite poduzeti preventivne mjere.
Budući da je vaš grad mali, točno znate koji će se parovi posjetitelja vjerojatno potući ako zajedno završe u baru. Imate li popis n ljudi koji će večeras doći u bar. Odlučite zadržati neke građane izvan bara, a da se nitko ne potuče. U isto vrijeme, vaši šefovi ne žele izgubiti profit i bit će nezadovoljni ako im ne dopustite više od k ljudi.
Nažalost, problem pred vama je klasični NP-teški problem. Možda je poznajete kao , ili kao problem pokrivanja vrhova. Za takve probleme, u općem slučaju, ne postoje algoritmi koji rade u prihvatljivom vremenu. Točnije, nedokazana i prilično jaka hipoteza ETH (Exponential Time Hypothesis) kaže da se ovaj problem ne može riješiti na vrijeme , odnosno ne možete smisliti ništa osjetno bolje od potpune pretrage. Na primjer, recimo da će netko doći u vaš bar n = 1000 ljudski. Tada će kompletna pretraga biti mogućnosti kojih ima otprilike - ludi iznos. Srećom, vaš menadžment vam je dao limit k = 10, tako da je broj kombinacija koje trebate ponoviti mnogo manji: broj podskupa od deset elemenata je . Ovo je bolje, ali još uvijek se neće računati u jednom danu čak ni na moćnom klasteru.
Kako biste eliminirali mogućnost tučnjave u ovoj konfiguraciji zategnutih odnosa među posjetiteljima bara, morate držati Boba, Daniela i Fedora podalje. Ne postoji rješenje u kojem će ostati samo dvoje.
Znači li to da je vrijeme da se prepustite i pustite sve unutra? Razmotrimo druge mogućnosti. Pa, na primjer, ne možete pustiti samo one koji će se vjerojatno boriti s vrlo velikim brojem ljudi. Ako se netko može boriti barem sa k+1 drugu osobu, onda je definitivno ne možete pustiti unutra - inače ćete morati držati sve vani k+1 varošani, s kojima se može potući, što će rukovodstvu svakako smetati.
Neka po ovom principu izbacite sve koje ste mogli. Tada se svi ostali mogu boriti s ne više od k narod. Izbacivši ih k čovječe, ne možeš spriječiti ništa više od sukobi. To znači da ako ima više od Ako je osoba uključena u barem jedan sukob, onda ih sigurno ne možete sve spriječiti. Budući da ćete, naravno, sigurno pustiti potpuno nekonfliktne ljude, morate proći kroz sve podskupove veličine deset od dvjesto ljudi. Ima ih otprilike , a ovaj broj operacija se već može sortirati na klasteru.
Ako možete sa sigurnošću uzeti pojedince koji nemaju nikakav sukob, što je onda s onima koji sudjeluju u samo jednom sukobu? Zapravo, mogu se pustiti unutra i zatvaranjem vrata protivniku. Dapače, ako je Alisa u sukobu samo s Bobom, onda ako Alisu izbacimo iz njih dvoje, nećemo izgubiti: Bob možda ima drugih sukoba, ali Alisa ih sigurno nema. Štoviše, nema smisla da nas oboje ne pustimo unutra. Nakon takvih operacija više nema ostataka gosti s neriješenom sudbinom: imamo samo sukobi, svaki s dva sudionika i svaki uključen u najmanje dva. Dakle, preostaje samo sortirati opcije, koje se lako mogu smatrati pola dana na prijenosnom računalu.
Zapravo, jednostavnim razmišljanjem možete postići još atraktivnije uvjete. Napominjemo da svakako moramo riješiti sve sporove, odnosno iz svakog sukobljenog para izabrati barem jednu osobu koju nećemo pustiti unutra. Razmotrimo sljedeći algoritam: uzmimo bilo koji sukob iz kojeg uklanjamo jednog sudionika i rekurzivno počinjemo od ostatka, zatim uklanjamo drugog i također počinjemo rekurzivno. Budući da na svakom koraku nekoga izbacujemo, rekurzijsko stablo takvog algoritma je binarno stablo dubine k, tako da ukupno algoritam radi u Gdje n je broj vrhova, i m - broj rebara. U našem primjeru to je oko deset milijuna, što se može izračunati u djeliću sekunde ne samo na prijenosnom računalu, već čak i na mobilnom telefonu.
Gornji primjer je primjer parametrizirani algoritam. Parametrirani algoritmi su algoritmi koji se izvršavaju u vremenu f(k) poli(n)Gdje p - polinom, f je proizvoljna izračunljiva funkcija, i k - neki parametar, koji će vrlo vjerojatno biti puno manji od veličine problema.
Sva razmišljanja prije ovog algoritma daju primjer kernelizacija je jedna od općih tehnika za stvaranje parametriziranih algoritama. Kernelizacija je smanjenje veličine problema na vrijednost ograničenu funkcijom parametra. Rezultirajući problem često se naziva kernel. Dakle, jednostavnim razmišljanjem o stupnjevima vrhova, dobili smo kvadratnu jezgru za problem Vertex Cover, parametriziranu veličinom odgovora. Postoje i druge postavke koje možete odabrati za ovaj zadatak (kao što je Vertex Cover Above LP), ali ovo je postavka o kojoj ćemo raspravljati.
Pace Challenge
Natjecanje (The Parameterized Algorithms and Computational Experiments Challenge) nastao je 2015. kako bi se uspostavila veza između parametriziranih algoritama i pristupa koji se u praksi koriste za rješavanje računalnih problema. Prva tri natjecanja bila su posvećena pronalaženju širine stabla grafa (), u potrazi za Steinerovim stablom () i traženje skupa vrhova koji sijeku cikluse (). Ove godine jedan od problema u kojem ste se mogli okušati bio je gore opisani problem pokrivanja vrhova.
Natjecanje svake godine postaje sve popularnije. Ako je vjerovati preliminarnim podacima, ove su godine u natjecanju samo za rješavanje problema pokrivanja vrhova sudjelovala 24 tima. Vrijedno je napomenuti da natjecanje ne traje nekoliko sati ili čak tjedan dana, već nekoliko mjeseci. Timovi imaju priliku proučiti literaturu, osmisliti vlastitu originalnu ideju i pokušati je provesti. U biti, ovaj natječaj je istraživački projekt. Ideje za najučinkovitija rješenja i dodjela nagrada pobjednicima održat će se uz konferenciju (International Symposium on Parameterized and Exact Computation) u sklopu najvećeg godišnjeg skupa algoritama u Europi . Detaljnije informacije o samom natječaju možete pronaći na , a rezultati prethodnih godina lažu .
Dijagram rješenja
Kako bih riješio problem pokrivanja vrhova, pokušao sam koristiti parametrizirane algoritme. Obično se sastoje od dva dijela: pravila pojednostavljenja (koja idealno vode do kernelizacije) i pravila razdvajanja. Pravila pojednostavljenja su pretprocesiranje ulaza u polinomnom vremenu. Svrha primjene takvih pravila je svesti problem na ekvivalentan manji problem. Pravila pojednostavljenja su najskuplji dio algoritma, a primjenom ovog dijela dolazi se do ukupnog vremena rada umjesto jednostavnog polinomskog vremena. U našem slučaju, pravila cijepanja temelje se na činjenici da za svaki vrh trebate uzeti ili njega ili njegovog susjeda kao odgovor.
Opća shema je sljedeća: primijenimo pravila pojednostavljenja, zatim odaberemo neki vrh i napravimo dva rekurzivna poziva: u prvom ga uzimamo kao odgovor, a u drugom uzimamo sve njegove susjede. To je ono što nazivamo cijepanjem (grananjem) duž ovog vrha.
Točno jedan dodatak će biti napravljen ovoj shemi u sljedećem paragrafu.
Ideje za cijepanje (brunching) pravila
Razgovarajmo o tome kako odabrati vrh duž kojeg će se dogoditi cijepanje.
Glavna ideja je vrlo pohlepna u algoritamskom smislu: uzmimo vrh maksimalnog stupnja i razdvojimo se duž njega. Zašto se čini bolje? Zato što ćemo u drugoj grani rekurzivnog poziva ukloniti puno vrhova na ovaj način. Možete računati na mali grafikon koji je preostao i možemo brzo raditi na njemu.
Ovaj pristup, s već razmotrenim jednostavnim tehnikama kernelizacije, dobro se pokazao i rješava neke testove veličine nekoliko tisuća vrhova. Ali, na primjer, ne radi dobro za kubične grafove (tj. grafove čiji je stupanj svakog vrha tri).
Postoji još jedna ideja koja se temelji na prilično jednostavnoj ideji: ako je graf nepovezan, problem na njegovim povezanim komponentama može se riješiti neovisno, kombinirajući odgovore na kraju. Ovo je, usput, mala obećana izmjena u shemi, koja će značajno ubrzati rješenje: prije smo, u ovom slučaju, radili za proizvod vremena za izračun odziva komponenti, ali sada radimo za zbroj. A da biste ubrzali grananje, trebate pretvoriti povezani graf u nepovezani.
Kako to učiniti? Ako postoji točka artikulacije na grafikonu, morate se boriti oko nje. Točka artikulacije je vrh takav da kada se ukloni, graf gubi svoju povezanost. Sve spojne točke u grafu mogu se pronaći korištenjem klasičnog algoritma u linearnom vremenu. Ovaj pristup značajno ubrzava grananje.
Kada se bilo koji od odabranih vrhova ukloni, graf će se podijeliti na povezane komponente.
Učinit ćemo to, ali želimo više. Na primjer, potražite male rezove vrhova u grafu i razdvojite vrhove iz njega. Najučinkovitiji način za pronalaženje minimalnog globalnog vrhnog rezanja je korištenje Gomori-Hu stabla, koje je izgrađeno u kubičnom vremenu. U PACE Challengeu, tipična veličina grafa je nekoliko tisuća vrhova. U ovoj situaciji potrebno je izvesti milijarde operacija na svakom vrhu rekurzivnog stabla. Ispada da je jednostavno nemoguće riješiti problem u zadanom vremenu.
Pokušajmo optimizirati rješenje. Minimalni vrh presječen između para vrhova može se pronaći bilo kojim algoritmom koji konstruira maksimalni protok. Možete ga pustiti u takvu mrežu , u praksi radi vrlo brzo. Sumnjam da je teoretski moguće dokazati procjenu radnog vremena , što je već sasvim prihvatljivo.
Pokušao sam nekoliko puta potražiti rezove između parova slučajnih vrhova i uzeti najuravnoteženiji. Nažalost, to je dalo loše rezultate u otvorenom PACE Challenge testiranju. Usporedio sam to s algoritmom koji dijeli vrhove maksimalnog stupnja, pokrećući ih s ograničenjem dubine spuštanja. Algoritam koji je pokušavao pronaći rez na ovaj način ostavio je iza sebe veće grafikone. To je zbog činjenice da su se rezovi pokazali vrlo neuravnoteženim: nakon uklanjanja 5-10 vrhova, bilo je moguće odvojiti samo 15-20.
Vrijedno je napomenuti da članci o teoretski najbržim algoritmima koriste puno naprednije tehnike za odabir vrhova za cijepanje. Takve tehnike imaju vrlo složenu implementaciju i često loše performanse u pogledu vremena i memorije. Nisam uspio identificirati one koji su sasvim prihvatljivi za praksu.
Kako primijeniti pravila pojednostavljenja
Već imamo ideje za kernelizaciju. Da vas podsjetim:
- Ako postoji izolirani vrh, izbrišite ga.
- Ako postoji vrh stupnja 1, uklonite ga i uzmite njegovog susjeda kao odgovor.
- Ako postoji vrh stupnja najmanje k+1, povuci to.
S prva dva je sve jasno, s trećim postoji jedan trik. Ako smo u komičnom problemu o baru dobili gornju granicu od k, tada u PACE Challengeu samo trebate pronaći pokrivač vrhova minimalne veličine. Ovo je tipična transformacija problema pretraživanja u probleme odlučivanja; često nema razlike između te dvije vrste problema. U praksi, ako pišemo rješenje za problem pokrivanja vrhova, može postojati razlika. Na primjer, kao u trećoj točki.
Sa stajališta provedbe, postoje dva načina za nastavak. Prvi pristup naziva se iterativno produbljivanje. To je sljedeće: možemo započeti s nekim razumnim ograničenjem odozdo na odgovor, a zatim pokrenuti naš algoritam koristeći to ograničenje kao ograničenje na odgovor odozgo, bez da idemo niže u rekurziji od ovog ograničenja. Ako smo pronašli neki odgovor, on je zajamčeno optimalan, u protivnom možemo povećati ovu granicu za jedan i krenuti ispočetka.
Drugi pristup je pohraniti neki trenutni optimalni odgovor i tražiti manji odgovor, mijenjajući ovaj parametar kada se pronađe k za veće odsijecanje nepotrebnih grana u potrazi.
Nakon nekoliko noćnih eksperimenata, odlučio sam se za kombinaciju ove dvije metode: prvo, pokrećem svoj algoritam s nekom vrstom ograničenja dubine pretraživanja (odabirem ga tako da traje zanemarivo malo vremena u usporedbi s glavnim rješenjem) i koristim najbolje rješenje pronađeno kao gornja granica odgovora - odnosno iste stvari k.
Vrhovi stupnja 2
Bavili smo se vrhovima stupnja 0 i 1. Ispada da se to može učiniti s vrhovima stupnja 2, ali to će zahtijevati složenije operacije iz grafa.
Da bismo to objasnili, moramo nekako označiti vrhove. Nazovimo vrh stupnja 2 vrhom v, a njegovi susjedi - vrhovi x и y. Zatim ćemo imati dva slučaja.
- Kada x и y - Susjedi. Onda možete odgovoriti x и yI v izbrisati. Doista, iz ovog trokuta treba uzeti barem dva vrha, a sigurno nećemo izgubiti ako uzmemo x и y: vjerojatno imaju druge susjede, i v nisu.
- Kada x и y - ne susjedi. Zatim se kaže da se sva tri vrha mogu zalijepiti u jedan. Ideja je da u ovom slučaju postoji optimalan odgovor, u kojem uzimamo bilo koji v, ili oba vrha x и y. Štoviše, u prvom slučaju morat ćemo uzeti sve susjede kao odgovor x и y, ali u drugom nije potrebno. To točno odgovara slučajevima kada ne uzmemo zalijepljeni vrh kao odgovor i kada to učinimo. Ostaje samo primijetiti da se u oba slučaja odgovor od takve operacije smanjuje za jedan.
Vrijedno je napomenuti da je ovaj pristup prilično teško točno implementirati u pravednom linearnom vremenu. Lijepljenje vrhova je složena operacija; trebate kopirati popise susjeda. Ako se to učini nemarno, možete završiti s asimptotski suboptimalnim vremenom rada (na primjer, ako kopirate puno rubova nakon svakog lijepljenja). Zaustavio sam se za pronalaženje cijelih staza iz vrhova stupnja 2 i analiziranje hrpe posebnih slučajeva, kao što su ciklusi iz takvih vrhova ili iz svih takvih vrhova osim jednog.
Osim toga, potrebno je da ova operacija bude reverzibilna, tako da pri povratku iz rekurzije vraćamo graf u izvorni oblik. Kako bih to osigurao, nisam očistio popise rubova spojenih vrhova, a onda sam jednostavno znao koji rubovi kamo trebaju ići. Ova implementacija grafova također zahtijeva točnost, ali pruža pošteno linearno vrijeme. A za grafove od nekoliko desetaka tisuća rubova, stane u predmemoriju procesora, što daje velike prednosti u brzini.
Linearna jezgra
Na kraju, najzanimljiviji dio kernela.
Za početak, prisjetimo se da se u bipartitnim grafovima minimalno pokrivanje vrhova može pronaći korištenjem . Da biste to učinili, morate koristiti algoritam kako bismo tamo pronašli maksimalno podudaranje, a zatim upotrijebimo teorem .
Ideja linearne jezgre je sljedeća: prvo račvamo graf, tj. umjesto svakog vrha v dodajmo dva vrha и , a umjesto svakog ruba u - v dodajmo dva rebra и . Rezultirajući graf će biti bipartitan. Nađimo u njemu minimalni vrh vrha. Neki će vrhovi izvornog grafa tamo stići dva puta, neki samo jednom, a neki nikada. Nemhauser-Trotterov teorem kaže da se u ovom slučaju mogu ukloniti vrhovi koji nisu pogodili niti jednom i vratiti oni koji su pogodili dva puta. Štoviše, ona kaže da od preostalih vrhova (onih koji pogode jednom) trebate uzeti barem polovicu kao odgovor.
Upravo smo naučili ne ostavljati više od 2k vrhovi Doista, ako je preostali odgovor barem polovica svih vrhova, tada ukupno nema više vrhova od 2k.
Ovdje sam uspio napraviti mali korak naprijed. Jasno je da ovako konstruirana jezgra ovisi o tome kakav smo minimalni vrhni pokrov uzeli u bipartitnom grafu. Htio bih uzeti jedan tako da broj preostalih vrhova bude minimalan. Ranije su to mogli učiniti samo na vrijeme . Svojedobno sam smislio implementaciju ovog algoritma , stoga se ova jezgra može tražiti u grafovima stotina tisuća vrhova u svakoj fazi grananja.
Rezultirati
Praksa pokazuje da moje rješenje dobro radi na testovima nekoliko stotina vrhova i nekoliko tisuća bridova. U ovakvim testovima sasvim je moguće očekivati da će se rješenje naći za pola sata. Vjerojatnost pronalaženja odgovora u prihvatljivom vremenu, u načelu, raste ako graf ima dovoljno velik broj vrhova visokog stupnja, na primjer, stupanj 10 i više.
Za sudjelovanje u natječaju rješenja je bilo potrebno poslati na . Sudeći prema tamo iznesenim informacijama , moje rješenje u otvorenim testovima zauzima treće mjesto od dvadeset, s velikim odmakom od drugog. Da budem potpuno iskren, nije sasvim jasno kako će se rješenja ocjenjivati na samom natjecanju: moje rješenje, primjerice, prolazi manje testova od četvrtog, ali na onima koji prolaze radi brže.
Rezultati zatvorenih testiranja bit će poznati XNUMX. srpnja.
Izvor: www.habr.com