{"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\/cs\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Jak \u0159e\u0161it NP-t\u011b\u017ek\u00e9 \u00falohy pomoc\u00ed parametrov\u00fdch algoritm\u016f","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

V\u00fdzkum je pravd\u011bpodobn\u011b tou nejzaj\u00edmav\u011bj\u0161\u00ed sou\u010d\u00e1st\u00ed na\u0161eho vzd\u011bl\u00e1v\u00e1n\u00ed. Idea spo\u010d\u00edv\u00e1 v tom, vyzkou\u0161et si je\u0161t\u011b na univerzit\u011b vybran\u00fd sm\u011br. Nap\u0159\u00edklad studenti z obor\u016f Software Engineering a Machine Learning \u010dasto d\u011blaj\u00ed v\u00fdzkumn\u00e9 projekty ve firm\u00e1ch (v\u011bt\u0161inou v JetBrains nebo Yandexu, ale nejen tam).<\/p>\n

V tomto p\u0159\u00edsp\u011bvku v\u00e1m pov\u00edm o sv\u00e9m projektu zam\u011b\u0159en\u00e9m na po\u010d\u00edta\u010dov\u00e9 v\u011bdy. V r\u00e1mci pr\u00e1ce jsem zkoumal a prakticky realizoval p\u0159\u00edstupy k \u0159e\u0161en\u00ed jednoho z nejzn\u00e1m\u011bj\u0161\u00edch NP-t\u011b\u017ek\u00fdch probl\u00e9m\u016f: probl\u00e9m pokryt\u00ed vrchol\u016f<\/b>.<\/p>\n

V posledn\u00ed dob\u011b se velmi rychle vyv\u00edj\u00ed zaj\u00edmav\u00fd p\u0159\u00edstup k NP-t\u011b\u017ek\u00fdm probl\u00e9m\u016fm \u2014 parametrizovan\u00e9 algoritmy. Pokus\u00edm se v\u00e1s zasv\u011btit do t\u00e9to problematiky, p\u0159edstav\u00edm n\u011bkolik z\u00e1kladn\u00edch parametrizovan\u00fdch algoritm\u016f a pop\u00ed\u0161u jeden siln\u00fd metod, kter\u00fd mi velmi pomohl. Sv\u00e9 v\u00fdsledky jsem p\u0159edstavil na sout\u011b\u017ei PACE Challenge: podle v\u00fdsledk\u016f otev\u0159en\u00fdch test\u016f moje \u0159e\u0161en\u00ed obsadilo t\u0159et\u00ed m\u00edsto, kone\u010dn\u00e9 v\u00fdsledky budou zn\u00e1my 1. \u010dervence.<\/p>\n

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

O mn\u011b<\/h3>\n

Jmenuji se Vasilij Alferov, moment\u00e1ln\u011b dokon\u010duji t\u0159et\u00ed rok na Vysok\u00e9 \u0161kole ekonomick\u00e9 \u2014 Petrohrad. Algoritmy m\u011b zaj\u00edmaj\u00ed u\u017e od \u0161koln\u00edch \u010das\u016f, kdy jsem studoval na moskevsk\u00e9 \u0161kole \u010d\u00edslo 179 a \u00fasp\u011b\u0161n\u011b se \u00fa\u010dastnil olympi\u00e1d z informatiky.<\/p>\n

Kone\u010dn\u00e9 mno\u017estv\u00ed specialist\u016f na parametrize algoritmy p\u0159ich\u00e1z\u00ed do baru\u2026<\/h3>\n

P\u0159\u00edklad je p\u0159evzat z knihy \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

P\u0159edstavte si, \u017ee jste vr\u00e1tn\u00fd v baru v mal\u00e9m m\u011bst\u011b. Ka\u017ed\u00fd p\u00e1tek polovina m\u011bsta p\u0159ich\u00e1z\u00ed do va\u0161eho baru odpo\u010d\u00edvat, co\u017e v\u00e1m d\u011bl\u00e1 nemal\u00e9 starosti: mus\u00edte vyhazovat divok\u00e9 n\u00e1v\u0161t\u011bvn\u00edky z baru, abyste zabr\u00e1nili bitk\u00e1m. Nakonec v\u00e1s to p\u0159est\u00e1v\u00e1 bavit a rozhodnete se p\u0159ijmout preventivn\u00ed opat\u0159en\u00ed.<\/p>\n

Proto\u017ee m\u00e1te mal\u00e9 m\u011bsto, p\u0159esn\u011b v\u00edte, kter\u00e9 p\u00e1ry n\u00e1v\u0161t\u011bvn\u00edk\u016f se s vysokou pravd\u011bpodobnost\u00ed poh\u00e1daj\u00ed, pokud se ocitnou v baru spolu. M\u00e1te seznam n<\/i> lid\u00ed, kte\u0159\u00ed p\u0159ijdou dnes ve\u010der do baru. Rozhodnete se nevpustit do baru n\u011bkter\u00e9 m\u00edstn\u00ed obyvatele tak, aby se nikdo nepobodal. Z\u00e1rove\u0148 va\u0161e veden\u00ed nechce p\u0159ij\u00edt o zisk a bude nespokojen\u00e9, pokud do baru nepust\u00edte v\u00edce ne\u017e k<\/i> lid\u00ed.<\/p>\n

Bohu\u017eel \u00fakol, kter\u00fd p\u0159ed v\u00e1mi stoj\u00ed, je klasick\u00fd NP-t\u011b\u017ek\u00fd probl\u00e9m. M\u011bli jste ho mo\u017en\u00e1 zn\u00e1t jako Vertex Cover<\/a><\/noindex>, nebo jak \u00falohu o vrcholov\u00e9m pokryt\u00ed. Pro takov\u00e9 \u00falohy obvykle neexistuj\u00ed algoritmy, kter\u00e9 by pracovaly v p\u0159ijateln\u00e9m \u010dase. Pokud budeme p\u0159esn\u00ed, tak nedok\u00e1zan\u00e1 a docela siln\u00e1 hypot\u00e9za ETH (Exponential Time Hypothesis) \u0159\u00edk\u00e1, \u017ee tato \u00faloha nen\u00ed \u0159e\u0161iteln\u00e1 za \u010das \"Jak, tedy \u017ee nen\u00ed nijak v\u00fdrazn\u011b lep\u0161\u00ed ne\u017e \u00fapln\u00e9 proch\u00e1zen\u00ed. Nap\u0159\u00edklad, pokud se k v\u00e1m do baru chyst\u00e1 p\u0159ij\u00edt n = 1000<\/i> lid\u00ed. Pot\u00e9 by \u00fapln\u00fd pr\u016fchod m\u011bl \"Jak variant, co\u017e je zhruba \"Jak \u2014 nesm\u00edrn\u011b mnoho. Na\u0161t\u011bst\u00ed v\u00e1m va\u0161e veden\u00ed stanovilo omezen\u00ed k = 10<\/i>, tak\u017ee po\u010det kombinac\u00ed, kter\u00e9 mus\u00edte proch\u00e1zet, je mnohem men\u0161\u00ed: po\u010det podmno\u017ein o deseti prvc\u00edch je roven \"Jak. To u\u017e je lep\u0161\u00ed, ale i tak to nevy\u010d\u00edt\u00e1te za den ani na v\u00fdkonn\u00e9m clusteru.
\n\"Jak
\nAby se vylou\u010dila pravd\u011bpodobnost h\u00e1dky p\u0159i takov\u00e9 konfiguraci napjat\u00fdch vztah\u016f mezi n\u00e1v\u0161t\u011bvn\u00edky baru, je nutn\u00e9 nepustit Boba, Daniela a Fjodora. \u0158e\u0161en\u00ed, kdy z\u016fstanou venku pouze dva, neexistuje.<\/p>\n

Znamen\u00e1 to, \u017ee je \u010das se vzd\u00e1t a vpustit v\u0161echny? Zv\u00e1\u017e\u00edme dal\u0161\u00ed mo\u017enosti. Nap\u0159\u00edklad m\u016f\u017eeme nepustit pouze ty, kdo pravd\u011bpodobn\u011b budou m\u00edt konflikt s velmi mnoha lidmi. Pokud se n\u011bkdo m\u016f\u017ee poprat alespo\u0148 s k + 1<\/i> dal\u0161\u00edmi lidmi, tak ho rozhodn\u011b pustit nelze \u2014 jinak budete muset nepustit v\u0161echny k + 1<\/i> obyvatele, se kter\u00fdmi m\u016f\u017ee m\u00edt konflikt, co\u017e ji\u017e ur\u010dit\u011b rozru\u0161\u00ed veden\u00ed.<\/p>\n

P\u0159edstavte si, \u017ee jste vyhodili v\u0161echny, kter\u00e9 jste mohli, podle tohoto principu. Pot\u00e9 mohou ostatn\u00ed m\u00edt konflikt maxim\u00e1ln\u011b s k<\/i> lidmi. Kdy\u017e z nich vyhod\u00edte k<\/i> lid\u00ed, m\u016f\u017eete zabr\u00e1nit maxim\u00e1ln\u011b \"Jak konflikt\u016fm. To znamen\u00e1, \u017ee pokud se v\u00edce ne\u017e \"Jak lid\u00ed \u00fa\u010dastn\u00ed alespo\u0148 jednoho konfliktu, jist\u011b nebudete moci zabr\u00e1nit v\u0161em. Jak je z\u0159ejm\u00e9, ty, kte\u0159\u00ed nejsou konfliktn\u00ed, ur\u010dit\u011b pust\u00edte, tak\u017ee mus\u00edte proj\u00edt v\u0161echny podmno\u017einy o velikosti deset ze dvou stovek lid\u00ed. T\u011bch je zhruba \"Jak, a takov\u00e9 mno\u017estv\u00ed operac\u00ed u\u017e lze projet na clusteru.<\/p>\n

Pokud je mo\u017en\u00e9 bezpe\u010dn\u011b vz\u00edt zcela nekonfliktn\u00ed osobnosti, co \u0159\u00edct o t\u011bch, kte\u0159\u00ed se \u00fa\u010dastn\u00ed jen jednoho konfliktu? Opravdu, i tyto m\u016f\u017eeme pustit dovnit\u0159, pokud zav\u0159eme dve\u0159e p\u0159ed jejich protivn\u00edkem. A vlastn\u011b, pokud Alice konfliktuje pouze s Bobem, tak kdy\u017e pust\u00edme Alici z t\u011bch dvou, neprohrajeme: Bob m\u016f\u017ee m\u00edt jin\u00e9 konflikty, zat\u00edmco Alice \u017e\u00e1dn\u00e9 ur\u010dit\u011b nem\u00e1. Nav\u00edc by pro n\u00e1s ned\u00e1valo smysl nepustit oba. Po takov\u00fdch operac\u00edch n\u00e1m zbyde maxim\u00e1ln\u011b \"Jak host\u016f s nevy\u0159e\u0161en\u00fdm osudem: celkem m\u00e1me \"Jak konflikt\u016f, v ka\u017ed\u00e9m jsou dva \u00fa\u010dastn\u00edci a ka\u017ed\u00fd se \u00fa\u010dastn\u00ed alespo\u0148 dvou. To znamen\u00e1, \u017ee mus\u00edme proj\u00edt pouze \"Jak varianty, co\u017e se d\u00e1 samoz\u0159ejm\u011b spo\u010d\u00edtat za p\u016fl dne na notebooku.<\/p>\n

Opravdu, jednoduch\u00fdmi \u00favahami m\u016f\u017eeme dos\u00e1hnout je\u0161t\u011b atraktivn\u011bj\u0161\u00edch podm\u00ednek. V\u0161imn\u011bme si, \u017ee nutn\u011b mus\u00edme vy\u0159e\u0161it v\u0161echny spory, tedy z ka\u017ed\u00e9 konfliktuj\u00edc\u00ed dvojice vybrat alespo\u0148 jednu osobu, kterou nepust\u00edme dovnit\u0159. Zva\u017eme takov\u00fd algoritmus: vezmeme jak\u00fdkoli konflikt, ze kter\u00e9ho odstran\u00edme jednoho \u00fa\u010dastn\u00edka a rekurzivn\u011b se pust\u00edme od zbytku, pot\u00e9 odstran\u00edme druh\u00e9ho a tak\u00e9 rekurzivn\u011b se pust\u00edme. Proto\u017ee na ka\u017ed\u00e9m kroku n\u011bkoho vylu\u010dujeme, strom rekurze tohoto algoritmu je bin\u00e1rn\u00ed strom hloubky k<\/i>, tak\u017ee celkov\u011b algoritmus pracuje za \"Jak, kde n<\/i> \u2013 po\u010det vrchol\u016f, a m<\/i> \u2013 po\u010det hran. V na\u0161em p\u0159\u00edkladu je to kolem deseti milion\u016f, co\u017e se za zlomek sekundy spo\u010d\u00edt\u00e1 nejen na notebooku, ale i na mobiln\u00edm telefonu.<\/p>\n

Uveden\u00fd p\u0159\u00edklad v\u00fd\u0161e je p\u0159\u00edkladem parametrizovan\u00e9ho algoritmu<\/b>. Parametrizovan\u00e9 algoritmy jsou algoritmy, kter\u00e9 pracuj\u00ed za \u010das f(k) poly(n)<\/i>, kde p<\/i> \u2013 polynom, f<\/i> \u2013 libovoln\u00e1 po\u010ditateln\u00e1 funkce, a k<\/i> \u2013 n\u011bjak\u00fd parametr, kter\u00fd m\u016f\u017ee b\u00fdt mnohem men\u0161\u00ed ne\u017e velikost \u00falohy.<\/p>\n

V\u0161echny \u00favahy do tohoto algoritmu vedou p\u0159\u00edklad kernelizace<\/b> \u2014 jednou z b\u011b\u017en\u00fdch technik pro vytv\u00e1\u0159en\u00ed parametrizovan\u00fdch algoritm\u016f. Kernelizace je zmen\u0161en\u00ed velikosti \u00falohy na hodnotu, kter\u00e1 je omezena funkc\u00ed od parametru. Z\u00edskanou \u00falohu \u010dasto naz\u00fdv\u00e1me j\u00e1drem. Tak jsme jednoduch\u00fdmi \u00favahami o stupn\u00edch vrchol\u016f z\u00edskali kvadratick\u00e9 j\u00e1dro pro \u00falohu Vertex Cover parametrizovanou velikost\u00ed odpov\u011bdi. Existuj\u00ed i jin\u00e9 parametry, kter\u00e9 lze zvolit pro tuto \u00falohu (nap\u0159\u00edklad Vertex Cover Above LP), ale budeme diskutovat pr\u00e1v\u011b o tomto parametru.<\/p>\n

Pace Challenge<\/h3>\n

Sout\u011b\u017e PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) vznikla v roce 2015, aby vytvo\u0159ila spojen\u00ed mezi parametrizovan\u00fdmi algoritmy a p\u0159\u00edstupy pou\u017e\u00edvan\u00fdmi v praxi k \u0159e\u0161en\u00ed v\u00fdpo\u010detn\u00edch \u00faloh. Prvn\u00ed t\u0159i sout\u011b\u017ee byly zam\u011b\u0159eny na hled\u00e1n\u00ed stromov\u00e9 \u0161\u00ed\u0159ky grafu (Treewidth<\/a><\/noindex>), hled\u00e1n\u00ed Steinertova stromu (Steiner Tree<\/a><\/noindex>) a hled\u00e1n\u00ed mno\u017einy vrchol\u016f, kter\u00e9 p\u0159ekrajuje cykly (Feedback Vertex Set<\/a><\/noindex>). V tomto roce jednou z \u00faloh, ve kter\u00fdch si mohli \u00fa\u010dastn\u00edci vyzkou\u0161et sv\u00e9 s\u00edly, byla v\u00fd\u0161e zm\u00edn\u011bn\u00e1 \u00faloha o vrcholov\u00e9m pokryt\u00ed.<\/p>\n

