Istraživački rad je možda najzanimljiviji dio naše obuke. Ideja je da se okušate u odabranom smjeru dok ste još na fakultetu. Na primjer, studenti iz oblasti softverskog inženjerstva i mašinskog učenja često odlaze da istražuju u kompanijama (uglavnom JetBrains ili Yandex, ali ne samo).
U ovom postu govoriću o svom projektu iz računarstva. U sklopu svog rada proučavao sam i 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 sa brzinom, reći vam nekoliko jednostavnih parametriziranih algoritama i opisati jednu moćnu metodu koja mi je puno pomogla. Svoje rezultate sam predstavio na takmičenju PACE Challenge: prema rezultatima otvorenih testova moje rješenje zauzima treće mjesto, a konačni rezultati će biti poznati 1. jula.
O meni
Moje ime je Vasilij Alferov, završavam treću godinu na Visokoj školi ekonomije Nacionalnog istraživačkog univerziteta - Sankt Peterburg. Za algoritme me zanimaju još od školskih dana, kada sam studirao u moskovskoj školi br. 179 i uspješno učestvovao na informatičkim olimpijadama.
Konačan broj stručnjaka za parametrizovane algoritme ulazi u traku...
Primjer preuzet iz knjige
Zamislite da ste čuvar bara u malom gradu. Svakog petka pola grada dolazi u vaš bar da se opustite, što vam zadaje mnogo problema: morate izbaciti napaćene mušterije iz lokala kako biste spriječili tuče. Na kraju se zasitite i odlučite se na preventivne mjere.
Budući da je vaš grad mali, tačno znate koji će se parovi posjetitelja posvađati ako zajedno završe u baru. Imate li listu n ljudi koji će večeras doći u bar. Odlučujete da neke građane držite podalje od bara, a da se niko ne potuče. U isto vrijeme, vaši šefovi ne žele izgubiti profit i bit će nesretni ako ne dozvolite više od k ljudi.
Nažalost, problem pred vama je klasičan NP-tvrd problem. Možda je poznajete kao , ili kao problem pokrivanja vrhova. Za takve probleme, u opštem slučaju, ne postoje algoritmi koji rade u prihvatljivom vremenu. Tačnije, nedokazana i prilično jaka hipoteza ETH (Hipoteza eksponencijalnog vremena) kaže da se ovaj problem ne može riješiti na vrijeme , to jest, ne možete smisliti ništa bolje od potpune pretrage. Na primjer, recimo da će neko doći u vaš bar n = 1000 Čovjek. Tada će biti kompletna pretraga opcije koje otprilike postoje - luda količina. Srećom, vaša uprava vam je dala ograničenje k = 10, tako da je broj kombinacija koje trebate ponoviti mnogo manji: broj podskupova od deset elemenata je . Ovo je bolje, ali se i dalje neće računati za jedan dan čak ni na moćnom klasteru.
Da biste eliminisali mogućnost tuče u ovoj konfiguraciji zategnutih odnosa između posetilaca bara, morate držati Boba, Daniela i Fedora podalje. Ne postoji rješenje u kojem će samo dvoje ostati iza.
Znači li to da je vrijeme da se predamo i pustimo sve unutra? Hajde da razmotrimo druge opcije. Pa, na primjer, ne možete pustiti samo one za koje je vjerovatno da će se boriti sa vrlo velikim brojem ljudi. Ako neko može da se bori bar sa k+1 drugu osobu, onda je definitivno ne možete pustiti unutra - inače ćete morati držati sve napolju k+1 gradjani, sa kojima se moze boriti, sto ce definitivno uznemiriti rukovodstvo.
Neka izbacite svakoga koga ste mogli po ovom principu. Tada se svi ostali mogu boriti sa najviše k ljudi. Izbacivanje k čovječe, ništa više ne možeš spriječiti sukobi. To znači da ako postoji više od Ako je osoba uključena u barem jedan sukob, onda ih sigurno ne možete spriječiti sve. Pošto ćete, naravno, sigurno pustiti potpuno nekonfliktne ljude, morate proći kroz sve podskupove veličine deset od dvije stotine ljudi. Ima ih otprilike , a ovaj broj operacija se već može razvrstati na klasteru.
Ako možete bezbedno uzeti pojedince koji nemaju nikakav sukob, šta je onda sa onima koji učestvuju u samo jednom sukobu? U stvari, mogu se pustiti unutra i zatvaranjem vrata svom protivniku. Zaista, ako je Alisa u sukobu samo sa Bobom, onda ako pustimo Alis iz njih dvoje, nećemo izgubiti: Bob može imati i druge sukobe, ali Alisa ih sigurno nema. Štaviše, nema smisla da nas oboje ne pustimo unutra. Nakon ovakvih operacija više ne ostaje gosti sa neriješenom sudbinom: imamo samo sukobi, svaki sa dva učesnika i svaki uključen u najmanje dva. Dakle, sve što ostaje je da se sredimo opcije, koje se lako mogu smatrati pola dana na laptopu.
Zapravo, jednostavnim rasuđivanjem možete postići još atraktivnije uslove. Imajte na umu 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 konflikt, iz kojeg uklanjamo jednog učesnika i rekurzivno počinjemo od ostatka, zatim uklanjamo drugog i također počinjemo rekurzivno. Pošto nekoga izbacujemo na svakom koraku, stablo rekurzije takvog algoritma je binarno stablo dubine k, tako da ukupno algoritam funkcionira gde n je broj vrhova, i m - broj rebara. U našem primjeru, to je oko deset miliona, što se može izračunati u djeliću sekunde ne samo na laptopu, već čak i na mobilnom telefonu.
Gornji primjer je primjer parametrizirani algoritam. Parametrizovani algoritmi su algoritmi koji rade u vremenu f(k) poli(n)gde p - polinom, f je proizvoljna izračunljiva funkcija, i k - neki parametar, koji će, vrlo moguće, biti mnogo manji od veličine problema.
Sva razmišljanja prije ovog algoritma daju primjer kernelizacija je jedna od općih tehnika za kreiranje parametriziranih algoritama. Kernelizacija je smanjenje veličine problema na vrijednost ograničenu funkcijom parametra. Rezultirajući problem se često naziva kernel. Dakle, jednostavnim razmišljanjem o stepenima vrhova, dobili smo kvadratno jezgro za problem pokrivanja vrhova, parametrizovano 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 razgovarati.
Pace Challenge
Takmičenje (The Parameterized Algorithms and Computational Experiments Challenge) je nastao 2015. godine kako bi uspostavio vezu između parametriziranih algoritama i pristupa koji se koriste u praksi za rješavanje računskih problema. Prva tri takmičenja bila su posvećena pronalaženju širine stabla grafa (), tražeći Steinerovo stablo () i traženje skupa vrhova koji seku cikluse (). Ove godine, jedan od problema u kojem ste se mogli okušati bio je gore opisani problem pokrivanja vrhova.
Takmičenje svake godine postaje sve popularnije. Ako je vjerovati preliminarnim podacima, ove godine u natjecanju su učestvovala 24 tima koji su samo riješili problem pokrivanja vrhova. Vrijedi napomenuti da takmičenje ne traje nekoliko sati ili čak sedmica, već nekoliko mjeseci. Timovi imaju priliku proučiti literaturu, osmisliti vlastitu originalnu ideju i pokušati je implementirati. U suštini, ovo takmičenje je istraživački projekat. Ideje za najefikasnija rješenja i dodjela nagrada pobjednicima održat će se u sklopu konferencije (International Symposium on Parameterized and Exact Computation) kao dio najvećeg godišnjeg algoritamskog skupa u Evropi . Detaljnije informacije o samom takmičenju možete pronaći na , a lažu rezultati prethodnih godina .
Dijagram rješenja
Da 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 cijepanja. Pravila pojednostavljenja su prethodna obrada inputa u polinomskom vremenu. Svrha primjene takvih pravila je da se problem svede na ekvivalentan manji problem. Pravila pojednostavljenja su najskuplji dio algoritma, a primjena ovog dijela dovodi do ukupnog vremena rada umjesto jednostavnog polinomskog vremena. U našem slučaju, pravila cijepanja su zasnovana na činjenici da za svaki vrh morate uzeti ili njega ili njegovog susjeda kao odgovor.
Opšta shema je ova: primjenjujemo pravila pojednostavljenja, zatim odabiremo neki vrh i vršimo dva rekurzivna poziva: u prvom ga uzimamo kao odgovor, au drugom uzimamo sve njegove susjede. To je ono što nazivamo cijepanjem (grananjem) duž ovog vrha.
Tačno jedan dodatak će biti uveden u ovu šemu u sljedećem paragrafu.
Ideje za podjelu (brunching) pravila
Hajde da razgovaramo o tome kako odabrati vrh duž kojeg će doći do cijepanja.
Glavna ideja je veoma pohlepna u algoritamskom smislu: uzmimo vrh maksimalnog stepena i podelimo ga duž njega. Zašto izgleda bolje? Zato što ćemo u drugoj grani rekurzivnog poziva ukloniti mnogo vrhova na ovaj način. Možete računati na mali preostali grafikon i možemo brzo raditi na njemu.
Ovaj pristup, uz već diskutovane jednostavne tehnike kernelizacije, dobro se pokazuje i rješava neke testove veličine nekoliko hiljada vrhova. Ali, na primjer, ne radi dobro za kubične grafove (tj. grafove čiji je stepen svakog temena tri).
Postoji još jedna ideja zasnovana na prilično jednostavnoj ideji: ako je graf nepovezan, problem na njegovim povezanim komponentama može se riješiti nezavisno, kombinujući odgovore na kraju. Ovo je, inače, mala obećana modifikacija sheme, koja će značajno ubrzati rješenje: ranije smo u ovom slučaju radili za proizvod vremena za izračunavanje odgovora komponenti, ali sada radimo za suma. A da biste ubrzali grananje, potrebno je da povezani graf pretvorite u nepovezani.
Kako uraditi? Ako postoji tačka artikulacije na grafu, morate se boriti protiv toga. Tačka artikulacije je vrh takav da kada se ukloni, graf gubi svoju povezanost. Sve spojne tačke u grafu mogu se pronaći pomoću klasičnog algoritma u linearnom vremenu. Ovaj pristup značajno ubrzava grananje.
Kada se ukloni bilo koji od odabranih vrhova, graf će se podijeliti na povezane komponente.
Uradićemo ovo, ali želimo više. Na primjer, potražite male rezove vrhova u grafu i podijelite ga duž vrhova iz njega. Najefikasniji način koji znam za pronalaženje minimalnog globalnog reznog vrha je korištenje Gomori-Hu stabla, koje je izgrađeno u kubnom vremenu. U PACE Challenge-u, tipična veličina grafa je nekoliko hiljada vrhova. U ovoj situaciji, milijarde operacija moraju biti izvedene na svakom vrhu rekurzivnog stabla. Ispada da je jednostavno nemoguće riješiti problem u predviđenom vremenu.
Pokušajmo optimizirati rješenje. Minimalni vrh između par vrhova može se naći bilo kojim algoritmom koji konstruiše maksimalni tok. Možete ga pustiti na takvu mrežu , u praksi radi vrlo brzo. Sumnjam da je teoretski moguće dokazati procjenu radnog vremena , što je već sasvim prihvatljivo.
Nekoliko puta sam pokušao da tražim rezove između parova nasumičnih vrhova i uzmem najizbalansiraniji. Nažalost, ovo je dovelo do loših rezultata u otvorenom testiranju PACE Challenge. Uporedio sam ga s algoritmom koji dijeli vrhove maksimalnog stepena, pokrećući ih s ograničenjem dubine spuštanja. Algoritam koji pokušava da pronađe rez na ovaj način ostavio je veće grafikone. To je zbog činjenice da su rezovi bili vrlo neuravnoteženi: nakon uklanjanja 5-10 vrhova, bilo je moguće odvojiti samo 15-20.
Vrijedi napomenuti da članci o teorijski najbržim algoritmima koriste mnogo naprednije tehnike za odabir vrhova za cijepanje. Takve tehnike imaju vrlo složenu implementaciju i često loše performanse u smislu vremena i pamćenja. Nisam uspeo da identifikujem one koji su sasvim prihvatljivi za praksu.
Kako primijeniti pravila pojednostavljenja
Već imamo ideje za kernelizaciju. da vas podsjetim:
- Ako postoji izolirani vrh, obrišite ga.
- Ako postoji vrh stepena 1, uklonite ga i uzmite njegovog susjeda kao odgovor.
- Ako postoji barem vrh stepena k+1, uzeti natrag.
Sa prva dva je sve jasno, sa trećim postoji jedan trik. Ako smo u komičnom problemu o baru dobili gornju granicu k, onda u PACE Challengeu samo trebate pronaći pokrivač vrha minimalne veličine. Ovo je tipična transformacija problema pretraživanja u probleme odlučivanja često nema razlike između ove dvije vrste problema. U praksi, ako pišemo rješavač za problem pokrivanja vrhova, može postojati razlika. Na primjer, kao u trećoj tački.
Sa stanovišta implementacije, postoje dva načina da se nastavi. Prvi pristup se zove Iterativno produbljivanje. To je sljedeće: možemo početi s nekim razumnim ograničenjem odozdo na odgovor, a zatim pokrenuti naš algoritam koristeći ovo ograničenje kao ograničenje na odgovor odozgo, bez spuštanja niže u rekurziji od ovog ograničenja. Ako smo pronašli neki odgovor, on je zagarantovano optimalan, inače možemo povećati ovu granicu za jedan i početi iznova.
Drugi pristup je pohranjivanje nekog trenutnog optimalnog odgovora i traženje manjeg odgovora, 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 na kombinaciju ove dvije metode: prvo, pokrećem svoj algoritam s nekakvim ograničenjem dubine pretraživanja (odabirom ga tako da traje zanemarivo vrijeme u odnosu na glavno rješenje) i koristim najbolje rješenje pronađeno kao gornja granica odgovora – odnosno iste stvari k.
Vrhovi stepena 2
Bavili smo se vrhovima stepena 0 i 1. Ispostavilo se da se to može učiniti sa vrhovima stepena 2, ali će to zahtijevati složenije operacije s grafom.
Da bismo ovo objasnili, moramo nekako označiti vrhove. Nazovimo vrh stepena 2 vrhom v, a njegovi susjedi - vrhovi x и y. Sljedeće ćemo imati dva slučaja.
- Kada x и y - komšije. Onda možete odgovoriti x и yi v izbrisati. Zaista, iz ovog trokuta treba uzeti najmanje dva vrha zauzvrat, a mi definitivno nećemo izgubiti ako uzmemo x и y: vjerovatno imaju druge komšije, i v Oni nisu ovde.
- Kada x и y - ne komšije. Tada se navodi da se sva tri vrha mogu zalijepiti u jedan. Ideja je da u ovom slučaju postoji optimalan odgovor, u kojem uzimamo bilo koje v, ili oba vrha x и y. Štaviše, u prvom slučaju morat ćemo uzeti sve susjede kao odgovor x и y, ali u drugom nije potrebno. To tačno odgovara slučajevima kada ne uzimamo zalijepljeni vrh kao odgovor i kada to činimo. Ostaje samo napomenuti da se u oba slučaja odziv od takve operacije smanjuje za jedan.
Vrijedi napomenuti da je ovaj pristup prilično teško precizno implementirati u prilično linearnom vremenu. Lijepljenje vrhova je složena operacija, morate kopirati liste susjeda. Ako se to učini nepažljivo, možete završiti s asimptotički podoptimalnim vremenom rada (na primjer, ako kopirate puno rubova nakon svakog lijepljenja). Odlučio sam da pronađem čitave puteve od vrhova stepena 2 i analiziram gomilu 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 vratimo graf u prvobitni oblik. Da bih to osigurao, nisam obrisao liste rubova spojenih vrhova, a onda sam samo znao koje rubove trebaju ići gdje. Ova implementacija grafova takođe zahteva tačnost, ali obezbeđuje prilično linearno vreme. A za grafove od nekoliko desetina hiljada ivica, uklapa se u keš procesora, što daje velike prednosti u brzini.
Linearno jezgro
Konačno, najzanimljiviji dio kernela.
Za početak, podsjetimo se da se u bipartitnim grafovima minimalno pokrivanje vrhova može pronaći pomoću . Da biste to učinili, morate koristiti algoritam kako bi se tamo pronašlo maksimalno podudaranje, a zatim upotrijebite teoremu .
Ideja linearnog kernela je sljedeća: prvo račvamo graf, odnosno umjesto svakog vrha v dodajmo dva vrha и , i umjesto svake ivice u - v dodajmo dva rebra и . Rezultirajući graf će biti bipartitan. Pronađimo minimalni poklopac vrha u njemu. Neki vrhovi originalnog grafa će tamo stići dvaput, neki samo jednom, a neki nikada. Nemhauser-Trotter teorem kaže da se u ovom slučaju mogu ukloniti vrhovi koji nisu pogodili niti jednom i vratiti one koji su pogodili dva puta. Štaviše, ona kaže da od preostalih vrhova (onih koji su pogodili jednom) morate uzeti barem polovinu kao odgovor.
Upravo smo naučili da ostavimo ne više od 2k vrhovi Zaista, ako je ostatak odgovora barem polovina svih vrhova, onda nema više vrhova ukupno od 2k.
Ovdje sam mogao napraviti mali korak naprijed. Jasno je da ovako konstruirano jezgro ovisi o tome kakvu smo minimalnu pokrivenost vrha uzeli u bipartitnom grafu. Želio bih uzeti jedan tako da broj preostalih vrhova bude minimalan. Ranije su to mogli samo na vrijeme . U to vrijeme sam smislio implementaciju ovog algoritma , tako da se ovo jezgro može tražiti u grafovima od stotina hiljada vrhova u svakoj fazi grananja.
rezultat
Praksa pokazuje da moje rješenje dobro radi na testovima nekoliko stotina vrhova i nekoliko hiljada ivica. U ovakvim testovima sasvim je moguće očekivati da će se rješenje pronaći za pola sata. Vjerovatnoća pronalaženja odgovora u prihvatljivom vremenu, u principu, raste ako graf ima dovoljno veliki broj vrhova visokog stupnja, na primjer, stepena 10 i više.
Za učešće na konkursu potrebno je poslati rješenja . Sudeći po informacijama koje su tamo predstavljene , moje rješenje u otvorenim testovima je na trećem mjestu od dvadeset, sa velikim zaostatkom od drugog. Da budem potpuno iskren, nije sasvim jasno kako će se rješenja ocjenjivati na samom takmičenju: na primjer, moje rješenje prolazi manje testova od rješenja na četvrtom mjestu, ali na onima koje prođu brže radi.
Rezultati zatvorenih testova biće poznati 1. jula.
izvor: www.habr.com