Forskningsarbejde er måske den mest interessante del af vores uddannelse. Ideen er at prøve dig selv i din valgte retning, mens du stadig er på universitetet. For eksempel går studerende fra områderne Software Engineering og Machine Learning ofte for at forske i virksomheder (hovedsageligt JetBrains eller Yandex, men ikke kun).
I dette indlæg vil jeg fortælle om mit projekt i Datalogi. Som en del af mit arbejde studerede og satte jeg i praksis tilgange til at løse et af de mest berømte NP-hårde problemer: toppunktsdækningsproblem.
I dag udvikles en interessant tilgang til NP-hårde problemer meget hurtigt - parameteriserede algoritmer. Jeg vil forsøge at få dig op til hastighed, fortælle dig nogle enkle parameteriserede algoritmer og beskrive en kraftfuld metode, der hjalp mig meget. Jeg præsenterede mine resultater ved PACE Challenge-konkurrencen: Ifølge resultaterne af åbne tests indtager min løsning tredjepladsen, og de endelige resultater vil blive kendt den 1. juli.
Om Mig
Mit navn er Vasily Alferov, jeg afslutter nu mit tredje år på National Research University Higher School of Economics - St. Petersborg. Jeg har været interesseret i algoritmer siden min skoletid, hvor jeg studerede på Moskva skole nr. 179 og med succes deltog i datalogi-olympiader.
Et begrænset antal specialister i parametriserede algoritmer kommer ind i bjælken...
Eksempel taget fra bogen
Forestil dig, at du er en barsikkerhedsvagt i en lille by. Hver fredag kommer halvdelen af byen til din bar for at slappe af, hvilket giver dig en masse problemer: du skal smide larmende kunder ud af baren for at forhindre slagsmål. Til sidst bliver du træt og beslutter dig for at tage forebyggende foranstaltninger.
Da din by er lille, ved du præcis, hvilke mæcener der sandsynligvis vil kæmpe, hvis de ender i en bar sammen. Har du en liste over n folk, der kommer i baren i aften. Du beslutter dig for at holde nogle byfolk ude af baren, uden at nogen kommer i slagsmål. Samtidig ønsker dine chefer ikke at miste overskud og vil være utilfredse, hvis du ikke lader mere end k mennesker.
Desværre er problemet foran dig et klassisk NP-hårdt problem. Du kender hende måske som , eller som et toppunktsdækningsproblem. For sådanne problemer er der i det generelle tilfælde ingen algoritmer, der virker inden for en acceptabel tid. For at være præcis siger den ubeviste og ret stærke hypotese ETH (Exponential Time Hypothesis), at dette problem ikke kan løses i tide , det vil sige, at du ikke kan komme i tanke om noget mærkbart bedre end en komplet søgning. Lad os f.eks. sige, at nogen kommer til din bar n = 1000 Human. Så vil den komplette søgning være muligheder, der er ca - vildt meget. Heldigvis har din ledelse givet dig en grænse k = 10, så antallet af kombinationer, du skal iterere over, er meget mindre: antallet af delmængder af ti elementer er . Dette er bedre, men det vil stadig ikke blive talt på en dag, selv på en kraftig klynge.
For at eliminere muligheden for et slagsmål i denne konfiguration af anstrengte forhold mellem barens besøgende, skal du holde Bob, Daniel og Fedor ude. Der er ingen løsning, hvor kun to bliver tilbage.
Betyder det, at det er tid til at give efter og lade alle komme ind? Lad os overveje andre muligheder. Nå, for eksempel, kan du ikke kun lukke dem ind, der sandsynligvis vil kæmpe med et meget stort antal mennesker. Hvis nogen kan slås i det mindste med k+1 en anden person, så kan du bestemt ikke lukke ham ind - ellers bliver du nødt til at holde alle ude k+1 byfolk, som han kan kæmpe med, hvilket helt sikkert vil forstyrre ledelsen.
Lad dig smide alle ud, du kunne ifølge dette princip. Så kan alle andre kæmpe med ikke mere end k mennesker. At smide dem ud k mand, du kan ikke forhindre andet end konflikter. Det betyder, at hvis der er mere end Hvis en person er involveret i mindst én konflikt, så kan du bestemt ikke forhindre dem alle. Da du selvfølgelig helt sikkert lukker helt konfliktfrie mennesker ind, skal du gennemgå alle undergrupper af størrelse ti ud af to hundrede mennesker. Der er ca , og dette antal operationer kan allerede sorteres fra på klyngen.
Hvis du roligt kan tage personer, der slet ikke har nogen konflikt, hvad så med dem, der kun deltager i én konflikt? Faktisk kan de også lukkes ind ved at lukke døren for deres modstander. Hvis Alice kun er i konflikt med Bob, så vil vi ikke tabe, hvis vi slipper Alice ud af dem to. Bob kan have andre konflikter, men Alice har dem bestemt ikke. Desuden giver det ingen mening for os ikke at lukke os begge ind. Efter sådanne operationer er der ikke mere tilbage gæster med en uafklaret skæbne: vi har kun konflikter, hver med to deltagere og hver involveret i mindst to. Så der er kun tilbage at ordne muligheder, som sagtens kan betragtes som en halv dag på en bærbar computer.
Faktisk kan du med enkle ræsonnementer opnå endnu mere attraktive betingelser. Bemærk, at vi absolut skal løse alle tvister, det vil sige fra hvert modstridende par, vælg mindst én person, som vi ikke vil lukke ind. Lad os overveje følgende algoritme: tag enhver konflikt, hvorfra vi fjerner en deltager og starter rekursivt fra resten, fjerner derefter den anden og starter også rekursivt. Da vi smider nogen ud ved hvert trin, er rekursionstræet for en sådan algoritme et binært dybdetræ k, så i alt virker algoritmen ind Hvor n er antallet af hjørner, og m - antal ribben. I vores eksempel er det omkring ti millioner, som kan beregnes på et splitsekund ikke kun på en bærbar computer, men endda på en mobiltelefon.
Ovenstående eksempel er et eksempel parametriseret algoritme. Parametriserede algoritmer er algoritmer, der kører i tid f(k) poly(n)Hvor p - polynomium, f er en vilkårlig beregnelig funktion, og k - en eller anden parameter, som muligvis vil være meget mindre end problemets størrelse.
Al ræsonnement før denne algoritme giver et eksempel kernelisering er en af de generelle teknikker til at skabe parameteriserede algoritmer. Kernelisering er reduktionen af problemstørrelsen til en værdi begrænset af en funktion af en parameter. Det resulterende problem kaldes ofte en kerne. Således opnåede vi ved simpelt ræsonnement omkring graderne af hjørner en kvadratisk kerne for Vertex Cover-problemet, parametriseret efter størrelsen af svaret. Der er andre indstillinger, du kan vælge til denne opgave (såsom Vertex Cover Above LP), men det er den indstilling, vi vil diskutere.
Tempo udfordring
Konkurrence (The Parameterized Algorithms and Computational Experiments Challenge) blev født i 2015 for at etablere en sammenhæng mellem parameteriserede algoritmer og tilgange, der anvendes i praksis til at løse beregningsmæssige problemer. De første tre konkurrencer var afsat til at finde træets bredde på en graf (), søger efter et Steiner-træ () og søger efter et sæt hjørner, der skærer cyklusser (). I år var et af de problemer, du kunne prøve dig på, problemet med topdækningsproblemet beskrevet ovenfor.
Konkurrencen vinder popularitet hvert år. Hvis man tror på de foreløbige data, deltog 24 hold i år i konkurrencen om at løse problemet med topdækning alene. Det er værd at bemærke, at konkurrencen ikke varer flere timer eller endda en uge, men flere måneder. Holdene har mulighed for at studere litteraturen, komme med deres egen originale idé og prøve at implementere den. I det væsentlige er denne konkurrence et forskningsprojekt. Ideer til de mest effektive løsninger og præmiering af vinderne vil blive afholdt i forbindelse med konferencen (International Symposium on Parameterized and Exact Computation) som en del af det største årlige algoritmiske møde i Europa . Mere detaljeret information om selve konkurrencen kan findes på , og resultaterne fra tidligere år ligger .
Løsningsdiagram
For at løse problemet med topdækning prøvede jeg at bruge parameteriserede algoritmer. De består typisk af to dele: forenklingsregler (som ideelt set fører til kernelisering) og opdelingsregler. Forenklingsregler er forbehandling af input i polynomiel tid. Formålet med at anvende sådanne regler er at reducere problemet til et tilsvarende mindre problem. Forenklingsregler er den dyreste del af algoritmen, og anvendelse af denne del fører til den samlede køretid i stedet for simpel polynomisk tid. I vores tilfælde er opdelingsreglerne baseret på, at du for hvert toppunkt skal tage enten den eller dens nabo som svar.
Det generelle skema er dette: vi anvender forenklingsreglerne, så vælger vi et toppunkt og laver to rekursive kald: i det første tager vi det som svar, og i det andet tager vi alle dets naboer. Det er det, vi kalder spaltning (forgrening) langs dette toppunkt.
Præcis én tilføjelse vil blive foretaget til denne ordning i næste afsnit.
Idéer til opdeling af (brunching) regler
Lad os diskutere, hvordan man vælger et toppunkt, langs hvilket opdelingen vil ske.
Hovedideen er meget grådig i algoritmisk forstand: lad os tage et toppunkt af maksimal grad og dele langs det. Hvorfor virker det bedre? For i den anden gren af det rekursive kald vil vi fjerne en masse hjørner på denne måde. Du kan regne med, at der er en lille graf tilbage, og vi kan arbejde på det hurtigt.
Denne tilgang, med de allerede diskuterede simple kerneliseringsteknikker, viser sig godt og løser nogle test af flere tusinde hjørner i størrelse. Men det fungerer for eksempel ikke godt til kubiske grafer (det vil sige grafer, hvis grad af hvert toppunkt er tre).
Der er en anden idé baseret på en ret simpel idé: Hvis grafen er afbrudt, kan problemet på dens tilsluttede komponenter løses uafhængigt ved at kombinere svarene i slutningen. Dette er i øvrigt en lille lovet ændring i ordningen, som vil fremskynde løsningen markant: tidligere arbejdede vi i dette tilfælde for tidens produkt til beregning af komponenternes svar, men nu arbejder vi for summen. Og for at fremskynde forgreningen skal du omdanne en forbundet graf til en frakoblet.
Hvordan gør man det? Hvis der er et artikulationspunkt i grafen, skal du kæmpe for det. Et artikulationspunkt er et toppunkt, således at grafen mister sin forbindelse, når den fjernes. Alle samlingspunkter i en graf kan findes ved hjælp af en klassisk algoritme i lineær tid. Denne tilgang fremskynder forgreningen betydeligt.
Når nogen af de valgte hjørner fjernes, opdeles grafen i forbundne komponenter.
Vi vil gøre dette, men vi vil have mere. Se f.eks. efter små knudepunkter i grafen og del langs spidserne fra den. Den mest effektive måde, jeg kender til at finde det mindste globale toppunktssnit, er at bruge et Gomori-Hu-træ, som er bygget i kubisk tid. I PACE Challenge er den typiske grafstørrelse flere tusinde hjørner. I denne situation skal der udføres milliarder af operationer ved hvert hjørne af rekursionstræet. Det viser sig, at det simpelthen er umuligt at løse problemet i den tildelte tid.
Lad os prøve at optimere løsningen. Den minimale toppunktsskæring mellem et par hjørner kan findes af enhver algoritme, der konstruerer et maksimalt flow. Du kan lade det ind på sådan et netværk , i praksis virker det meget hurtigt. Jeg har en formodning om, at det teoretisk er muligt at bevise et estimat for driftstiden , hvilket allerede er ganske acceptabelt.
Jeg forsøgte flere gange at se efter snit mellem par af tilfældige hjørner og tage den mest afbalancerede. Desværre gav dette dårlige resultater i åben PACE Challenge-testning. Jeg sammenlignede det med en algoritme, der opdelte hjørner af maksimal grad, og kører dem med en begrænsning af nedstigningsdybden. En algoritme, der forsøger at finde et snit på denne måde, efterlod større grafer. Dette skyldes det faktum, at nedskæringerne viste sig at være meget ubalancerede: efter at have fjernet 5-10 hjørner, var det muligt at opdele kun 15-20.
Det er værd at bemærke, at artikler om de teoretisk hurtigste algoritmer bruger meget mere avancerede teknikker til at vælge toppunkter til opdeling. Sådanne teknikker har en meget kompleks implementering og ofte dårlig ydeevne med hensyn til tid og hukommelse. Jeg var ikke i stand til at identificere dem, der er helt acceptable for praksis.
Sådan anvender du forenklingsregler
Vi har allerede ideer til kernelisering. Lad mig minde dig om:
- Hvis der er et isoleret toppunkt, skal du slette det.
- Hvis der er et toppunkt på grad 1, skal du fjerne det og tage naboen som svar.
- Hvis der er et toppunkt af grad i det mindste k+1, tage det tilbage.
Med de to første er alt klart, med det tredje er der et trick. Hvis vi i et tegneserieproblem om en bar fik en øvre grænse på k, så skal du i PACE-udfordringen bare finde et topdæksel af minimumsstørrelsen. Dette er en typisk transformation af søgeproblemer til beslutningsproblemer; ofte er der ingen forskel mellem de to typer problemer. I praksis, hvis vi skriver en løser til toppunktsdækningsproblemet, kan der være en forskel. For eksempel som i tredje punkt.
Fra et implementeringssynspunkt er der to måder at gå videre på. Den første tilgang kaldes Iterative Deepening. Det er som følger: vi kan starte med en rimelig begrænsning nedefra på svaret, og derefter køre vores algoritme ved at bruge denne begrænsning som en begrænsning på svaret fra oven, uden at gå lavere i rekursion end denne begrænsning. Hvis vi har fundet et svar, er det garanteret optimalt, ellers kan vi øge denne grænse med én og starte forfra.
En anden tilgang er at gemme nogle aktuelle optimale svar og lede efter et mindre svar, og ændre denne parameter, når den findes k for større afskæring af unødvendige grene i søgningen.
Efter at have udført flere natlige eksperimenter, besluttede jeg mig for en kombination af disse to metoder: For det første kører jeg min algoritme med en form for grænse for søgedybden (vælger den, så det tager ubetydelig tid i forhold til hovedløsningen) og bruger den bedste løsning fundet som en øvre grænse for svaret - altså til det samme k.
Toppunkter af grad 2
Vi har beskæftiget os med toppunkter af grad 0 og 1. Det viser sig, at dette kan gøres med toppunkter af grad 2, men det vil kræve mere komplekse operationer fra grafen.
For at forklare dette skal vi på en eller anden måde udpege hjørnerne. Lad os kalde et toppunkt af grad 2 for et toppunkt v, og dens naboer - hjørner x и y. Dernæst vil vi have to sager.
- Hvornår x и y - naboer. Så kan du svare x и yOg v slette. Ja, fra denne trekant skal der tages mindst to hjørner til gengæld, og vi vil bestemt ikke tabe, hvis vi tager x и y: de har sikkert andre naboer, og v De er her ikke.
- Hvornår x и y - ikke naboer. Derefter oplyses det, at alle tre hjørner kan limes til én. Tanken er, at der i dette tilfælde er et optimalt svar, hvor vi tager enten v, eller begge hjørner x и y. Desuden bliver vi i det første tilfælde nødt til at tage alle naboer som svar x и y, men i den anden er det ikke nødvendigt. Dette svarer nøjagtigt til de tilfælde, hvor vi ikke tager det limede toppunkt som svar, og når vi gør det. Det er kun at bemærke, at i begge tilfælde falder svaret fra en sådan operation med én.
Det er værd at bemærke, at denne tilgang er ret vanskelig at implementere nøjagtigt i rimelig lineær tid. Limning af hjørner er en kompleks operation; du skal kopiere lister over naboer. Hvis dette gøres skødesløst, kan du ende med asymptotisk suboptimal køretid (f.eks. hvis du kopierer mange kanter efter hver limning). Jeg besluttede mig for at finde hele stier fra toppunkter i grad 2 og analysere en masse specielle tilfælde, såsom cyklusser fra sådanne toppunkter eller fra alle sådanne toppunkter undtagen én.
Derudover er det nødvendigt, at denne operation er reversibel, så når vi vender tilbage fra rekursion, genopretter vi grafen til dens oprindelige form. For at sikre dette ryddede jeg ikke kantlisterne for de flettede hjørner, og så vidste jeg bare, hvilke kanter der skulle gå hvor. Denne implementering af grafer kræver også nøjagtighed, men den giver rimelig lineær tid. Og til grafer på flere titusindvis af kanter passer den ind i processorcachen, hvilket giver store fordele i hastighed.
Lineær kerne
Endelig den mest interessante del af kernen.
Til at begynde med skal du huske, at i todelte grafer kan den mindste toppunktsdækning findes ved hjælp af . For at gøre dette skal du bruge algoritmen for at finde den maksimale overensstemmelse der, og brug derefter sætningen .
Ideen med en lineær kerne er denne: først deler vi grafen, det vil sige i stedet for hvert toppunkt v lad os tilføje to toppe и , og i stedet for hver kant u - v lad os tilføje to ribben и . Den resulterende graf vil være todelt. Lad os finde den mindste toppunktsdækning i den. Nogle hjørner af den originale graf kommer dertil to gange, nogle kun én gang og nogle aldrig. Nemhauser-Trotter-sætningen siger, at man i dette tilfælde kan fjerne toppunkter, der ikke ramte en gang, og tage dem tilbage, der ramte to gange. Desuden siger hun, at af de resterende hjørner (dem der rammer én gang) skal du tage mindst halvdelen som svar.
Vi har lige lært at forlade ikke mere end 2k toppe Faktisk, hvis det resterende svar er mindst halvdelen af alle knudepunkter, så er der ikke flere knudepunkter i alt end 2k.
Her kunne jeg tage et lille skridt fremad. Det er klart, at kernen, der er konstrueret på denne måde, afhænger af, hvilken slags minimal toppunktsdækning, vi tog i den todelte graf. Jeg vil gerne tage en, så antallet af resterende hjørner er minimalt. Tidligere var de kun i stand til at gøre dette i tide . Jeg fandt på en implementering af denne algoritme i sin tid , således kan denne kerne søges efter i grafer af hundredtusindvis af hjørner på hvert forgreningstrin.
Outcome
Praksis viser, at min løsning fungerer godt på test af flere hundrede hjørner og flere tusinde kanter. I sådanne test er det meget muligt at forvente, at en løsning vil blive fundet om en halv time. Sandsynligheden for at finde et svar på en acceptabel tid stiger i princippet, hvis grafen har et tilstrækkeligt stort antal hjørner af høj grad, for eksempel grad 10 og højere.
For at deltage i konkurrencen skulle løsninger sendes til . At dømme efter de oplysninger, der præsenteres der , min løsning i åbne test ligger på tredjepladsen ud af tyve, med en stor afstand fra andenpladsen. For at være helt ærlig er det ikke helt klart, hvordan løsninger vil blive evalueret ved selve konkurrencen: For eksempel består min løsning færre test end løsningen på fjerdepladsen, men på dem, der består, virker den hurtigere.
Resultaterne af lukkede tests vil blive kendt den XNUMX. juli.
Kilde: www.habr.com