Onderzoekswerk is misschien wel het meest interessante onderdeel van onze training. Het idee is om jezelf in de door jou gekozen richting te proberen terwijl je nog op de universiteit zit. Studenten uit de vakgebieden Software Engineering en Machine Learning gaan bijvoorbeeld vaak onderzoek doen bij bedrijven (voornamelijk JetBrains of Yandex, maar niet alleen).
In dit bericht zal ik het hebben over mijn project in Computerwetenschappen. Als onderdeel van mijn werk heb ik benaderingen voor het oplossen van een van de beroemdste NP-harde problemen bestudeerd en in de praktijk gebracht: hoekpuntbedekkingsprobleem.
Tegenwoordig ontwikkelt zich zeer snel een interessante benadering van NP-harde problemen: geparametriseerde algoritmen. Ik zal proberen je op de hoogte te brengen, je enkele eenvoudige geparametriseerde algoritmen vertellen en een krachtige methode beschrijven die me veel heeft geholpen. Ik presenteerde mijn resultaten tijdens de PACE Challenge-wedstrijd: volgens de resultaten van open tests staat mijn oplossing op de derde plaats en de definitieve resultaten zullen op 1 juli bekend zijn.
Over mij
Mijn naam is Vasily Alferov, ik rond nu mijn derde jaar af aan de National Research University Higher School of Economics - St. Petersburg. Ik ben geïnteresseerd in algoritmen sinds mijn schooltijd, toen ik studeerde aan de Moskouse school nr. 179 en met succes deelnam aan de computerwetenschappenolympiades.
Een eindig aantal specialisten in geparametriseerde algoritmen betreedt de bar...
Voorbeeld uit het boek
Stel je voor dat je een barbewaker bent in een klein stadje. Elke vrijdag komt de halve stad naar je bar om te ontspannen, wat je veel problemen bezorgt: je moet luidruchtige klanten uit de bar gooien om ruzies te voorkomen. Uiteindelijk word je het beu en besluit je preventieve maatregelen te nemen.
Omdat je stad klein is, weet je precies welke klantenparen waarschijnlijk zullen vechten als ze samen in een bar belanden. Heeft u een lijst van n mensen die vanavond naar de bar komen. Je besluit een aantal stadsmensen uit de bar te houden zonder dat iemand ruzie krijgt. Tegelijkertijd willen uw bazen geen winst verliezen en zullen zij ongelukkig zijn als u niet meer dan k mensen.
Helaas is het probleem dat voor u ligt een klassiek NP-moeilijk probleem. Je kent haar misschien als , of als een hoekpuntoverdekkend probleem. Voor dergelijke problemen zijn er in het algemeen geen algoritmen die binnen een acceptabele tijd werken. Om precies te zijn zegt de onbewezen en vrij sterke hypothese ETH (Exponential Time Hypothesis) dat dit probleem niet op tijd kan worden opgelost. , dat wil zeggen dat u niets merkbaar beters kunt bedenken dan een volledige zoekopdracht. Laten we bijvoorbeeld zeggen dat iemand naar uw bar komt n = 1000 Menselijk. Dan zal de volledige zoekopdracht zijn opties die er ongeveer zijn - gek bedrag. Gelukkig heeft uw management u een limiet gesteld k = 10, dus het aantal combinaties dat je moet herhalen is veel kleiner: het aantal subsets van tien elementen is . Dit is beter, maar het wordt nog steeds niet binnen een dag geteld, zelfs niet op een krachtige cluster.
Om de mogelijkheid van een gevecht uit te sluiten in deze configuratie van gespannen relaties tussen de bezoekers van de bar, moet je Bob, Daniel en Fedor buiten houden. Er is geen oplossing waarbij er slechts twee achterblijven.
Betekent dit dat het tijd is om toe te geven en iedereen binnen te laten? Laten we andere opties overwegen. Nou, je kunt bijvoorbeeld niet alleen degenen binnenlaten die waarschijnlijk met een heel groot aantal mensen zullen vechten. Als iemand er tenminste mee kan vechten k+1 iemand anders, dan kun je hem absoluut niet binnenlaten, anders moet je iedereen buiten houden k+1 stadsmensen, met wie hij kan vechten, wat de leiding zeker van streek zal maken.
Mogen jullie volgens dit principe iedereen eruit gooien die je maar kunt. Dan kan iedereen met niet meer dan vechten k mensen. Ze eruit gooien k man, je kunt niets anders voorkomen dan conflicten. Dit betekent dat als er meer dan Als een persoon betrokken is bij ten minste één conflict, kun je ze zeker niet allemaal voorkomen. Omdat je natuurlijk zeker volledig niet-conflicterende mensen binnenlaat, moet je alle subsets van maat tien van de tweehonderd mensen doorlopen. Er zijn ongeveer , en dit aantal bewerkingen kan al op het cluster worden uitgezocht.
Als je veilig individuen kunt meenemen die helemaal geen conflict hebben, hoe zit het dan met degenen die slechts aan één conflict deelnemen? Sterker nog, ze kunnen ook binnengelaten worden door de deur voor hun tegenstander dicht te doen. Als Alice alleen met Bob in conflict is, zullen we niet verliezen als we Alice uit hen beiden laten: Bob heeft misschien andere conflicten, maar Alice heeft die zeker niet. Bovendien heeft het voor ons geen zin om ons allebei niet binnen te laten. Na zulke operaties blijft er niets meer over gasten met een onopgelost lot: dat hebben we alleen conflicten, elk met twee deelnemers en elk betrokken bij minstens twee. Dus het enige dat overblijft is het uitzoeken opties, die gemakkelijk een halve dag op een laptop kunnen worden overwogen.
Sterker nog, met een simpele redenering kunt u nog aantrekkelijkere voorwaarden realiseren. Houd er rekening mee dat we zeker alle geschillen moeten oplossen, dat wil zeggen dat we uit elk conflicterend paar ten minste één persoon moeten kiezen die we niet binnenlaten. Laten we het volgende algoritme bekijken: neem een willekeurig conflict, waaruit we één deelnemer verwijderen en recursief beginnen met de rest, en vervolgens de andere verwijderen en ook recursief beginnen. Omdat we bij elke stap iemand eruit gooien, is de recursieboom van zo'n algoritme een binaire diepteboom k, dus in totaal werkt het algoritme Waar n is het aantal hoekpunten, en m - aantal ribben. In ons voorbeeld is dit ongeveer tien miljoen, wat in een fractie van een seconde kan worden berekend, niet alleen op een laptop, maar zelfs op een mobiele telefoon.
Bovenstaand voorbeeld is een voorbeeld geparametriseerd algoritme. Geparametriseerde algoritmen zijn algoritmen die in de tijd lopen f(k) poly(n)Waar p - polynoom, f is een willekeurige berekenbare functie, en k - een parameter, die waarschijnlijk veel kleiner zal zijn dan de omvang van het probleem.
Alle redeneringen vóór dit algoritme geven een voorbeeld kernelisatie is een van de algemene technieken voor het maken van geparametriseerde algoritmen. Kernelisatie is het verkleinen van de probleemgrootte tot een waarde die wordt beperkt door een functie van een parameter. Het resulterende probleem wordt vaak een kernel genoemd. Door eenvoudig te redeneren over de graden van hoekpunten hebben we dus een kwadratische kern voor het Vertex Cover-probleem verkregen, geparametriseerd door de grootte van het antwoord. Er zijn andere instellingen die u voor deze taak kunt kiezen (zoals Vertex Cover Above LP), maar dit is de instelling die we zullen bespreken.
Tempo-uitdaging
Wedstrijd (The Parameterized Algorithms and Computational Experiments Challenge) werd in 2015 geboren om een verband te leggen tussen geparametriseerde algoritmen en benaderingen die in de praktijk worden gebruikt om computationele problemen op te lossen. De eerste drie wedstrijden waren gewijd aan het vinden van de boombreedte van een grafiek (), op zoek naar een Steiner-boom () en zoeken naar een reeks hoekpunten die cycli doorsnijden (). Dit jaar was een van de problemen die je kon uitproberen het hierboven beschreven probleem met het bedekken van hoekpunten.
De competitie wint elk jaar aan populariteit. Als je de voorlopige gegevens mag geloven, namen dit jaar 24 teams deel aan de competitie om alleen het probleem met de hoekpunten op te lossen. Het is vermeldenswaard dat de competitie niet enkele uren of zelfs een week duurt, maar meerdere maanden. Teams krijgen de mogelijkheid om de literatuur te bestuderen, met hun eigen originele idee te komen en dit te proberen uit te voeren. In essentie is deze wedstrijd een onderzoeksproject. In samenhang met de conferentie zullen ideeën voor de meest effectieve oplossingen en de toekenning van de winnaars worden gehouden (International Symposium on Parameterized and Exact Computation) als onderdeel van de grootste jaarlijkse algoritmische bijeenkomst in Europa . Meer gedetailleerde informatie over de wedstrijd zelf is te vinden op , en de resultaten van voorgaande jaren liegen .
Oplossing schema
Om het probleem met het bedekken van hoekpunten op te lossen, heb ik geprobeerd geparametriseerde algoritmen te gebruiken. Ze bestaan doorgaans uit twee delen: vereenvoudigingsregels (die idealiter tot kernelisatie leiden) en splitsingsregels. Vereenvoudigingsregels zijn het voorbewerken van de invoer in polynomiale tijd. Het doel van het toepassen van dergelijke regels is om het probleem terug te brengen tot een gelijkwaardig kleiner probleem. Vereenvoudigingsregels vormen het duurste onderdeel van het algoritme en het toepassen van dit onderdeel leidt tot de totale looptijd in plaats van een eenvoudige polynomiale tijd. In ons geval zijn de splitsingsregels gebaseerd op het feit dat je voor elk hoekpunt ofwel het hoekpunt, ofwel het aangrenzende hoekpunt als antwoord moet nemen.
Het algemene schema is als volgt: we passen de vereenvoudigingsregels toe, selecteren vervolgens een hoekpunt en voeren twee recursieve oproepen uit: in de eerste nemen we het als reactie, en in de andere nemen we al zijn buren. Dit noemen we splitsing (vertakking) langs dit hoekpunt.
In de volgende paragraaf wordt precies één aanvulling op dit schema gedaan.
Ideeën voor het splitsen (brunchen) van regels
Laten we bespreken hoe we een hoekpunt kunnen kiezen waarlangs de splitsing zal plaatsvinden.
Het hoofdidee is erg hebzuchtig in algoritmische zin: laten we een hoekpunt van maximale graad nemen en daarlangs splitsen. Waarom lijkt het beter? Omdat we in de tweede tak van de recursieve aanroep op deze manier veel hoekpunten zullen verwijderen. U kunt erop rekenen dat er nog een kleine grafiek overblijft en wij kunnen er snel aan werken.
Deze aanpak, met de reeds besproken eenvoudige kernelisatietechnieken, laat zich goed zien en lost enkele tests van enkele duizenden hoekpunten op. Maar het werkt bijvoorbeeld niet goed voor kubieke grafieken (dat wil zeggen grafieken waarvan de graad van elk hoekpunt drie is).
Er is nog een ander idee gebaseerd op een vrij eenvoudig idee: als de grafiek wordt losgekoppeld, kan het probleem met de verbonden componenten onafhankelijk worden opgelost, waarbij de antwoorden aan het einde worden gecombineerd. Dit is trouwens een kleine beloofde wijziging in het schema, die de oplossing aanzienlijk zal versnellen: voorheen werkten we in dit geval voor het product van de tijd voor het berekenen van de antwoorden van de componenten, maar nu werken we voor de som. En om de vertakking te versnellen, moet je een verbonden grafiek in een niet-verbonden grafiek veranderen.
Hoe je dat doet? Als er een articulatiepunt in de grafiek is, moet je daartegen vechten. Een articulatiepunt is een zodanig hoekpunt dat de grafiek zijn connectiviteit verliest wanneer hij wordt verwijderd. Alle knooppunten in een grafiek kunnen worden gevonden met behulp van een klassiek algoritme in lineaire tijd. Deze aanpak versnelt de vertakking aanzienlijk.
Wanneer een van de geselecteerde hoekpunten wordt verwijderd, wordt de grafiek opgesplitst in verbonden componenten.
Dat gaan we doen, maar we willen meer. Zoek bijvoorbeeld naar kleine hoekpunten in de grafiek en splits deze langs de hoekpunten. De meest efficiënte manier die ik ken om de minimale mondiale hoekpuntsnede te vinden, is door een Gomori-Hu-boom te gebruiken, die in kubieke tijd is gebouwd. In de PACE Challenge is de typische grafiekgrootte enkele duizenden hoekpunten. In deze situatie moeten miljarden bewerkingen worden uitgevoerd op elk hoekpunt van de recursieboom. Het blijkt dat het simpelweg onmogelijk is om het probleem binnen de toegewezen tijd op te lossen.
Laten we proberen de oplossing te optimaliseren. De minimale hoekpuntsnede tussen een paar hoekpunten kan worden gevonden door elk algoritme dat een maximale stroom construeert. Je kunt het op zo'n netwerk laten In de praktijk werkt het heel snel. Ik heb het vermoeden dat het theoretisch mogelijk is om een schatting van de bedrijfstijd te bewijzen , wat al heel acceptabel is.
Ik heb verschillende keren geprobeerd te zoeken naar sneden tussen paren willekeurige hoekpunten en de meest gebalanceerde hoekpunt te nemen. Helaas leverde dit slechte resultaten op bij open PACE Challenge-testen. Ik vergeleek het met een algoritme dat hoekpunten van maximale graad splitste en ze uitvoerde met een beperking van de afdalingsdiepte. Een algoritme dat op deze manier een snede probeerde te vinden, liet grotere grafieken achter. Dit komt door het feit dat de bezuinigingen erg onevenwichtig bleken te zijn: nadat 5-10 hoekpunten waren verwijderd, was het mogelijk om slechts 15-20 af te splitsen.
Het is vermeldenswaard dat artikelen over de theoretisch snelste algoritmen veel geavanceerdere technieken gebruiken voor het selecteren van hoekpunten voor splitsing. Dergelijke technieken hebben een zeer complexe implementatie en vaak slechte prestaties in termen van tijd en geheugen. Ik kon er geen identificeren die heel acceptabel zijn voor de praktijk.
Hoe u vereenvoudigingsregels toepast
We hebben al ideeën voor kernelisatie. Laat me je herinneren:
- Als er een geïsoleerd hoekpunt is, verwijdert u dit.
- Als er een hoekpunt van graad 1 is, verwijder het dan en neem als reactie het buurpunt.
- Als er tenminste een hoekpunt van graad is k+1, Neem het terug.
Bij de eerste twee is alles duidelijk, bij de derde is er één truc. Als we bij een komisch probleem over een reep een bovengrens kregen van k, dan hoef je in de PACE Challenge alleen maar een hoekpuntdekking van de minimale grootte te vinden. Dit is een typische transformatie van zoekproblemen in beslissingsproblemen; vaak is er geen verschil tussen de twee soorten problemen. Als we in de praktijk een oplosser schrijven voor het probleem dat de hoekpunten bedekt, kan er een verschil zijn. Bijvoorbeeld zoals in het derde punt.
Vanuit implementatieoogpunt zijn er twee manieren om verder te gaan. De eerste benadering heet Iteratieve verdieping. Het gaat als volgt: we kunnen beginnen met een redelijke beperking van onderaf op het antwoord, en vervolgens ons algoritme uitvoeren met deze beperking als beperking op het antwoord van bovenaf, zonder lager te gaan in recursie dan deze beperking. Als we een antwoord hebben gevonden, is het gegarandeerd optimaal, anders kunnen we deze limiet met één verhogen en opnieuw beginnen.
Een andere benadering is om een huidig optimaal antwoord op te slaan en naar een kleiner antwoord te zoeken, waarbij deze parameter wordt gewijzigd wanneer dit wordt gevonden k voor het beter afsnijden van onnodige takken tijdens het zoeken.
Na verschillende nachtelijke experimenten te hebben uitgevoerd, kwam ik tot een combinatie van deze twee methoden: eerst voer ik mijn algoritme uit met een soort limiet op de zoekdiepte (selecteer het zo dat het verwaarloosbare tijd kost in vergelijking met de hoofdoplossing) en gebruik de beste oplossing gevonden als bovengrens voor het antwoord – dat wil zeggen: voor hetzelfde k.
Hoekpunten van graad 2
We hebben hoekpunten van graad 0 en 1 behandeld. Het blijkt dat dit kan worden gedaan met hoekpunten van graad 2, maar hiervoor zijn complexere bewerkingen uit de grafiek vereist.
Om dit uit te leggen, moeten we op de een of andere manier de hoekpunten aanduiden. Laten we een hoekpunt van graad 2 een hoekpunt noemen v, en zijn buren - hoekpunten x и y. Vervolgens hebben we twee gevallen.
- Wanneer x и y - buren. Dan kun je antwoorden x и yEn v verwijderen. Uit deze driehoek moeten in ruil daarvoor minstens twee hoekpunten worden genomen, en we zullen zeker niet verliezen als we x и y: ze hebben waarschijnlijk andere buren, en v Ze zijn niet hier.
- Wanneer x и y - geen buren. Vervolgens wordt vermeld dat alle drie de hoekpunten in één kunnen worden gelijmd. Het idee is dat er in dit geval een optimaal antwoord is, waarbij we een van beide nemen v, of beide hoekpunten x и y. Bovendien zullen we in het eerste geval alle buren als reactie moeten nemen x и y, maar in de tweede is het niet nodig. Dit komt precies overeen met de gevallen waarin we het gelijmde hoekpunt niet als reactie nemen en wanneer we dat wel doen. Het blijft alleen om op te merken dat in beide gevallen de respons van een dergelijke operatie met één afneemt.
Het is vermeldenswaard dat deze aanpak vrij moeilijk is om nauwkeurig te implementeren in een redelijk lineaire tijd. Het lijmen van hoekpunten is een complexe operatie; je moet lijsten met buren kopiëren. Als u dit onzorgvuldig doet, kunt u een asymptotisch suboptimale looptijd krijgen (bijvoorbeeld als u na elke verlijming veel randen kopieert). Ik besloot hele paden te vinden vanaf hoekpunten van graad 2 en een aantal speciale gevallen te analyseren, zoals cycli vanaf dergelijke hoekpunten of vanaf al deze hoekpunten behalve één.
Bovendien is het noodzakelijk dat deze bewerking omkeerbaar is, zodat we bij terugkeer uit recursie de grafiek naar zijn oorspronkelijke vorm herstellen. Om dit te garanderen, heb ik de randenlijsten van de samengevoegde hoekpunten niet gewist, en toen wist ik gewoon welke randen waar naartoe moesten. Deze implementatie van grafieken vereist ook nauwkeurigheid, maar biedt een redelijke lineaire tijd. En voor grafieken met enkele tienduizenden randen past het in de processorcache, wat grote snelheidsvoordelen oplevert.
Lineaire kern
Eindelijk het meest interessante deel van de kernel.
Bedenk om te beginnen dat in bipartiete grafieken de minimale hoekpuntdekking kan worden gevonden met behulp van . Om dit te doen, moet je het algoritme gebruiken om daar de maximale matching te vinden, en gebruik dan de stelling .
Het idee van een lineaire kernel is dit: eerst splitsen we de grafiek, dat wil zeggen, in plaats van elk hoekpunt v laten we twee pieken toevoegen и , en in plaats van elke rand u - v laten we twee ribben toevoegen и . De resulterende grafiek zal bipartiet zijn. Laten we de minimale hoekpuntdekking daarin vinden. Sommige hoekpunten van de originele grafiek komen daar twee keer terecht, andere slechts één keer en andere nooit. De stelling van Nemhauser-Trotter stelt dat je in dit geval hoekpunten kunt verwijderen die niet eens één keer zijn geraakt, en de hoekpunten die twee keer zijn geraakt, terug kunt nemen. Bovendien zegt ze dat je van de resterende hoekpunten (die één keer geraakt zijn) minstens de helft als antwoord moet nemen.
We hebben net geleerd om niet meer te vertrekken dan 2k pieken Als het resterende antwoord tenminste de helft van alle hoekpunten bedraagt, zijn er in totaal niet meer hoekpunten dan 2k.
Hier kon ik een kleine stap vooruit zetten. Het is duidelijk dat de op deze manier geconstrueerde kern afhangt van het soort minimale hoekpuntbedekking dat we in de bipartiete grafiek hebben genomen. Ik zou er graag een willen nemen zodat het aantal resterende hoekpunten minimaal is. Voorheen konden ze dit alleen op tijd doen . Ik heb destijds een implementatie van dit algoritme bedacht Deze kern kan dus worden gezocht in grafieken van honderdduizenden hoekpunten in elke vertakkingsfase.
Resultaat
De praktijk leert dat mijn oplossing goed werkt bij tests van enkele honderden hoekpunten en enkele duizenden randen. Bij dergelijke tests is het goed mogelijk om te verwachten dat er binnen een half uur een oplossing wordt gevonden. De kans om binnen een acceptabele tijd een antwoord te vinden, neemt in principe toe als de grafiek een voldoende groot aantal hoekpunten van hoge graad heeft, bijvoorbeeld graad 10 en hoger.
Om aan de wedstrijd deel te nemen, moesten er oplossingen naar worden gestuurd . Afgaande op de informatie die daar wordt gepresenteerd , mijn oplossing in open tests staat op de derde plaats van de twintig, met een groot verschil met de tweede plaats. Om heel eerlijk te zijn is het niet helemaal duidelijk hoe oplossingen zullen worden beoordeeld tijdens de wedstrijd zelf: mijn oplossing doorstaat bijvoorbeeld minder tests dan de oplossing op de vierde plaats, maar bij de oplossingen die wel slagen, werkt het sneller.
De uitslag van gesloten toetsen is op XNUMX juli bekend.
Bron: www.habr.com