Hur man löser NP-svåra problem med hjälp av parameteriserade algoritmer

Forskning är förmodligen den mest intressanta delen av vår utbildning. Idén är att redan på universitetet pröva sig inom det valda området. Till exempel går studenter från programmen Software Engineering och Machine Learning ofta för att göra forskningsprojekt på företag (främst JetBrains eller Yandex, men inte bara).

I det här inlägget ska jag berätta om mitt projekt inom Computer Science. Inom ramen för arbetet har jag studerat och implementerat metoder för att lösa ett av de mest kända NP-svåra problemen: vertex-cover problemet.

Just nu utvecklas en intressant metod för NP-svåra problem - parametriserade algoritmer. Jag ska försöka ge er en inblick, berätta om några enkla parametriserade algoritmer och beskriva en kraftfull metod som har hjälpt mig mycket. Jag presenterade mina resultat på tävlingen PACE Challenge: efter de öppna testerna ligger min lösning på tredje plats, medan de slutgiltiga resultaten kommer att bli kända den 1 juli.

Om mig

Jag heter Vasily Alfjorov, och jag avslutar just nu mitt tredje år på HSE - Sankt Petersburg. Jag har varit intresserad av algoritmer ända sedan gymnasiet, när jag gick i Moskvas skola 179 och deltog framgångsrikt i informatikolympiader.

Ett ändligt antal specialister inom parametriserade algoritmer går in i en bar...

Exemplet är från boken «Parameterized algorithms»

Tänk dig att du är vakten på en bar i en liten stad. Varje fredag kväll kommer hälften av staden till din bar för att koppla av, vilket ger dig en hel del besvär: du måste kasta ut de stökiga besökarna för att förhindra slagsmål. Till slut blir det tråkigt och du beslutar dig för att ta förebyggande åtgärder.

Eftersom staden är liten vet du precis vilka par besökare som troligtvis kommer att bråka om de hamnar i baren tillsammans. Du har en lista med n människor som kommer till baren ikväll. Du beslutar dig för att inte släppa in några invånare på ett sätt så att ingen bråkar. Samtidigt vill din chef inte förlora intäkter och kommer att bli missnöjd om du inte släpper in fler än vågvektor människor.

Tyvärr är problemet du står inför ett klassiskt NP-svårt problem. Du kanske känner det som vertex cover, eller hur man löser ett uppdrag om toppbeläggning. För sådana problem är det generellt sett oklart om det finns algoritmer som fungerar på rimlig tid. För att vara exakt, så indikerar den icke-bevisade och ganska starka hypotesen ETH (Exponential Time Hypothesis) att detta problem inte kan lösas inom tiden , vilket innebär att det inte finns något bättre än att pröva alla alternativ. Till exempel, om det kommer att komma n = 1000 personer till din bar. Då kommer ett komplett test att innebära alternativ, vilket är ungefär — ofattbart mycket. Som tur är, har din ledning satt en begränsning på k = 10, så antalet kombinationer som du behöver utvärdera är mycket mindre: antalet delmängder av tio element är lika med . Detta är redan bättre, men det är fortfarande för många för att räkna på en dag även med en kraftfull kluster.

För att utesluta risken för bråk under sådan konfiguration av relationer mellan barbesökarna måste man inte släppa in Bob, Daniel och Fyodor. Lösningar där endast två blir kvar ute finns inte.

Betyder detta att det är dags att ge upp och släppa in alla? Låt oss överväga andra alternativ. Till exempel, man kan bara neka inträde till dem som troligtvis kommer bråka med ett stort antal människor. Om någon kan bråka med minst k + 1 andra människor, så kan han definitivt inte släppas in — annars måste alla k + 1 medborgare, som han kan bråka med, nekas inträde, vilket definitivt kommer att missnöja ledningen.

