Undersykswurk is miskien it meast nijsgjirrige diel fan ús training. It idee is om josels te besykjen yn jo keazen rjochting wylst jo noch op 'e universiteit binne. Bygelyks, studinten út 'e gebieten fan Software Engineering en Machine Learning geane faak om ûndersyk te dwaan yn bedriuwen (benammen JetBrains of Yandex, mar net allinich).
Yn dizze post sil ik prate oer myn projekt yn Computer Science. As ûnderdiel fan myn wurk studearre ik en praktisearre oanpakken foar it oplossen fan ien fan 'e meast ferneamde NP-hurde problemen: vertex covering probleem.
Tsjintwurdich ûntwikkelet in nijsgjirrige oanpak fan NP-hurde problemen heul fluch - parameterisearre algoritmen. Ik sil besykje jo op 'e hichte te krijen, jo wat ienfâldige parameterisearre algoritmen te fertellen en ien krêftige metoade te beskriuwen dy't my in protte holp. Ik presinteare myn resultaten by de PACE Challenge-kompetysje: neffens de resultaten fan iepen tests nimt myn oplossing it tredde plak, en de definitive resultaten sille op 1 july bekend wurde.
Oer mysels
Myn namme is Vasily Alferov, ik bin no ôfmeitsje myn tredde jier oan de National Research University Hegere Skoalle fan Ekonomy - St. Ik haw west ynteressearre yn algoritmen sûnt myn skoaltiid, doe't ik studearre oan Moskou skoalle No.. 179 en mei súkses meidien oan kompjûter wittenskip Olympiades.
In einich oantal spesjalisten yn parameterisearre algoritmen komt de bar yn ...
Foarbyld nommen út it boek
Stel jo foar dat jo in barfeiligenswacht binne yn in lytse stêd. Elke freed komt de helte fan 'e stêd nei jo bar om te ûntspannen, wat jo in soad problemen jout: jo moatte rûzige klanten út 'e bar smite om fjochtpartijen foar te kommen. Uteinlik wurde jo nocht en beslute om previntive maatregels te nimmen.
Sûnt jo stêd is lyts, jo witte krekt hokker pearen fan patroanen binne wierskynlik te fjochtsjen as se einigje yn in bar tegearre. Hawwe jo in list fan n minsken dy't fannacht nei de bar komme. Jo beslute om guon stedslju út 'e bar te hâlden sûnder dat ien yn in gefjocht komt. Tagelyk wolle jo bazen gjin winst ferlieze en sille ûngelokkich wêze as jo net mear litte as k Minske.
Spitigernôch is it probleem foar jo in klassyk NP-hurd probleem. Jo kinne har kenne as , of as in toppuntbedekkingsprobleem. Foar sokke problemen, yn 't algemien, binne d'r gjin algoritmen dy't wurkje yn in akseptabele tiid. Om krekt te wêzen, seit de net bewiisde en frij sterke hypoteze ETH (Exponential Time Hypothesis) dat dit probleem net yn 'e tiid kin wurde oplost , dat is, kinne jo net tinke oan neat merkber better as in folsleine sykopdracht. Litte wy bygelyks sizze dat immen nei jo bar komt n = 1000 Minske. Dan sil de folsleine sykopdracht wêze opsjes dy't der likernôch - gek bedrach. Gelokkich hat jo behear jo in limyt jûn k = 10, dus it oantal kombinaasjes dat jo moatte iterearje is folle lytser: it oantal subsets fan tsien eleminten is . Dit is better, mar it sil noch net teld wurde yn in dei sels op in krêftige kluster.
Om elimineren de mooglikheid fan in gefjocht yn dizze konfiguraasje fan spanning relaasjes tusken de bar syn besikers, Jo moatte hâlden Bob, Daniel en Fedor út. Der is gjin oplossing wêrby't mar twa efterbliuwe.
Betsjut dit dat it tiid is om yn te jaan en elkenien yn te litten? Litte wy oare opsjes beskôgje. No, bygelyks, jo kinne net allinich dejingen ynlitte dy't wierskynlik mei in heul grut oantal minsken sille fjochtsje. As immen kin fjochtsje op syn minst mei k+1 in oare persoan, dan kinne jo him perfoarst net ynlitte - oars moatte jo elkenien bûten hâlde k+1 stedsbewenners, mei wa't er fjochtsje kin, wat de lieding definityf fergriemje sil.
Meie jo elkenien útsmite dy't jo koenen neffens dit prinsipe. Dan kin elkenien mei net mear fjochtsje as k folk. Smyt se út k man, do kinst foarkomme neat mear as konflikten. Dit betsjut dat as der mear as As in persoan belutsen is by op syn minst ien konflikt, dan kinne jo se wis net allegear foarkomme. Om't jo, fansels, perfoarst folslein net-konflikt minsken ynlitte, moatte jo alle subsets fan grutte tsien fan twahûndert minsken trochjaan. Der binne likernôch , en dit oantal operaasjes kin al wurde sortearre út op it kluster.
As jo persoanen feilich kinne nimme dy't hielendal gjin konflikt hawwe, hoe sit it dan mei dyjingen dy't meidwaan oan mar ien konflikt? Eins kinne se ek ynlitten wurde troch de doar op harren tsjinstanner ticht te dwaan. Ja, as Alice allinich yn konflikt is mei Bob, dan as wy Alice út har twa litte litte, sille wy net ferlieze: Bob kin oare konflikten hawwe, mar Alice hat se wis net. Boppedat hat it gjin sin foar ús om ús beide net yn te litten. Nei sokke operaasjes is der net mear oer gasten mei in unresolved lot: wy hawwe allinne konflikten, elk mei twa dielnimmers en elk belutsen by op syn minst twa. Dus alles wat bliuwt is te sortearjen opsjes, dy't maklik in heale dei kinne wurde beskôge op in laptop.
Yn feite, mei ienfâldige redenearring kinne jo berikke noch mear oantreklike betingsten. Tink derom dat wy perfoarst alle skelen moatte oplosse, dat is, út elk tsjinstridich pear, kieze op syn minst ien persoan dy't wy net ynlitte. Litte wy it folgjende algoritme beskôgje: nim elk konflikt, wêrfan wy ien dielnimmer fuortsmite en rekursyf begjinne fan 'e rest, ferwiderje dan de oare en begjinne ek rekursyf. Om't wy by elke stap immen útsmite, is de rekursjebeam fan sa'n algoritme in binêre beam fan djipte k, dus yn totaal wurket it algoritme yn wêr n is it oantal hoekpunten, en m - oantal ribben. Yn ús foarbyld is dit sa'n tsien miljoen, dat kin wurde berekkene yn in split sekonde net allinnich op in laptop, mar sels op in mobile telefoan.
It boppesteande foarbyld is in foarbyld parameterisearre algoritme. Parameterisearre algoritmen binne algoritmen dy't yn 'e tiid rinne f(k) poly(n)wêr p - polynoom, f is in willekeurich berekkenbere funksje, en k - guon parameter, dy't, frijwol, folle lytser sil wêze as de grutte fan it probleem.
Alle redenearring foar dit algoritme jout in foarbyld kernelization is ien fan 'e algemiene techniken foar it meitsjen fan parameterisearre algoritmen. Kernelisaasje is de reduksje fan 'e probleemgrutte nei in wearde beheind troch in funksje fan in parameter. It resultearjende probleem wurdt faaks in kernel neamd. Sa, troch ienfâldige redenearring oer de graden fan hoekpunten, hawwe wy in kwadratyske kearn krigen foar it Vertex Cover-probleem, parameterisearre troch de grutte fan it antwurd. Der binne oare opsjes dy't kinne wurde selektearre foar dizze taak (Bygelyks, Vertex Cover Above LP), mar dit is de opsje wy sille beprate.
Pace Challenge
Kompetysje (The Parameterized Algorithms and Computational Experiments Challenge) waard berne yn 2015 om in ferbining te meitsjen tusken parameterisearre algoritmen en oanpakken dy't yn 'e praktyk brûkt wurde om komputaasjeproblemen op te lossen. De earste trije kompetysjes wiene wijd oan it finen fan de beambreedte fan in grafyk (), op syk nei in Steinerbeam () en sykjen nei in set hoekpunten dy't syklusen snijt (). Dit jier wie ien fan 'e problemen wêryn't jo jo hân besykje koenen it hjirboppe beskreaune probleem fan topbedekking.
De konkurrinsje wint alle jierren populariteit. As jo de foarriedige gegevens leauwe, namen dit jier 24 ploegen diel oan 'e kompetysje om allinich it probleem fan topbedekking op te lossen. It is de muoite wurdich opskriuwen dat de konkurrinsje duorret net ferskate oeren of sels in wike, mar ferskate moannen. Teams hawwe de kâns om de literatuer te bestudearjen, mei har eigen orizjinele idee te kommen en te besykjen it út te fieren. Yn essinsje is dizze konkurrinsje in ûndersyksprojekt. Ideeën foar de meast effektive oplossingen en it takennen fan 'e winners wurde hâlden yn' e mande mei de konferinsje (International Symposium on Parameterized and Exact Computation) as ûnderdiel fan 'e grutste jierlikse algoritmyske gearkomste yn Jeropa . Mear detaillearre ynformaasje oer de kompetysje sels is te finen op , en de resultaten fan foargeande jierren lizze .
Oplossing diagram
Foar it oplossen fan it probleem fan topdekkende problemen, haw ik besocht parameterisearre algoritmen te brûken. Se besteane typysk út twa dielen: ferienfâldigingsregels (dy't ideaal liede ta kernelisaasje) en splitsingsregels. Simplification regels binne preprocessing fan de ynfier yn polynomiale tiid. It doel fan it tapassen fan sokke regels is om it probleem te ferminderjen ta in lykweardich lytser probleem. Simplification regels binne it djoerste diel fan it algoritme, en it tapassen fan dit diel liedt ta de totale rinnende tiid ynstee fan ienfâldige polynomial tiid. Yn ús gefal binne de splitsingsregels basearre op it feit dat jo foar elke hoekpunt it of har buorman as antwurd moatte nimme.
It algemiene skema is dit: wy tapasse de ferienfâldigingsregels, dan selektearje wy wat hoekpunt, en meitsje twa rekursive oproppen: yn 'e earste nimme wy it as antwurd, en yn' e oare nimme wy al har buorlju. Dit is wat wy splitsje (fertakking) lâns dit toppunt neame.
Krekt ien tafoeging wurdt makke oan dit skema yn de folgjende paragraaf.
Ideeën foar splitsing (brunching) regels
Litte wy beprate hoe't jo in toppunt kieze wêr't de splitsing sil plakfine.
It haadgedachte is heul gierig yn 'e algoritmyske sin: lit ús in toppunt fan maksimale graad nimme en dêr lâns splitse. Wêrom liket it better? Want yn 'e twadde tûke fan 'e rekursive oprop sille wy op dizze manier in protte hoekpunten fuortsmite. Jo kinne rekkenje op in lytse grafyk oerbleaun en wy kinne wurkje oan it fluch.
Dizze oanpak, mei de al besprutsen ienfâldige kernelisaasjetechniken, lit him goed sjen en lost guon tests op fan ferskate tûzen hoekpunten yn grutte. Mar, bygelyks, it wurket net goed foar kubike grafiken (dat is, grafiken wêrfan de graad fan elke hoekpunt trije is).
D'r is in oar idee basearre op in frij ienfâldich idee: as de grafyk is loskeppele, kin it probleem op har ferbûne komponinten selsstannich oplost wurde, troch de antwurden oan 'e ein te kombinearjen. Dit, trouwens, is in lytse taseine wiziging yn it skema, dy't de oplossing signifikant sil fersnelle: earder, yn dit gefal, wurken wy foar it produkt fan 'e tiid foar it berekkenjen fan' e antwurden fan 'e komponinten, mar no wurkje wy foar de som. En om fertakking te rapperjen, moatte jo in ferbûne grafyk omsette yn in loskeppele.
Hoe it te dwaan? As d'r in artikulaasjepunt yn 'e grafyk is, moatte jo derop fjochtsje. In artikulaasjepunt is in hoekpunt sadanich dat as it fuorthelle wurdt, de grafyk syn ferbining ferliest. Alle knooppunten yn in grafyk kinne fûn wurde mei in klassyk algoritme yn lineêre tiid. Dizze oanpak fersnelt de fertakking signifikant.
As ien fan 'e selektearre hoekpunten wurdt fuortsmiten, sil de grafyk splitst yn ferbûne komponinten.
Wy sille dit dwaan, mar wy wolle mear. Sjoch bygelyks foar lytse hoekpunten yn 'e grafyk en spjalte dêrút lâns de hoekpunten. De meast effisjinte manier dy't ik wit om de minimale globale vertex-knip te finen is in Gomori-Hu-beam te brûken, dy't yn kubike tiid is boud. Yn 'e PACE Challenge is de typyske grafykgrutte ferskate tûzen hoekpunten. Yn dizze situaasje moatte miljarden operaasjes útfierd wurde op elke hoekpunt fan 'e rekursjebeam. It docht bliken dat it gewoan ûnmooglik is om it probleem yn 'e tawiisde tiid op te lossen.
Litte wy besykje de oplossing te optimalisearjen. De minimale vertex-knip tusken in pear hoekpunten kin fûn wurde troch elk algoritme dat in maksimale stream konstruearret. Jo kinne it op sa'n netwurk litte , yn 'e praktyk wurket it hiel fluch. Ik haw it fermoeden dat it teoretysk mooglik is om in skatting foar de wurktiid te bewizen , dat is al hiel akseptabel.
Ik besocht ferskate kearen te sykjen foar besunigings tusken pearen willekeurige hoekpunten en nim de meast lykwichtige. Spitigernôch produsearre dit minne resultaten yn iepen PACE Challenge-testen. Ik fergelike it mei in algoritme dat spjalte hoekpunten fan maksimale graad, rinne se mei in beheining op 'e djipte fan komôf. In algoritme dat op dizze manier in besuniging besiket te finen, liet gruttere grafiken efter. Dit is te tankjen oan it feit dat de besunigings tige unbalansearre wiene: nei't 5-10 hoekpunten fuorthelle wiene, koe it allinich 15-20 ôfsplitst wurde.
It is de muoite wurdich op te merken dat artikels oer de teoretysk fluchste algoritmen brûke folle mear avansearre techniken foar it selektearjen fan hoekpunten foar splitsing. Sokke techniken hawwe tige komplekse ymplemintaasje en faak minne prestaasjes yn termen fan tiid en ûnthâld. Ik koe dejingen net identifisearje dy't frij akseptabel binne foar praktyk.
Hoe kinne jo ferienfâldigingsregels tapasse
Wy hawwe al ideeën foar kernelization. Lit my jo herinnerje:
- As d'r in isolearre toppunt is, wiskje it dan.
- As der in toppunt fan graad 1, fuortsmite en nim syn buorman yn antwurd.
- As der op syn minst in toppunt fan graad is k+1, nim it werom.
By de earste twa is alles dúdlik, by de tredde is der ien trúkje. As yn in komysk probleem oer in bar wy krigen in boppegrins fan k, dan moatte jo yn 'e PACE Challenge gewoan in topdeksel fan' e minimale grutte fine. Dit is in typyske transformaasje fan sykproblemen yn beslútproblemen; faak is d'r gjin ferskil tusken de twa soarten problemen. Yn 'e praktyk, as wy in oplosser skriuwe foar it probleem fan vertexbedekking, kin d'r in ferskil wêze. Bygelyks, lykas yn it tredde punt.
Ut in ymplemintaasje eachpunt binne der twa manieren om fierder te gean. De earste oanpak wurdt Iterative Deepening neamd. It is as folget: wy kinne begjinne mei wat ridlike beheining fan ûnderen op it antwurd, en dan rinne ús algoritme mei help fan dizze beheining as in beheining op it antwurd fan boppen, sûnder gean leger yn rekursion as dizze beheining. As wy wat antwurd hawwe fûn, is it garandearre optimaal, oars kinne wy dizze limyt mei ien ferheegje en opnij begjinne.
In oare oanpak is om wat aktueel optimaal antwurd op te slaan en in lytser antwurd te sykjen, dizze parameter te feroarjen as it fûn wurdt k foar grutter ôfsnijen fan ûnnedige tûken yn it sykjen.
Nei it útfieren fan ferskate nachtlike eksperiminten, haw ik my fêststeld op in kombinaasje fan dizze twa metoaden: earst rinne ik myn algoritme mei in soarte fan limyt op 'e sykdjipte (selektearje it sa dat it ferwaarloazele tiid nimt yn ferliking mei de haadoplossing) en brûk de bêste oplossing fûn as in boppegrins foar it antwurd - dat is, op itselde ding k.
Hânpunten fan graad 2
Wy hawwe te krijen mei hoekpunten fan graad 0 en 1. It docht bliken dat dit kin dien wurde mei hoekpunten fan graad 2, mar dit sil fereaskje mear komplekse operaasjes út de grafyk.
Om dit te ferklearjen, moatte wy op ien of oare manier de hoekpunten oanwize. Litte wy in toppunt fan graad 2 in toppunt neame v, en syn buorlju - hoekpunten x и y. Folgjende sille wy twa gefallen hawwe.
- Wannear x и y - buorlju. Dan kinne jo antwurdzje x и yen v wiskje. Yndied, fan dizze trijehoek moatte op syn minst twa hoekpunten yn ruil nommen wurde, en wy sille perfoarst net ferlieze as wy nimme x и y: se hawwe wierskynlik oare buorlju, en v Se binne hjir net.
- Wannear x и y - gjin buorlju. Dan wurdt steld dat alle trije hoekpunten yn ien lijme kinne. It idee is dat yn dit gefal is der in optimaal antwurd, dêr't wy nimme beide v, of beide hoekpunten x и y. Boppedat moatte wy yn it earste gefal alle buorlju yn reaksje nimme x и y, mar yn 'e twadde is it net nedich. Dit komt krekt oerien mei de gefallen doe't wy net nimme de lijm vertex yn antwurd en as wy dogge. It bliuwt allinich om te notearjen dat yn beide gefallen it antwurd fan sa'n operaasje mei ien ôfnimt.
It is de muoite wurdich opskriuwen dat dizze oanpak is frij lestich om sekuer te fieren yn earlike lineêre tiid. Lijmen fan hoekpunten is in komplekse operaasje; jo moatte listen fan buorlju kopiearje. As dit wurdt dien foarsichtich, kinne jo einigje mei asymptotically suboptimal rinnende tiid (Bygelyks, as jo kopiearje in protte rânen nei eltse gluing). Ik bin besletten op it finen fan folsleine paden fan hoekpunten fan graad 2 en analysearjen fan in boskje spesjale gefallen, lykas syklusen fan sokke hoekpunten of fan al sokke hoekpunten útsein ien.
Dêrnjonken is it nedich dat dizze operaasje omkearber is, sadat wy by it weromkommen fan rekursje de grafyk weromsette nei syn oarspronklike foarm. Om dit te garandearjen, haw ik de rânelisten fan 'e gearfoege hoekpunten net wiske, en doe wist ik gewoan hokker rânen wêr moasten gean. Dizze ymplemintaasje fan grafiken fereasket ek krektens, mar it leveret earlike lineêre tiid. En foar grafiken fan ferskate tsientûzenen rânen past it yn 'e prosessor-cache, wat grutte foardielen jout yn snelheid.
Lineêre kernel
As lêste, it meast nijsgjirrige diel fan 'e kernel.
Om te begjinnen, tink derom dat yn bipartite-grafiken de minimale vertexdekking kin fûn wurde mei help fan . Om dit te dwaan moatte jo it algoritme brûke om dêr de maksimale oerienkomst te finen, en brûk dan de stelling .
It idee fan in lineêre kearn is dit: earst bifurcate wy de grafyk, dat is, ynstee fan elke hoekpunt v lit ús twa peaks tafoegje и , en ynstee fan elke râne u - v lit ús tafoegje twa ribben и . De resultearjende grafyk sil bipartite wêze. Lit ús fine de minimale toppunt dekking dêryn. Guon hoekpunten fan 'e oarspronklike grafyk komme dêr twa kear, guon mar ien kear, en guon nea. De Nemhauser-Trotter stelling stelt dat men yn dit gefal hoekpunten fuortsmite kin dy't net ien kear troffen binne en dy weromnimme dy't twa kear troffen. Boppedat seit se dat jo fan 'e oerbleaune hoekpunten (dy't ien kear slaan) op syn minst de helte as antwurd nimme moatte.
Wy hawwe krekt leard te ferlitten net mear as 2k peaks Yndied, as it restant antwurd op syn minst de helte fan alle hoekpunten is, dan binne der yn totaal net mear hoekpunten dan 2k.
Hjir koe ik in lytse stap foarút sette. It is dúdlik dat de kearn dy't op dizze manier konstruearre is hinget ôf fan hokker soarte fan minimale vertex-dekking wy hawwe naam yn 'e bipartite-grafyk. Ik wol ien nimme, sadat it oantal oerbleaune hoekpunten minimaal is. Earder koene se dat mar op 'e tiid . Ik kaam mei in ymplemintaasje fan dit algoritme yn 'e tiid , sadwaande kin nei dizze kearn socht wurde yn grafiken fan hûnderttûzenen hoekpunten by elke fertakking.
resultaat
Oefenjen lit sjen dat myn oplossing goed wurket op tests fan ferskate hûndert hoekpunten en ferskate tûzen rânen. By sokke tests is goed te ferwachtsjen dat der oer in healoere in oplossing fûn wurdt. De kâns op it finen fan in antwurd yn in akseptabel tiid, yn prinsipe, nimt ta as de grafyk hat in foldwaande grut oantal hoekpunten fan hege graad, bygelyks, graad 10 en heger.
Om mei te dwaan oan de kompetysje moasten oplossings stjoerd wurde nei . Te oardieljen nei de ynformaasje dy't dêr presintearre , myn oplossing yn iepen tests stiet tredde fan de tweintich, mei in grut gat fan twadde. Om folslein earlik te wêzen, is it net hielendal dúdlik hoe't oplossings by de konkurrinsje sels evaluearre wurde: myn oplossing slacht bygelyks minder tests troch as de oplossing op it fjirde plak, mar op dyjingen dy't passe, wurket it flugger.
De resultaten fan sletten tests wurde op XNUMX july bekend.
Boarne: www.habr.com