Sout\u011b\u017e ka\u017ed\u00fdm rokem z\u00edsk\u00e1v\u00e1 na popularit\u011b. Pokud se v\u011b\u0159\u00ed p\u0159edb\u011b\u017en\u00fdm \u00fadaj\u016fm, v tomto roce se v sout\u011b\u017ei zam\u011b\u0159en\u00e9 na \u0159e\u0161en\u00ed \u00falohy vrcholov\u00e9ho pokryt\u00ed \u00fa\u010dastnilo 24 t\u00fdm\u016f. Je t\u0159eba poznamenat, \u017ee sout\u011b\u017e netrv\u00e1 n\u011bkolik hodin ani t\u00fdden, ale n\u011bkolik m\u011bs\u00edc\u016f. T\u00fdmy maj\u00ed mo\u017enost prostudovat literaturu, vymyslet sv\u016fj origin\u00e1ln\u00ed n\u00e1pad a pokusit se jej realizovat. V podstat\u011b tato sout\u011b\u017e p\u0159edstavuje v\u00fdzkumnou pr\u00e1ci. N\u00e1pady nejefektivn\u011bj\u0161\u00edch \u0159e\u0161en\u00ed a vyhl\u00e1\u0161en\u00ed v\u00edt\u011bz\u016f prob\u011bhne spole\u010dn\u011b s konferenc\u00ed IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) v r\u00e1mci nejv\u011bt\u0161\u00edho ka\u017edoro\u010dn\u00edho algoritmick\u00e9ho setk\u00e1n\u00ed v Evrop\u011b ALGO<\/a><\/noindex>. Podrobn\u011bj\u0161\u00ed informace o samotn\u00e9 sout\u011b\u017ei lze nal\u00e9zt na webu<\/a><\/noindex>, zat\u00edmco v\u00fdsledky z minul\u00fdch let jsou k dispozici tady<\/a><\/noindex>.<\/p>\n