Anta att du har tagit bort alla som du kan enligt detta princip. Så alla andra kan bråka med högst vågvektor människor. Genom att ta bort vågvektor personer, kan du förhindra högst konflikter. Så om mer än personer är involverade i åtminstone en konflikt, kan du definitivt inte förhindra dem alla. Eftersom det uppenbarligen finns helt konfliktsfria människor som du kommer att släppa in, behöver du utvärdera alla delmängder som består av tio av två hundra människor. De är ungefär , och en sådan mängd operationer kan redan utvärderas på klustret.

Om vi kan säkert ta med helt konfliktfria personer, hur är det då med dem som deltar i endast en konflikt? Egentligen kan vi också släppa in dem, genom att stänga dörren för deras motståndare. I verkligheten, om Alice har konflikt endast med Bob, så om vi släpper in Alice av de två, förlorar vi ingenting: Bob kan ha andra konflikter, medan Alice definitivt inte har några. Dessutom är det meningslöst för oss att inte släppa in dem båda. Efter sådana operationer återstår inte mer än gäster med osäker öde: totalt har vi konflikter, där varje konflikt har två deltagare och varje deltagare är involverad i åtminstone två konflikter. Det betyder att vi bara behöver gå igenom alternativ, vilket mycket väl kan beräknas på en halv dag på en laptop.

Egentligen kan enkla resonemang leda till ännu mer fördelaktiga förhållanden. Låt oss notera att vi nödvändigtvis måste lösa alla tvister, det vill säga från varje konfliktpar behöva välja minst en person som vi inte släpper in. Låt oss överväga följande algoritm: vi tar en konflikt och tar bort en deltagare och startar rekursivt från resterande, sedan tar vi bort den andra och startar också rekursivt. Eftersom vi vid varje steg tar bort någon, blir rekursions trädet för denna algoritm ett binärt träd med djup vågvektor, så algoritmen arbetar totalt på , där n — antalet noder, och m — antalet kanter. I vårt exempel handlar det om ungefär tio miljoner, vilket kan beräknas på bråkdelar av en sekund, inte bara på en laptop utan till och med på en mobiltelefon.

Exemplet ovan är ett exempel på parametriserad algoritm. Parametriserade algoritmer är algoritmer som fungerar på tid f(k) poly(n), där p — ett polynom, f — en godtycklig beräkningsbar funktion, och vågvektor — någon parameter som mycket väl kan vara mycket mindre än uppgiftens storlek.

Alla resonemang fram till denna algoritm ger ett exempel på kärnalisering — en av de vanliga teknikerna för att skapa parametriska algoritmer. Kernalisering innebär att minska storleken på en uppgift till ett värde som begränsas av en funktion av parametern. Den resulterande uppgiften kallas ofta för kärnan. Genom enkla resonemang om noderna fick vi en kvadratisk kärna för uppgiften Vertex Cover, parametiserad efter svarstyp. Det finns även andra parametrar som kan väljas för denna uppgift (till exempel Vertex Cover Above LP), men vi kommer att diskutera just denna parameter.

Pace Challenge

Tävling PACE Challenge (The Parameterized Algorithms and Computational Experiments Challenge) började 2015 för att skapa en koppling mellan parametriska algoritmer och metoder som används i praktiken för att lösa beräkningsproblem. De första tre tävlingarna handlade om att hitta trädets bredd (Treewidth), att hitta Steiner-träd (Steiner Tree) och att hitta en uppsättning av noder som skär cykler (Feedback Vertex Set). I år var en av uppgifterna där man kunde pröva sina färdigheter den ovan beskrivna uppgiften om nodöverdragning.

