{"id":35406,"date":"2019-10-31T22:04:08","date_gmt":"2019-10-31T19:04:08","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov\/"},"modified":"2021-01-02T13:01:41","modified_gmt":"2021-01-02T11:01:41","slug":"kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sv\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Hur man l\u00f6ser NP-sv\u00e5ra problem med hj\u00e4lp av parameteriserade algoritmer","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Forskning \u00e4r f\u00f6rmodligen den mest intressanta delen av v\u00e5r utbildning. Id\u00e9n \u00e4r att redan p\u00e5 universitetet pr\u00f6va sig inom det valda omr\u00e5det. Till exempel g\u00e5r studenter fr\u00e5n programmen Software Engineering och Machine Learning ofta f\u00f6r att g\u00f6ra forskningsprojekt p\u00e5 f\u00f6retag (fr\u00e4mst JetBrains eller Yandex, men inte bara).<\/p>\n

I det h\u00e4r inl\u00e4gget ska jag ber\u00e4tta om mitt projekt inom Computer Science. Inom ramen f\u00f6r arbetet har jag studerat och implementerat metoder f\u00f6r att l\u00f6sa ett av de mest k\u00e4nda NP-sv\u00e5ra problemen: vertex-cover problemet<\/b>.<\/p>\n

Just nu utvecklas en intressant metod f\u00f6r NP-sv\u00e5ra problem - parametriserade algoritmer. Jag ska f\u00f6rs\u00f6ka ge er en inblick, ber\u00e4tta om n\u00e5gra enkla parametriserade algoritmer och beskriva en kraftfull metod som har hj\u00e4lpt mig mycket. Jag presenterade mina resultat p\u00e5 t\u00e4vlingen PACE Challenge: efter de \u00f6ppna testerna ligger min l\u00f6sning p\u00e5 tredje plats, medan de slutgiltiga resultaten kommer att bli k\u00e4nda den 1 juli.<\/p>\n

\"Hur
\n<\/a><\/noindex><\/p>\n

Om mig<\/h3>\n

Jag heter Vasily Alfjorov, och jag avslutar just nu mitt tredje \u00e5r p\u00e5 HSE - Sankt Petersburg. Jag har varit intresserad av algoritmer \u00e4nda sedan gymnasiet, n\u00e4r jag gick i Moskvas skola 179 och deltog framg\u00e5ngsrikt i informatikolympiader.<\/p>\n

Det slutgiltiga antalet specialister p\u00e5 parameteriserade algoritmer g\u00e5r in p\u00e5 en bar\u2026<\/h3>\n

Exemplet \u00e4r fr\u00e5n boken \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

T\u00e4nk dig att du \u00e4r vakten p\u00e5 en bar i en liten stad. Varje fredag kv\u00e4ll kommer h\u00e4lften av staden till din bar f\u00f6r att koppla av, vilket ger dig en hel del besv\u00e4r: du m\u00e5ste kasta ut de st\u00f6kiga bes\u00f6karna f\u00f6r att f\u00f6rhindra slagsm\u00e5l. Till slut blir det tr\u00e5kigt och du beslutar dig f\u00f6r att ta f\u00f6rebyggande \u00e5tg\u00e4rder.<\/p>\n

Eftersom staden \u00e4r liten vet du precis vilka par bes\u00f6kare som troligtvis kommer att br\u00e5ka om de hamnar i baren tillsammans. Du har en lista med n<\/i> m\u00e4nniskor som kommer till baren ikv\u00e4ll. Du beslutar dig f\u00f6r att inte sl\u00e4ppa in n\u00e5gra inv\u00e5nare p\u00e5 ett s\u00e4tt s\u00e5 att ingen br\u00e5kar. Samtidigt vill din chef inte f\u00f6rlora int\u00e4kter och kommer att bli missn\u00f6jd om du inte sl\u00e4pper in fler \u00e4n v\u00e5gvektor<\/i> m\u00e4nniskor.<\/p>\n