Sch\u00e9ma \u0159e\u0161en\u00ed<\/h3>\n

Aby se vypo\u0159\u00e1dal se probl\u00e9mem pokryt\u00ed vrchol\u016f, zkusil jsem pou\u017e\u00edt parametrizovan\u00e9 algoritmy. Obvykle se skl\u00e1daj\u00ed ze dvou \u010d\u00e1st\u00ed: pravidel zjednodu\u0161en\u00ed (kter\u00e1 ide\u00e1ln\u011b vedou k j\u00e1drov\u00e1n\u00ed) a pravidel d\u011blen\u00ed. Pravidla zjednodu\u0161en\u00ed jsou p\u0159edzpracov\u00e1n\u00ed vstupu v polynomi\u00e1ln\u00edm \u010dase. C\u00edlem pou\u017eit\u00ed t\u011bchto pravidel je p\u0159ev\u00e9st probl\u00e9m na ekvivalentn\u00ed probl\u00e9m men\u0161\u00ed velikosti. Pravidla zjednodu\u0161en\u00ed jsou nejn\u00e1kladn\u011bj\u0161\u00ed \u010d\u00e1st\u00ed algoritmu a aplikace t\u00e9to \u010d\u00e1sti vede ke celkov\u00e9mu \u010dasu b\u011bhu \"Jak nam\u00edsto jednoduch\u00e9ho polynomi\u00e1ln\u00edho \u010dasu. V na\u0161em p\u0159\u00edpad\u011b jsou pravidla d\u011blen\u00ed zalo\u017eena na tom, \u017ee pro ka\u017ed\u00fd vrchol je pot\u0159eba vz\u00edt bu\u010f jeho, nebo jeho souseda.<\/p>\n