Tävlingen blir mer populär för varje år som går. Om man ska tro preliminära uppgifter deltog endast 24 lag i årets tävling för att lösa uppgiften om nodöverdragning. Det är värt att notera att tävlingen pågår inte i några timmar eller ens en vecka, utan i flera månader. Lag har möjlighet att studera litteratur, komma med egna originalidéer och försöka implementera dem. I grund och botten representerar denna tävling ett forskningsarbete. Idéerna bakom de mest effektiva lösningarna och belöningarna för vinnarna presenteras i samband med konferensen IPEC (International Symposium on Parameterized and Exact Computation) som en del av den största årliga algoritmkonferensen i Europa ALGO. Mer information om själva tävlingen kan hittas på webbplats, och resultaten från tidigare år finns ). Ett typiskt exempel på användning:.

Lösningsschema

För att hantera problemet med toppöverdragning försökte jag tillämpa parameteriserade algoritmer. Dessa består vanligtvis av två delar: förenklingsregler (som i idealfallet leder till kernalisering) och delningsregler. Förenklingsreglerna är en förbehandling av ingången på polynomiell tid. Målet med att tillämpa sådana regler är att reducera problemet till ett ekvivalent problem av mindre storlek. Förenklingsreglerna är den mest kostsamma delen av algoritmen, och tillämpningen av just denna del leder till den totala körtiden. istället för enkel polynomiell tid. I vårt fall baseras delningsreglerna på att för varje topp behöver vi ta som svar antingen den eller dess granne.

Den allmänna planen är följande: vi tillämpar förenklingsreglerna, väljer sedan en topp, och gör två rekursiva anrop: i det första tar vi den som svar, och i det andra tar vi alla dess grannar. Detta kallar vi att dela (branching) vid denna topp.

I detta schema kommer exakt ett tillägg att göras i nästa stycke.

Idéer för delningsregler (branching)

Låt oss diskutera hur vi väljer en topp vid vilken delningen ska äga rum.
Huvudidén är mycket girig i algoritmisk mening: låt oss ta den topp med maximal grad och dela oss just vid den. Varför verkar det som om det är bättre? För att vi på så sätt i den andra grenen av det rekursiva anropet kommer att ta bort väldigt många toppar. Man kan förvänta sig att det kommer att finnas en liten graf kvar och att vi snabbt kan bearbeta den.

Denna metod med redan diskuterade enkla tekniker för kernalisering presterar ganska bra och löser vissa tester med några tusen toppar. Men till exempel fungerar den dåligt för kubiska grafer (vilket innebär grafer där graden av varje topp är tre).
Det finns ytterligare en idé, baserad på en ganska enkel tanke: om grafen är icke-ansluten kan problemet med dess sammanhängande komponenter lösas oberoende, genom att sammanfoga svaren i slutet. Detta är förresten den lilla lovade modifieringen i schemat som avsevärt kommer att påskynda lösningen: tidigare arbetade vi i så fall med produkten av tiderna för att räkna svar från komponenterna, men nu arbetar vi med summan. Och för att påskynda delningen behöver vi omvandla den anslutna grafen till en icke-ansluten.

Hur gör man detta? Om grafen har en skärningspunkt, måste man bryta vid den. En skärningspunkt är en sådan toppunkt, vars borttagning gör grafen osammanhängande. Man kan hitta alla skärningspunkter i grafen med en klassisk algoritm på linjär tid. Denna metod påskyndar brytningen avsevärt.

Vid borttagning av vilken som helst av de markerade noderna kommer grafen att dela upp sig i sammanhängande komponenter.

Detta kommer vi att göra, men vi vill ha mer. Till exempel att söka små nodskärningar i grafen och utföra delning baserat på dessa noder. Det mest effektiva sättet jag känner till för att hitta den minimala globala nodskärningen är att använda Gomory-Hu-trädet, som konstrueras på kubisk tid. I PACE Challenge är den typiska storleken på grafen flera tusen noder. Givet detta förhållande behöver man utföra miljarder operationer i varje nod i rekursionsträdet. Det visar sig att det är omöjligt att lösa problemet inom den givna tiden.