Tyv\u00e4rr \u00e4r problemet du st\u00e5r inf\u00f6r ett klassiskt NP-sv\u00e5rt problem. Du kanske k\u00e4nner det som vertex cover<\/a><\/noindex>, eller hur man l\u00f6ser ett uppdrag om toppbel\u00e4ggning. F\u00f6r s\u00e5dana problem \u00e4r det generellt sett oklart om det finns algoritmer som fungerar p\u00e5 rimlig tid. F\u00f6r att vara exakt, s\u00e5 indikerar den icke-bevisade och ganska starka hypotesen ETH (Exponential Time Hypothesis) att detta problem inte kan l\u00f6sas inom tiden \"Hur, vilket inneb\u00e4r att det inte finns n\u00e5got b\u00e4ttre \u00e4n att pr\u00f6va alla alternativ. Till exempel, om det kommer att komma n = 1000<\/i> personer till din bar. D\u00e5 kommer ett komplett test att inneb\u00e4ra \"Hur alternativ, vilket \u00e4r ungef\u00e4r \"Hur \u2014 ofattbart mycket. Som tur \u00e4r, har din ledning satt en begr\u00e4nsning p\u00e5 k = 10<\/i>, s\u00e5 antalet kombinationer som du beh\u00f6ver utv\u00e4rdera \u00e4r mycket mindre: antalet delm\u00e4ngder av tio element \u00e4r lika med \"Hur. Detta \u00e4r redan b\u00e4ttre, men det \u00e4r fortfarande f\u00f6r m\u00e5nga f\u00f6r att r\u00e4kna p\u00e5 en dag \u00e4ven med en kraftfull kluster.
\n\"Hur
\nF\u00f6r att utesluta risken f\u00f6r br\u00e5k under s\u00e5dan konfiguration av relationer mellan barbes\u00f6karna m\u00e5ste man inte sl\u00e4ppa in Bob, Daniel och Fyodor. L\u00f6sningar d\u00e4r endast tv\u00e5 blir kvar ute finns inte.<\/p>\n

Betyder detta att det \u00e4r dags att ge upp och sl\u00e4ppa in alla? L\u00e5t oss \u00f6verv\u00e4ga andra alternativ. Till exempel, man kan bara neka intr\u00e4de till dem som troligtvis kommer br\u00e5ka med ett stort antal m\u00e4nniskor. Om n\u00e5gon kan br\u00e5ka med minst k + 1<\/i> andra m\u00e4nniskor, s\u00e5 kan han definitivt inte sl\u00e4ppas in \u2014 annars m\u00e5ste alla k + 1<\/i> medborgare, som han kan br\u00e5ka med, nekas intr\u00e4de, vilket definitivt kommer att missn\u00f6ja ledningen.<\/p>\n

Anta att du har tagit bort alla som du kan enligt detta princip. S\u00e5 alla andra kan br\u00e5ka med h\u00f6gst v\u00e5gvektor<\/i> m\u00e4nniskor. Genom att ta bort v\u00e5gvektor<\/i> personer, kan du f\u00f6rhindra h\u00f6gst \"Hur konflikter. S\u00e5 om mer \u00e4n \"Hur personer \u00e4r involverade i \u00e5tminstone en konflikt, kan du definitivt inte f\u00f6rhindra dem alla. Eftersom det uppenbarligen finns helt konfliktsfria m\u00e4nniskor som du kommer att sl\u00e4ppa in, beh\u00f6ver du utv\u00e4rdera alla delm\u00e4ngder som best\u00e5r av tio av tv\u00e5 hundra m\u00e4nniskor. De \u00e4r ungef\u00e4r \"Hur, och en s\u00e5dan m\u00e4ngd operationer kan redan utv\u00e4rderas p\u00e5 klustret.<\/p>\n

Om vi kan s\u00e4kert ta med helt konfliktfria personer, hur \u00e4r det d\u00e5 med dem som deltar i endast en konflikt? Egentligen kan vi ocks\u00e5 sl\u00e4ppa in dem, genom att st\u00e4nga d\u00f6rren f\u00f6r deras motst\u00e5ndare. I verkligheten, om Alice har konflikt endast med Bob, s\u00e5 om vi sl\u00e4pper in Alice av de tv\u00e5, f\u00f6rlorar vi ingenting: Bob kan ha andra konflikter, medan Alice definitivt inte har n\u00e5gra. Dessutom \u00e4r det meningsl\u00f6st f\u00f6r oss att inte sl\u00e4ppa in dem b\u00e5da. Efter s\u00e5dana operationer \u00e5terst\u00e5r inte mer \"Hur \u00e4n g\u00e4ster med os\u00e4ker \u00f6de: totalt har vi \"Hur konflikter, d\u00e4r varje konflikt har tv\u00e5 deltagare och varje deltagare \u00e4r involverad i \u00e5tminstone tv\u00e5 konflikter. Det betyder att vi bara beh\u00f6ver g\u00e5 igenom \"Hur alternativ, vilket mycket v\u00e4l kan ber\u00e4knas p\u00e5 en halv dag p\u00e5 en laptop.<\/p>\n