Obecn\u00e1 sch\u00e9ma je takov\u00e1: pou\u017e\u00edv\u00e1me pravidla zjednodu\u0161en\u00ed, pak si vyb\u00edr\u00e1me n\u011bjak\u00fd vrchol a prov\u00e1d\u00edme dva rekurzivn\u00ed vol\u00e1n\u00ed: v prvn\u00edm bereme jeho jako odpov\u011b\u010f, a ve druh\u00e9m bereme v\u0161echny jeho sousedy. To naz\u00fdv\u00e1me d\u011blen\u00edm (branching) podle tohoto vrcholu.<\/p>\n

Do t\u00e9to sch\u00e9my bude p\u0159id\u00e1no p\u0159esn\u011b jedno dopln\u011bn\u00ed v n\u00e1sleduj\u00edc\u00edm odstavci.<\/p>\n

My\u0161lenky pro pravidla d\u011blen\u00ed (branching)<\/h3>\n

Poj\u010fme diskutovat, jak vybrat vrchol, podle kter\u00e9ho dojde k d\u011blen\u00ed.
\nHlavn\u00ed my\u0161lenka je velmi chtiv\u00e1 v algoritmick\u00e9m smyslu: vezm\u011bme vrchol s maxim\u00e1ln\u00edm stupn\u011bm a rozd\u011blme se pr\u00e1v\u011b podle n\u011bj. Pro\u010d se zd\u00e1, \u017ee je to lep\u0161\u00ed? Proto\u017ee ve druh\u00e9 v\u011btvi rekurzivn\u00edho vol\u00e1n\u00ed takto odstran\u00edme spoustu vrchol\u016f. M\u016f\u017eeme o\u010dek\u00e1vat, \u017ee z\u016fstane mal\u00fd graf a na n\u011bm budeme pracovat rychle.<\/p>\n

