Forskningsarbeid er kanskje den mest interessante delen av opplæringen vår. Tanken er å prøve deg selv i din valgte retning mens du fortsatt er på universitetet. For eksempel går studenter fra områdene Software Engineering og Machine Learning ofte for å forske i selskaper (hovedsakelig JetBrains eller Yandex, men ikke bare).
I dette innlegget skal jeg snakke om prosjektet mitt i informatikk. Som en del av arbeidet mitt studerte og implementerte jeg tilnærminger for å løse et av de mest kjente NP-harde problemene: problem med toppunktdekning.
I dag utvikler en interessant tilnærming til NP-harde problemer seg veldig raskt - parameteriserte algoritmer. Jeg vil prøve å få deg oppdatert, fortelle deg noen enkle parameteriserte algoritmer og beskrive en kraftig metode som hjalp meg mye. Jeg presenterte resultatene mine i PACE Challenge-konkurransen: i henhold til resultatene fra åpne tester tar løsningen min tredjeplass, og de endelige resultatene vil bli kjent 1. juli.
Om meg
Mitt navn er Vasily Alferov, jeg fullfører nå mitt tredje år ved National Research University Higher School of Economics - St. Petersburg. Jeg har vært interessert i algoritmer siden skoledagene mine, da jeg studerte ved Moskva skole nr. 179 og deltok med hell i informatikk-olympiadene.
Et begrenset antall spesialister innen parameteriserte algoritmer kommer inn i linjen...
Eksempel hentet fra boken
Tenk deg at du er en barsikkerhetsvakt i en liten by. Hver fredag kommer halve byen til baren din for å slappe av, noe som gir deg mye trøbbel: du må kaste bøllete kunder ut av baren for å forhindre slagsmål. Til slutt blir du lei og bestemmer deg for å ta forebyggende tiltak.
Siden byen din er liten, vet du nøyaktig hvilke gjestepar som sannsynligvis vil slåss hvis de havner i en bar sammen. Har du en liste over n folk som kommer til baren i kveld. Du bestemmer deg for å holde noen byfolk ute av baren uten at noen havner i en kamp. Samtidig ønsker ikke sjefene dine å tape fortjeneste og vil være misfornøyde hvis du ikke lar mer enn k C ‡ RμR "RѕRІRμRє.
Dessverre er problemet foran deg et klassisk NP-hardt problem. Du kjenner henne kanskje som , eller som et toppunktdekkeproblem. For slike problemer, i det generelle tilfellet, er det ingen algoritmer som fungerer på en akseptabel tid. For å være presis sier den uprøvde og ganske sterke hypotesen ETH (Exponential Time Hypothesis) at dette problemet ikke kan løses i tide , det vil si at du ikke kan tenke på noe merkbart bedre enn et fullstendig søk. La oss for eksempel si at noen kommer til baren din n = 1000 Menneskelig. Da vil hele søket være alternativer som det er omtrentlig - vanvittig mye. Heldigvis har ledelsen gitt deg en grense k = 10, så antallet kombinasjoner du trenger å iterere over er mye mindre: antall undersett av ti elementer er . Dette er bedre, men det vil fortsatt ikke telles på en dag selv på en kraftig klynge.
For å eliminere muligheten for kamp i denne konfigurasjonen av anstrengte forhold mellom barens besøkende, må du holde Bob, Daniel og Fedor ute. Det er ingen løsning der bare to blir stående igjen.
Betyr dette at det er på tide å gi etter og slippe alle inn? La oss vurdere andre alternativer. Vel, for eksempel, du kan ikke bare slippe inn de som sannsynligvis vil slåss med et veldig stort antall mennesker. Hvis noen kan slåss i det minste med k+1 en annen person, så kan du definitivt ikke slippe ham inn - ellers må du holde alle ute k+1 byfolk, som han kan kjempe med, noe som definitivt vil opprøre ledelsen.
La deg kaste ut alle du kunne i henhold til dette prinsippet. Da kan alle andre kjempe med ikke mer enn k mennesker. Kaster dem ut k mann, du kan ikke forhindre noe mer enn konflikter. Dette betyr at hvis det er mer enn Hvis en person er involvert i minst én konflikt, kan du absolutt ikke forhindre dem alle. Siden du selvfølgelig vil slippe inn fullstendig ikke-konfliktpersoner, må du gå gjennom alle undergrupper av størrelse ti av to hundre personer. Det er ca , og dette antallet operasjoner kan allerede sorteres ut på klyngen.
Hvis du trygt kan ta personer som ikke har noen konflikt i det hele tatt, hva med de som bare deltar i én konflikt? De kan faktisk også slippes inn ved å lukke døren for motstanderen. Faktisk, hvis Alice bare er i konflikt med Bob, så hvis vi slipper Alice ut av de to, vil vi ikke tape: Bob kan ha andre konflikter, men Alice har dem absolutt ikke. Dessuten gir det ingen mening for oss å ikke slippe oss inn begge to. Etter slike operasjoner gjenstår det ikke mer gjester med en uavklart skjebne: vi har bare konflikter, hver med to deltakere og hver involvert i minst to. Så det gjenstår bare å sortere alternativer, som lett kan betraktes som en halv dag på en bærbar datamaskin.
Faktisk kan du med enkle resonnement oppnå enda mer attraktive forhold. Merk at vi definitivt må løse alle tvister, det vil si at fra hvert motstridende par, velg minst én person som vi ikke slipper inn. La oss vurdere følgende algoritme: ta enhver konflikt, hvorfra vi fjerner en deltaker og starter rekursivt fra resten, fjerner deretter den andre og starter også rekursivt. Siden vi kaster noen ut ved hvert trinn, er rekursjonstreet til en slik algoritme et binært dybdetre k, så totalt fungerer algoritmen inn Der n er antall toppunkter, og m - antall ribber. I vårt eksempel er dette rundt ti millioner, som kan beregnes på et brøkdel av et sekund ikke bare på en bærbar PC, men til og med på en mobiltelefon.
Eksempelet ovenfor er et eksempel parameterisert algoritme. Parameteriserte algoritmer er algoritmer som kjører i tid f(k) poly(n)Der p - polynom, f er en vilkårlig beregningsbar funksjon, og k - noen parameter, som ganske mulig vil være mye mindre enn størrelsen på problemet.
Alle resonnementer før denne algoritmen gir et eksempel kernelisering er en av de generelle teknikkene for å lage parameteriserte algoritmer. Kernelisering er reduksjonen av problemstørrelsen til en verdi begrenset av en funksjon av en parameter. Det resulterende problemet kalles ofte en kjerne. Ved enkle resonnementer om toppene av toppunktene fikk vi altså en kvadratisk kjerne for Vertex Cover-problemet, parameterisert av størrelsen på svaret. Det er andre innstillinger du kan velge for denne oppgaven (som Vertex Cover Above LP), men dette er innstillingen vi skal diskutere.
Pace Challenge
Konkurranse (The Parameterized Algorithms and Computational Experiments Challenge) ble født i 2015 for å etablere en sammenheng mellom parameteriserte algoritmer og tilnærminger som brukes i praksis for å løse beregningsproblemer. De tre første konkurransene ble viet til å finne trebredden til en graf (), søker etter et Steiner-tre () og søker etter et sett med toppunkter som kutter sykluser (). I år var et av problemene du kunne prøve deg på problemet med toppunktdekning beskrevet ovenfor.
Konkurransen øker i popularitet hvert år. Hvis du skal tro de foreløpige dataene, deltok i år 24 lag i konkurransen om å løse toppunktdekningsproblemet alene. Det er verdt å merke seg at konkurransen ikke varer i flere timer eller til og med en uke, men flere måneder. Lagene har mulighet til å studere litteraturen, komme opp med sin egen originale idé og prøve å implementere den. I hovedsak er denne konkurransen et forskningsprosjekt. Ideer til de mest effektive løsningene og premiering av vinnerne vil bli holdt i forbindelse med konferansen (International Symposium on Parameterized and Exact Computation) som en del av det største årlige algoritmemøtet i Europa . Mer detaljert informasjon om selve konkurransen finner du på , og resultatene fra tidligere år lyver .
Løsningsdiagram
For å løse toppunktdekningsproblemet prøvde jeg å bruke parameteriserte algoritmer. De består vanligvis av to deler: forenklingsregler (som ideelt sett fører til kernelisering) og splittingsregler. Forenklingsregler er forbehandling av inndata i polynomtid. Hensikten med å anvende slike regler er å redusere problemet til et tilsvarende mindre problem. Forenklingsregler er den dyreste delen av algoritmen, og bruk av denne delen fører til total driftstid i stedet for enkel polynomtid. I vårt tilfelle er delingsreglene basert på det faktum at for hvert toppunkt må du ta enten det eller naboen som et svar.
Det generelle opplegget er dette: vi bruker forenklingsreglene, så velger vi noen toppunkt og gjør to rekursive anrop: i det første tar vi det som svar, og i det andre tar vi alle naboene. Dette er det vi kaller splitting (forgrening) langs dette toppunktet.
Nøyaktig ett tillegg vil bli gitt til denne ordningen i neste avsnitt.
Ideer for å dele (brunching) regler
La oss diskutere hvordan du velger et toppunkt som splittingen vil skje langs.
Hovedideen er veldig grådig i algoritmisk forstand: la oss ta et toppunkt av maksimal grad og dele langs det. Hvorfor virker det bedre? For i den andre grenen av det rekursive kallet vil vi fjerne mange hjørner på denne måten. Du kan regne med at en liten graf gjenstår, og vi kan jobbe med den raskt.
Denne tilnærmingen, med de allerede diskuterte enkle kjerneiseringsteknikkene, viser seg godt og løser noen tester med flere tusen hjørner i størrelse. Men det fungerer for eksempel ikke bra for kubiske grafer (det vil si grafer hvis grad av hvert toppunkt er tre).
Det er en annen idé basert på en ganske enkel idé: hvis grafen er frakoblet, kan problemet på de tilkoblede komponentene løses uavhengig, ved å kombinere svarene på slutten. Dette er forresten en liten lovet modifikasjon i ordningen, som vil fremskynde løsningen betydelig: tidligere, i dette tilfellet, jobbet vi for tidenes produkt for å beregne responsene til komponentene, men nå jobber vi for summen. Og for å få fart på forgreningen, må du gjøre en tilkoblet graf til en frakoblet.
Hvordan gjøre det? Hvis det er et artikulasjonspunkt i grafen, må du kjempe mot det. Et artikulasjonspunkt er et toppunkt slik at grafen mister tilkoblingen når den fjernes. Alle koblingspunkter i en graf kan bli funnet ved hjelp av en klassisk algoritme i lineær tid. Denne tilnærmingen øker forgreningen betydelig.
Når noen av de valgte toppunktene fjernes, vil grafen deles opp i tilkoblede komponenter.
Vi skal gjøre dette, men vi vil ha mer. Se for eksempel etter små toppunktkutt i grafen og del langs toppunktene fra den. Den mest effektive måten jeg vet for å finne minimum globale toppunktkuttet er å bruke et Gomori-Hu-tre, som er bygget i kubikktid. I PACE-utfordringen er den typiske grafstørrelsen flere tusen hjørner. I denne situasjonen må milliarder av operasjoner utføres ved hvert toppunkt av rekursjonstreet. Det viser seg at det rett og slett er umulig å løse problemet i den tildelte tiden.
La oss prøve å optimalisere løsningen. Minimum toppunktkuttet mellom et par toppunkter kan finnes av enhver algoritme som konstruerer en maksimal flyt. Du kan slippe den inn på et slikt nettverk , i praksis fungerer det veldig raskt. Jeg har en mistanke om at det er teoretisk mulig å bevise et estimat for driftstiden , som allerede er ganske akseptabelt.
Jeg prøvde flere ganger å se etter kutt mellom par av tilfeldige hjørner og ta den mest balanserte. Dessverre ga dette dårlige resultater i åpen PACE Challenge-testing. Jeg sammenlignet det med en algoritme som delte hjørner av maksimal grad, og kjører dem med en begrensning på dybden av nedstigningen. En algoritme som prøver å finne et kutt på denne måten etterlot seg større grafer. Dette skyldes det faktum at kuttene viste seg å være veldig ubalanserte: etter å ha fjernet 5-10 hjørner, var det mulig å dele av bare 15-20.
Det er verdt å merke seg at artikler om de teoretisk raskeste algoritmene bruker mye mer avanserte teknikker for å velge toppunkter for splitting. Slike teknikker har svært kompleks implementering og ofte dårlig ytelse når det gjelder tid og minne. Jeg klarte ikke å identifisere de som er ganske akseptable for praksis.
Slik bruker du forenklingsregler
Vi har allerede ideer for kernelisering. La meg minne deg på:
- Hvis det er et isolert toppunkt, slett det.
- Hvis det er et toppunkt på grad 1, fjern det og ta naboen som svar.
- Hvis det er et toppunkt av grad i det minste k+1, ta det tilbake.
Med de to første er alt klart, med det tredje er det ett triks. Hvis i et tegneserieproblem om en bar vi fikk en øvre grense på k, så i PACE-utfordringen trenger du bare å finne et toppunktdeksel av minimumsstørrelsen. Dette er en typisk transformasjon av søkeproblemer til beslutningsproblemer; ofte er det ingen forskjell mellom de to typene problemer. I praksis, hvis vi skriver en løser for toppunktdekningsproblemet, kan det være en forskjell. For eksempel som i det tredje punktet.
Fra et implementeringssynspunkt er det to måter å gå frem på. Den første tilnærmingen kalles Iterative Deepening. Det er som følger: vi kan starte med en rimelig begrensning nedenfra på svaret, og deretter kjøre algoritmen vår ved å bruke denne begrensningen som en begrensning på svaret ovenfra, uten å gå lavere i rekursjon enn denne begrensningen. Hvis vi har funnet noe svar, er det garantert optimalt, ellers kan vi øke denne grensen med én og begynne på nytt.
En annen tilnærming er å lagre et nåværende optimalt svar og se etter et mindre svar, og endre denne parameteren når den er funnet k for større avskjæring av unødvendige greiner i søket.
Etter å ha utført flere nattlige eksperimenter bestemte jeg meg for en kombinasjon av disse to metodene: først kjører jeg algoritmen min med en slags grense for søkedybden (velger den slik at det tar ubetydelig tid sammenlignet med hovedløsningen) og bruker den beste løsning funnet som en øvre grense for svaret - altså til det samme k.
Toppunkt av grad 2
Vi har behandlet hjørner av grad 0 og 1. Det viser seg at dette kan gjøres med toppunkter på grad 2, men dette vil kreve mer komplekse operasjoner fra grafen.
For å forklare dette, må vi på en eller annen måte utpeke toppunktene. La oss kalle et toppunkt av grad 2 for et toppunkt v, og dens naboer - hjørner x и y. Deretter vil vi ha to saker.
- Når x и y - naboer. Da kan du svare x и yOg v slette. Faktisk, fra denne trekanten må minst to hjørner tas i retur, og vi vil definitivt ikke tape hvis vi tar x и y: de har sikkert andre naboer, og v De er ikke her.
- Når x и y - ikke naboer. Da står det at alle tre toppunktene kan limes til ett. Tanken er at i dette tilfellet er det et optimalt svar, der vi tar enten v, eller begge toppunktene x и y. Dessuten, i det første tilfellet må vi ta alle naboer som svar x и y, men i den andre er det ikke nødvendig. Dette tilsvarer nøyaktig tilfellene når vi ikke tar det limte toppunktet som svar og når vi gjør det. Det gjenstår bare å merke seg at i begge tilfeller reduseres responsen fra en slik operasjon med én.
Det er verdt å merke seg at denne tilnærmingen er ganske vanskelig å implementere nøyaktig på rettferdig lineær tid. Liming av hjørner er en kompleks operasjon; du må kopiere lister over naboer. Hvis dette gjøres uforsiktig, kan du ende opp med asymptotisk suboptimal kjøretid (for eksempel hvis du kopierer mange kanter etter hver liming). Jeg bestemte meg for å finne hele stier fra toppunkter av grad 2 og analysere en haug med spesielle tilfeller, for eksempel sykluser fra slike toppunkter eller fra alle slike toppunkter unntatt ett.
I tillegg er det nødvendig at denne operasjonen er reversibel, slik at når vi kommer tilbake fra rekursjon, gjenoppretter vi grafen til sin opprinnelige form. For å sikre dette ryddet jeg ikke kantlistene for de sammenslåtte toppunktene, og da visste jeg bare hvilke kanter som måtte gå hvor. Denne implementeringen av grafer krever også nøyaktighet, men den gir rimelig lineær tid. Og for grafer på flere titusenvis av kanter passer den inn i prosessorcachen, noe som gir store fordeler i hastighet.
Lineær kjerne
Til slutt, den mest interessante delen av kjernen.
Til å begynne med, husk at i todelte grafer kan minimum toppunktdekning finnes ved å bruke . For å gjøre dette må du bruke algoritmen for å finne maksimal matching der, og bruk deretter teoremet .
Ideen med en lineær kjerne er denne: først deler vi grafen, det vil si i stedet for hvert toppunkt v la oss legge til to topper и , og i stedet for hver kant u - v la oss legge til to ribber и . Den resulterende grafen vil være todelt. La oss finne minimum toppunktdekning i den. Noen hjørner av den originale grafen vil komme dit to ganger, noen bare én gang og noen aldri. Nemhauser-Trotter-teoremet sier at man i dette tilfellet kan fjerne toppunkter som ikke traff en gang og ta tilbake de som traff to ganger. Dessuten sier hun at av de gjenværende hjørnene (de som treffer en gang) må du ta minst halvparten som svar.
Vi har nettopp lært å forlate ikke mer enn 2k topper Faktisk, hvis resten av svaret er minst halvparten av alle hjørner, er det ikke flere hjørner totalt enn 2k.
Her kunne jeg ta et lite steg videre. Det er klart at kjernen som er konstruert på denne måten, avhenger av hva slags minimalt toppunktdekke vi tok i todelt graf. Jeg vil gjerne ta en slik at antall gjenværende hjørner er minimalt. Tidligere klarte de dette bare i tide . Jeg kom opp med en implementering av denne algoritmen i tiden , dermed kan denne kjernen søkes etter i grafer av hundretusenvis av hjørner på hvert forgreningsstadium.
Resultat
Praksis viser at min løsning fungerer bra på tester av flere hundre hjørner og flere tusen kanter. I slike tester er det fullt mulig å forvente at en løsning vil bli funnet om en halvtime. Sannsynligheten for å finne et svar på en akseptabel tid øker i prinsippet hvis grafen har et tilstrekkelig stort antall hjørner av høy grad, for eksempel grad 10 og høyere.
For å delta i konkurransen måtte løsninger sendes til . Etter informasjonen som presenteres der å dømme , min løsning i åpne tester ligger på tredjeplass av tjue, med et stort gap fra andre. For å være helt ærlig er det ikke helt klart hvordan løsninger vil bli vurdert på selve konkurransen: For eksempel består løsningen min færre tester enn løsningen på fjerdeplass, men på de som består fungerer den raskere.
Resultatene av lukkede tester vil bli kjent XNUMX. juli.
Kilde: www.habr.com