Activitatea de cercetare este poate cea mai interesantă parte a pregătirii noastre. Ideea este să te încerci în direcția pe care ai ales-o în timp ce ești la universitate. De exemplu, studenții din domeniile Inginerie software și Învățare automată merg adesea să facă cercetări în companii (în principal JetBrains sau Yandex, dar nu numai).
În această postare voi vorbi despre proiectul meu în Informatică. Ca parte a muncii mele, am studiat și am pus în practică abordări pentru rezolvarea uneia dintre cele mai faimoase probleme NP-hard: problema de acoperire a vârfurilor.
În zilele noastre, o abordare interesantă a problemelor NP-hard se dezvoltă foarte rapid - algoritmi parametrizați. Voi încerca să vă pun la curent, să vă spun niște algoritmi parametrizați simpli și să vă descriu o metodă puternică care m-a ajutat foarte mult. Mi-am prezentat rezultatele la competiția PACE Challenge: conform rezultatelor testelor deschise, soluția mea ocupă locul trei, iar rezultatele finale vor fi cunoscute pe 1 iulie.
Despre mine
Numele meu este Vasily Alferov, acum termin anul al treilea la Școala Superioară de Economie a Universității Naționale de Cercetare - Sankt Petersburg. Am fost interesat de algoritmi încă din timpul școlii, când am studiat la școala nr. 179 din Moscova și am participat cu succes la olimpiadele de informatică.
Un număr finit de specialiști în algoritmi parametrizați intră în bară...
Exemplu luat din carte
Imaginați-vă că sunteți paznic de bar într-un oraș mic. În fiecare vineri, jumătate din oraș vine la barul tău pentru a te relaxa, ceea ce îți dă multe bătăi de cap: trebuie să arunci clienții zbuciumați din bar pentru a preveni certuri. În cele din urmă, te sături și decizi să iei măsuri preventive.
Deoarece orașul tău este mic, știi exact ce perechi de patroni se vor lupta dacă ajung împreună într-un bar. Ai o listă cu n oameni care vor veni la bar în seara asta. Te hotărăști să ții niște orășeni departe de bar fără ca cineva să intre într-o ceartă. În același timp, șefii tăi nu vor să piardă profituri și vor fi nefericiți dacă nu lași mai mult de k oameni.
Din păcate, problema din față este o problemă clasică NP-hard. S-ar putea să o cunoști ca , sau ca o problemă de acoperire a vârfurilor. Pentru astfel de probleme, în cazul general, nu există algoritmi care să funcționeze într-un timp acceptabil. Mai exact, ipoteza nedovedită și destul de puternică ETH (Exponential Time Hypothesis) spune că această problemă nu poate fi rezolvată în timp. , adică nu vă puteți gândi la nimic semnificativ mai bun decât o căutare completă. De exemplu, să presupunem că cineva va veni la barul tău n = 1000 Uman. Atunci căutarea completă va fi opțiuni care există aproximativ - suma nebună. Din fericire, managementul tău ți-a dat o limită k = 10, deci numărul de combinații pe care trebuie să le iterați este mult mai mic: numărul de submulțimi de zece elemente este . Acest lucru este mai bine, dar tot nu va fi numărat într-o zi, chiar și pe un cluster puternic.
Pentru a elimina posibilitatea unei lupte în această configurație de relații tensionate între vizitatorii barului, trebuie să-i ții pe Bob, Daniel și Fedor afară. Nu există o soluție în care doar doi să rămână în urmă.
Înseamnă asta că este timpul să cedezi și să lași pe toți să intre? Să luăm în considerare și alte opțiuni. Ei bine, de exemplu, nu îi poți lăsa să intre doar pe cei care sunt susceptibili de a lupta cu un număr foarte mare de oameni. Dacă cineva poate lupta măcar cu k+1 altă persoană, atunci cu siguranță nu o poți lăsa să intre - altfel va trebui să-i ții pe toți afară k+1 orășeni, cu care să se poată lupta, ceea ce cu siguranță va supăra conducerea.
Lasă-te să dai afară pe toți ai putea, conform acestui principiu. Atunci toți ceilalți se pot lupta cu cel mult k oameni. Aruncându-le afară k omule, nu poți preveni nimic mai mult decât conflicte. Aceasta înseamnă că dacă există mai mult decât Dacă o persoană este implicată în cel puțin un conflict, atunci cu siguranță nu le poți preveni pe toate. Deoarece, desigur, veți lăsa cu siguranță să intre oameni complet neconflictuali, trebuie să parcurgeți toate subseturile de dimensiunea zece din două sute de oameni. Există aproximativ , iar acest număr de operațiuni poate fi deja sortat pe cluster.
Dacă puteți lua în siguranță persoane care nu au niciun conflict, atunci ce rămâne cu cei care participă la un singur conflict? De fapt, ei pot fi lăsați să intre închizând ușa adversarului. Într-adevăr, dacă Alice este în conflict doar cu Bob, atunci dacă o lăsăm pe Alice să iasă din cei doi, nu vom pierde: Bob poate avea alte conflicte, dar Alice cu siguranță nu le are. Mai mult, nu are sens să nu ne lăsăm pe amândoi să intrăm. După astfel de operațiuni nu mai rămâne nimic musafiri cu o soartă nerezolvată: avem doar conflicte, fiecare cu doi participanți și fiecare implicat în cel puțin doi. Deci tot ce rămâne este să rezolvi opțiuni, care pot fi considerate cu ușurință o jumătate de zi pe un laptop.
De fapt, cu un raționament simplu poți obține condiții și mai atractive. Rețineți că trebuie neapărat să rezolvăm toate disputele, adică din fiecare pereche conflictuală, alegeți cel puțin o persoană pe care nu o vom lăsa să intre. Să luăm în considerare următorul algoritm: luăm orice conflict, din care eliminăm un participant și începem recursiv de la restul, apoi îl eliminăm pe celălalt și, de asemenea, începem recursiv. Deoarece aruncăm pe cineva la fiecare pas, arborele recursiv al unui astfel de algoritm este un arbore binar de adâncime k, deci în total algoritmul funcționează Unde n este numărul de vârfuri și m - numărul de coaste. În exemplul nostru, este vorba de aproximativ zece milioane, care pot fi calculate într-o fracțiune de secundă nu numai pe un laptop, ci chiar și pe un telefon mobil.
Exemplul de mai sus este un exemplu algoritm parametrizat. Algoritmii parametrizați sunt algoritmi care rulează în timp f(k) poli(n)Unde p - polinom, f este o funcție calculabilă arbitrară și k - un parametru, care, foarte posibil, va fi mult mai mic decât dimensiunea problemei.
Toate raționamentele dinaintea acestui algoritm oferă un exemplu kernelizare este una dintre tehnicile generale de creare a algoritmilor parametrizați. Kernelizarea este reducerea dimensiunii problemei la o valoare limitată de o funcție a unui parametru. Problema rezultată este adesea numită nucleu. Astfel, prin simplu rationament despre gradele vârfurilor, am obținut un nucleu pătratic pentru problema Vertex Cover, parametrizat de mărimea răspunsului. Există și alte setări pe care le puteți alege pentru această sarcină (cum ar fi Vertex Cover Above LP), dar aceasta este setarea pe care o vom discuta.
Provocarea ritmului
Competiție (The Parameterized Algorithms and Computational Experiments Challenge) a luat naștere în 2015 pentru a stabili o conexiune între algoritmii parametrizați și abordările utilizate în practică pentru rezolvarea problemelor de calcul. Primele trei competiții au fost dedicate găsirii lățimii arborelui unui grafic (), în căutarea unui copac Steiner () și căutarea unui set de vârfuri care taie ciclurile (). Anul acesta, una dintre problemele la care ai putut încerca a fost problema acoperirii vârfurilor descrisă mai sus.
Competiția câștigă popularitate în fiecare an. Dacă credeți datele preliminare, anul acesta 24 de echipe au participat la competiție pentru a rezolva singur problema acoperirii vârfurilor. Este de remarcat faptul că competiția nu durează câteva ore sau chiar o săptămână, ci câteva luni. Echipele au ocazia să studieze literatura, să vină cu propria lor idee originală și să încerce să o implementeze. În esență, acest concurs este un proiect de cercetare. Idei pentru cele mai eficiente soluții și premierea câștigătorilor vor avea loc odată cu conferința (International Symposium on Parameterized and Exact Computation) ca parte a celei mai mari întâlniri algoritmice anuale din Europa . Informații mai detaliate despre competiția în sine pot fi găsite la , iar rezultatele anilor anteriori mint .
Diagrama soluției
Pentru a rezolva problema acoperirii vârfurilor, am încercat să folosesc algoritmi parametrizați. Ele constau în mod obișnuit din două părți: reguli de simplificare (care duc în mod ideal la kernelizare) și reguli de divizare. Regulile de simplificare sunt preprocesarea intrării în timp polinomial. Scopul aplicării unor astfel de reguli este de a reduce problema la o problemă mai mică echivalentă. Regulile de simplificare sunt partea cea mai costisitoare a algoritmului, iar aplicarea acestei părți duce la timpul total de rulare în loc de timp polinom simplu. În cazul nostru, regulile de împărțire se bazează pe faptul că pentru fiecare vârf trebuie să-l luați fie pe acesta, fie pe vecinul său ca răspuns.
Schema generală este următoarea: aplicăm regulile de simplificare, apoi selectăm un vârf și facem două apeluri recursive: în primul îl luăm ca răspuns, iar în celălalt luăm toți vecinii săi. Aceasta este ceea ce numim divizare (ramificare) de-a lungul acestui vârf.
În paragraful următor se va face exact o adăugare la această schemă.
Idei de împărțire (brunching) a regulilor
Să discutăm cum să alegem un vârf de-a lungul căruia va avea loc divizarea.
Ideea principală este foarte lacomă în sens algoritmic: să luăm un vârf de grad maxim și să împărțim de-a lungul lui. De ce pare mai bine? Pentru că în a doua ramură a apelului recursiv vom elimina o mulțime de vârfuri în acest fel. Puteți conta pe un mic grafic rămas și putem lucra la el rapid.
Această abordare, cu tehnicile simple de kernelizare deja discutate, se arată bine și rezolvă unele teste de câteva mii de vârfuri în dimensiune. Dar, de exemplu, nu funcționează bine pentru graficele cubice (adică, graficele al căror grad al fiecărui vârf este trei).
Există o altă idee bazată pe o idee destul de simplă: dacă graficul este deconectat, problema componentelor sale conectate poate fi rezolvată independent, combinând răspunsurile de la sfârșit. Aceasta, apropo, este o mică modificare promisă a schemei, care va accelera semnificativ soluția: anterior, în acest caz, am lucrat pentru produsul timpilor pentru calcularea răspunsurilor componentelor, dar acum lucrăm pentru suma. Și pentru a accelera ramificarea, trebuie să transformați un grafic conectat într-unul deconectat.
Cum să o facă? Dacă există un punct de articulare în grafic, trebuie să lupți pentru el. Un punct de articulare este un vârf astfel încât, atunci când este îndepărtat, graficul își pierde conectivitatea. Toate punctele de joncțiune dintr-un grafic pot fi găsite folosind un algoritm clasic în timp liniar. Această abordare accelerează semnificativ ramificarea.
Când oricare dintre vârfurile selectate este eliminat, graficul se va împărți în componente conectate.
Vom face asta, dar vrem mai mult. De exemplu, căutați mici tăieturi de vârfuri în grafic și împărțiți de-a lungul vârfurilor din acesta. Cea mai eficientă modalitate pe care o cunosc pentru a găsi tăietura minimă globală a vârfurilor este utilizarea unui arbore Gomori-Hu, care este construit în timp cubic. În PACE Challenge, dimensiunea tipică a graficului este de câteva mii de vârfuri. În această situație, miliarde de operații trebuie efectuate la fiecare vârf al arborelui recursiv. Se pare că este pur și simplu imposibil să rezolvi problema în timpul alocat.
Să încercăm să optimizăm soluția. Taietura minimă a vârfurilor între o pereche de vârfuri poate fi găsită de orice algoritm care construiește un flux maxim. Îl poți lăsa într-o astfel de rețea , în practică funcționează foarte repede. Am o suspiciune ca teoretic este posibil sa dovedesc o estimare a timpului de functionare , ceea ce este deja destul de acceptabil.
Am încercat de mai multe ori să caut tăieturi între perechile de vârfuri aleatorii și să o iau pe cea mai echilibrată. Din păcate, acest lucru a produs rezultate slabe în testarea deschisă PACE Challenge. L-am comparat cu un algoritm care împarte vârfurile de grad maxim, rulându-le cu o limitare a adâncimii de coborâre. Un algoritm care încearcă să găsească o tăietură în acest fel a lăsat în urmă grafice mai mari. Acest lucru se datorează faptului că tăieturile s-au dovedit a fi foarte dezechilibrate: după ce au eliminat 5-10 vârfuri, a fost posibil să se despartă doar 15-20.
Este demn de remarcat faptul că articolele despre algoritmii teoretic cei mai rapizi folosesc tehnici mult mai avansate pentru selectarea vârfurilor pentru împărțire. Astfel de tehnici au o implementare foarte complexă și adesea performanțe slabe din punct de vedere al timpului și al memoriei. Nu am reușit să le identific pe cele care sunt destul de acceptabile pentru practică.
Cum se aplică regulile de simplificare
Avem deja idei pentru kernelizare. Lasă-mă să-ți amintesc:
- Dacă există un vârf izolat, ștergeți-l.
- Dacă există un vârf de gradul 1, îndepărtați-l și luați vecinul său ca răspuns.
- Dacă există un vârf de grad cel puțin k+1, Ia-o inapoi.
Cu primele două totul este clar, cu al treilea există un truc. Dacă într-o problemă comică despre un bar ni s-a dat o limită superioară de k, apoi în PACE Challenge trebuie doar să găsiți o acoperire de vârf de dimensiune minimă. Aceasta este o transformare tipică a problemelor de căutare în probleme de decizie; adesea nu există nicio diferență între cele două tipuri de probleme. În practică, dacă scriem un rezolvator pentru problema acoperirii vârfurilor, poate exista o diferență. De exemplu, ca în al treilea punct.
Din punct de vedere al implementării, există două moduri de a proceda. Prima abordare se numește Iterative Deepening. Este după cum urmează: putem începe cu o constrângere rezonabilă de dedesubt asupra răspunsului și apoi rulăm algoritmul folosind această constrângere ca constrângere pentru răspunsul de sus, fără a merge mai jos în recursivitate decât această constrângere. Dacă am găsit vreun răspuns, este garantat că va fi optim, altfel putem crește această limită cu unul și începe din nou.
O altă abordare este de a stoca un răspuns optim curent și de a căuta un răspuns mai mic, schimbând acest parametru atunci când este găsit k pentru o mai mare tăiere a ramurilor inutile în căutare.
După ce am efectuat mai multe experimente nocturne, m-am hotărât pe o combinație a acestor două metode: în primul rând, îmi rulez algoritmul cu un fel de limită a adâncimii de căutare (selectându-l astfel încât să ia timp neglijabil în comparație cu soluția principală) și folosesc cea mai bună soluție. soluție găsită ca limită superioară a răspunsului – adică la același lucru k.
Vârfurile de gradul 2
Ne-am ocupat de vârfuri de gradul 0 și 1. Se pare că acest lucru se poate face cu vârfuri de gradul 2, dar acest lucru va necesita operații mai complexe din grafic.
Pentru a explica acest lucru, trebuie să desemnăm cumva vârfurile. Să numim un vârf de gradul 2 un vârf v, și vecinii săi - vârfuri x и y. În continuare vom avea două cazuri.
- Când x и y - vecini. Atunci poți răspunde x и yȘi v șterge. Într-adevăr, din acest triunghi trebuie luate cel puțin două vârfuri în schimb și cu siguranță nu vom pierde dacă luăm x и y: probabil că au alți vecini, și v nu este niciuna dintre ele.
- Când x и y - nu vecini. Apoi se afirmă că toate cele trei vârfuri pot fi lipite într-unul singur. Ideea este că în acest caz există un răspuns optim, în care luăm fie v, sau ambele vârfuri x и y. Mai mult, în primul caz va trebui să luăm toți vecinii ca răspuns x и y, dar în al doilea nu este necesar. Acest lucru corespunde exact cazurilor în care nu luăm vârful lipit ca răspuns și când facem. Rămâne doar de observat că în ambele cazuri răspunsul la o astfel de operație scade cu unul.
Este demn de remarcat faptul că această abordare este destul de dificil de implementat cu precizie în timp liniar corect. Lipirea vârfurilor este o operațiune complexă; trebuie să copiați liste de vecini. Dacă acest lucru este făcut cu neatenție, puteți ajunge cu un timp de rulare asimptotic suboptim (de exemplu, dacă copiați multe margini după fiecare lipire). M-am hotărât să găsesc căi întregi de la vârfuri de gradul 2 și să analizez o grămadă de cazuri speciale, cum ar fi cicluri de la astfel de vârfuri sau din toate astfel de vârfuri, cu excepția unuia.
În plus, este necesar ca această operație să fie reversibilă, astfel încât la revenirea din recursivitate să restabilim graficul la forma sa inițială. Pentru a asigura acest lucru, nu am șters listele de margini ale vârfurilor îmbinate și apoi am știut doar ce margini trebuie să meargă unde. Această implementare a graficelor necesită, de asemenea, acuratețe, dar oferă un timp liniar corect. Iar pentru grafice de câteva zeci de mii de muchii, se potrivește în memoria cache a procesorului, ceea ce oferă mari avantaje în ceea ce privește viteza.
Miez liniar
În cele din urmă, cea mai interesantă parte a nucleului.
Pentru început, amintiți-vă că în graficele bipartite acoperirea minimă a vârfurilor poate fi găsită folosind . Pentru a face acest lucru, trebuie să utilizați algoritmul pentru a găsi potrivirea maximă acolo și apoi utilizați teorema .
Ideea unui nucleu liniar este aceasta: mai întâi bifurcăm graficul, adică în loc de fiecare vârf v hai sa adaugam doua varfuri и , iar în loc de fiecare margine u - v hai sa adaugam doua coaste и . Graficul rezultat va fi bipartit. Să găsim acoperirea minimă a vârfurilor în el. Unele vârfuri ale graficului original vor ajunge acolo de două ori, unele doar o dată, iar altele niciodată. Teorema Nemhauser-Trotter afirmă că în acest caz se pot elimina vârfurile care nu s-au lovit nici măcar o dată și se pot lua înapoi pe cele care au lovit de două ori. Mai mult, ea spune că dintre vârfurile rămase (cele care lovesc o dată) trebuie să luați cel puțin jumătate ca răspuns.
Tocmai am învățat să plecăm nu mai mult de 2k culmi Într-adevăr, dacă răspunsul rămas este cel puțin jumătate din toate vârfurile, atunci nu există mai multe vârfuri în total decât 2k.
Aici am putut să fac un mic pas înainte. Este clar că nucleul construit în acest fel depinde de ce fel de acoperire minimă a vârfurilor am luat în graficul bipartit. Aș dori să iau unul, astfel încât numărul de vârfuri rămase să fie minim. Anterior, au putut face acest lucru doar la timp . Am venit cu o implementare a acestui algoritm în timp , astfel, acest nucleu poate fi căutat în grafice de sute de mii de vârfuri la fiecare etapă de ramificare.
Rezultat
Practica arată că soluția mea funcționează bine pe teste de câteva sute de vârfuri și câteva mii de muchii. În astfel de teste, este foarte posibil să ne așteptăm ca o soluție să fie găsită într-o jumătate de oră. Probabilitatea de a găsi un răspuns într-un timp acceptabil, în principiu, crește dacă graficul are un număr suficient de mare de vârfuri de grad înalt, de exemplu, gradul 10 și mai mare.
Pentru a participa la concurs, soluțiile trebuiau trimise la . Judecând după informațiile prezentate acolo , soluția mea în testele deschise ocupă locul trei din douăzeci, cu un decalaj mare față de a doua. Ca să fiu complet sincer, nu este în totalitate clar cum vor fi evaluate soluțiile la competiție în sine: de exemplu, soluția mea trece mai puține teste decât soluția de pe locul al patrulea, dar la cele care trec, funcționează mai repede.
Rezultatele testelor închise vor fi cunoscute pe XNUMX iulie.
Sursa: www.habr.com