Tento p\u0159\u00edstup s ji\u017e projednan\u00fdmi jednoduch\u00fdmi technikami j\u00e1drov\u00e1n\u00ed se ukazuje jako slu\u0161n\u00fd, \u0159e\u0161\u00ed ur\u010dit\u00e9 testy o velikosti n\u011bkolika tis\u00edc vrchol\u016f. Ale nap\u0159\u00edklad \u0161patn\u011b funguje pro kubick\u00e9 grafy (tj. grafy, jejich\u017e stupe\u0148 ka\u017ed\u00e9ho vrcholu je t\u0159i).
\nJe tu je\u0161t\u011b jedna my\u0161lenka, vych\u00e1zej\u00edc\u00ed z pom\u011brn\u011b jednoduch\u00e9 my\u0161lenky: pokud je graf nespojen\u00fd, \u00falohu na jeho komponent\u00e1ch spojitosti lze \u0159e\u0161it nez\u00e1visle, a na konci spojit odpov\u011bdi. To je mimochodem mal\u00e1 sl\u00edben\u00e1 modifikace ve sch\u00e9matu, kter\u00e1 podstatn\u011b urychl\u00ed \u0159e\u0161en\u00ed: d\u0159\u00edve jsme v takov\u00e9m p\u0159\u00edpad\u011b pracovali za n\u00e1soben\u00ed \u010das\u016f po\u010d\u00edt\u00e1n\u00ed odpov\u011bd\u00ed komponent, a nyn\u00ed pracujeme za sou\u010det. A pro zrychlen\u00ed d\u011blen\u00ed je pot\u0159eba p\u0159ev\u00e9st spojit\u00fd graf na nespojen\u00fd.<\/p>\n

Jak to ud\u011blat? Pokud je v grafu bod rozv\u011btven\u00ed, je t\u0159eba rozv\u011btvit pr\u00e1v\u011b podle n\u011bj. Bod rozv\u011btven\u00ed je vrchol, jeho\u017e odstran\u011bn\u00ed zp\u016fsob\u00ed ztr\u00e1tu spojitosti grafu. V\u0161echny body rozv\u011btven\u00ed lze v grafu naj\u00edt klasikou algoritmem v line\u00e1rn\u00edm \u010dase. Tento p\u0159\u00edstup v\u00fdrazn\u011b urychluje rozv\u011btvov\u00e1n\u00ed.
\n\"Jak
\nP\u0159i odstran\u011bn\u00ed libovoln\u00e9ho z vyzna\u010den\u00fdch vrchol\u016f se graf rozpadne na komponenty spojitosti.<\/p>\n

To ud\u011bl\u00e1me, ale cht\u011bli bychom v\u00edce. Nap\u0159\u00edklad hledat v grafu mal\u00e9 vrcholov\u00e9 \u0159ezy a prov\u00e1d\u011bt rozd\u011blen\u00ed podle vrchol\u016f z n\u011bj. Nejefektivn\u011bj\u0161\u00ed zp\u016fsob, kter\u00fd zn\u00e1m pro nalezen\u00ed minim\u00e1ln\u00edho glob\u00e1ln\u00edho vrcholov\u00e9ho \u0159ezu, je vyu\u017eit\u00ed Gomorii-Huova stromu, kter\u00fd se stav\u00ed v kubick\u00e9m \u010dase. V PACE Challenge je typick\u00e1 velikost grafu n\u011bkolik tis\u00edc vrchol\u016f. P\u0159i tomto sc\u00e9n\u00e1\u0159i mus\u00ed b\u00fdt na ka\u017ed\u00e9m vrcholu rekurzivn\u00edho stromu provedeno miliardy operac\u00ed. Tak\u017ee vy\u0159e\u0161it \u00falohu v dan\u00e9m \u010dase je prost\u011b nemo\u017en\u00e9.<\/p>\n

Pokus\u00edme se optimalizovat \u0159e\u0161en\u00ed. Minim\u00e1ln\u00ed vrcholov\u00fd \u0159ez mezi dvojic\u00ed vrchol\u016f lze nal\u00e9zt jak\u00fdmkoliv algoritmem, kter\u00fd stav\u00ed maxim\u00e1ln\u00ed tok. M\u016f\u017eeme na takovou s\u00ed\u0165 aplikovat Dinic\u016fv algoritmus<\/a><\/noindex>, kter\u00fd v praxi funguje velmi rychle. M\u00e1m podez\u0159en\u00ed, \u017ee teoreticky lze dok\u00e1zat odhad na \u010dasovou slo\u017eitost \"Jak, co\u017e je u\u017e zcela p\u0159ijateln\u00e9.<\/p>\n

Zkou\u0161el jsem n\u011bkolikr\u00e1t hledat \u0159ezy mezi p\u00e1ry n\u00e1hodn\u00fdch vrchol\u016f a br\u00e1t z nich ten nejvyv\u00e1\u017een\u011bj\u0161\u00ed. Bohu\u017eel, na otev\u0159en\u00fdch testech PACE Challenge to p\u0159ineslo \u0161patn\u00e9 v\u00fdsledky. Porovn\u00e1val jsem s algoritmem, kter\u00fd se pokou\u0161el rozd\u011blit podle vrchol\u016f s maxim\u00e1ln\u00edm stupn\u011bm, spou\u0161t\u011bj\u00edc\u00edm je s omezen\u00edm na hloubku poklesu. Po algoritmu, kter\u00fd se sna\u017eil naj\u00edt \u0159ez t\u00edmto zp\u016fsobem, z\u016fst\u00e1valy grafy v\u011bt\u0161\u00edho rozm\u011bru. To souvis\u00ed s t\u00edm, \u017ee \u0159ezy byly velmi nevyv\u00e1\u017een\u00e9: odstran\u011bn\u00edm 5-10 vrchol\u016f bylo mo\u017en\u00e9 od\u0161t\u011bpit pouze 15-20.<\/p>\n