Vi försöker optimera lösningen. Den minimala nodskärningen mellan ett par noder kan hittas med vilken algoritm som helst som bygger ett maximalt flöde. Man kan använda Dinic-algoritmen, som i praktiken fungerar mycket snabbt. Jag är misstänksam mot att man teoretiskt kan bevisa en tidskomplexitetsbedömning , vilket redan är fullt acceptabelt.

Jag har försökt flera gånger att söka skärningar mellan par av slumpmässiga noder och ta den mest balanserade. Tyvärr gav det dåliga resultat på de öppna testerna i PACE Challenge. Jag jämförde med en algoritm som skar med avseende på noder av maximal grad, med en begränsning för hur djupt man fick gå. Efter algoritmen som försökte hitta skärningen på detta sätt kvarstod större grafer. Detta berodde på att skärningarna blev mycket obalanserade: genom att ta bort 5-10 noder lyckades man endast skära bort 15-20.

Det är värt att notera att i artiklar om de teoretiskt snabbaste algoritmerna används mycket mer avancerade tekniker för att välja noder för delning. Sådana tekniker har en mycket komplicerad implementering och ofta dåliga uppskattningar av tids- och minnesanvändning. Jag har inte lyckats extrahera några acceptabla metoder för praktisk tillämpning från dem.

Hur man tillämpar förenklingsregler

Vi har redan idéer för kärnalisering. Låt mig påminna om:

1. Om det finns en isolerad nod, ta bort den.
2. Om det finns en topp med grad 1, ta bort den och ta dess granne som svar.
3. Om det finns en topp med grad åtminstone k + 1, ta den som svar.

Det är klart med de två första, men den tredje har en liten knep. Om vi i det skämtande problemet om baren fick en övre gräns på vågvektor, så måste man i PACE Challenge helt enkelt hitta ett minsta toppöverdrag. Det är en typisk omvandling av sökproblem till beslut/problem, och man gör ofta ingen skillnad mellan de två slags problem. I praktiken, om vi skriver en lösare för toppöverdraget, kan skillnaden vara märkbar. Till exempel, som i den tredje punkten.

Sett ur ett implementeringsperspektiv kan man gå tillväga på två sätt. Den första metoden kallas Iterative Deepening. Den innebär att vi kan börja med någon rimlig nedre gräns för svaret och sedan köra vår algoritm, med denna begränsning som en övre gräns för svaret, utan att gå djupare ner i rekursionen än den begränsningen. Om vi hittar något svar är det garanterat optimalt, annars kan vi bara öka den gränsen med ett och köra igen.

Det andra tillvägagångssättet är att behålla något nuvarande optimalt svar och söka efter ett svar av mindre storlek, och när man hittar det ändrar man denna parameter vågvektor för att kapa onödiga grenar i sökningen.

Efter att ha genomfört några nattliga experiment stannade jag vid en kombination av dessa två metoder: först kör jag min algoritm med en viss begränsning på sökdjupet (välj den så att det tar försumbar tid i förhållande till huvudlösningen) och använder den bästa hittade lösningen som en övre gräns för svaret — det vill säga den där vågvektor.

Topp med grad 2

Vi har hanterat toppar med grad 0 och 1. Det visar sig att detta också kan göras med toppar med grad 2, men grafen kräver mer komplexa operationer.

För att förklara detta behöver vi på något sätt benämna topparna. Låt oss kalla en topp med grad 2 för topp v, och dess grannar för toppar x och y. Vi har nu två fall.

1. När x och y — grannar. Då kan vi ta som svar x och y, och v ta bort. Och verkligen, från denna triangel måste vi ta åtminstone två toppar som svar och vi kommer definitivt inte att förlora om vi tar x och y: de har förmodligen fler grannar, medan v de har inga.
2. När x och y — inte grannar. Då påstås det att alla tre topparna kan klistras ihop till en. Idén är att det i så fall finns ett optimalt svar, där vi tar antingen v, eller båda topparna x och y. I det första fallet måste vi ta alla grannar x och y, medan det i det andra inte är nödvändigt. Detta motsvarar exakt de fall där vi inte tar den sammanfogade toppen i svaret och där vi gör det. Det återstår bara att notera att svaret från denna operation minskar med ett.