Egentligen kan enkla resonemang leda till \u00e4nnu mer f\u00f6rdelaktiga f\u00f6rh\u00e5llanden. L\u00e5t oss notera att vi n\u00f6dv\u00e4ndigtvis m\u00e5ste l\u00f6sa alla tvister, det vill s\u00e4ga fr\u00e5n varje konfliktpar beh\u00f6va v\u00e4lja minst en person som vi inte sl\u00e4pper in. L\u00e5t oss \u00f6verv\u00e4ga f\u00f6ljande algoritm: vi tar en konflikt och tar bort en deltagare och startar rekursivt fr\u00e5n resterande, sedan tar vi bort den andra och startar ocks\u00e5 rekursivt. Eftersom vi vid varje steg tar bort n\u00e5gon, blir rekursions tr\u00e4det f\u00f6r denna algoritm ett bin\u00e4rt tr\u00e4d med djup v\u00e5gvektor<\/i>, s\u00e5 algoritmen arbetar totalt p\u00e5 \"Hur, d\u00e4r n<\/i> \u2014 antalet noder, och m<\/i> \u2014 antalet kanter. I v\u00e5rt exempel handlar det om ungef\u00e4r tio miljoner, vilket kan ber\u00e4knas p\u00e5 br\u00e5kdelar av en sekund, inte bara p\u00e5 en laptop utan till och med p\u00e5 en mobiltelefon.<\/p>\n

Exemplet ovan \u00e4r ett exempel p\u00e5 parametriserad algoritm<\/b>. Parametriserade algoritmer \u00e4r algoritmer som fungerar p\u00e5 tid f(k) poly(n)<\/i>, d\u00e4r p<\/i> \u2014 ett polynom, f<\/i> \u2014 en godtycklig ber\u00e4kningsbar funktion, och v\u00e5gvektor<\/i> \u2014 n\u00e5gon parameter som mycket v\u00e4l kan vara mycket mindre \u00e4n uppgiftens storlek.<\/p>\n

Alla resonemang fram till denna algoritm ger ett exempel p\u00e5 k\u00e4rnalisering<\/b> \u2014 en av de vanliga teknikerna f\u00f6r att skapa parametriska algoritmer. Kernalisering inneb\u00e4r att minska storleken p\u00e5 en uppgift till ett v\u00e4rde som begr\u00e4nsas av en funktion av parametern. Den resulterande uppgiften kallas ofta f\u00f6r k\u00e4rnan. Genom enkla resonemang om noderna fick vi en kvadratisk k\u00e4rna f\u00f6r uppgiften Vertex Cover, parametiserad efter svarstyp. Det finns \u00e4ven andra parametrar som kan v\u00e4ljas f\u00f6r denna uppgift (till exempel Vertex Cover Above LP), men vi kommer att diskutera just denna parameter.<\/p>\n

Pace Challenge<\/h3>\n

T\u00e4vling PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) b\u00f6rjade 2015 f\u00f6r att skapa en koppling mellan parametriska algoritmer och metoder som anv\u00e4nds i praktiken f\u00f6r att l\u00f6sa ber\u00e4kningsproblem. De f\u00f6rsta tre t\u00e4vlingarna handlade om att hitta tr\u00e4dets bredd (Treewidth<\/a><\/noindex>), att hitta Steiner-tr\u00e4d (Steiner Tree<\/a><\/noindex>) och att hitta en upps\u00e4ttning av noder som sk\u00e4r cykler (Feedback Vertex Set<\/a><\/noindex>). I \u00e5r var en av uppgifterna d\u00e4r man kunde pr\u00f6va sina f\u00e4rdigheter den ovan beskrivna uppgiften om nod\u00f6verdragning.<\/p>\n

