{"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\/ro\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Cum s\u0103 rezolvi problemele NP-difficult cu ajutorul algoritmilor parametrici","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Cercetarea \u0219tiin\u021bific\u0103 este, probabil, cea mai interesant\u0103 parte a \u00eenv\u0103\u021b\u0103m\u00e2ntului nostru. Ideea este de a \u00eencerca s\u0103 ne facem o experien\u021b\u0103 \u00een direc\u021bia aleas\u0103 \u00eenc\u0103 din timpul facult\u0103\u021bii. De exemplu, studen\u021bii de la specializ\u0103rile Software Engineering \u0219i Machine Learning merg adesea s\u0103 fac\u0103 lucr\u0103ri de cercetare \u00een companii (\u00een principal, JetBrains sau Yandex, dar nu numai).<\/p>\n

\u00cen acest post, voi povesti despre proiectul meu \u00een domeniul Computer Science. \u00cen cadrul lucr\u0103rii, am studiat \u0219i implementat practic abord\u0103rile pentru a rezolva una dintre cele mai cunoscute probleme NP-grele: problema acoperirii v\u00e2rfului<\/b>.<\/p>\n

\u00cen prezent, se dezvolt\u0103 foarte rapid o abordare interesant\u0103 pentru problemele NP-grele - algoritmii parametrici. Voi \u00eencerca s\u0103 v\u0103 introduc \u00een subiect, s\u0103 v\u0103 vorbesc despre c\u00e2\u021biva algoritmi parametrici simpli \u0219i s\u0103 descriu o metod\u0103 puternic\u0103 care m-a ajutat foarte mult. Rezultatele mele le-am prezentat la competi\u021bia PACE Challenge: de-a lungul testelor deschise, solu\u021bia mea ocup\u0103 locul trei, iar rezultatele finale vor fi cunoscute pe 1 iulie.<\/p>\n

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

Despre mine<\/h3>\n

M\u0103 numesc Vasili Alfiorev, acum finalizez anul trei la NIU HSE - Sankt Petersburg. M\u0103 pasioneaz\u0103 algoritmii \u00eenc\u0103 din \u0219coal\u0103, c\u00e2nd am studiat la \u0219coala 179 din Moscova \u0219i am participat cu succes la olimpiade de informatic\u0103.<\/p>\n

Un num\u0103r limitat de speciali\u0219ti \u00een algoritmi parametrici intr\u0103 \u00eentr-un bar\u2026<\/h3>\n

Exemplul este preluat din cartea \u201eAlgoritmi parametriza\u021bi\u201d<\/a><\/noindex><\/i><\/p>\n

Imagina\u021bi-v\u0103 c\u0103 sunte\u021bi un agent de securitate \u00eentr-un bar dintr-un ora\u0219 mic. \u00cen fiecare vineri, jum\u0103tate din ora\u0219 vine la barul dumneavoastr\u0103 pentru a se relaxa, ceea ce v\u0103 d\u0103 multe b\u0103t\u0103i de cap: trebuie s\u0103 expulza\u021bi clien\u021bii agita\u021bi pentru a preveni scandalurile. La un moment dat, v\u0103 s\u0103tura\u021bi de asta \u0219i decide\u021bi s\u0103 lua\u021bi m\u0103suri preventive.<\/p>\n

Deoarece ora\u0219ul dumneavoastr\u0103 este mic, \u0219ti\u021bi exact care perechi de clien\u021bi au o probabilitate mare s\u0103 se certe dac\u0103 ajung \u00eempreun\u0103 \u00een bar. Ave\u021bi o list\u0103 de n<\/i> oameni care vor veni \u00een seara asta \u00een bar. Deci, decide\u021bi s\u0103 nu l\u0103sa\u021bi s\u0103 intre anumi\u021bi cet\u0103\u021beni astfel \u00eenc\u00e2t nimeni s\u0103 nu se bat\u0103. \u00cen acela\u0219i timp, conducerea nu vrea s\u0103 piard\u0103 profitul \u0219i va fi nemul\u021bumit\u0103 dac\u0103 nu l\u0103sa\u021bi s\u0103 intre mai mult de k<\/i> oameni.<\/p>\n

Din p\u0103cate, problema cu care v\u0103 confrunta\u021bi este o problem\u0103 clasic\u0103 NP-grele. A\u021bi putea-o cunoa\u0219te ca Acoperirea v\u00e2rfului<\/a><\/noindex>, sau despre problema acoperirii v\u00e2rfului. Pentru astfel de probleme, \u00een general, nu exist\u0103 algoritmi care s\u0103 func\u021bioneze \u00eentr-un timp acceptabil. Dac\u0103 vrem s\u0103 fim precisi, atunci ipoteza ETH (Exponential Time Hypothesis), care nu a fost demonstrat\u0103, sugereaz\u0103 c\u0103 aceast\u0103 problem\u0103 nu poate fi rezolvat\u0103 \u00eentr-un timp \"Cum, adic\u0103 nu exist\u0103 nimic mai bun dec\u00e2t metoda de \u00eencercare exhaustiv\u0103. De exemplu, s\u0103 presupunem c\u0103 urmeaz\u0103 s\u0103 vin\u0103 n = 1000<\/i> de oameni \u00een bar. Atunci \u00eencercarea exhaustiv\u0103 ar genera \"Cum variante, ceea ce reprezint\u0103 aproximativ \"Cum \u2014 extrem de multe. Din fericire, conducerea dumneavoastr\u0103 v-a impus o limitare k = 10<\/i>, astfel c\u0103 num\u0103rul de combina\u021bii pe care trebuie s\u0103 le examina\u021bi este mult mai mic: num\u0103rul submul\u021bimilor din zece elemente este \"Cum. Aceasta este deja mai bine, dar tot nu va putea fi contabilizat \u00eentr-o zi, nici pe un cluster puternic.
\n\"Cum
\nPentru a exclude posibilitatea unei b\u0103t\u0103i \u00een aceast\u0103 configura\u021bie de rela\u021bii tensionate \u00eentre clien\u021bii barului, trebuie s\u0103 nu-l l\u0103sa\u021bi pe Bob, Daniel \u0219i Fiodor. Nu exist\u0103 solu\u021bii \u00een care s\u0103 r\u0103m\u00e2n\u0103 doar doi \u00een afar\u0103.<\/p>\n

Asta \u00eenseamn\u0103 c\u0103 ar trebui s\u0103 ne pred\u0103m \u0219i s\u0103-i l\u0103s\u0103m pe to\u021bi s\u0103 intre? S\u0103 lu\u0103m \u00een considerare alte op\u021biuni. De exemplu, am putea s\u0103 nu-i l\u0103s\u0103m doar pe cei care ar putea s\u0103 se bat\u0103 cu un num\u0103r foarte mare de oameni. Dac\u0103 cineva poate s\u0103 se bat\u0103 m\u0103car cu k + 1<\/i> alte persoane, atunci cu siguran\u021b\u0103 nu ar trebui s\u0103-l l\u0103s\u0103m s\u0103 intre \u2014 altfel va trebui s\u0103-i refuz\u0103m pe to\u021bi k + 1<\/i> ora\u0219enii cu care ar putea s\u0103 se bat\u0103, ceea ce va deranja cu siguran\u021b\u0103 conducerea.<\/p>\n

S\u0103 presupunem c\u0103 a\u021bi eliminat pe to\u021bi cei pe care \u00eei pute\u021bi, conform acestui principiu. Atunci to\u021bi ceilal\u021bi pot s\u0103 se bat\u0103 cu mai mult de k<\/i> oamenii. \u00cendep\u0103rt\u00e2nd din ei k<\/i> persoane, pute\u021bi preveni cu nu mai mult de \"Cum conflicte. Asta \u00eenseamn\u0103 c\u0103, dac\u0103 mai mult de \"Cum oameni particip\u0103 la m\u0103car un conflict, atunci cu siguran\u021b\u0103 nu ve\u021bi putea preveni toate. Deoarece, sper c\u0103 este evident, oamenii complet neconflicta\u021bi \u00eei ve\u021bi l\u0103sa cu siguran\u021b\u0103 s\u0103 intre, atunci trebuie s\u0103 examina\u021bi toate submul\u021bimile de dimensiune zece din dou\u0103 sute de oameni. Ace\u0219tia sunt aproximativ \"Cum, iar un astfel de num\u0103r de opera\u021biuni poate fi deja examinat pe un cluster.<\/p>\n

Dac\u0103 putem primi f\u0103r\u0103 probleme persoane care nu sunt \u00een conflict, ce ne facem cu cei care particip\u0103 la un singur conflict? De fapt, putem s\u0103-i primim \u0219i pe ei, \u00eenchiz\u00e2nd u\u0219a \u00een fa\u021ba adversarului. Adev\u0103rat, dac\u0103 Alice este \u00een conflict doar cu Bob, atunci, dac\u0103 \u00eel primim pe Alice, nu vom pierde: Bob ar putea avea alte conflicte, iar Alice cu siguran\u021b\u0103 nu are. Cu at\u00e2t mai mult, este lipsit de sens s\u0103 nu-i primim pe am\u00e2ndoi. Dup\u0103 astfel de opera\u021biuni, r\u0103m\u00e2n nu mai mult de \"Cum oaspe\u021bi cu soarta nerezolvat\u0103: \u00een total avem \"Cum conflicte, fiecare av\u00e2nd c\u00e2te dou\u0103 persoane implicate, iar fiecare particip\u00e2nd la cel pu\u021bin dou\u0103. Asta \u00eenseamn\u0103 c\u0103 r\u0103m\u00e2ne de evaluat doar \"Cum op\u021biuni, ceea ce poate fi calculat \u00een jum\u0103tate de zi pe un laptop.<\/p>\n

De fapt, prin ra\u021bionamente simple putem ob\u021bine condi\u021bii \u0219i mai atractive. S\u0103 observ\u0103m c\u0103 este esen\u021bial s\u0103 rezolv\u0103m toate disputele, adic\u0103 s\u0103 alegem din fiecare pereche \u00een conflict cel pu\u021bin o persoan\u0103 pe care nu o vom primi. S\u0103 lu\u0103m \u00een considerare un astfel de algoritm: s\u0103 lu\u0103m orice conflict, s\u0103 elimin\u0103m un participant \u0219i s\u0103 relu\u0103m recursiv de la rest, apoi s\u0103 elimin\u0103m pe cel\u0103lalt \u0219i s\u0103 facem la fel. Deoarece la fiecare pas elimin\u0103m pe cineva, arborele de recursivitate al acestui algoritm este un arbore binar de ad\u00e2ncime k<\/i>, deci algoritmul func\u021bioneaz\u0103 \u00een \"Cum, unde n<\/i> \u2014 num\u0103rul de v\u00e2rfuri \u0219i m<\/i> \u2014 num\u0103rul de muchii. \u00cen exemplul nostru, aceasta este \u00een jur de zece milioane, ceea ce poate fi calculat \u00een c\u00e2teva frac\u021biuni de secund\u0103, nu doar pe un laptop, ci chiar \u0219i pe un telefon mobil.<\/p>\n

Exemplul de mai sus este un exemplu de algoritm parametrizat<\/b>. Algoritmii parametriza\u021bi sunt algoritmi care func\u021bioneaz\u0103 \u00een timp f(k) poly(n)<\/i>, unde p<\/i> \u2014 polinom, f<\/i> \u2014 o func\u021bie calculabil\u0103 arbitrar\u0103, iar k<\/i> \u2014 un parametru care, foarte probabil, va fi mult mai mic dec\u00e2t dimensiunea problemei.<\/p>\n

Toate ra\u021bionamentele p\u00e2n\u0103 la acest algoritm ofer\u0103 exemplul kerneliz\u0103rii<\/b> \u2014 una dintre tehnicile comune pentru crearea algoritmilor parametriza\u021bi. Kernelizarea reprezint\u0103 reducerea dimensiunii unei sarcini la o valoare limitat\u0103 de o func\u021bie a parametrului. Sarcina ob\u021binut\u0103 este adesea denumit\u0103 nucleu. Astfel, din ra\u021bionamente simple despre gradele v\u00e2rfurilor, am ob\u021binut un nucleu quadratic pentru problema Vertex Cover, parametrizat\u0103 \u00een func\u021bie de dimensiunea r\u0103spunsului. Exist\u0103 \u0219i al\u021bi parametri care pot fi ale\u0219i pentru aceast\u0103 problem\u0103 (de exemplu, Vertex Cover Above LP), dar vom discuta exact acest parametru.<\/p>\n

Pace Challenge<\/h3>\n

Competi\u021bie PACE Challenge<\/a><\/noindex> (Provocarea Algoritmilor Parametriza\u021bi \u0219i Experimentele Computa\u021bionale) a fost \u00eenfiin\u021bat\u0103 \u00een 2015 pentru a stabili o leg\u0103tur\u0103 \u00eentre algoritmii parametriza\u021bi \u0219i abord\u0103rile utilizate \u00een practic\u0103 pentru a rezolva probleme computa\u021bionale. Primele trei competi\u021bii au fost dedicate g\u0103sirii l\u0103\u021bimii arborilor grafurilor (Treewidth<\/a><\/noindex>), g\u0103sirii arborelui lui Steiner (Steiner Tree<\/a><\/noindex>) \u0219i g\u0103sirii unui set de v\u00e2rfuri care taie ciclurile (Feedback Vertex Set<\/a><\/noindex>). \u00cen acest an, una dintre problemele \u00een care participan\u021bii au putut s\u0103 \u00ee\u0219i \u00eencerce for\u021bele a fost problema de acoperire a v\u00e2rfurilor men\u021bionat\u0103 mai sus.<\/p>\n

Competi\u021bia c\u00e2\u0219tig\u0103 popularitate de la an la an. Dac\u0103 ne baz\u0103m pe date preliminare, anul acesta, doar \u00een competi\u021bia de rezolvare a problemei de acoperire a v\u00e2rfurilor au participat 24 de echipe. Este important de men\u021bionat c\u0103 competi\u021bia nu dureaz\u0103 c\u00e2teva ore, nici m\u0103car o s\u0103pt\u0103m\u00e2n\u0103, ci c\u00e2teva luni. Echipele au oportunitatea de a studia literatura, de a veni cu o idee original\u0103 \u0219i de a \u00eencerca s\u0103 o implementeze. Practic, aceast\u0103 competi\u021bie reprezint\u0103 o munc\u0103 de cercetare. Ideile celor mai eficiente solu\u021bii \u0219i premierea c\u00e2\u0219tig\u0103torilor vor avea loc \u00een cadrul conferin\u021bei IPEC<\/a><\/noindex> (Simpozion Interna\u021bional pe Calcul Parametrizat \u0219i Exact) \u00een cadrul celei mai mari adun\u0103ri anuale de algoritmi din Europa ALGO<\/a><\/noindex>. Mai multe informa\u021bii despre competi\u021bie pot fi g\u0103site la site<\/a><\/noindex>, iar rezultatele anilor anteriori sunt disponibile aici<\/a><\/noindex>.<\/p>\n

Schema de solu\u021bie<\/h3>\n

Pentru a aborda problema acoperirii v\u00e2rfului, am \u00eencercat s\u0103 aplic algoritmi parametriza\u021bi. Ace\u0219tia constau, de obicei, din dou\u0103 p\u0103r\u021bi: reguli de simplificare (care ideal ar trebui s\u0103 conduc\u0103 la kernelizare) \u0219i reguli de ramificare. Reguli de simplificare sunt preprocesarea intr\u0103rii \u00eentr-un timp polinomial. Scopul aplic\u0103rii acestor reguli este reducerea problemei la o problem\u0103 echivalent\u0103 de dimensiuni mai mici. Reguli de simplificare reprezint\u0103 cea mai costisitoare parte a algoritmului, iar aplicarea acestei p\u0103r\u021bi duce la un timp total de execu\u021bie \"Cum \u00een loc de un timp polinomial simplu. \u00cen cazul nostru, regulile de ramificare se bazeaz\u0103 pe faptul c\u0103 pentru fiecare v\u00e2rf trebuie s\u0103 lu\u0103m \u00een considerare fie acesta, fie vecinul s\u0103u.<\/p>\n

Schema general\u0103 este urm\u0103toarea: aplic\u0103m regulile de simplificare, apoi alegem un v\u00e2rf \u0219i facem dou\u0103 apeluri recursive: \u00een primul lu\u0103m acest v\u00e2rf \u00een considerare, iar \u00een al doilea lu\u0103m to\u021bi vecinii s\u0103i. Asta numim a ne ramifica (branched) dup\u0103 acest v\u00e2rf.<\/p>\n

\u00cen aceast\u0103 schema va fi ad\u0103ugat exact o singur\u0103 completare \u00een urm\u0103torul paragraf.<\/p>\n

Idei pentru regulile de ramificare<\/h3>\n

S\u0103 discut\u0103m despre cum s\u0103 alegem v\u00e2rful pe care va avea loc ramificarea.
\nIdeea principal\u0103 este foarte avar\u0103 din punct de vedere algoritmic: s\u0103 lu\u0103m v\u00e2rful cu gradul maxim \u0219i s\u0103 ne ramific\u0103m exact pe acesta. De ce pare c\u0103 este mai bine a\u0219a? Pentru c\u0103 \u00een a doua ramur\u0103 a apelului recursiv astfel vom elimina foarte multe v\u00e2rfuri. Se poate estima c\u0103 va r\u0103m\u00e2ne un graf mic \u0219i vom lucra rapid pe acesta.<\/p>\n

Aceast\u0103 abordare, combinat\u0103 cu tehnicile simple de kernelizare discutate anterior, se dovede\u0219te a fi eficient\u0103, rezolv\u00e2nd teste de dimensiuni de c\u00e2teva mii de v\u00e2rfuri. Totu\u0219i, de exemplu, func\u021bioneaz\u0103 slab pentru grafuri cubice (adic\u0103 grafuri \u00een care gradul fiec\u0103rui v\u00e2rf este egal cu trei).
\nExist\u0103 \u0219i o alt\u0103 idee, bazat\u0103 pe o g\u00e2ndire destul de simpl\u0103: dac\u0103 graful este neconectat, problema pe componentele sale de conectivitate poate fi rezolvat\u0103 independent, combin\u00e2nd r\u0103spunsurile la final. Aceasta, de altfel, este modificarea promis\u0103 anterior \u00een schem\u0103, care va accelera semnificativ solu\u021bia: anterior, \u00een astfel de cazuri lucram cu produsul timpilor de calcul pentru r\u0103spunsurile componentelor, iar acum lucr\u0103m cu suma. Iar pentru a accelera ramificarea, trebuie s\u0103 transform\u0103m graful conectat \u00eentr-unul neconectat.<\/p>\n

Cum s\u0103 facem asta? Dac\u0103 \u00een grafic exist\u0103 un punct de articula\u021bie, trebuie s\u0103 ne bran\u0219\u0103m exact pe el. Punctul de articula\u021bie este un v\u00e2rf, iar eliminarea sa face ca graficul s\u0103 piard\u0103 conexiunea. Toate punctele de articula\u021bie dintr-un grafic pot fi g\u0103site folosind un algoritm clasic \u00een timp liniar. Aceast\u0103 abordare accelereaz\u0103 semnificativ bran\u0219area.
\n\"Cum
\nLa eliminarea oric\u0103rei dintre v\u00e2rfurile marcate, graficul se va descompune \u00een componente de conexiune.<\/p>\n

Acest lucru \u00eel vom face, dar ne dorim mai mult. De exemplu, s\u0103 c\u0103ut\u0103m \u00een grafic t\u0103ieturi mici de v\u00e2rf \u0219i s\u0103 efectu\u0103m descompunerea pe v\u00e2rfuri din acestea. Cea mai eficient\u0103 metod\u0103 pe care o cunosc pentru a g\u0103si t\u0103ietura minim\u0103 global\u0103 a v\u00e2rfului este utilizarea arborilor Gomory-Hu, care se construiesc \u00een timp cubic. \u00cen cadrul PACE Challenge, dimensiunea tipic\u0103 a graficului este de c\u00e2teva mii de v\u00e2rfuri. \u00cen aceste condi\u021bii, \u00een fiecare v\u00e2rf al recursivit\u0103\u021bii ar trebui s\u0103 execut\u0103m miliarde de opera\u021biuni. Se dovede\u0219te c\u0103 este pur \u0219i simplu imposibil s\u0103 rezolv\u0103m problema \u00een timpul alocat.<\/p>\n

S\u0103 \u00eencerc\u0103m s\u0103 optimiz\u0103m solu\u021bia. T\u0103ietura minim\u0103 a v\u00e2rfului \u00eentre o pereche de v\u00e2rfuri poate fi g\u0103sit\u0103 cu orice algoritm care construie\u0219te fluxul maxim. Putem rula un asemenea algoritm pe o astfel de re\u021bea algoritmul lui Dinic<\/a><\/noindex>, \u00een practic\u0103 acesta func\u021bioneaz\u0103 foarte rapid. Am o suspiciune c\u0103 teoretic se poate demonstra o estimare a timpului de execu\u021bie \"Cum, care este deja destul de acceptabil.<\/p>\n

Am \u00eencercat de mai multe ori s\u0103 caut t\u0103ieturi \u00eentre perechi de v\u00e2rfuri aleatoare \u0219i s\u0103 iau cea mai bine echilibrat\u0103. Din p\u0103cate, \u00een testele deschise ale PACE Challenge, acest lucru a dat rezultate slabe. Am comparat cu un algoritm care s-a concentrat pe v\u00e2rfurile cu grad maxim, rul\u00e2ndu-l cu o limitare a ad\u00e2ncimii de c\u0103utare. Dup\u0103 algoritmul care a \u00eencercat s\u0103 g\u0103seasc\u0103 t\u0103ietura \u00een acest fel, au r\u0103mas grafuri mai mari. Aceasta se datoreaz\u0103 faptului c\u0103 t\u0103ieturile ob\u021binute erau foarte dezechilibrate: elimin\u00e2nd 5-10 v\u00e2rfuri, reu\u0219eam s\u0103 \u00eendep\u0103rtez doar 15-20.<\/p>\n

Merit\u0103 observat c\u0103 \u00een articolele despre cele teoretic cele mai rapide algoritme sunt folosite tehnici de selec\u021bie a v\u00e2rfurilor mult mai avansate pentru descompunere. Aceste tehnici au o implementare foarte complex\u0103 \u0219i de multe ori evalu\u0103ri slabe \u00een ceea ce prive\u0219te timpul \u0219i memoria. Nu am reu\u0219it s\u0103 extrag dintre ele ceva acceptabil pentru practic\u0103.<\/p>\n

Cum s\u0103 aplic\u0103m regulile de simplificare<\/h3>\n

Avem deja idei de kernelizare. \u00cemi amintesc:<\/p>\n

    \n
  1. Dac\u0103 exist\u0103 un v\u00e2rf izolat, elimin\u0103-l.<\/li>\n
  2. Dac\u0103 exist\u0103 un v\u00e2rf de grad 1, \u00eel elimin\u0103m \u0219i lu\u0103m vecinul s\u0103u ca r\u0103spuns.<\/li>\n
  3. Dac\u0103 exist\u0103 un v\u00e2rf de grad cel pu\u021bin k + 1<\/i>, \u00eel lu\u0103m ca r\u0103spuns.<\/li>\n<\/ol>\n

    Cu primele dou\u0103 e totul clar, dar cu a treia exist\u0103 o mic\u0103 \u0219mecherie. Dac\u0103 \u00een problema glumei cu barul ni s-a dat o limit\u0103 superioar\u0103 pe k<\/i>, \u00een PACE Challenge trebuie doar s\u0103 g\u0103sim o acoperire minim\u0103 a v\u00e2rfurilor. Aceasta este o transformare tipic\u0103 a problemelor de c\u0103utare (Search Problem) \u00een probleme de decizie (Decision Problem), adesea \u00eentre cele dou\u0103 tipuri de probleme nu se face distinc\u021bie. \u00cen practic\u0103, dac\u0103 scrii un rezolvitor pentru problema acoperirii v\u00e2rfurilor, diferen\u021ba poate fi semnificativ\u0103. De exemplu, ca \u00een punctul trei.<\/p>\n

    Din perspectiva implement\u0103rii, se pot folosi dou\u0103 metode. Primul abordare se nume\u0219te Iterative Deepening. Acesta const\u0103 \u00een: putem \u00eencepe cu o limit\u0103 inferioar\u0103 rezonabil\u0103 pentru r\u0103spuns \u0219i apoi s\u0103 rulez algoritmul nostru, utiliz\u00e2nd aceast\u0103 limit\u0103 ca limit\u0103 superioar\u0103 a r\u0103spunsului, f\u0103r\u0103 a cobor\u00ee \u00een recursie mai jos dec\u00e2t aceast\u0103 limit\u0103. Dac\u0103 am g\u0103sit un r\u0103spuns, acesta este garantat optim, altfel putem cre\u0219te aceast\u0103 limit\u0103 cu unu \u0219i s\u0103 relu\u0103m executarea.<\/p>\n

    Cealalt\u0103 abordare este de a p\u0103stra un r\u0103spuns optim curent \u0219i de a c\u0103uta un r\u0103spuns de dimensiune mai mic\u0103, modific\u00e2nd acest parametru atunci c\u00e2nd este g\u0103sit k<\/i> pentru a reduce ramific\u0103rile inutile \u00een c\u0103utare.<\/p>\n

    Dup\u0103 c\u00e2teva experimente nocturne, m-am oprit la combina\u021bia acestor dou\u0103 metode: mai \u00eent\u00e2i, \u00eemi rulez algoritmul cu o limit\u0103 asupra ad\u00e2ncimii c\u0103ut\u0103rii (ajust\u00e2nd-o astfel \u00eenc\u00e2t s\u0103 dureze un timp neglijabil \u00een compara\u021bie cu solu\u021bia principal\u0103) \u0219i folosesc cea mai bun\u0103 solu\u021bie g\u0103sit\u0103 ca limit\u0103 superioar\u0103 a r\u0103spunsului \u2014 adic\u0103 aceea k<\/i>.<\/p>\n

    V\u00e2rfurile de grad 2<\/h3>\n

    Ne-am clarificat cu v\u00e2rfurile de grad 0 \u0219i 1. Se pare c\u0103 este posibil s\u0103 facem acela\u0219i lucru \u0219i cu v\u00e2rfurile de grad 2, dar pentru aceasta grafurile vor necesita opera\u021bii mai complexe.<\/p>\n

    Pentru a explica acest lucru, trebuie cumva s\u0103 desemn\u0103m v\u00e2rfurile. S\u0103 numim un v\u00e2rf de grad 2 v\u00e2rf v<\/i>, iar vecinii s\u0103i \u2014 v\u00e2rfuri x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i>. Apoi, vom avea dou\u0103 cazuri.<\/p>\n

      \n
    1. C\u00e2nd x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i> \u2014 vecinii. Atunci putem lua ca r\u0103spuns x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i>, iar v<\/i> elimin\u0103m. \u0218i, \u00eentr-adev\u0103r, din acest triunghi, trebuie s\u0103 lu\u0103m cel pu\u021bin dou\u0103 v\u00e2rfuri ca r\u0103spuns \u0219i cu siguran\u021b\u0103 nu vom pierde dac\u0103 lu\u0103m x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i>: probabil mai au vecini, iar v<\/i> ace\u0219tia nu au.<\/li>\n
    2. C\u00e2nd x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i> \u2014 nu vecinii. Atunci se afirm\u0103 c\u0103 toate cele trei v\u00e2rfuri pot fi unite \u00eentr-unul singur. Ideea este c\u0103, \u00een acest caz, exist\u0103 un r\u0103spuns optim, \u00een care vom lua fie v<\/i>, fie ambele v\u00e2rfuri x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i>. \u00cens\u0103, \u00een primul caz, va trebui s\u0103 lu\u0103m \u00een considerare to\u021bi vecinii x<\/i> \u0219i Stabili\u021bi o parol\u0103 \u0219i p\u0103stra\u021bi-o \u00een siguran\u021b\u0103!<\/i>, iar \u00een al doilea nu este neap\u0103rat. Acest lucru corespunde exact cazurilor c\u00e2nd nu lu\u0103m \u00een considerare v\u00e2rful unit \u0219i c\u00e2nd \u00eel lu\u0103m. R\u0103m\u00e2ne doar s\u0103 observ\u0103m c\u0103 \u00een ambele cazuri r\u0103spunsul acestei opera\u021bii scade cu unu.<\/li>\n<\/ol>\n

      \"Cum<\/p>\n

      Merit\u0103 men\u021bionat c\u0103 aceast\u0103 abordare este destul de greu de implementat cu precizie \u00eentr-un timp liniar corect. Unirea v\u00e2rfurilor este o opera\u021bie complex\u0103, trebuie s\u0103 copi\u0435m listele vecinilor. Dac\u0103 nu ne ocup\u0103m cu aten\u021bie, putem ob\u021bine un timp de execu\u021bie asimptotic suboptimal (de exemplu, dac\u0103 dup\u0103 fiecare unire copiem multe arce). M-am oprit pe c\u0103utarea de c\u0103i \u00eentregi din v\u00e2rfuri de gradul 2 \u0219i analiza multor cazuri particulare, precum cicluri din astfel de v\u00e2rfuri sau din toate acele v\u00e2rfuri, cu excep\u021bia unuia.<\/p>\n

      \u00cen plus, trebuie s\u0103 ne asigur\u0103m c\u0103 aceast\u0103 opera\u021bie este reversibil\u0103, astfel \u00eenc\u00e2t \u00een timpul revenirii din recursivitate s\u0103 refacem graful \u00een forma sa ini\u021bial\u0103. Pentru a asigura acest lucru, nu am cur\u0103\u021bat listelor de arce ale v\u00e2rfurilor unite, dup\u0103 care \u0219tiam pur \u0219i simplu care arce trebuie s\u0103 fie direc\u021bionate. Aceast\u0103 implementare a grafurilor necesit\u0103, de asemenea, aten\u021bie, dar asigur\u0103 un timp liniar corect. Iar pentru grafuri cu c\u00e2teva zeci de mii de arce, se \u00eencadreaz\u0103 perfect \u00een cache-ul procesorului, ceea ce ofer\u0103 avantaje semnificative de vitez\u0103.<\/p>\n

      Nucleul liniar<\/h3>\n

      \u00cen final, cea mai interesant\u0103 parte a nucleului.<\/p>\n

      Pentru \u00eenceput, s\u0103 ne amintim c\u0103 \u00een grafurile bipartite, acoperirea minim\u0103 a v\u00e2rfurilor poate fi c\u0103utat\u0103 \u00een \"Cum. Pentru aceasta, trebuie folosit algoritmul Hopcroft-Karp<\/a><\/noindex> pentru a g\u0103si acolo o pereche maxim\u0103, apoi s\u0103 folosim teorema K\u00f6nig-Egervari<\/a><\/noindex>.<\/p>\n

      Ideea nucleului liniar este urm\u0103toarea: mai \u00eent\u00e2i descompunem graful, adic\u0103 \u00een locul fiec\u0103rui v\u00e2rf v<\/i> cre\u0103m dou\u0103 v\u00e2rfuri \"Cum \u0219i \"Cum, iar \u00een locul fiec\u0103rui arc u \u2014 v<\/i> cre\u0103m dou\u0103 arce \"Cum \u0219i \"CumGraful ob\u021binut va fi bipartit. S\u0103 g\u0103sim o acoperire minim\u0103 a v\u00e2rfului. Unele v\u00e2rfuri din graful ini\u021bial vor ap\u0103rea de dou\u0103 ori, altele o singur\u0103 dat\u0103, iar unele \u2013 deloc. Teorema Nemhauser-Trotter afirm\u0103 c\u0103 \u00een acest caz putem elimina v\u00e2rfurile care nu au ap\u0103rut deloc \u0219i s\u0103 lu\u0103m \u00een considerare pe cele care au ap\u0103rut de dou\u0103 ori. Mai mult, aceasta spune c\u0103 dintre v\u00e2rfurile r\u0103mase (cele care au ap\u0103rut o singur\u0103 dat\u0103) trebuie s\u0103 lu\u0103m \u00een considerare cel pu\u021bin jum\u0103tate.<\/p>\n

      Tocmai am \u00eenv\u0103\u021bat s\u0103 l\u0103s\u0103m \u00een grafic nu mai mult de 2k<\/i> v\u00e2rfuri. \u0218i, \u00eentr-adev\u0103r, dac\u0103 \u00een r\u0103spunsul r\u0103mas se afl\u0103 cel pu\u021bin jum\u0103tate din toate v\u00e2rfurile, atunci \u00een total nu pot fi mai multe v\u00e2rfuri dec\u00e2t 2k<\/i>.<\/p>\n

      Aici am reu\u0219it s\u0103 fac un mic pas \u00eenainte. Este clar c\u0103 nucleul construit astfel depinde de ce acoperire minim\u0103 a v\u00e2rfului din graful bipartit am ales. \u00cemi doresc s\u0103 aleg astfel \u00eenc\u00e2t num\u0103rul v\u00e2rfurilor r\u0103mase s\u0103 fie minim. \u00cen trecut, acest lucru se putea face doar \u00een timpul \"Cum. Eu am g\u0103sit o implementare a acestui algoritm \u00een timp \"Cum, astfel \u00eenc\u00e2t acest nucleu poate fi c\u0103utat \u00een grafuri cu sute de mii de v\u00e2rfuri \u00een fiecare etap\u0103 a ramific\u0103rii.<\/p>\n

      Rezultatul<\/h3>\n

      Practic, solu\u021bia mea func\u021bioneaz\u0103 bine pe teste cu c\u00e2teva sute de v\u00e2rfuri \u0219i c\u00e2teva mii de muchii. Pe astfel de teste, este destul de realist s\u0103 ne a\u0219tept\u0103m c\u0103 solu\u021bia va fi g\u0103sit\u0103 \u00een jum\u0103tate de or\u0103. Probabilitatea g\u0103sirii unei solu\u021bii \u00eentr-un timp acceptabil cre\u0219te, de principiu, dac\u0103 \u00een grafic sunt destul de multe v\u00e2rfuri de grad mare, de exemplu, grad 10 sau mai mult.<\/p>\n

      Pentru a participa la competi\u021bie, solu\u021biile trebuiau trimise la optil.io<\/a><\/noindex>. Judec\u00e2nd dup\u0103 tabloul prezentat acolo , solu\u021bia mea pe testele deschise ocup\u0103 locul trei din dou\u0103zeci, cu un avans mare fa\u021b\u0103 de locul doi. Dac\u0103 vreau s\u0103 fiu complet onest, nu este foarte clar cum vor fi evaluate solu\u021biile la concursul propriu-zis: de exemplu, solu\u021bia mea trece prin mai pu\u021bine teste dec\u00e2t solu\u021bia de pe locul patru, dar pe cele prin care trece, func\u021bioneaz\u0103 mai repede.<\/a><\/noindex>Rezultatele pe testele \u00eenchise vor fi cunoscute pe 1 iulie.<\/p>\n

      Cercetarea \u0219tiin\u021bific\u0103, probabil, este cea mai interesant\u0103 parte a studiului nostru. Ideea este s\u0103 \u00eencerc\u0103m \u00eenc\u0103 din universitate s\u0103 ne test\u0103m abilit\u0103\u021bile \u00een direc\u021bia aleas\u0103.<\/p>\n

      Sursa: 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\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\udd47Cum s\u0103 rezolvi problemele NP-dificile cu ajutorul algoritmilor parametriza\u021bi | ProHoster","description":"\ud83e\udd47Cum s\u0103 rezolvi problemele NP-dificile cu ajutorul algoritmilor parametriza\u021bi | ProHoster","canonical_url":"https:\/\/prohoster.info\/ro\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"ro_RO","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\/ro\/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\/ro\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}