Det är värt att notera att en sådan metod är ganska svår att genomföra noggrant på ett rättvist linjärt sätt. Att klistra toppen är en komplicerad operation, man måste kopiera listorna över grannar. Om detta görs slarvigt kan man få en asymptotiskt suboptimal körtid (till exempel, om man efter varje sammanslagning kopierar många kanter). Jag stannade vid att söka hela vägar från toppar av grad 2 och analyserade en mängd olika fall, som cykler av sådana toppar eller av alla sådana toppar utom en.

Dessutom måste denna operation vara omvändbar, så att vi kan återställa grafen till sitt ursprungliga skick när vi återvänder från rekursionen. För att säkerställa detta rensade jag inte listorna över kanter för de sammanfogade topparna, efter vilket jag visste exakt vilka kanter som skulle riktas. En sådan grafimplementation kräver också noggrannhet, men garanterar rättvist linjär tid. Dessutom, för grafer med flera tiotusentals kanter, ryms det ganska bra i processorens cache, vilket ger stora hastighetsfördelar.

Linjära kärnor

Till sist, den mest intressanta delen av kärnan.

Låt oss först minnas att i bipartita grafer kan det minimiella vertextäcket sökas på . För detta är det nödvändigt att använda algoritmen Hopcroft-Karp för att hitta det maximala matchningen där, och sedan använda teoremet Königs-Egervári.

Idén om den linjära kärnan är följande: först delar vi grafen, det vill säga istället för varje topp v introducerar vi två toppar och , och istället för varje kant u — v introducerar vi två kanter och Den erhållna grafen blir tvådelad. Vi ska hitta ett minimalt vertexöverdrag i den. Vissa hörn i den ursprungliga grafen kommer att förekomma där två gånger, vissa bara en gång, och vissa inte alls. Nemhauser-Trotters teorem hävdar att i detta fall kan vi ta bort de hörn som inte förekommit alls och ta med de som förekommit två gånger i svaret. Dessutom säger den att från de kvarstående hörnen (de som förekommit en gång) ska vi ta minst hälften i svaret.

Vi har just lärt oss att lämna högst 2k hörn i grafen. Och verkligen, om svaret är kvar — minst hälften av alla hörn, så finns det högst 2k.

Här har jag lyckats ta ett litet steg framåt. Det är tydligt att det kärna som byggs på detta sätt beror på vilket minimalt vertexöverdrag i den tvådelade grafen vi valt. Det vill sade att vi vill välja det som gör antalet kvarvarande hörn så lågt som möjligt. Tidigare kunde detta endast göras på tid . Jag har dock kommit på en implementering av den här algoritmen som tar tid , vilket gör att detta kärna kan sökas i grafer med hundratusentals hörn vid varje branching-steg.

Resultat

Praktiken visar att min lösning fungerar bra på tester med flera hundra hörn och flera tusen kanter. På sådana tester kan man rimligt förvänta sig att lösningen hittas inom en halvtimme. Sannolikheten att hitta ett svar inom rimlig tid ökar i princip om grafen har tillräckligt många hörn med hög grad, till exempel grad 10 och uppåt.

För att delta i tävlingen behövde vi skicka in våra lösningar till optil.io. Enligt den tabell som presenterades där tabell, ligger min lösning på öppna tester på tredje plats av tjugo med stor marginal till andra plats. För att vara helt ärlig är det inte helt klart hur lösningarna kommer att bedömas i själva tävlingen: till exempel, min lösning klarar färre tester än lösningen på fjärde plats, men de som den klarar går snabbare.

Resultaten på de stängda testerna kommer att bli kända den första juli.

Källa: habr.com