T\u00e4vlingen blir mer popul\u00e4r f\u00f6r varje \u00e5r som g\u00e5r. Om man ska tro prelimin\u00e4ra uppgifter deltog endast 24 lag i \u00e5rets t\u00e4vling f\u00f6r att l\u00f6sa uppgiften om nod\u00f6verdragning. Det \u00e4r v\u00e4rt att notera att t\u00e4vlingen p\u00e5g\u00e5r inte i n\u00e5gra timmar eller ens en vecka, utan i flera m\u00e5nader. Lag har m\u00f6jlighet att studera litteratur, komma med egna originalid\u00e9er och f\u00f6rs\u00f6ka implementera dem. I grund och botten representerar denna t\u00e4vling ett forskningsarbete. Id\u00e9erna bakom de mest effektiva l\u00f6sningarna och bel\u00f6ningarna f\u00f6r vinnarna presenteras i samband med konferensen IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) som en del av den st\u00f6rsta \u00e5rliga algoritmkonferensen i Europa ALGO<\/a><\/noindex>. Mer information om sj\u00e4lva t\u00e4vlingen kan hittas p\u00e5 webbplats<\/a><\/noindex>, och resultaten fr\u00e5n tidigare \u00e5r finns ). Ett typiskt exempel p\u00e5 anv\u00e4ndning:<\/a><\/noindex>.<\/p>\n

L\u00f6sningsschema<\/h3>\n

F\u00f6r att hantera problemet med topp\u00f6verdragning f\u00f6rs\u00f6kte jag till\u00e4mpa parameteriserade algoritmer. Dessa best\u00e5r vanligtvis av tv\u00e5 delar: f\u00f6renklingsregler (som i idealfallet leder till kernalisering) och delningsregler. F\u00f6renklingsreglerna \u00e4r en f\u00f6rbehandling av ing\u00e5ngen p\u00e5 polynomiell tid. M\u00e5let med att till\u00e4mpa s\u00e5dana regler \u00e4r att reducera problemet till ett ekvivalent problem av mindre storlek. F\u00f6renklingsreglerna \u00e4r den mest kostsamma delen av algoritmen, och till\u00e4mpningen av just denna del leder till den totala k\u00f6rtiden. \"Hur ist\u00e4llet f\u00f6r enkel polynomiell tid. I v\u00e5rt fall baseras delningsreglerna p\u00e5 att f\u00f6r varje topp beh\u00f6ver vi ta som svar antingen den eller dess granne.<\/p>\n

Den allm\u00e4nna planen \u00e4r f\u00f6ljande: vi till\u00e4mpar f\u00f6renklingsreglerna, v\u00e4ljer sedan en topp, och g\u00f6r tv\u00e5 rekursiva anrop: i det f\u00f6rsta tar vi den som svar, och i det andra tar vi alla dess grannar. Detta kallar vi att dela (branching) vid denna topp.<\/p>\n

I detta schema kommer exakt ett till\u00e4gg att g\u00f6ras i n\u00e4sta stycke.<\/p>\n

Id\u00e9er f\u00f6r delningsregler (branching)<\/h3>\n

L\u00e5t oss diskutera hur vi v\u00e4ljer en topp vid vilken delningen ska \u00e4ga rum.
\nHuvudid\u00e9n \u00e4r mycket girig i algoritmisk mening: l\u00e5t oss ta den topp med maximal grad och dela oss just vid den. Varf\u00f6r verkar det som om det \u00e4r b\u00e4ttre? F\u00f6r att vi p\u00e5 s\u00e5 s\u00e4tt i den andra grenen av det rekursiva anropet kommer att ta bort v\u00e4ldigt m\u00e5nga toppar. Man kan f\u00f6rv\u00e4nta sig att det kommer att finnas en liten graf kvar och att vi snabbt kan bearbeta den.<\/p>\n

Denna metod med redan diskuterade enkla tekniker f\u00f6r kernalisering presterar ganska bra och l\u00f6ser vissa tester med n\u00e5gra tusen toppar. Men till exempel fungerar den d\u00e5ligt f\u00f6r kubiska grafer (vilket inneb\u00e4r grafer d\u00e4r graden av varje topp \u00e4r tre).
\nDet finns ytterligare en id\u00e9, baserad p\u00e5 en ganska enkel tanke: om grafen \u00e4r icke-ansluten kan problemet med dess sammanh\u00e4ngande komponenter l\u00f6sas oberoende, genom att sammanfoga svaren i slutet. Detta \u00e4r f\u00f6rresten den lilla lovade modifieringen i schemat som avsev\u00e4rt kommer att p\u00e5skynda l\u00f6sningen: tidigare arbetade vi i s\u00e5 fall med produkten av tiderna f\u00f6r att r\u00e4kna svar fr\u00e5n komponenterna, men nu arbetar vi med summan. Och f\u00f6r att p\u00e5skynda delningen beh\u00f6ver vi omvandla den anslutna grafen till en icke-ansluten.<\/p>\n

