Raziskovalno delo je morda najbolj zanimiv del našega izobraževanja. Ideja je, da se preizkusite v izbrani smeri še na univerzi. Študenti s področja programskega inženiringa in strojnega učenja se na primer pogosto odpravijo raziskovat v podjetja (predvsem JetBrains ali Yandex, a ne le).
V tej objavi bom govoril o svojem projektu računalništva. V okviru svojega dela sem proučeval in v praksi uvajal pristope k reševanju enega najbolj znanih NP-težkih problemov: problem pokrivanja vozlišč.
Dandanes se zelo hitro razvija zanimiv pristop k NP-težkim problemom - parametrizirani algoritmi. Poskušal vas bom seznaniti, vam povedal nekaj preprostih parametriranih algoritmov in opisal eno zmogljivo metodo, ki mi je zelo pomagala. Svoje rezultate sem predstavil na tekmovanju PACE Challenge: po rezultatih odprtih testov moja rešitev zaseda tretje mesto, končni rezultati pa bodo znani 1. julija.
O sebi
Moje ime je Vasily Alferov, zdaj končujem tretji letnik na Nacionalni raziskovalni univerzi Visoka šola za ekonomijo - St. Petersburg. Algoritmi me zanimajo že od šolskih dni, ko sem študiral v moskovski šoli št. 179 in uspešno sodeloval na računalniških olimpijadah.
Končno število specialistov za parametrizirane algoritme vstopi v bar ...
Primer vzet iz knjige
Predstavljajte si, da ste varnostnik v baru v majhnem mestu. Vsak petek se pol mesta pride sprostit v vaš lokal, kar vam povzroča veliko težav: iz lokala morate vreči nemirne stranke, da preprečite pretepe. Sčasoma se naveličate in se odločite za preventivne ukrepe.
Ker je vaše mesto majhno, natančno veste, kateri pari obiskovalcev se bodo verjetno sprli, če bodo skupaj končali v baru. Ali imate seznam n ljudi, ki bodo nocoj prišli v bar. Odločite se, da boste nekatere meščane pregnali iz lokala, ne da bi se kdo sprl. Obenem pa vaši šefi ne želijo izgubiti dobička in bodo nezadovoljni, če jim ne dovolite več kot k ljudje.
Na žalost je težava pred vami klasična NP-težka težava. Morda jo poznate kot , ali kot problem pokrivanja vozlišč. Za takšne probleme v splošnem primeru ni algoritmov, ki bi delovali v sprejemljivem času. Če smo natančni, nedokazana in precej močna hipoteza ETH (Exponential Time Hypothesis) pravi, da tega problema ni mogoče pravočasno rešiti. , to pomeni, da si ne morete zamisliti nič opazno boljšega od popolnega iskanja. Na primer, recimo, da bo nekdo prišel v vaš lokal n = 1000 Človek. Potem bo popolno iskanje možnosti, ki jih je približno - nor znesek. Na srečo vam je vodstvo dalo mejo k = 10, zato je število kombinacij, ki jih morate ponoviti, veliko manjše: število podnaborov desetih elementov je . To je bolje, vendar se še vedno ne bo štelo v enem dnevu, tudi na močni gruči.
Če želite odpraviti možnost pretepa v tej konfiguraciji napetih odnosov med obiskovalci bara, morate Boba, Daniela in Fedorja preprečiti. Ni rešitve, pri kateri bosta za seboj ostala samo dva.
Ali to pomeni, da je čas, da se vdamo in pustimo vsem noter? Razmislimo o drugih možnostih. No, na primer, ne morete pustiti samo tistih, ki se bodo verjetno borili z zelo velikim številom ljudi. Če se lahko kdo bori vsaj z k+1 druge osebe, potem je zagotovo ne morete spustiti noter - sicer boste morali vse preprečiti k+1 meščane, s katerimi se lahko pomeri, kar bo zagotovo razburilo vodstvo.
Naj po tem principu vrže ven vse, ki bi jih lahko. Potem se lahko vsi drugi borijo z največ k ljudi. Metanje jih ven k človek, ne moreš preprečiti nič drugega kot konflikti. To pomeni, da če je več kot Če je oseba vpletena v vsaj en konflikt, potem vseh zagotovo ne moreš preprečiti. Ker boste seveda zagotovo spustili popolnoma nekonfliktne ljudi, morate iti skozi vse podmnožice velikosti deset od dvesto ljudi. Obstaja približno , in to število operacij je že mogoče razvrstiti v gruči.
Če lahko varno vzamete posameznike, ki nimajo nobenega konflikta, kaj je potem s tistimi, ki sodelujejo samo v enem konfliktu? Pravzaprav jih lahko spustijo noter tudi tako, da nasprotniku zaprejo vrata. Dejansko, če je Alice v konfliktu samo z Bobom, potem, če Alice izpustimo iz obeh, ne bomo izgubili: Bob ima lahko druge konflikte, vendar jih Alice zagotovo nima. Še več, nima smisla, da naju ne spustiva noter. Po takšnih operacijah ne ostane nič več goste z nerešeno usodo: imamo samo konfliktov, pri čemer ima vsak po dva udeleženca in je vsak vpleten v vsaj dva. Torej ostane le še razvrščanje možnosti, ki jih zlahka obravnavamo pol dneva na prenosniku.
Pravzaprav lahko s preprostim razmišljanjem dosežete še privlačnejše pogoje. Upoštevajte, da moramo vsekakor rešiti vse spore, torej iz vsakega konfliktnega para izbrati vsaj eno osebo, ki je ne bomo spustili noter. Oglejmo si naslednji algoritem: vzemimo poljuben konflikt, iz katerega odstranimo enega udeleženca in rekurzivno začnemo od ostanka, nato odstranimo drugega in prav tako začnemo rekurzivno. Ker na vsakem koraku nekoga vržemo ven, je rekurzijsko drevo takega algoritma binarno drevo globine k, tako da algoritem v celoti deluje v Če n je število vozlišč in m - število reber. V našem primeru je to približno deset milijonov, ki jih lahko v delčku sekunde izračunamo ne samo na prenosniku, ampak celo na mobilnem telefonu.
Zgornji primer je primer parametriran algoritem. Parametrirani algoritmi so algoritmi, ki tečejo v času f(k) poli(n)Če p - polinom, f je poljubna izračunljiva funkcija in k - nek parameter, ki bo zelo verjetno veliko manjši od velikosti problema.
Vsa razmišljanja pred tem algoritmom dajejo primer kernelizacija je ena od splošnih tehnik za ustvarjanje parametriziranih algoritmov. Kernelizacija je zmanjšanje velikosti problema na vrednost, omejeno s funkcijo parametra. Nastala težava se pogosto imenuje jedro. Tako smo s preprostim sklepanjem o stopnjah oglišč dobili kvadratno jedro za problem pokritja oglišč, parametrizirano z velikostjo odgovora. Obstajajo še druge nastavitve, ki jih lahko izberete za to nalogo (kot je Vertex Cover Above LP), vendar je to nastavitev, o kateri bomo razpravljali.
Pace Challenge
Tekmovanje (The Parameterized Algorithms and Computational Experiments Challenge) se je rodil leta 2015, da bi vzpostavil povezavo med parametriziranimi algoritmi in pristopi, ki se v praksi uporabljajo za reševanje računalniških problemov. Prva tri tekmovanja so bila namenjena iskanju drevesne širine grafa (), iskanje Steinerjevega drevesa () in iskanje nabora vozlišč, ki reže cikle (). Letos je bil eden od problemov, v katerem ste se lahko preizkusili, zgoraj opisani problem pokrivanja vozlišč.
Tekmovanje postaja vsako leto bolj priljubljeno. Če verjamete preliminarnim podatkom, se je letos tekmovanja udeležilo 24 ekip samo za reševanje problema pokrivanja vozlišč. Omeniti velja, da tekmovanje ne traja več ur ali celo teden, ampak več mesecev. Ekipe imajo možnost preučiti literaturo, pripraviti svojo izvirno idejo in jo poskušati uresničiti. V bistvu je to tekmovanje raziskovalna naloga. Vzporedno s konferenco bodo potekale ideje za najučinkovitejše rešitve in podelitev nagrad zmagovalcem (International Symposium on Parameterized and Exact Computation) v okviru največjega letnega algoritemskega srečanja v Evropi . Podrobnejše informacije o samem tekmovanju najdete na , rezultati preteklih let pa lažejo .
Diagram rešitve
Da bi rešil problem pokrivanja vozlišč, sem poskusil uporabiti parametrirane algoritme. Običajno so sestavljena iz dveh delov: poenostavitvenih pravil (ki v idealnem primeru vodijo k jedrnačenju) in razdelitvenih pravil. Pravila poenostavljanja so predprocesiranje vnosa v polinomskem času. Namen uporabe takšnih pravil je zmanjšati problem na enakovreden manjši problem. Pravila poenostavljanja so najdražji del algoritma in uporaba tega dela vodi do skupnega časa delovanja namesto enostavnega polinomskega časa. V našem primeru pravila cepitve temeljijo na dejstvu, da morate za vsako vozlišče kot odgovor vzeti bodisi njega ali njegovega soseda.
Splošna shema je naslednja: uporabimo pravila poenostavitve, nato izberemo neko vozlišče in naredimo dva rekurzivna klica: v prvem ga vzamemo kot odgovor, v drugem pa vse njegove sosede. Temu pravimo razcep (razvejanje) vzdolž tega vrha.
V naslednjem odstavku bo tej shemi dodan natanko en dodatek.
Ideje za cepitev (brunching) pravila
Pogovorimo se o tem, kako izbrati točko, po kateri bo prišlo do cepitve.
Glavna ideja je v algoritemskem smislu zelo požrešna: vzemimo oglišče največje stopnje in ga razdelimo. Zakaj se zdi bolje? Ker bomo v drugi veji rekurzivnega klica na ta način odstranili veliko vozlišč. Računate lahko na majhen preostanek grafa, na katerem lahko hitro delamo.
Ta pristop se z že obravnavanimi preprostimi tehnikami kernelizacije dobro izkaže in rešuje nekatere teste velikosti več tisoč vozlišč. Toda, na primer, ne deluje dobro za kubične grafe (to je grafe, katerih stopnja vsakega vozlišča je tri).
Obstaja še ena ideja, ki temelji na dokaj preprosti ideji: če je graf nepovezan, je mogoče problem na njegovih povezanih komponentah rešiti neodvisno, z združevanjem odgovorov na koncu. Mimogrede, to je majhna obljubljena sprememba v shemi, ki bo bistveno pospešila rešitev: prej smo v tem primeru delali za produkt časov za izračun odzivov komponent, zdaj pa delamo za Vsota. In da pospešite razvejanje, morate povezani graf spremeniti v nepovezanega.
Kako narediti? Če je na grafu točka artikulacije, se morate zanjo boriti. Zgibna točka je oglišče, pri katerem graf, ko ga odstranimo, izgubi povezljivost. Vse stičišča v grafu je mogoče najti s klasičnim algoritmom v linearnem času. Ta pristop bistveno pospeši razvejanje.
Ko katero koli od izbranih vozlišč odstranimo, se graf razdeli na povezane komponente.
To bomo storili, vendar želimo več. Na primer, poiščite majhne izreze oglišč v grafu in jih razdelite vzdolž oglišč iz njega. Najučinkovitejši način, ki ga poznam za iskanje najmanjšega globalnega reza vozlišč, je uporaba drevesa Gomori-Hu, ki je zgrajeno v kubičnem času. V PACE Challenge je tipična velikost grafa več tisoč točk. V tej situaciji je treba na vsaki točki rekurzijskega drevesa izvesti milijarde operacij. Izkazalo se je, da je preprosto nemogoče rešiti problem v predvidenem času.
Poskusimo optimizirati rešitev. Najmanjše oglišče, razrezano med parom oglišč, je mogoče najti s katerim koli algoritmom, ki konstruira največji tok. Lahko ga spustiš v takšno omrežje , v praksi deluje zelo hitro. Sumim, da je teoretično možno dokazati oceno časa delovanja , kar je že kar sprejemljivo.
Večkrat sem poskušal iskati reze med pari naključnih oglišč in vzeti najbolj uravnoteženega. Na žalost je to prineslo slabe rezultate pri odprtem testiranju PACE Challenge. Primerjal sem ga z algoritmom, ki razdeli oglišča največje stopnje in jih izvaja z omejitvijo globine spuščanja. Algoritem, ki je na ta način poskušal najti rez, je pustil za sabo večje grafe. To je posledica dejstva, da so se rezi izkazali za zelo neuravnotežene: po odstranitvi 5-10 oglišč je bilo mogoče odcepiti le 15-20.
Omeniti velja, da članki o teoretično najhitrejših algoritmih uporabljajo veliko bolj napredne tehnike za izbiro vozlišč za cepljenje. Takšne tehnike imajo zelo zapleteno izvedbo in pogosto slabo zmogljivost v smislu časa in spomina. Nisem mogel identificirati tistih, ki so povsem sprejemljivi za prakso.
Kako uporabiti pravila poenostavitve
Ideje za kernelizacijo že imamo. Naj vas spomnim:
- Če obstaja izolirano oglišče, ga izbrišite.
- Če obstaja oglišče stopnje 1, ga odstranite in v odgovor vzemite njegovega soseda.
- Če obstaja vsaj vrh stopnje k+1, vzeti nazaj.
S prvima dvema je vse jasno, s tretjim je en trik. Če smo v komičnem problemu o lokalu dobili zgornjo mejo k, nato pa morate v PACE Challenge le najti pokrov vrha najmanjše velikosti. To je tipična preobrazba težav pri iskanju v težave z odločanjem; pogosto med obema vrstama težav ni razlike. V praksi, če pišemo reševalec za problem pokrivanja vozlišč, lahko pride do razlike. Na primer, kot v tretji točki.
Z izvedbenega vidika obstajata dva načina za nadaljevanje. Prvi pristop se imenuje iterativno poglabljanje. To je naslednje: lahko začnemo z neko razumno omejitvijo od spodaj na odgovor in nato zaženemo naš algoritem z uporabo te omejitve kot omejitve na odgovor od zgoraj, ne da bi šli v rekurziji nižje od te omejitve. Če smo našli nek odgovor, je garantirano optimalen, sicer lahko to mejo povečamo za eno in začnemo znova.
Drug pristop je shranjevanje trenutnega optimalnega odgovora in iskanje manjšega odgovora ter spreminjanje tega parametra, ko ga najdemo k za večje odrezovanje nepotrebnih vej pri iskanju.
Po več nočnih poskusih sem se odločil za kombinacijo teh dveh metod: najprej zaženem svoj algoritem z nekakšno omejitvijo globine iskanja (izberem jo tako, da traja zanemarljivo malo časa v primerjavi z glavno rešitvijo) in uporabim najboljšo rešitev najdemo kot zgornjo mejo odgovora – torej iste stvari k.
Oglišča stopnje 2
Ukvarjali smo se z vozlišči stopnje 0 in 1. Izkazalo se je, da je to mogoče storiti z vozlišči stopnje 2, vendar bo to zahtevalo bolj zapletene operacije iz grafa.
Da bi to pojasnili, moramo nekako določiti oglišča. Oglišče stopnje 2 imenujemo oglišče v, in njegove sosede - vozlišča x и y. Nato bomo imeli dva primera.
- Pri x и y - sosedi. Potem lahko odgovoriš x и yIn v izbrisati. Dejansko je treba iz tega trikotnika vzeti vsaj dve oglišči in zagotovo ne bomo izgubili, če vzamemo x и y: verjetno imajo druge sosede in v Ni jih tukaj.
- Pri x и y - ne sosedje. Nato je navedeno, da lahko vsa tri oglišča zlepimo v eno. Ideja je, da v tem primeru obstaja optimalen odgovor, v katerem vzamemo bodisi v, ali obe točki x и y. Poleg tega bomo v prvem primeru morali odgovoriti na vse sosede x и y, v drugem pa ni nujno. To natančno ustreza primeroma, ko ne vzamemo zlepljenega vrha kot odgovor in ko ga. Omeniti velja le, da se v obeh primerih odziv takšne operacije zmanjša za eno.
Treba je omeniti, da je ta pristop precej težko natančno izvesti v poštenem linearnem času. Lepljenje vozlišč je zapletena operacija; kopirati morate sezname sosedov. Če to naredite malomarno, lahko končate z asimptotično neoptimalnim časom delovanja (na primer, če kopirate veliko robov po vsakem lepljenju). Odločil sem se za iskanje celotnih poti iz oglišč stopnje 2 in analiziral kup posebnih primerov, kot so cikli iz takšnih oglišč ali iz vseh takih oglišč razen enega.
Poleg tega je nujno, da je ta operacija reverzibilna, tako da ob vrnitvi iz rekurzije povrnemo graf v prvotno obliko. Da bi to zagotovil, nisem počistil seznamov robov združenih vozlišč in potem sem samo vedel, kateri robovi morajo kam iti. Ta izvedba grafov prav tako zahteva natančnost, vendar zagotavlja pravičen linearni čas. In za grafe več deset tisoč robov se prilega v predpomnilnik procesorja, kar daje velike prednosti pri hitrosti.
Linearno jedro
Za konec še najbolj zanimiv del jedra.
Za začetek se spomnimo, da je v bipartitnih grafih najmanjšo pokritost vozlišč mogoče najti z uporabo . Če želite to narediti, morate uporabiti algoritem da tam najdemo največje ujemanje, in nato uporabimo izrek .
Ideja linearnega jedra je naslednja: najprej razcepimo graf, to je namesto vsakega vozlišča v dodamo dva vrha и , in namesto vsakega roba u - v dodamo dve rebrci и . Nastali graf bo bipartiten. Poiščimo v njem najmanjšo pokritost vozlišč. Nekatera vozlišča izvirnega grafa bodo prišla tja dvakrat, nekatera samo enkrat in nekatera nikoli. Nemhauser-Trotterjev izrek pravi, da je v tem primeru mogoče odstraniti vozlišča, ki niso zadela niti enkrat, in vzeti nazaj tista, ki so zadela dvakrat. Poleg tega pravi, da morate od preostalih vozlišč (tistih, ki zadenejo enkrat) vzeti vsaj polovico kot odgovor.
Pravkar smo se naučili pustiti več kot 2k vrhovi Dejansko, če je preostali odgovor vsaj polovica vseh tock, potem ni več tock skupaj kot 2k.
Tukaj sem lahko naredil majhen korak naprej. Jasno je, da je tako zgrajeno jedro odvisno od tega, kakšno minimalno pokritost vozlišč smo vzeli v bipartitnem grafu. Rad bi vzel enega, tako da je število preostalih vozlišč minimalno. Prej so to lahko storili le pravočasno . V tistem času sem prišel do izvedbe tega algoritma , zato lahko to jedro iščemo v grafih s stotisoči vozlišč na vsaki stopnji razvejanja.
Rezultat
Praksa kaže, da se moja rešitev dobro obnese na testih več sto vozlišč in več tisoč robov. Pri takšnih testih je povsem mogoče pričakovati, da se bo rešitev našla v pol ure. Verjetnost najti odgovor v sprejemljivem času se načeloma poveča, če ima graf dovolj veliko število vozlišč visoke stopnje, na primer stopnje 10 in več.
Za sodelovanje na natečaju je bilo treba rešitve poslati na . Sodeč po tam predstavljenih informacijah , je moja rešitev v odprtih preizkusih uvrščena na tretje mesto od dvajsetih, z velikim zaostankom za drugo. Če sem povsem iskren, ni povsem jasno, kako se bodo rešitve ocenjevale na samem tekmovanju: moja rešitev na primer prestane manj testov kot četrtouvrščena, a na tistih, ki so uspešne, deluje hitreje.
Rezultati zaprtih testov bodo znani XNUMX. julija.
Vir: www.habr.com