Navorsingswerk is miskien die interessantste deel van ons opleiding. Die idee is om jouself in jou gekose rigting te probeer terwyl jy nog op universiteit is. Studente uit die gebiede van sagteware-ingenieurswese en masjienleer gaan byvoorbeeld dikwels navorsing in maatskappye doen (hoofsaaklik JetBrains of Yandex, maar nie net nie).
In hierdie pos sal ek oor my projek in Rekenaarwetenskap praat. As deel van my werk het ek benaderings tot die oplossing van een van die bekendste NP-harde probleme bestudeer en in die praktyk toegepas: hoekpuntbedekkingsprobleem.
Deesdae ontwikkel 'n interessante benadering tot NP-harde probleme baie vinnig - geparameteriseerde algoritmes. Ek sal probeer om jou op hoogte te bring, vir jou 'n paar eenvoudige geparameteriseerde algoritmes vertel en een kragtige metode beskryf wat my baie gehelp het. Ek het my uitslae by die PACE Challenge-kompetisie aangebied: volgens die uitslae van oop toetse neem my oplossing die derde plek in, en die finale uitslae sal op 1 Julie bekend wees.
About Me
My naam is Vasily Alferov, ek voltooi nou my derde jaar by die Nasionale Navorsingsuniversiteit Hoër Skool vir Ekonomie - St. Petersburg. Ek het sedert my skooldae in algoritmes belanggestel, toe ek by Moskou skool nr. 179 gestudeer het en suksesvol aan rekenaarwetenskap-olimpiades deelgeneem het.
'n Begrensde aantal spesialiste in geparameteriseerde algoritmes betree die balk ...
Voorbeeld geneem uit die boek
Stel jou voor dat jy 'n kroeg sekuriteitswag in 'n klein dorpie is. Elke Vrydag kom die helfte van die stad na jou kroeg om te ontspan, wat jou baie moeilikheid gee: jy moet rumoerige klante uit die kroeg gooi om gevegte te voorkom. Uiteindelik raak jy keelvol en besluit om voorkomende maatreëls te tref.
Aangesien jou stad klein is, weet jy presies watter pare besoekers waarskynlik sal veg as hulle saam in 'n kroeg beland. Het jy 'n lys van n mense wat vanaand na die kroeg sal kom. Jy besluit om 'n paar dorpsmense uit die kroeg te hou sonder dat iemand baklei. Terselfdertyd wil jou base nie winste verloor nie en sal hulle ongelukkig wees as jy nie meer as k mense.
Ongelukkig is die probleem voor jou 'n klassieke NP-harde probleem. Jy ken haar dalk as , of as 'n hoekpuntbedekkingsprobleem. Vir sulke probleme, in die algemene geval, is daar geen algoritmes wat in 'n aanvaarbare tyd werk nie. Om presies te wees, die onbewese en redelik sterk hipotese ETH (Eksponensiële Tydhipotese) sê dat hierdie probleem nie betyds opgelos kan word nie , dit wil sê, jy kan aan niks merkbaar beter dink as 'n volledige soektog nie. Byvoorbeeld, kom ons sê iemand gaan na jou kroeg toe kom n = 1000 Mens. Dan sal die volledige soektog wees opsies wat daar ongeveer is - mal bedrag. Gelukkig het jou bestuur jou 'n perk gegee k = 10, dus is die aantal kombinasies waaroor jy moet herhaal baie kleiner: die aantal substelle van tien elemente is . Dit is beter, maar dit sal steeds nie in 'n dag getel word nie, selfs op 'n kragtige groep.
Om die moontlikheid van 'n geveg in hierdie opset van gespanne verhoudings tussen die kroeg se besoekers uit te skakel, moet jy Bob, Daniel en Fedor uithou. Daar is geen oplossing waarin net twee sal agterbly nie.
Beteken dit dat dit tyd is om in te gee en almal in te laat? Kom ons kyk na ander opsies. Wel, byvoorbeeld, jy kan nie net diegene inlaat wat waarskynlik met 'n baie groot aantal mense sal veg nie. As iemand kan baklei ten minste met k+1 'n ander persoon, dan kan jy hom beslis nie inlaat nie - anders sal jy almal moet uithou k+1 dorpsmense, met wie hy kan veg, wat beslis die leierskap sal ontstel.
Mag jy almal uitgooi wat jy kon volgens hierdie beginsel. Dan kan almal anders baklei met nie meer as k mense. Gooi hulle uit k man, jy kan niks meer voorkom as konflikte. Dit beteken dat as daar meer as As 'n persoon in ten minste een konflik betrokke is, dan kan jy beslis nie almal verhoed nie. Aangesien jy beslis mense wat heeltemal nie konflik is nie, sal inlaat, moet jy deur alle subsets van grootte tien uit tweehonderd mense gaan. Daar is ongeveer , en hierdie aantal bewerkings kan reeds op die cluster uitgesorteer word.
As jy veilig individue kan vat wat glad nie konflik het nie, wat dan van diegene wat aan net een konflik deelneem? Trouens, hulle kan ook ingelaat word deur die deur op hul teenstander toe te maak. Inderdaad, as Alice net met Bob in konflik is, dan sal ons nie verloor as ons Alice uit hulle twee los nie: Bob kan ander konflikte hê, maar Alice het dit beslis nie. Boonop maak dit geen sin dat ons nie albei van ons inlaat nie. Na sulke operasies bly daar nie meer oor nie gaste met 'n onopgeloste lot: ons het net konflikte, elk met twee deelnemers en elkeen betrokke by ten minste twee. So al wat oorbly is om deur te sorteer opsies, wat maklik 'n halwe dag op 'n skootrekenaar oorweeg kan word.
Trouens, met eenvoudige redenasie kan jy selfs aantrekliker toestande bereik. Let daarop dat ons beslis alle dispute moet oplos, dit wil sê uit elke botsende paar, kies ten minste een persoon wat ons nie sal inlaat nie. Kom ons oorweeg die volgende algoritme: neem enige konflik, waaruit ons een deelnemer verwyder en rekursief by die res begin, verwyder dan die ander en begin ook rekursief. Aangesien ons iemand by elke stap uitgooi, is die rekursieboom van so 'n algoritme 'n binêre boom van diepte k, so in totaal werk die algoritme in Waar n is die aantal hoekpunte, en m - aantal ribbes. In ons voorbeeld is dit ongeveer tien miljoen, wat in 'n breukdeel van 'n sekonde bereken kan word nie net op 'n skootrekenaar nie, maar selfs op 'n selfoon.
Die voorbeeld hierbo is 'n voorbeeld geparameteriseerde algoritme. Geparameteriseerde algoritmes is algoritmes wat in tyd loop f(k) poli(n)Waar p - polinoom, f is 'n arbitrêre berekenbare funksie, en k - een of ander parameter, wat heel moontlik baie kleiner sal wees as die grootte van die probleem.
Alle redenasies voor hierdie algoritme gee 'n voorbeeld kernelisering is een van die algemene tegnieke vir die skep van geparameteriseerde algoritmes. Kernelisering is die vermindering van die probleemgrootte tot 'n waarde beperk deur 'n funksie van 'n parameter. Die gevolglike probleem word dikwels 'n kern genoem. Dus, deur eenvoudige redenering oor die grade van hoekpunte, het ons 'n kwadratiese kern vir die Vertex Cover-probleem verkry, geparameteriseer deur die grootte van die antwoord. Daar is ander instellings wat jy vir hierdie taak kan kies (soos Vertex Cover Above LP), maar dit is die instelling wat ons sal bespreek.
Tempo Uitdaging
Kompetisie (The Parameterized Algorithms and Computational Experiments Challenge) is in 2015 gebore om 'n verband te vestig tussen geparameteriseerde algoritmes en benaderings wat in die praktyk gebruik word om rekenaarprobleme op te los. Die eerste drie kompetisies is gewy aan die vind van die boomwydte van 'n grafiek (), op soek na 'n Steiner-boom () en soek na 'n stel hoekpunte wat siklusse sny (). Vanjaar was een van die probleme waarin jy jou hand kon probeer die hoekpuntbedekkingsprobleem wat hierbo beskryf is.
Die kompetisie wen elke jaar gewildheid. As jy die voorlopige data glo, het vanjaar 24 spanne aan die kompetisie deelgeneem om die hoekpuntbedekkingsprobleem alleen op te los. Dit is opmerklik dat die kompetisie nie 'n paar uur of selfs 'n week duur nie, maar 'n paar maande. Spanne het die geleentheid om die literatuur te bestudeer, met hul eie oorspronklike idee vorendag te kom en dit te probeer implementeer. In wese is hierdie kompetisie 'n navorsingsprojek. Idees vir die mees doeltreffende oplossings en toekenning van die wenners sal saam met die konferensie gehou word (International Simposium on Parameterized and Exact Computation) as deel van die grootste jaarlikse algoritmiese vergadering in Europa . Meer gedetailleerde inligting oor die kompetisie self kan gevind word by , en die resultate van vorige jare lieg .
Oplossingsdiagram
Om die hoekpuntbedekkingsprobleem op te los, het ek probeer om geparameteriseerde algoritmes te gebruik. Hulle bestaan tipies uit twee dele: vereenvoudigingsreëls (wat ideaal lei tot kernelisering) en verdeelreëls. Vereenvoudigingsreëls is voorverwerking van die invoer in polinoomtyd. Die doel van die toepassing van sulke reëls is om die probleem tot 'n ekwivalente kleiner probleem te reduseer. Vereenvoudigingsreëls is die duurste deel van die algoritme, en die toepassing van hierdie deel lei tot die totale looptyd in plaas van eenvoudige polinoomtyd. In ons geval is die verdelingsreëls gebaseer op die feit dat jy vir elke hoekpunt óf dit óf sy buurman as 'n antwoord moet neem.
Die algemene skema is dit: ons pas die vereenvoudigingsreëls toe, dan kies ons 'n hoekpunt, en maak twee rekursiewe oproepe: in die eerste neem ons dit in reaksie, en in die ander neem ons al sy bure. Dit is wat ons splitsing (vertakting) langs hierdie hoekpunt noem.
Presies een toevoeging sal in die volgende paragraaf tot hierdie skema gemaak word.
Idees vir verdeling (brunching) reëls
Kom ons bespreek hoe om 'n hoekpunt te kies waarlangs die splitsing sal plaasvind.
Die hoofgedagte is baie gulsig in die algoritmiese sin: kom ons neem 'n hoekpunt van maksimum graad en verdeel daarlangs. Hoekom lyk dit beter? Want in die tweede tak van die rekursiewe oproep sal ons baie hoekpunte op hierdie manier verwyder. Jy kan daarop reken dat 'n klein grafiek oorbly en ons kan vinnig daaraan werk.
Hierdie benadering, met die reeds bespreekte eenvoudige kerneliseringstegnieke, wys homself goed en los sommige toetse van etlike duisend hoekpunte in grootte op. Maar dit werk byvoorbeeld nie goed vir kubieke grafieke nie (dit wil sê grafieke waarvan die graad van elke hoekpunt drie is).
Daar is nog 'n idee wat gebaseer is op 'n redelik eenvoudige idee: as die grafiek ontkoppel is, kan die probleem op sy gekoppelde komponente onafhanklik opgelos word deur die antwoorde aan die einde te kombineer. Dit is terloops 'n klein beloofde wysiging in die skema, wat die oplossing aansienlik sal bespoedig: voorheen, in hierdie geval, het ons gewerk vir die produk van die tye om die reaksies van die komponente te bereken, maar nou werk ons vir die som. En om vertakking te bespoedig, moet jy 'n gekoppelde grafiek in 'n ontkoppelde een verander.
Hoe om dit te doen? As daar 'n artikulasiepunt in die grafiek is, moet jy daarteen veg. 'n Artikulasiepunt is 'n hoekpunt sodat wanneer dit verwyder word, die grafiek sy konnektiwiteit verloor. Alle aansluitingspunte in 'n grafiek kan gevind word deur 'n klassieke algoritme in lineêre tyd te gebruik. Hierdie benadering versnel vertakking aansienlik.
Wanneer enige van die geselekteerde hoekpunte verwyder word, sal die grafiek in gekoppelde komponente verdeel.
Ons sal dit doen, maar ons wil meer hê. Soek byvoorbeeld vir klein hoekpuntsnitte in die grafiek en verdeel langs die hoekpunte daarvan. Die doeltreffendste manier wat ek ken om die minimum globale hoekpuntsnit te vind, is om 'n Gomori-Hu-boom te gebruik, wat in kubieke tyd gebou is. In die PACE Challenge is die tipiese grafiekgrootte 'n paar duisend hoekpunte. In hierdie situasie moet biljoene bewerkings by elke hoekpunt van die rekursieboom uitgevoer word. Dit blyk dat dit eenvoudig onmoontlik is om die probleem op die toegelate tyd op te los.
Kom ons probeer om die oplossing te optimaliseer. Die minimum hoekpunt sny tussen 'n paar hoekpunte kan gevind word deur enige algoritme wat 'n maksimum vloei konstrueer. Jy kan dit op so 'n netwerk laat , in die praktyk werk dit baie vinnig. Ek het 'n vermoede dat dit teoreties moontlik is om 'n skatting vir die bedryfstyd te bewys , wat reeds heel aanvaarbaar is.
Ek het verskeie kere probeer om snitte tussen pare ewekansige hoekpunte te soek en die mees gebalanseerde een te neem. Ongelukkig het dit swak resultate in oop PACE Challenge-toetse opgelewer. Ek het dit vergelyk met 'n algoritme wat hoekpunte van maksimum graad verdeel, met 'n beperking op die diepte van afkoms. 'n Algoritme wat op hierdie manier 'n snit probeer vind, het groter grafieke agtergelaat. Dit is te wyte aan die feit dat die snitte baie ongebalanseerd blyk te wees: nadat 5-10 hoekpunte verwyder is, was dit moontlik om slegs 15-20 af te skei.
Dit is opmerklik dat artikels oor die teoreties vinnigste algoritmes baie meer gevorderde tegnieke gebruik om hoekpunte vir splitsing te kies. Sulke tegnieke het baie komplekse implementering en dikwels swak prestasie in terme van tyd en geheue. Ek kon nie diegene identifiseer wat redelik aanvaarbaar is vir oefening nie.
Hoe om vereenvoudigingsreëls toe te pas
Ons het reeds idees vir kernelisering. Laat ek jou herinner:
- As daar 'n geïsoleerde hoekpunt is, verwyder dit.
- As daar 'n hoekpunt van graad 1 is, verwyder dit en neem sy buurman in reaksie.
- As daar ten minste 'n hoekpunt van graad is k+1, neem dit terug.
Met die eerste twee is alles duidelik, met die derde is daar een truuk. As in 'n komiese probleem oor 'n kroeg ons 'n boonste limiet van k, dan moet jy in die PACE Challenge net 'n hoekpuntbedekking van die minimum grootte vind. Dit is 'n tipiese transformasie van Soekprobleme in Besluitprobleme; daar is dikwels geen verskil tussen die twee tipes probleme nie. In die praktyk, as ons 'n oplosser vir die hoekpuntbedekkingsprobleem skryf, kan daar 'n verskil wees. Byvoorbeeld, soos in die derde punt.
Vanuit 'n implementeringsoogpunt is daar twee maniere om voort te gaan. Die eerste benadering word Iteratiewe Verdieping genoem. Dit is soos volg: ons kan begin met 'n redelike beperking van onder op die antwoord, en dan ons algoritme hardloop deur hierdie beperking as 'n beperking op die antwoord van bo af te gebruik, sonder om laer te gaan in rekursie as hierdie beperking. As ons 'n antwoord gevind het, is dit gewaarborg om optimaal te wees, anders kan ons hierdie limiet met een verhoog en weer begin.
Nog 'n benadering is om 'n huidige optimale antwoord te stoor en na 'n kleiner antwoord te soek, en hierdie parameter te verander wanneer dit gevind word k vir groter afsny van onnodige takke in die soektog.
Nadat ek verskeie nagtelike eksperimente uitgevoer het, het ek op 'n kombinasie van hierdie twee metodes besluit: eerstens voer ek my algoritme uit met 'n soort beperking op die soekdiepte (kies dit so dat dit weglaatbaar tyd neem in vergelyking met die hoofoplossing) en gebruik die beste oplossing gevind as 'n boonste limiet vir die antwoord - dit wil sê vir dieselfde ding k.
Toppunte van graad 2
Ons het met hoekpunte van graad 0 en 1 gehandel. Dit blyk dat dit gedoen kan word met hoekpunte van graad 2, maar dit sal meer komplekse bewerkings van die grafiek vereis.
Om dit te verduidelik, moet ons op een of ander manier die hoekpunte aanwys. Kom ons noem 'n hoekpunt van graad 2 'n hoekpunt v, en sy bure - hoekpunte x и y. Volgende sal ons twee gevalle hê.
- Wanneer x и y - bure. Dan kan jy antwoord x и yEn v skrap. Inderdaad, uit hierdie driehoek moet ten minste twee hoekpunte in ruil geneem word, en ons sal beslis nie verloor as ons x и y: hulle het seker ander bure, en v hulle is nie.
- Wanneer x и y - nie bure nie. Dan word gestel dat al drie hoekpunte in een vasgeplak kan word. Die idee is dat daar in hierdie geval 'n optimale antwoord is, waarin ons óf neem v, of albei hoekpunte x и y. Boonop sal ons in die eerste geval alle bure in reaksie moet neem x и y, maar in die tweede is dit nie nodig nie. Dit stem presies ooreen met die gevalle wanneer ons nie die vasgeplakte hoekpunt in reaksie neem nie en wanneer ons dit doen. Dit bly net om daarop te let dat die reaksie van so 'n operasie in beide gevalle met een afneem.
Dit is opmerklik dat hierdie benadering redelik moeilik is om akkuraat te implementeer in redelike lineêre tyd. Om hoekpunte vas te plak is 'n komplekse operasie; jy moet lyste van bure kopieer. As dit onverskillig gedoen word, kan jy asimptoties suboptimale looptyd opeindig (byvoorbeeld as jy baie rande na elke gom kopieer). Ek het besluit om hele paaie vanaf hoekpunte van graad 2 te vind en 'n klomp spesiale gevalle te ontleed, soos siklusse vanaf sulke hoekpunte of van al sulke hoekpunte behalwe een.
Daarbenewens is dit nodig dat hierdie operasie omkeerbaar is, sodat ons die grafiek na sy oorspronklike vorm herstel wanneer ons terugkeer van rekursie. Om dit te verseker, het ek nie die randlyste van die saamgevoegde hoekpunte skoongemaak nie, en toe het ek net geweet watter rande waarheen moes gaan. Hierdie implementering van grafieke vereis ook akkuraatheid, maar dit verskaf billike lineêre tyd. En vir grafieke van etlike tienduisende rande, pas dit in die verwerkerkas, wat groot voordele in spoed bied.
Lineêre kern
Ten slotte, die interessantste deel van die kern.
Om mee te begin, onthou dat in tweeledige grafieke die minimum hoekpuntbedekking gevind kan word deur gebruik te maak van . Om dit te doen, moet jy die algoritme gebruik om die maksimum passing daar te vind, en gebruik dan die stelling .
Die idee van 'n lineêre kern is dit: eers verdeel ons die grafiek, dit wil sê in plaas van elke hoekpunt v kom ons voeg twee pieke by и , en in plaas van elke rand u - v kom ons voeg twee ribbes by и . Die resulterende grafiek sal tweeledig wees. Kom ons vind die minimum hoekpuntbedekking daarin. Sommige hoekpunte van die oorspronklike grafiek sal twee keer daar kom, sommige net een keer en ander nooit. Die Nemhauser-Trotter-stelling stel dat 'n mens in hierdie geval hoekpunte kan verwyder wat nie eers een keer getref het nie en dié wat twee keer getref het, kan terugneem. Boonop sê sy dat jy van die oorblywende hoekpunte (dié wat een keer getref het) ten minste die helfte as 'n antwoord moet neem.
Ons het pas geleer om nie meer as te verlaat nie 2k pieke Inderdaad, as die res antwoord ten minste die helfte van alle hoekpunte is, dan is daar nie meer hoekpunte in totaal as 2k.
Hier kon ek 'n klein treetjie vorentoe gee. Dit is duidelik dat die kern wat op hierdie manier gebou is, afhang van watter soort minimale hoekpuntbedekking ons in die tweeledige grafiek geneem het. Ek wil graag een neem sodat die aantal oorblywende hoekpunte minimaal is. Voorheen kon hulle dit net betyds doen . Ek het in die tyd met 'n implementering van hierdie algoritme vorendag gekom , dus kan na hierdie kern gesoek word in grafieke van honderdduisende hoekpunte by elke vertakkingstadium.
Gevolg
Oefening wys dat my oplossing goed werk op toetse van 'n paar honderd hoekpunte en 'n paar duisend rande. In sulke toetse is dit heel moontlik om te verwag dat 'n oplossing binne 'n halfuur gevind sal word. Die waarskynlikheid om 'n antwoord binne 'n aanvaarbare tyd te vind, neem in beginsel toe as die grafiek baie hoekpunte van hoë graad het, byvoorbeeld graad 10 en hoër.
Om aan die kompetisie deel te neem, moes oplossings gestuur word aan . Te oordeel aan die inligting wat daar aangebied word , my oplossing in oop toetse is derde uit twintig, met 'n groot gaping van tweede. Om heeltemal eerlik te wees, is dit nie heeltemal duidelik hoe oplossings by die kompetisie self geëvalueer sal word nie: my oplossing slaag byvoorbeeld minder toetse as die oplossing in die vierde plek, maar op dié wat slaag, werk dit vinniger.
Die uitslae van geslote toetse sal op XNUMX Julie bekend wees.
Bron: will.com