Hur g\u00f6r man detta? Om grafen har en sk\u00e4rningspunkt, m\u00e5ste man bryta vid den. En sk\u00e4rningspunkt \u00e4r en s\u00e5dan toppunkt, vars borttagning g\u00f6r grafen osammanh\u00e4ngande. Man kan hitta alla sk\u00e4rningspunkter i grafen med en klassisk algoritm p\u00e5 linj\u00e4r tid. Denna metod p\u00e5skyndar brytningen avsev\u00e4rt.
\n\"Hur
\nVid borttagning av vilken som helst av de markerade noderna kommer grafen att dela upp sig i sammanh\u00e4ngande komponenter.<\/p>\n

Detta kommer vi att g\u00f6ra, men vi vill ha mer. Till exempel att s\u00f6ka sm\u00e5 nodsk\u00e4rningar i grafen och utf\u00f6ra delning baserat p\u00e5 dessa noder. Det mest effektiva s\u00e4ttet jag k\u00e4nner till f\u00f6r att hitta den minimala globala nodsk\u00e4rningen \u00e4r att anv\u00e4nda Gomory-Hu-tr\u00e4det, som konstrueras p\u00e5 kubisk tid. I PACE Challenge \u00e4r den typiska storleken p\u00e5 grafen flera tusen noder. Givet detta f\u00f6rh\u00e5llande beh\u00f6ver man utf\u00f6ra miljarder operationer i varje nod i rekursionstr\u00e4det. Det visar sig att det \u00e4r om\u00f6jligt att l\u00f6sa problemet inom den givna tiden.<\/p>\n

Vi f\u00f6rs\u00f6ker optimera l\u00f6sningen. Den minimala nodsk\u00e4rningen mellan ett par noder kan hittas med vilken algoritm som helst som bygger ett maximalt fl\u00f6de. Man kan anv\u00e4nda Dinic-algoritmen<\/a><\/noindex>, som i praktiken fungerar mycket snabbt. Jag \u00e4r misst\u00e4nksam mot att man teoretiskt kan bevisa en tidskomplexitetsbed\u00f6mning \"Hur, vilket redan \u00e4r fullt acceptabelt.<\/p>\n

Jag har f\u00f6rs\u00f6kt flera g\u00e5nger att s\u00f6ka sk\u00e4rningar mellan par av slumpm\u00e4ssiga noder och ta den mest balanserade. Tyv\u00e4rr gav det d\u00e5liga resultat p\u00e5 de \u00f6ppna testerna i PACE Challenge. Jag j\u00e4mf\u00f6rde med en algoritm som skar med avseende p\u00e5 noder av maximal grad, med en begr\u00e4nsning f\u00f6r hur djupt man fick g\u00e5. Efter algoritmen som f\u00f6rs\u00f6kte hitta sk\u00e4rningen p\u00e5 detta s\u00e4tt kvarstod st\u00f6rre grafer. Detta berodde p\u00e5 att sk\u00e4rningarna blev mycket obalanserade: genom att ta bort 5-10 noder lyckades man endast sk\u00e4ra bort 15-20.<\/p>\n

Det \u00e4r v\u00e4rt att notera att i artiklar om de teoretiskt snabbaste algoritmerna anv\u00e4nds mycket mer avancerade tekniker f\u00f6r att v\u00e4lja noder f\u00f6r delning. S\u00e5dana tekniker har en mycket komplicerad implementering och ofta d\u00e5liga uppskattningar av tids- och minnesanv\u00e4ndning. Jag har inte lyckats extrahera n\u00e5gra acceptabla metoder f\u00f6r praktisk till\u00e4mpning fr\u00e5n dem.<\/p>\n

Hur man till\u00e4mpar f\u00f6renklingsregler<\/h3>\n