Je t\u0159eba si pov\u0161imnout, \u017ee v \u010dl\u00e1nc\u00edch o teoreticky nejrychlej\u0161\u00edch algoritmech se pou\u017e\u00edvaj\u00ed mnohem pokro\u010dilej\u0161\u00ed techniky v\u00fdb\u011bru vrchol\u016f pro d\u011blen\u00ed. Tyto techniky maj\u00ed velmi slo\u017eitou implementaci a \u010dasto \u0161patn\u00e9 odhady na \u010das a pam\u011b\u0165. Nepoda\u0159ilo se mi z nich vybrat zcela p\u0159ijateln\u00e9 pro praxi.<\/p>\n

Jak aplikovat pravidla zjednodu\u0161en\u00ed<\/h3>\n

U\u017e m\u00e1me n\u00e1pady na kernelizaci. P\u0159ipom\u00edn\u00e1m:<\/p>\n

    \n
  1. Pokud je vrchol izolovan\u00fd, je t\u0159eba jej odstranit.<\/li>\n
  2. Pokud existuje vrchol stupn\u011b 1, odstra\u0148te ho a vezm\u011bte jeho souseda jako odpov\u011b\u010f.<\/li>\n
  3. Pokud existuje vrchol stupn\u011b alespo\u0148 k + 1<\/i>, vezm\u011bte ho jako odpov\u011b\u010f.<\/li>\n<\/ol>\n

    Prvn\u00ed dva jsou jasn\u00ed, s t\u0159et\u00edm je jeden trik. Pokud jsme v vtipn\u00e9 \u00faloze o baru m\u011bli horn\u00ed omezen\u00ed na k<\/i>, v PACE Challenge mus\u00edme jednodu\u0161e naj\u00edt vrcholov\u00e9 pokryt\u00ed minim\u00e1ln\u00ed velikosti. To je typick\u00e1 transformace \u00faloh hled\u00e1n\u00ed (Search Problem) na \u00falohy rozhodov\u00e1n\u00ed (Decision Problem), \u010dasto se mezi t\u011bmito dv\u011bma typy \u00faloh ned\u011bl\u00e1 rozd\u00edl. V praxi, pokud p\u00ed\u0161eme \u0159e\u0161itel \u00falohy o vrcholov\u00e9m pokryt\u00ed, rozd\u00edl m\u016f\u017ee b\u00fdt. Nap\u0159\u00edklad v t\u0159et\u00edm bod\u011b.<\/p>\n

    Z pohledu implementace lze postupovat dv\u011bma zp\u016fsoby. Prvn\u00ed p\u0159\u00edstup se naz\u00fdv\u00e1 Iterative Deepening. Ten spo\u010d\u00edv\u00e1 v tom, \u017ee m\u016f\u017eeme za\u010d\u00edt s n\u011bjak\u00fdm rozumn\u00fdm doln\u00edm omezen\u00edm na odpov\u011b\u010f a pot\u00e9 spustit n\u00e1\u0161 algoritmus, pou\u017e\u00edvaj\u00edc\u00ed toto omezen\u00ed jako horn\u00ed omezen\u00ed na odpov\u011b\u010f, ani\u017e bychom se dostali do rekurze hloub\u011bji, ne\u017e na toto omezen\u00ed. Pokud jsme na\u0161li n\u011bjakou odpov\u011b\u010f, je zaru\u010den\u011b optim\u00e1ln\u00ed, jinak m\u016f\u017eeme toto omezen\u00ed zv\u00fd\u0161it o jednotku a znovu spustit.<\/p>\n

    Druh\u00fd p\u0159\u00edstup \u2013 uchov\u00e1vat n\u011bjakou aktu\u00e1ln\u00ed optim\u00e1ln\u00ed odpov\u011b\u010f a hledat odpov\u011b\u010f men\u0161\u00ed velikosti, p\u0159i nalezen\u00ed m\u011bn\u00edme tento parametr k<\/i> k v\u011bt\u0161\u00edmu otravov\u00e1n\u00ed nadbyte\u010dn\u00fdch v\u011btv\u00ed v hled\u00e1n\u00ed.<\/p>\n

    Po n\u011bkolika no\u010dn\u00edch experimentech jsem se zastavil na kombinaci t\u011bchto dvou zp\u016fsob\u016f: nejprve spust\u00edm sv\u016fj algoritmus s n\u011bjak\u00fdm omezen\u00edm na hloubku hled\u00e1n\u00ed (navrhuji ho tak, aby to trvalo zanedbateln\u00fd \u010das ve srovn\u00e1n\u00ed s hlavn\u00edm \u0159e\u0161en\u00edm) a pou\u017e\u00edv\u00e1m nejlep\u0161\u00ed nalezen\u00e9 \u0159e\u0161en\u00ed jako horn\u00ed omezen\u00ed na odpov\u011b\u010f \u2013 tedy na to pr\u00e1v\u011b k<\/i>.<\/p>\n

    Vrchol\u016fm stupn\u011b 2<\/h3>\n

    S vrcholy stupn\u011b 0 a 1 jsme se vypo\u0159\u00e1dali. Ukazuje se, \u017ee to lze ud\u011blat i s vrcholy stupn\u011b 2, ale pro to si graf vy\u017eaduje slo\u017eit\u011bj\u0161\u00ed operace.<\/p>\n

    Aby to bylo vysv\u011btleno, je pot\u0159eba n\u011bjak ozna\u010dit vrcholy. Ozna\u010dme vrchol stupn\u011b 2 jako vrchol v<\/i>, a jeho sousedy jako vrcholy x<\/i> a y<\/i>. D\u00e1le budeme m\u00edt dva p\u0159\u00edpady.<\/p>\n

      \n
    1. Kdy\u017e x<\/i> a y<\/i> \u2013 sousedy. Pak lze vz\u00edt jako odpov\u011b\u010f x<\/i> a y<\/i>, a v<\/i> odstranit. A opravdu, z tohoto troj\u00faheln\u00edku mus\u00ed b\u00fdt alespo\u0148 dva vrcholy vzaty jako odpov\u011b\u010f a rozhodn\u011b neprohrajeme, pokud vezmeme x<\/i> a y<\/i>: pravd\u011bpodobn\u011b maj\u00ed je\u0161t\u011b sousedy, ale v<\/i> oni nemaj\u00ed.<\/li>\n
    2. Kdy\u017e x<\/i> a y<\/i> \u2014 ne soused\u00e9. Pot\u00e9 se tvrd\u00ed, \u017ee v\u0161echny t\u0159i vrcholy lze spojit do jednoho. My\u0161lenka je v tom, \u017ee v takov\u00e9m p\u0159\u00edpad\u011b existuje optim\u00e1ln\u00ed odpov\u011b\u010f, ve kter\u00e9 vezmeme bu\u010f v<\/i>, nebo oba vrcholy x<\/i> a y<\/i>. V\u00fdslovn\u011b v prvn\u00edm p\u0159\u00edpad\u011b budeme muset vz\u00edt v\u0161echny sousedy x<\/i> a y<\/i>, zat\u00edmco ve druh\u00e9m to nen\u00ed nutn\u00e9. To p\u0159esn\u011b odpov\u00edd\u00e1 p\u0159\u00edpad\u016fm, kdy nesb\u00edr\u00e1me spojen\u00fd vrchol jako odpov\u011b\u010f a kdy ho sb\u00edr\u00e1me. Nyn\u00ed je t\u0159eba poznamenat, \u017ee v obou p\u0159\u00edpadech se odpov\u011b\u010f takov\u00e9 operace sni\u017euje o jednotku.<\/li>\n<\/ol>\n

      \"Jak<\/p>\n

      Stoj\u00ed za zm\u00ednku, \u017ee takov\u00fd p\u0159\u00edstup je p\u0159i dodr\u017een\u00ed \u010destn\u00e9ho line\u00e1rn\u00edho \u010dasu pom\u011brn\u011b obt\u00ed\u017en\u00e9 dokonale realizovat. Spojen\u00ed vrchol\u016f je slo\u017eit\u00e1 operace, je t\u0159eba zkop\u00edrovat seznamy soused\u016f. Pokud to ud\u011bl\u00e1te neopatrn\u011b, m\u016f\u017eete z\u00edskat asymptoticky suboptim\u00e1ln\u00ed \u010das pr\u00e1ce (nap\u0159\u00edklad pokud po ka\u017ed\u00e9m spojen\u00ed zkop\u00edrujete mnoho hran). Zastavil jsem se u hled\u00e1n\u00ed cel\u00fdch cest z vrchol\u016f s 2 stupni a analyzoval jsem celou \u0159adu speci\u00e1ln\u00edch p\u0159\u00edpad\u016f, jako jsou cykly z t\u011bchto vrchol\u016f nebo ze v\u0161ech takov\u00fdch vrchol\u016f krom\u011b jednoho.<\/p>\n

      Krom\u011b toho je t\u0159eba, aby tato operace byla vratn\u00e1, aby jsme b\u011bhem n\u00e1vratu z rekurze obnovili graf do p\u016fvodn\u00edho stavu. Pro zaji\u0161t\u011bn\u00ed toho jsem ne\u010distil seznamy hran spojen\u00fdch vrchol\u016f, po \u010dem\u017e jsem v\u011bd\u011bl, kter\u00e9 hrany kam nasm\u011brovat. Takov\u00e1 implementace graf\u016f tak\u00e9 vy\u017eaduje opatrnost, ale poskytuje \u010destn\u00fd line\u00e1rn\u00ed \u010das. A pro grafy s n\u011bkolika des\u00edtkami tis\u00edc hran u\u017e se vejde do mezipam\u011bti procesoru, co\u017e p\u0159in\u00e1\u0161\u00ed velk\u00e9 v\u00fdhody ve rychlosti.<\/p>\n

      Line\u00e1rn\u00ed j\u00e1dro<\/h3>\n

      Nakonec, nejzaj\u00edmav\u011bj\u0161\u00ed \u010d\u00e1st\u00ed j\u00e1dra.<\/p>\n

      Nejprve si vzpome\u0148me, \u017ee v bipartitn\u00edch grafech lze minim\u00e1ln\u00ed vrcholov\u00e9 pokryt\u00ed hledat za \"Jak. K tomu je t\u0159eba pou\u017e\u00edt algoritmus Hopcroft-Karp<\/a><\/noindex> pro nalezen\u00ed maxim\u00e1ln\u00ed p\u00e1rov\u00e9 p\u0159ihr\u00e1vky, a pot\u00e9 vyu\u017e\u00edt v\u011bty K\u00f6nig-Egerv\u00e1ry<\/a><\/noindex>.<\/p>\n

      My\u0161lenka line\u00e1rn\u00edho j\u00e1dra je n\u00e1sleduj\u00edc\u00ed: nejprve rozd\u011bl\u00edme graf, to znamen\u00e1, \u017ee m\u00edsto ka\u017ed\u00e9ho vrcholu v<\/i> vytvo\u0159\u00edme dva vrcholy \"Jak a \"Jak, a m\u00edsto ka\u017ed\u00e9 hrany u \u2014 v<\/i> vytvo\u0159\u00edme dv\u011b hrany \"Jak a \"JakZ\u00edskan\u00fd graf bude dvoud\u00edln\u00fd. Najdeme v n\u011bm minim\u00e1ln\u00ed vrcholov\u00e9 pokryt\u00ed. N\u011bkter\u00e9 vrcholy p\u016fvodn\u00edho grafu se tam dostanou dvakr\u00e1t, n\u011bkter\u00e9 pouze jednou a n\u011bkter\u00e9 ani jednou. V\u011bta Nemhausera-Trottera tvrd\u00ed, \u017ee v tomto p\u0159\u00edpad\u011b m\u016f\u017eeme odstranit vrcholy, kter\u00e9 se nedostaly ani jednou, a do odpov\u011bdi zahrnout ty, kter\u00e9 se dostaly dvakr\u00e1t. Nav\u00edc \u0159\u00edk\u00e1, \u017ee z zb\u00fdvaj\u00edc\u00edch vrchol\u016f (t\u011bch, kter\u00e9 se dostaly jednou) je t\u0159eba vz\u00edt alespo\u0148 polovinu.<\/p>\n

      Pr\u00e1v\u011b jsme se nau\u010dili ponechat v grafu maxim\u00e1ln\u011b 2k<\/i> vrchol\u016f. A skute\u010dn\u011b, pokud zb\u00fdv\u00e1 odpov\u011b\u010f \u2014 alespo\u0148 polovina v\u0161ech vrchol\u016f, pak celkov\u00fd po\u010det vrchol\u016f tam nen\u00ed v\u011bt\u0161\u00ed ne\u017e 2k<\/i>.<\/p>\n

      Tady se mi poda\u0159ilo ud\u011blat mal\u00fd krok vp\u0159ed. Je jasn\u00e9, \u017ee j\u00e1dro postaven\u00e9 t\u00edmto zp\u016fsobem z\u00e1vis\u00ed na tom, kter\u00e9 minim\u00e1ln\u00ed vrcholov\u00e9 pokryt\u00ed v dvoud\u00edln\u00e9m grafu jsme vzali. R\u00e1d bych vzal takov\u00e9, aby po\u010det zb\u00fdvaj\u00edc\u00edch vrchol\u016f byl minim\u00e1ln\u00ed. D\u0159\u00edve to \u0161lo ud\u011blat jen za \u010das \"Jak. Jsem v\u0161ak vymyslel implementaci tohoto algoritmu za \u010das \"Jak, tak\u017ee toto j\u00e1dro lze hledat na grafech s n\u011bkolika sty tis\u00edci vrcholy na ka\u017ed\u00e9m kroku v\u011btven\u00ed.<\/p>\n

      V\u00fdsledek<\/h3>\n

      Praxe ukazuje, \u017ee moje \u0159e\u0161en\u00ed dob\u0159e funguje na testech se stovkami vrchol\u016f a n\u011bkolika tis\u00edci hranami. Na takov\u00fdch testech je docela mo\u017en\u00e9 o\u010dek\u00e1vat, \u017ee \u0159e\u0161en\u00ed bude nalezeno za p\u016fl hodiny. Pravd\u011bpodobnost nalezen\u00ed odpov\u011bdi v p\u0159ijateln\u00e9m \u010dase obecn\u011b roste, pokud je v grafu dostate\u010dn\u011b mnoho vrchol\u016f s vysok\u00fdm stupn\u011bm, nap\u0159\u00edklad stupn\u011b 10 a v\u00edce.<\/p>\n

      Pro \u00fa\u010dast v sout\u011b\u017ei bylo t\u0159eba odeslat \u0159e\u0161en\u00ed na optil.io<\/a><\/noindex>. Podle uveden\u00e9 tabulky<\/a><\/noindex>, moje \u0159e\u0161en\u00ed na otev\u0159en\u00fdch testech obsazuje t\u0159et\u00ed m\u00edsto z dvaceti s velk\u00fdm odstupem od druh\u00e9ho. Pokud jsem \u00fapln\u011b up\u0159\u00edmn\u00fd, nen\u00ed \u00fapln\u011b jasn\u00e9, jak budou hodnocena \u0159e\u0161en\u00ed na samotn\u00e9 sout\u011b\u017ei: nap\u0159\u00edklad m\u00e9 \u0159e\u0161en\u00ed proch\u00e1z\u00ed m\u00e9n\u011b testy ne\u017e \u0159e\u0161en\u00ed na \u010dtvrt\u00e9m m\u00edst\u011b, ale na t\u011bch, kter\u00e9 proch\u00e1z\u00ed, pracuje rychleji.<\/p>\n

      V\u00fdsledky na uzav\u0159en\u00fdch testech se stanou zn\u00e1m\u00fdmi prvn\u00edho \u010dervence.<\/p>\n

      Zdroj: 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\udd47Jak \u0159e\u0161it NP-t\u011b\u017ek\u00e9 \u00falohy pomoc\u00ed parametrizovan\u00fdch algoritm\u016f | ProHoster","description":"V\u011bdecko-v\u00fdzkumn\u00e1 pr\u00e1ce je snad nejzaj\u00edmav\u011bj\u0161\u00ed \u010d\u00e1st\u00ed na\u0161eho vzd\u011bl\u00e1v\u00e1n\u00ed. My\u0161lenka je, \u017ee se u\u017e na univerzit\u011b zkus\u00edme v zvolen\u00e9m sm\u011bru.","canonical_url":"https:\/\/prohoster.info\/cs\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"cs_CZ","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\/cs\/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\/cs\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}