Vi har redan id\u00e9er f\u00f6r k\u00e4rnalisering. L\u00e5t mig p\u00e5minna om:<\/p>\n

    \n
  1. Om det finns en isolerad nod, ta bort den.<\/li>\n
  2. Om det finns en topp med grad 1, ta bort den och ta dess granne som svar.<\/li>\n
  3. Om det finns en topp med grad \u00e5tminstone k + 1<\/i>, ta den som svar.<\/li>\n<\/ol>\n

    Det \u00e4r klart med de tv\u00e5 f\u00f6rsta, men den tredje har en liten knep. Om vi i det sk\u00e4mtande problemet om baren fick en \u00f6vre gr\u00e4ns p\u00e5 v\u00e5gvektor<\/i>, s\u00e5 m\u00e5ste man i PACE Challenge helt enkelt hitta ett minsta topp\u00f6verdrag. Det \u00e4r en typisk omvandling av s\u00f6kproblem till beslut\/problem, och man g\u00f6r ofta ingen skillnad mellan de tv\u00e5 slags problem. I praktiken, om vi skriver en l\u00f6sare f\u00f6r topp\u00f6verdraget, kan skillnaden vara m\u00e4rkbar. Till exempel, som i den tredje punkten.<\/p>\n

    Sett ur ett implementeringsperspektiv kan man g\u00e5 tillv\u00e4ga p\u00e5 tv\u00e5 s\u00e4tt. Den f\u00f6rsta metoden kallas Iterative Deepening. Den inneb\u00e4r att vi kan b\u00f6rja med n\u00e5gon rimlig nedre gr\u00e4ns f\u00f6r svaret och sedan k\u00f6ra v\u00e5r algoritm, med denna begr\u00e4nsning som en \u00f6vre gr\u00e4ns f\u00f6r svaret, utan att g\u00e5 djupare ner i rekursionen \u00e4n den begr\u00e4nsningen. Om vi hittar n\u00e5got svar \u00e4r det garanterat optimalt, annars kan vi bara \u00f6ka den gr\u00e4nsen med ett och k\u00f6ra igen.<\/p>\n

    Det andra tillv\u00e4gag\u00e5ngss\u00e4ttet \u00e4r att beh\u00e5lla n\u00e5got nuvarande optimalt svar och s\u00f6ka efter ett svar av mindre storlek, och n\u00e4r man hittar det \u00e4ndrar man denna parameter v\u00e5gvektor<\/i> f\u00f6r att kapa on\u00f6diga grenar i s\u00f6kningen.<\/p>\n

    Efter att ha genomf\u00f6rt n\u00e5gra nattliga experiment stannade jag vid en kombination av dessa tv\u00e5 metoder: f\u00f6rst k\u00f6r jag min algoritm med en viss begr\u00e4nsning p\u00e5 s\u00f6kdjupet (v\u00e4lj den s\u00e5 att det tar f\u00f6rsumbar tid i f\u00f6rh\u00e5llande till huvudl\u00f6sningen) och anv\u00e4nder den b\u00e4sta hittade l\u00f6sningen som en \u00f6vre gr\u00e4ns f\u00f6r svaret \u2014 det vill s\u00e4ga den d\u00e4r v\u00e5gvektor<\/i>.<\/p>\n

    Topp med grad 2<\/h3>\n

    Vi har hanterat toppar med grad 0 och 1. Det visar sig att detta ocks\u00e5 kan g\u00f6ras med toppar med grad 2, men grafen kr\u00e4ver mer komplexa operationer.<\/p>\n

    F\u00f6r att f\u00f6rklara detta beh\u00f6ver vi p\u00e5 n\u00e5got s\u00e4tt ben\u00e4mna topparna. L\u00e5t oss kalla en topp med grad 2 f\u00f6r topp v<\/i>, och dess grannar f\u00f6r toppar x<\/i> och y<\/i>. Vi har nu tv\u00e5 fall.<\/p>\n

      \n
    1. N\u00e4r x<\/i> och y<\/i> \u2014 grannar. D\u00e5 kan vi ta som svar x<\/i> och y<\/i>, och v<\/i> ta bort. Och verkligen, fr\u00e5n denna triangel m\u00e5ste vi ta \u00e5tminstone tv\u00e5 toppar som svar och vi kommer definitivt inte att f\u00f6rlora om vi tar x<\/i> och y<\/i>: de har f\u00f6rmodligen fler grannar, medan v<\/i> de har inga.<\/li>\n
    2. N\u00e4r x<\/i> och y<\/i> \u2014 inte grannar. D\u00e5 p\u00e5st\u00e5s det att alla tre topparna kan klistras ihop till en. Id\u00e9n \u00e4r att det i s\u00e5 fall finns ett optimalt svar, d\u00e4r vi tar antingen v<\/i>, eller b\u00e5da topparna x<\/i> och y<\/i>. I det f\u00f6rsta fallet m\u00e5ste vi ta alla grannar x<\/i> och y<\/i>, medan det i det andra inte \u00e4r n\u00f6dv\u00e4ndigt. Detta motsvarar exakt de fall d\u00e4r vi inte tar den sammanfogade toppen i svaret och d\u00e4r vi g\u00f6r det. Det \u00e5terst\u00e5r bara att notera att svaret fr\u00e5n denna operation minskar med ett.<\/li>\n<\/ol>\n

      \"Hur<\/p>\n

      Det \u00e4r v\u00e4rt att notera att en s\u00e5dan metod \u00e4r ganska sv\u00e5r att genomf\u00f6ra noggrant p\u00e5 ett r\u00e4ttvist linj\u00e4rt s\u00e4tt. Att klistra toppen \u00e4r en komplicerad operation, man m\u00e5ste kopiera listorna \u00f6ver grannar. Om detta g\u00f6rs slarvigt kan man f\u00e5 en asymptotiskt suboptimal k\u00f6rtid (till exempel, om man efter varje sammanslagning kopierar m\u00e5nga kanter). Jag stannade vid att s\u00f6ka hela v\u00e4gar fr\u00e5n toppar av grad 2 och analyserade en m\u00e4ngd olika fall, som cykler av s\u00e5dana toppar eller av alla s\u00e5dana toppar utom en.<\/p>\n

      Dessutom m\u00e5ste denna operation vara omv\u00e4ndbar, s\u00e5 att vi kan \u00e5terst\u00e4lla grafen till sitt ursprungliga skick n\u00e4r vi \u00e5terv\u00e4nder fr\u00e5n rekursionen. F\u00f6r att s\u00e4kerst\u00e4lla detta rensade jag inte listorna \u00f6ver kanter f\u00f6r de sammanfogade topparna, efter vilket jag visste exakt vilka kanter som skulle riktas. En s\u00e5dan grafimplementation kr\u00e4ver ocks\u00e5 noggrannhet, men garanterar r\u00e4ttvist linj\u00e4r tid. Dessutom, f\u00f6r grafer med flera tiotusentals kanter, ryms det ganska bra i processorens cache, vilket ger stora hastighetsf\u00f6rdelar.<\/p>\n

      Linj\u00e4ra k\u00e4rnor<\/h3>\n

      Till sist, den mest intressanta delen av k\u00e4rnan.<\/p>\n

      L\u00e5t oss f\u00f6rst minnas att i bipartita grafer kan det minimiella vertext\u00e4cket s\u00f6kas p\u00e5 \"Hur. F\u00f6r detta \u00e4r det n\u00f6dv\u00e4ndigt att anv\u00e4nda algoritmen Hopcroft-Karp<\/a><\/noindex> f\u00f6r att hitta det maximala matchningen d\u00e4r, och sedan anv\u00e4nda teoremet K\u00f6nigs-Egerv\u00e1ri<\/a><\/noindex>.<\/p>\n

      Id\u00e9n om den linj\u00e4ra k\u00e4rnan \u00e4r f\u00f6ljande: f\u00f6rst delar vi grafen, det vill s\u00e4ga ist\u00e4llet f\u00f6r varje topp v<\/i> introducerar vi tv\u00e5 toppar \"Hur och \"Hur, och ist\u00e4llet f\u00f6r varje kant u \u2014 v<\/i> introducerar vi tv\u00e5 kanter \"Hur och \"HurDen erh\u00e5llna grafen blir tv\u00e5delad. Vi ska hitta ett minimalt vertex\u00f6verdrag i den. Vissa h\u00f6rn i den ursprungliga grafen kommer att f\u00f6rekomma d\u00e4r tv\u00e5 g\u00e5nger, vissa bara en g\u00e5ng, och vissa inte alls. Nemhauser-Trotters teorem h\u00e4vdar att i detta fall kan vi ta bort de h\u00f6rn som inte f\u00f6rekommit alls och ta med de som f\u00f6rekommit tv\u00e5 g\u00e5nger i svaret. Dessutom s\u00e4ger den att fr\u00e5n de kvarst\u00e5ende h\u00f6rnen (de som f\u00f6rekommit en g\u00e5ng) ska vi ta minst h\u00e4lften i svaret.<\/p>\n

      Vi har just l\u00e4rt oss att l\u00e4mna h\u00f6gst 2k<\/i> h\u00f6rn i grafen. Och verkligen, om svaret \u00e4r kvar \u2014 minst h\u00e4lften av alla h\u00f6rn, s\u00e5 finns det h\u00f6gst 2k<\/i>.<\/p>\n

      H\u00e4r har jag lyckats ta ett litet steg fram\u00e5t. Det \u00e4r tydligt att det k\u00e4rna som byggs p\u00e5 detta s\u00e4tt beror p\u00e5 vilket minimalt vertex\u00f6verdrag i den tv\u00e5delade grafen vi valt. Det vill sade att vi vill v\u00e4lja det som g\u00f6r antalet kvarvarande h\u00f6rn s\u00e5 l\u00e5gt som m\u00f6jligt. Tidigare kunde detta endast g\u00f6ras p\u00e5 tid \"Hur. Jag har dock kommit p\u00e5 en implementering av den h\u00e4r algoritmen som tar tid \"Hur, vilket g\u00f6r att detta k\u00e4rna kan s\u00f6kas i grafer med hundratusentals h\u00f6rn vid varje branching-steg.<\/p>\n

      Resultat<\/h3>\n

      Praktiken visar att min l\u00f6sning fungerar bra p\u00e5 tester med flera hundra h\u00f6rn och flera tusen kanter. P\u00e5 s\u00e5dana tester kan man rimligt f\u00f6rv\u00e4nta sig att l\u00f6sningen hittas inom en halvtimme. Sannolikheten att hitta ett svar inom rimlig tid \u00f6kar i princip om grafen har tillr\u00e4ckligt m\u00e5nga h\u00f6rn med h\u00f6g grad, till exempel grad 10 och upp\u00e5t.<\/p>\n

      F\u00f6r att delta i t\u00e4vlingen beh\u00f6vde vi skicka in v\u00e5ra l\u00f6sningar till optil.io<\/a><\/noindex>. Enligt den tabell som presenterades d\u00e4r tabell<\/a><\/noindex>, ligger min l\u00f6sning p\u00e5 \u00f6ppna tester p\u00e5 tredje plats av tjugo med stor marginal till andra plats. F\u00f6r att vara helt \u00e4rlig \u00e4r det inte helt klart hur l\u00f6sningarna kommer att bed\u00f6mas i sj\u00e4lva t\u00e4vlingen: till exempel, min l\u00f6sning klarar f\u00e4rre tester \u00e4n l\u00f6sningen p\u00e5 fj\u00e4rde plats, men de som den klarar g\u00e5r snabbare.<\/p>\n

      Resultaten p\u00e5 de st\u00e4ngda testerna kommer att bli k\u00e4nda den f\u00f6rsta juli.<\/p>\n

      K\u00e4lla: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

      \u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u044b \u0441 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 Software Engineering \u0438 Machine Learning \u0447\u0430\u0441\u0442\u043e \u0438\u0434\u0443\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u041d\u0418\u0420\u044b \u0432 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438 (\u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c, JetBrains \u0438\u043b\u0438 \u042f\u043d\u0434\u0435\u043a\u0441, \u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e). \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u043f\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e Computer Science. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":26562,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-35406","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Hur man l\u00f6ser NP-sv\u00e5ra problem med parametriserade algoritmer | ProHoster","description":"Forskningen \u00e4r f\u00f6rmodligen den mest intressanta delen av v\u00e5r utbildning. Id\u00e9n \u00e4r att redan p\u00e5 universitetet prova p\u00e5 det valda omr\u00e5det.","canonical_url":"https:\/\/prohoster.info\/sv\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sv_SE","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c NP-\u0442\u0440\u0443\u0434\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 | ProHoster","og:description":"\u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438.","og:url":"https:\/\/prohoster.info\/sv\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:04:08+00:00","article:modified_time":"2021-01-02T11:01:41+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"35406","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 23:06:35","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:03:22","updated":"2026-01-21 23:06:35","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}