{"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\/hu\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Hogyan lehet NP-nehezen megoldhat\u00f3 feladatokat param\u00e9terezett algoritmusokkal megoldani","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

A tudom\u00e1nyos kutat\u00e1s tal\u00e1n a legizgalmasabb r\u00e9sze a tanulm\u00e1nyainknak. Az \u00f6tlet az, hogy m\u00e9g az egyetemen pr\u00f3b\u00e1ljuk ki magunkat a v\u00e1lasztott ir\u00e1nyban. P\u00e9ld\u00e1ul a Software Engineering \u00e9s Machine Learning szakos hallgat\u00f3k gyakran v\u00e9geznek kutat\u00e1si projekteket k\u00fcl\u00f6nb\u00f6z\u0151 c\u00e9gekn\u00e9l (f\u0151k\u00e9nt a JetBrainsn\u00e9l vagy a Yandexn\u00e9l, de nem csak ott).<\/p>\n

Ebben a bejegyz\u00e9sben a Computer Science ir\u00e1ny\u00fa projektemr\u0151l fogok besz\u00e9lni. A munka keret\u00e9ben megvizsg\u00e1ltam \u00e9s gyakorlatba \u00fcltettem a megold\u00e1sok megk\u00f6zel\u00edt\u00e9seit az egyik legismertebb NP-neh\u00e9z feladatban: a cs\u00facsbor\u00edt\u00e1ssal kapcsolatos feladatban<\/b>.<\/p>\n

Jelenleg rendk\u00edv\u00fcl gyorsan fejl\u0151dik egy \u00e9rdekes megk\u00f6zel\u00edt\u00e9s az NP-neh\u00e9z probl\u00e9m\u00e1khoz \u2014 a param\u00e9terezett algoritmusok. Megpr\u00f3b\u00e1lom bevezetni \u00f6n\u00f6ket a t\u00e9m\u00e1ba, mes\u00e9lni n\u00e9h\u00e1ny egyszer\u0171 param\u00e9terezett algoritmusr\u00f3l, \u00e9s egy hat\u00e9kony m\u00f3dszert bemutatni, amely nagyon seg\u00edtett nekem. Az eredm\u00e9nyeimet a PACE Challenge versenyen mutattam be: a ny\u00edlt tesztek eredm\u00e9nyei szerint a megold\u00e1som a harmadik helyen \u00e1ll, \u00e9s a v\u00e9gs\u0151 eredm\u00e9nyekre j\u00falius 1-j\u00e9n der\u00fcl f\u00e9ny.<\/p>\n

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

R\u00f3lam<\/h3>\n

Vasiliy Alferov vagyok, jelenleg a harmadik \u00e9vet v\u00e9gzem a HSE - Szentp\u00e9terv\u00e1ri Egyetemen. Az algoritmusok ir\u00e1nti \u00e9rdekl\u0151d\u00e9sem m\u00e9g iskol\u00e1s koromban kezd\u0151d\u00f6tt, amikor a moszkvai 179. iskol\u00e1ba j\u00e1rtam, \u00e9s sikeresen r\u00e9szt vettem informatikai versenyeken.<\/p>\n

A v\u00e9gs\u0151 sz\u00e1m\u00fa param\u00e9terezett algoritmusok szak\u00e9rt\u0151i bemennek a b\u00e1rba\u2026<\/h3>\n

A p\u00e9lda a k\u00f6nyvb\u0151l sz\u00e1rmazik \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

K\u00e9pzelje el, hogy \u00f6n a b\u00e1r biztons\u00e1gi \u0151re egy kisv\u00e1rosban. Minden p\u00e9nteken a v\u00e1ros fele a b\u00e1rj\u00e1ba j\u00f6n laz\u00edtani, ami sok gondot okoz \u00f6nnek: ki kell dobnia a rekedtes l\u00e1togat\u00f3kat, hogy elker\u00fclje a vereked\u00e9seket. V\u00e9g\u00fcl m\u00e1r eleged van, \u00e9s \u00fagy d\u00f6ntesz, hogy megel\u0151z\u0151 int\u00e9zked\u00e9seket teszel.<\/p>\n

Mivel a v\u00e1ros kicsi, pontosan tudja, hogy kik azok a l\u00e1togat\u00f3k, akik nagy val\u00f3sz\u00edn\u0171s\u00e9ggel \u00f6ssze fognak verekedni, ha egy\u00fctt ker\u00fclnek a b\u00e1rba. Van egy list\u00e1ja n<\/i> emberekr\u0151l, akik ma este a b\u00e1rba j\u00f6nnek. \u00dagy d\u00f6nt, hogy nem enged be bizonyos v\u00e1rosbelieket, \u00fagy, hogy senki se verekedjen meg. K\u00f6zben a f\u0151n\u00f6ke nem szeretne profitot vesz\u00edteni, \u00e9s el\u00e9gedetlen lesz, ha nem enged be t\u00f6bb mint k<\/i> embert.<\/p>\n

Sajnos a feladat, amely el\u0151tt \u00e1ll, klasszikus NP-neh\u00e9z feladat. Tal\u00e1n ismeri ezt mint Vertex Cover<\/a><\/noindex>, vagyis a cs\u00facsbor\u00edt\u00e1ssal kapcsolatos feladat. Az ilyen feladatokra \u00e1ltal\u00e1noss\u00e1gban nem ismertek olyan algoritmusok, amelyek elfogadhat\u00f3 id\u0151 alatt m\u0171k\u00f6dnek. Pontosan megfogalmazva, a nem bizony\u00edtott \u00e9s meglehet\u0151sen er\u0151s ETH (Exponenci\u00e1lis Id\u0151hipot\u00e9zis) azt \u00e1ll\u00edtja, hogy ezt a feladatot nem lehet megoldani \"Hogyan, vagyis hogy nem l\u00e9tezik szignifik\u00e1nsan jobb megold\u00e1s, mint a teljes keres\u00e9s. P\u00e9ld\u00e1ul, tegy\u00fck fel, hogy a b\u00e1rba n = 1000<\/i> ember k\u00e9sz\u00fcl \u00e9rkezni. Akkor a teljes keres\u00e9s \"Hogyan kukucsk\u00e1l\u00e1sra \"Hogyan \u2014 \u0151r\u00fclt sok. Szerencs\u00e9re, az ir\u00e1ny\u00edt\u00e1s korl\u00e1toz\u00e1st \u00e1ll\u00edtott fel \u00d6n sz\u00e1m\u00e1ra k = 10<\/i>, \u00edgy a kombin\u00e1ci\u00f3k sz\u00e1ma sokkal kevesebb: t\u00edz elem r\u00e9szhalmazainak sz\u00e1ma \"Hogyan. Ez m\u00e1r jobb, de m\u00e9g mindig nem lehet nap alatt kisz\u00e1molni m\u00e9g egy er\u0151teljes klaszteren sem.
\n\"Hogyan
\nAnnak \u00e9rdek\u00e9ben, hogy kiz\u00e1rjuk a vereked\u00e9s lehet\u0151s\u00e9g\u00e9t a l\u00e1togat\u00f3k k\u00f6z\u00f6tti ilyen fesz\u00fclts\u00e9ges konfigu\u00e1ci\u00f3 eset\u00e9n, Bobot, Danielt \u00e9s Fyodorot nem szabad beengedni. Olyan megold\u00e1s, amelyben csak ketten maradnak kinn, nem l\u00e9tezik.<\/p>\n

Jelenti ez, hogy fel kell adnunk \u00e9s be kell engedn\u00fcnk mindenkit? Vizsg\u00e1ljunk meg m\u00e1s lehet\u0151s\u00e9geket. P\u00e9ld\u00e1ul, tal\u00e1n nem engedhetn\u00e9nk be csak azokat, akik val\u00f3sz\u00edn\u0171leg sok emberrel fognak verekedni. Ha valaki legal\u00e1bb k + 1<\/i> m\u00e1sik emberrel viaskodhat, akkor \u0151t biztosan nem szabad beengedni \u2014 k\u00fcl\u00f6nben minden olyan k + 1<\/i> v\u00e1rosit ki kell z\u00e1rnunk, akivel \u00f6ssze\u00fctk\u00f6z\u00e9sbe l\u00e9phet, ami m\u00e1r biztosan felbosszantja az ir\u00e1ny\u00edt\u00e1st.<\/p>\n

Tegy\u00fck fel, hogy elt\u00e1vol\u00edtotta az \u00f6sszes olyan embert, akit csak tudott, ezen elv alapj\u00e1n. Akkor a t\u00f6bbiek legfeljebb k<\/i> emberekkel fognak viaskodni. Ha k\u00f6z\u00fcl\u00fck k<\/i> embert kisz\u00f3r, akkor legfeljebb \"Hogyan konfliktust tud megel\u0151zni. Teh\u00e1t, ha t\u00f6bb mint \"Hogyan ember r\u00e9szese b\u00e1rmely konfliktusnak, akkor biztosan nem tudja megel\u0151zni mindet. Mivel nyilv\u00e1nval\u00f3, hogy a teljesen konfliktusmentes embereket biztosan be fogja engedni, ez\u00e9rt \u00e1t kell n\u00e9zni az \u00f6sszes t\u00edz elem\u0171 r\u00e9szhalmazt a k\u00e9tsz\u00e1z emberb\u0151l. Ezek k\u00f6r\u00fclbel\u00fcl \"Hogyan, \u00e9s ezt a m\u0171veletsz\u00e1mot m\u00e1r meg lehet dolgozni egy klaszteren.<\/p>\n

Ha biztons\u00e1gosan be tudunk engedni teljesen konfliktusmentes szem\u00e9lyeket, akkor mit mondhatunk azokkal, akik csak egy konfliktusban vesznek r\u00e9szt? Val\u00f3j\u00e1ban \u0151ket is be lehet engedni, ha bez\u00e1rjuk a kaput az ellenfel\u00fck el\u0151tt. Igaz, ha Alice csak Bobbal konflikt\u00e1l, ha k\u00f6z\u00fcl\u00fck Alice-t engedj\u00fck be, nem vesz\u00edt\u00fcnk: Bobnak lehetnek m\u00e1s konfliktusai, m\u00edg Alice-nak biztosan nincsenek. K\u00fcl\u00f6n\u00f6sen \u00e9rtelmetlen nem engedni be \u0151ket kettes\u00e9vel. Ilyen m\u0171veletek ut\u00e1n nem marad t\u00f6bb \"Hogyan vend\u00e9g megoldatlan sorssal: \u00f6sszesen \"Hogyan konfliktusunk van, mindegyikben k\u00e9t r\u00e9sztvev\u0151vel, \u00e9s mindenki legal\u00e1bb kett\u0151ben r\u00e9szt vesz. Teh\u00e1t csak annyit kell \u00e1tvizsg\u00e1lni, hogy \"Hogyan vari\u00e1ci\u00f3t, ami egy f\u00e9l napra elegend\u0151 lehet egy laptopon.<\/p>\n

Val\u00f3j\u00e1ban egyszer\u0171 \u00e9rvel\u00e9sekkel m\u00e9g vonz\u00f3bb felt\u00e9teleket is el\u00e9rhet\u00fcnk. Vegy\u00fck \u00e9szre, hogy mindenk\u00e9ppen meg kell oldanunk minden vit\u00e1t, teh\u00e1t minden konflikt\u00e1l\u00f3 p\u00e1rb\u00f3l legal\u00e1bb egy embert ki kell v\u00e1lasztanunk, akit nem enged\u00fcnk be. Vegy\u00fcnk egy algoritmust: vegy\u00fcnk egy konfliktust, amelyb\u0151l elt\u00e1vol\u00edtunk egy r\u00e9sztvev\u0151t, \u00e9s rekurz\u00edvan folytatjuk a marad\u00e9kkal, majd t\u00e1vol\u00edtsuk el a m\u00e1sikat, \u00e9s szint\u00e9n rekurz\u00edvan folytatjuk. Mivel minden l\u00e9p\u00e9sben valakit elt\u00e1vol\u00edtunk, az ilyen algoritmus rekurzi\u00f3s f\u00e1ja bin\u00e1ris fa m\u00e9lys\u00e9ge k<\/i>, ez\u00e9rt az algoritmus \u00f6sszess\u00e9g\u00e9ben \"Hogyan, ahol n<\/i> \u2014 a cs\u00facsok sz\u00e1ma, \u00e9s m<\/i> \u2014 az \u00e9lek sz\u00e1ma. A mi p\u00e9ld\u00e1nk szerint ez k\u00f6r\u00fclbel\u00fcl t\u00edz milli\u00f3, ami n\u00e9h\u00e1ny m\u00e1sodperc alatt kisz\u00e1m\u00edthat\u00f3 nemcsak egy laptopon, de m\u00e9g egy mobiltelefonon is.<\/p>\n

A fent eml\u00edtett p\u00e9lda egy parametrikus algoritmus<\/b>. A parametrikus algoritmusok olyan algoritmusok, amelyek f(k) poly(n)<\/i>, ahol p<\/i> \u2014 polinom, f<\/i> \u2014 tetsz\u0151leges sz\u00e1m\u00edthat\u00f3 f\u00fcggv\u00e9ny, \u00e9s k<\/i> \u2014 valamilyen param\u00e9ter, amely lehet, hogy sokkal kisebb, mint a feladat m\u00e9rete.<\/p>\n

Minden eddigi \u00e9rvel\u00e9s a kerneliz\u00e1ci\u00f3ra vezet.<\/b> \u2014 az egyik \u00e1ltal\u00e1nos technika a param\u00e9terezett algoritmusok l\u00e9trehoz\u00e1s\u00e1ra. A kerneliz\u00e1ci\u00f3 a feladat m\u00e9ret\u00e9nek cs\u00f6kkent\u00e9se egy param\u00e9tert\u0151l f\u00fcgg\u0151 \u00e9rt\u00e9kre. A kapott feladatot gyakran a kernel n\u00e9ven nevezik. \u00cdgy, egyszer\u0171 \u00e9rvel\u00e9ssel a cs\u00facsok fokain\u00e1l n\u00e9gyzetes kernelt kaptunk a Vertex Cover probl\u00e9m\u00e1hoz, amely a v\u00e1lasz m\u00e9ret\u00e9hez van param\u00e9terezve. Vannak m\u00e1s param\u00e9terek is, amelyeket v\u00e1laszthatunk ehhez a feladathoz (p\u00e9ld\u00e1ul Vertex Cover Above LP), de mi pontosan ezt a param\u00e9tert fogjuk megvitatni.<\/p>\n

Pace Challenge<\/h3>\n

Verseny PACE Challenge<\/a><\/noindex> (A Param\u00e9terezett Algoritmusok \u00e9s Sz\u00e1m\u00edt\u00e1stechnikai K\u00eds\u00e9rletek Versenye) 2015-ben indult, hogy kapcsolatot teremtsen a param\u00e9terezett algoritmusok \u00e9s a gyakorlatban alkalmazott megold\u00e1si megk\u00f6zel\u00edt\u00e9sek k\u00f6z\u00f6tt a sz\u00e1m\u00edt\u00e1stechnikai probl\u00e9m\u00e1k megold\u00e1s\u00e1hoz. Az els\u0151 h\u00e1rom verseny a gr\u00e1f f\u00e1ja sz\u00e9less\u00e9g\u00e9nek keres\u00e9s\u00e9re, (Treewidth<\/a><\/noindex>) a Steiner-f\u00e1nak keres\u00e9s\u00e9re (Steiner Tree<\/a><\/noindex>) \u00e9s a visszajelz\u0151 cs\u00facs halmaz keres\u00e9s\u00e9re (Feedback Vertex Set<\/a><\/noindex>). Id\u00e9n egy olyan feladat volt, amelyre pr\u00f3b\u00e1lhatt\u00e1k a k\u00e9pess\u00e9geiket, a fent le\u00edrt cs\u00facsbor\u00edt\u00e1si feladat.<\/p>\n

A verseny \u00e9vr\u0151l \u00e9vre n\u00e9pszer\u0171bb. Ha a prelimin\u00e1ris adatoknak hihet\u00fcnk, id\u00e9n a cs\u00facsbor\u00edt\u00e1si probl\u00e9ma megold\u00f3 verseny\u00e9n 24 csapat vett r\u00e9szt. \u00c9rdemes megjegyezni, hogy a verseny nem n\u00e9h\u00e1ny \u00f3r\u00e1ig, s\u0151t nem is egy h\u00e9tig, hanem t\u00f6bb h\u00f3napig tart. A csapatoknak lehet\u0151s\u00e9g\u00fck van \u00e1ttekinteni az irodalmat, kital\u00e1lni saj\u00e1t eredeti \u00f6tleteiket \u00e9s megpr\u00f3b\u00e1lni megval\u00f3s\u00edtani azokat. L\u00e9nyeg\u00e9ben ez a verseny kutat\u00f3munk\u00e1nak min\u0151s\u00fcl. A legjobb megold\u00e1sok \u00f6tletei \u00e9s a gy\u0151ztesek d\u00edjaz\u00e1sa egyidej\u0171leg zajlik az IPEC<\/a><\/noindex> (Nemzetk\u00f6zi Szimp\u00f3zium a Param\u00e9terezett \u00e9s Pontos Sz\u00e1m\u00edt\u00e1sr\u00f3l) keretein bel\u00fcl, amely Europa legnagyobb \u00e9ves algoritmikai \u00f6sszej\u00f6vetel\u00e9n zajlik ALGO<\/a><\/noindex>. A verseny r\u00e9szleteir\u0151l tov\u00e1bbi inform\u00e1ci\u00f3t tal\u00e1lhatunk a weboldalon<\/a><\/noindex>, a kor\u00e1bbi \u00e9vek eredm\u00e9nyei pedig az al\u00e1bbi helyen \u00e9rhet\u0151k el itt<\/a><\/noindex>.<\/p>\n

A megold\u00e1s s\u00e9m\u00e1ja<\/h3>\n

A cs\u00facsbor\u00edt\u00e1si feladat megold\u00e1s\u00e1ra megpr\u00f3b\u00e1ltam parametrikus algoritmusokat alkalmazni. Ezek \u00e1ltal\u00e1ban k\u00e9t r\u00e9szb\u0151l \u00e1llnak: egyszer\u0171s\u00edt\u00e9si szab\u00e1lyokb\u00f3l (amelyek ide\u00e1lisan kernalis\u00e1l\u00e1shoz vezetnek) \u00e9s oszt\u00e1si szab\u00e1lyokb\u00f3l. Az egyszer\u0171s\u00edt\u00e9si szab\u00e1lyok a bemenet el\u0151feldolgoz\u00e1s\u00e1t jelentik polinomi\u00e1lis id\u0151ben. Ezek c\u00e9lja a feladat \u00e1tkonvert\u00e1l\u00e1sa egy kisebb m\u00e9ret\u0171, ekvivalens probl\u00e9m\u00e1v\u00e1. Az egyszer\u0171s\u00edt\u00e9si szab\u00e1lyok a legid\u0151ig\u00e9nyesebb r\u00e9sze az algoritmusnak, \u00e9s ennek a r\u00e9sznek a haszn\u00e1lata vezet az \u00f6sszes v\u00e9grehajt\u00e1si id\u0151h\u00f6z. \"Hogyan ahelyett, hogy csak polinomi\u00e1lis id\u0151t ig\u00e9nyelne. Ebben az esetben az oszt\u00e1si szab\u00e1lyok azon alapulnak, hogy minden cs\u00facsra v\u00e1lasszunk a v\u00e1laszba vagy mag\u00e1t a cs\u00facsot, vagy annak szomsz\u00e9dj\u00e1t.<\/p>\n

Az \u00e1ltal\u00e1nos s\u00e9ma a k\u00f6vetkez\u0151: alkalmazzuk az egyszer\u0171s\u00edt\u00e9si szab\u00e1lyokat, majd kiv\u00e1lasztunk egy cs\u00facsot, \u00e9s k\u00e9t rekurz\u00edv h\u00edv\u00e1st v\u00e9gz\u00fcnk: az els\u0151ben ezt a cs\u00facsot vegy\u00fck figyelembe, a m\u00e1sodikban pedig minden szomsz\u00e9dj\u00e1t. Ezt nevezz\u00fck oszt\u00e1snak (branching) ennek a cs\u00facsnak az alapj\u00e1n.<\/p>\n

Ehhez a s\u00e9m\u00e1hoz pontosan egy kieg\u00e9sz\u00edt\u00e9st fogunk tenni a k\u00f6vetkez\u0151 bekezd\u00e9sben.<\/p>\n

Az oszt\u00e1si (branching) szab\u00e1lyok \u00f6tletei<\/h3>\n

Besz\u00e9lj\u00fck meg, hogyan v\u00e1lasszunk egy cs\u00facsot, amin oszt\u00e1s fog t\u00f6rt\u00e9nni.
\nA f\u0151 \u00f6tlet nagyon moh\u00f3 algoritmikus \u00e9rtelemben: v\u00e1lasszunk egy maxim\u00e1lis fok\u00fa cs\u00facsot, \u00e9s oszlassunk \u00e9ppen ezen. Mi\u00e9rt t\u0171nik ez a legjobbnak? Mert a rekurz\u00edv h\u00edv\u00e1s m\u00e1sodik \u00e1g\u00e1ban \u00edgy nagyon sok cs\u00facsot elt\u00e1vol\u00edtunk. Sz\u00e1m\u00edthatunk arra, hogy egy kis grafikon marad, amin gyorsan tudunk dolgozni.<\/p>\n

Ez a megk\u00f6zel\u00edt\u00e9s, a m\u00e1r t\u00e1rgyalt egyszer\u0171 kernalis\u00e1l\u00e1si technik\u00e1kkal egy\u00fctt, j\u00f3l teljes\u00edt, n\u00e9h\u00e1ny ezer cs\u00facs m\u00e9ret\u0171 teszteket megold. De p\u00e9ld\u00e1ul rosszul m\u0171k\u00f6dik a kubikus gr\u00e1fokra (azaz azok gr\u00e1fja, amelyeknek mindegyik cs\u00facs\u00e1nak foka h\u00e1rom).
\nVan egy \u00fajabb \u00f6tlet, amely egy el\u00e9g egyszer\u0171 gondolaton alapul: ha a gr\u00e1f nem \u00f6sszef\u00fcgg\u0151, a kapcsolatkomponensein a feladat f\u00fcggetlen\u00fcl megoldhat\u00f3, \u00e9s a v\u00e1laszokat a v\u00e9g\u00e9n \u00f6ssze lehet kombin\u00e1lni. Ez egy\u00e9bk\u00e9nt a kor\u00e1bban \u00edg\u00e9rt kis m\u00f3dos\u00edt\u00e1s a s\u00e9m\u00e1ban, amely jelent\u0151sen felgyors\u00edtja a megold\u00e1st: kor\u00e1bban ilyen esetben az \u00f6sszes komponens v\u00e1laszainak sz\u00e1mol\u00e1si idej\u00e9nek szorzatak\u00e9nt dolgoztunk, most viszont az \u00f6sszegek szerint. Az oszt\u00e1s gyors\u00edt\u00e1sa \u00e9rdek\u00e9ben a kapcsolt gr\u00e1fot sz\u00fcks\u00e9ges \u00e1talak\u00edtani \u00f6sszef\u00fcgg\u0151v\u00e9.<\/p>\n

Hogyan kell ezt megtenni? Ha van egy grafikonban egy v\u00e1g\u00f3pont, akkor pontosan ott kell \u00e1gaznunk. A v\u00e1g\u00f3pont egy olyan cs\u00facs, amelynek elt\u00e1vol\u00edt\u00e1sakor a grafikon elvesz\u00edti a kapcsolatoss\u00e1g\u00e1t. A grafikonban az \u00f6sszes v\u00e1g\u00f3pont megtal\u00e1lhat\u00f3 egy klasszikus algoritmus seg\u00edts\u00e9g\u00e9vel, line\u00e1ris id\u0151 alatt. Ez a megk\u00f6zel\u00edt\u00e9s jelent\u0151sen felgyors\u00edtja az \u00e1gakra bont\u00e1st.
\n\"Hogyan
\nB\u00e1rmelyik kiemelt cs\u00facs elt\u00e1vol\u00edt\u00e1sakor a grafikon elt\u00e1vol\u00edtja a kapcsolatoss\u00e1gait.<\/p>\n

Ezt meg fogjuk tenni, de t\u00f6bbre v\u00e1gyunk. P\u00e9ld\u00e1ul, keresni a grafikonban kis cs\u00facsv\u00e1g\u00e1sokat \u00e9s a cs\u00facsok ment\u00e9n v\u00e9gezni az \u00e1gaz\u00e1st. A leghat\u00e9konyabb m\u00f3dszer, amit ismerek a glob\u00e1lis minim\u00e1lis cs\u00facsv\u00e1g\u00e1s megtal\u00e1l\u00e1s\u00e1ra, a Gomori-Hu fa haszn\u00e1lata, amely kubikus id\u0151 alatt \u00e9p\u00fcl. A PACE Challenge-ben a tipikus grafikon m\u00e9rete n\u00e9h\u00e1ny ezer cs\u00facs. Ilyen k\u00f6r\u00fclm\u00e9nyek k\u00f6z\u00f6tt a rekurszi\u00f3 f\u00e1j\u00e1nak minden cs\u00facs\u00e1ban milli\u00e1rdnyi m\u0171veletet kell v\u00e9grehajtani. Ez\u00e9rt a feladatot a rendelkez\u00e9sre \u00e1ll\u00f3 id\u0151 alatt egyszer\u0171en lehetetlen megoldani.<\/p>\n

Pr\u00f3b\u00e1ljuk meg optimaliz\u00e1lni a megold\u00e1st. A p\u00e1r cs\u00facs k\u00f6z\u00f6tti minim\u00e1lis cs\u00facsv\u00e1g\u00e1s b\u00e1rmelyik maxim\u00e1lis \u00e1ramot \u00e9p\u00edt\u0151 algoritmussal megtal\u00e1lhat\u00f3. Egy ilyen h\u00e1l\u00f3zatra r\u00e1 lehet vez\u00e9nyelni Dinic algoritmus\u00e1t<\/a><\/noindex>, a gyakorlatban ez nagyon gyorsan m\u0171k\u00f6dik. Gyan\u00edtom, hogy elm\u00e9letileg bizony\u00edtani lehet a fut\u00e1si id\u0151re vonatkoz\u00f3 becsl\u00e9st \"Hogyan, ami m\u00e1r teljesen elfogadhat\u00f3.<\/p>\n

T\u00f6bbsz\u00f6r megpr\u00f3b\u00e1ltam v\u00e1g\u00e1sokat keresni v\u00e9letlenszer\u0171 cs\u00facsok k\u00f6z\u00f6tt \u00e9s a legjobban kiegyens\u00falyozottakat v\u00e1lasztani. Sajnos a PACE Challenge ny\u00edlt tesztjein ez rossz eredm\u00e9nyeket hozott. \u00d6sszehasonl\u00edtottam a cs\u00facsok maxim\u00e1lis fok\u00e1val foglalkoz\u00f3 algoritmussal, \u00e9s korl\u00e1tozva ind\u00edtottam \u0151ket a mer\u00fcl\u00e9si m\u00e9lys\u00e9gre. Miut\u00e1n az algoritmus megpr\u00f3b\u00e1lta \u00edgy megtal\u00e1lni a v\u00e1g\u00e1st, a nagyobb m\u00e9ret\u0171 grafikonok maradtak. Ez az\u00e9rt van, mert a v\u00e1g\u00e1sok nagyon kiegyens\u00falyozatlanok lettek: 5-10 cs\u00facs elt\u00e1vol\u00edt\u00e1s\u00e1val csup\u00e1n 15-20 tudott lev\u00e1lni.<\/p>\n

\u00c9rdemes megjegyezni, hogy a leggyorsabb algoritmusokkal kapcsolatos cikkekben sokkal kifinomultabb technik\u00e1kat haszn\u00e1lnak a v\u00e1g\u00e1sra sz\u00e1nt cs\u00facsok kiv\u00e1laszt\u00e1s\u00e1ra. Ezek a technik\u00e1k nagyon bonyolult megval\u00f3s\u00edt\u00e1ssal rendelkeznek, \u00e9s gyakran rossz id\u0151- \u00e9s mem\u00f3riabecsl\u00e9sekkel b\u00edrnak. Nem tudtam bel\u0151l\u00fck kiemelni elfogadhat\u00f3 megold\u00e1sokat a gyakorlat sz\u00e1m\u00e1ra.<\/p>\n

Hogyan alkalmazzuk az egyszer\u0171s\u00edt\u00e9si szab\u00e1lyokat<\/h3>\n

M\u00e1r van \u00f6tlet\u00fcnk a kerneliz\u00e1ci\u00f3ra. Eml\u00e9keztetek:<\/p>\n

    \n
  1. Ha van egy elszigetelt cs\u00facs, t\u00e1vol\u00edtsuk el.<\/li>\n
  2. Ha van egy 1. fok\u00fa cs\u00facs, t\u00f6r\u00f6lj\u00fck, \u00e9s vegy\u00fck a szomsz\u00e9dj\u00e1t v\u00e1laszk\u00e9nt.<\/li>\n
  3. Ha van legal\u00e1bb egy 2. fok\u00fa cs\u00facs, vegy\u00fck azt v\u00e1laszk\u00e9nt. k + 1<\/i>, vegy\u00fck v\u00e1laszk\u00e9nt.<\/li>\n<\/ol>\n

    Az els\u0151 kett\u0151 tiszta, a harmadik eset\u00e9ben van egy tr\u00fckk. Ha a vicces feladatban a b\u00e1rra korl\u00e1toz\u00e1st adtunk meg, k<\/i>, akkor a PACE Challenge-ban egyszer\u0171en meg kell tal\u00e1lni a lehet\u0151 legkisebb cs\u00facsbor\u00edt\u00e1st. Ez a keres\u00e9si feladatok (Search Problem) megold\u00e1si feladatokk\u00e1 (Decision Problem) t\u00f6rt\u00e9n\u0151 tipikus \u00e1talak\u00edt\u00e1sa, gyakran nem tesznek k\u00fcl\u00f6nbs\u00e9get a k\u00e9tf\u00e9le feladat k\u00f6z\u00f6tt. A gyakorlatban, ha cs\u00facsbor\u00edt\u00e1si feladatot oldunk meg, a k\u00fcl\u00f6nbs\u00e9g sz\u00e1m\u00edt. P\u00e9ld\u00e1ul a harmadik pontban.<\/p>\n

    A megval\u00f3s\u00edt\u00e1s szempontj\u00e1b\u00f3l k\u00e9t m\u00f3don j\u00e1rhatunk el. Az els\u0151 megk\u00f6zel\u00edt\u00e9s az Iterat\u00edv M\u00e9ly\u00edt\u00e9s. Ez abban \u00e1ll, hogy elkezd\u00fcnk egy \u00e9sszer\u0171 als\u00f3 korl\u00e1ttal a v\u00e1laszra, \u00e9s ezut\u00e1n elind\u00edtjuk az algoritmusunkat, haszn\u00e1lva ezt a korl\u00e1toz\u00e1st fels\u0151 korl\u00e1toz\u00e1sk\u00e9nt, nem m\u00e9lyedve el a rekurzi\u00f3ban az als\u00f3 hat\u00e1r alatt. Ha tal\u00e1lunk valamilyen v\u00e1laszt, az garant\u00e1ltan optim\u00e1lis, k\u00fcl\u00f6nben n\u00f6velj\u00fck ezt a korl\u00e1tot egy egys\u00e9ggel \u00e9s \u00fajra elindulunk.<\/p>\n

    A m\u00e1sik megk\u00f6zel\u00edt\u00e9s az, hogy t\u00e1rolunk egy aktu\u00e1lis optim\u00e1lis v\u00e1laszt, \u00e9s kisebb m\u00e9ret\u0171 v\u00e1laszt keres\u00fcnk, ha megtal\u00e1ljuk, m\u00f3dos\u00edtva ezt a param\u00e9tert k<\/i> a felesleges \u00e1gak lev\u00e1g\u00e1s\u00e1nak \u00e9rdek\u00e9ben a keres\u00e9sben.<\/p>\n

    Miut\u00e1n n\u00e9h\u00e1ny \u00e9jszakai k\u00eds\u00e9rletet v\u00e9geztem, egyes\u00edtettem ezeket a k\u00e9t m\u00f3dszert: el\u0151sz\u00f6r az algoritmusomat elind\u00edtom egy bizonyos keres\u00e9si m\u00e9lys\u00e9g korl\u00e1toz\u00e1ssal (\u00fagy v\u00e1lasztva, hogy ez elhanyagolhat\u00f3 id\u0151t vegyen ig\u00e9nybe a f\u0151 megold\u00e1shoz k\u00e9pest), \u00e9s a legjobb megtal\u00e1lt megold\u00e1st haszn\u00e1lom mint fels\u0151 korl\u00e1toz\u00e1st \u2013 azaz ugyanezt k<\/i>.<\/p>\n

    A 2. fok\u00fa cs\u00facsok<\/h3>\n

    A 0. \u00e9s 1. fok\u00fa cs\u00facsokkal tiszt\u00e1ban vagyunk. Kider\u00fcl, hogy a 2. fok\u00fa cs\u00facsokkal is megtehet\u0151, de ehhez \u00f6sszetettebb m\u0171veletek sz\u00fcks\u00e9gesek a gr\u00e1fban.<\/p>\n

    Ehhez valahogyan jel\u00f6ln\u00fcnk kell a cs\u00facsokat. Nevezz\u00fck a 2. fok\u00fa cs\u00facsot cs\u00facsnak v<\/i>, a szomsz\u00e9dait pedig cs\u00facsoknak x<\/i> \u00e9s y<\/i>. Ezut\u00e1n k\u00e9t esetben lesz dolgunk.<\/p>\n

      \n
    1. Amikor x<\/i> \u00e9s y<\/i> \u2014 szomsz\u00e9dok. Ekkor v\u00e1laszk\u00e9nt elfogadhatjuk, hogy x<\/i> \u00e9s y<\/i>, \u00e9s v<\/i> t\u00f6r\u00f6lni kell. Val\u00f3ban, ebb\u0151l a h\u00e1romsz\u00f6gb\u0151l legal\u00e1bb k\u00e9t cs\u00facsnak szerepelnie kell a v\u00e1laszban, \u00e9s biztosan nem vesz\u00edt\u00fcnk, ha v\u00e1lasztunk x<\/i> \u00e9s y<\/i>: val\u00f3sz\u00edn\u0171leg van m\u00e9g szomsz\u00e9djuk, a v<\/i> nincs.<\/li>\n
    2. Amikor x<\/i> \u00e9s y<\/i> \u2014 nem szomsz\u00e9dok. Ekkor azt \u00e1ll\u00edtjuk, hogy mindh\u00e1rom cs\u00facsot \u00f6ssze lehet ragasztani egybe. Az \u00f6tlet az, hogy ilyenkor van egy optim\u00e1lis v\u00e1lasz, amibe vagy v<\/i>, vagy mindk\u00e9t cs\u00facsot x<\/i> \u00e9s y<\/i>be kell venn\u00fcnk. R\u00e1ad\u00e1sul az els\u0151 esetben az \u00f6sszes szomsz\u00e9dot is be kell venn\u00fcnk x<\/i> \u00e9s y<\/i>, m\u00edg a m\u00e1sodik esetben nem felt\u00e9tlen\u00fcl. Ez pontosan megfelel azoknak az eseteknek, amikor nem vessz\u00fck be a ragasztott cs\u00facsot a v\u00e1laszba, \u00e9s amikor belefoglaljuk. Csak annyit kell megjegyezni, hogy mindk\u00e9t esetben az ilyen m\u0171velet \u00e1ltal adott v\u00e1lasz egy egys\u00e9ggel cs\u00f6kken.<\/li>\n<\/ol>\n

      \"Hogyan<\/p>\n

      \u00c9rdemes megjegyezni, hogy az ilyen megk\u00f6zel\u00edt\u00e9st tiszt\u00e1n line\u00e1ris id\u0151 alatt meglehet\u0151sen neh\u00e9z pontosan megval\u00f3s\u00edtani. A cs\u00facsok \u00f6sszeragaszt\u00e1sa bonyolult m\u0171velet, sz\u00fcks\u00e9ges a szomsz\u00e9dok list\u00e1it lem\u00e1solni. Ha ezt nem figyelmesen csin\u00e1ljuk, akkor aszimptotikusan nem optim\u00e1lis m\u0171k\u00f6d\u00e9si id\u0151t kaphatunk (p\u00e9ld\u00e1ul ha minden egyes \u00f6sszeragaszt\u00e1s ut\u00e1n sok \u00e9lt m\u00e1solunk). Le\u00e1lltam a 2 fok\u00fa cs\u00facsokb\u00f3l \u00e1ll\u00f3 eg\u00e9sz utak keres\u00e9s\u00e9n, \u00e9s sok egyedi eset, p\u00e9ld\u00e1ul ilyen cs\u00facsokb\u00f3l \u00e1ll\u00f3 ciklusok vizsg\u00e1lat\u00e1n\u00e1l.<\/p>\n

      Ezen k\u00edv\u00fcl sz\u00fcks\u00e9ges, hogy ez a m\u0171velet visszaford\u00edthat\u00f3 legyen, hogy a rekurzi\u00f3b\u00f3l val\u00f3 visszat\u00e9r\u00e9skor a gr\u00e1fot az eredeti \u00e1llapot\u00e1ba tudjuk helyre\u00e1ll\u00edtani. Ennek biztos\u00edt\u00e1sa \u00e9rdek\u00e9ben nem t\u00f6r\u00f6ltem az \u00f6sszeragasztott cs\u00facsok \u00e9llist\u00e1it, \u00edgy egyszer\u0171en tudtam, hogy mely \u00e9leket hov\u00e1 kell ir\u00e1ny\u00edtani. Az ilyen gr\u00e1fok megval\u00f3s\u00edt\u00e1sa is \u00f3vatoss\u00e1got ig\u00e9nyel, viszont biztos\u00edtja a tiszt\u00e1n line\u00e1ris id\u0151t. A t\u00f6bb t\u00edzezer \u00e9lb\u0151l \u00e1ll\u00f3 gr\u00e1fok pedig j\u00f3l belef\u00e9rnek a processzor gyors\u00edt\u00f3t\u00e1r\u00e1ba, ami nagy sebess\u00e9gel\u0151ny\u00f6ket biztos\u00edt.<\/p>\n

      Line\u00e1ris mag<\/h3>\n

      V\u00e9g\u00fcl, a mag leg\u00e9rdekesebb r\u00e9sze.<\/p>\n

      Kezdetben eml\u00e9kezz\u00fcnk arra, hogy bipartit gr\u00e1fokban a minim\u00e1lis cs\u00facsbor\u00edt\u00e1st \"Hogyankereshetj\u00fck. Ehhez a Hopcroft-Karp algoritmust<\/a><\/noindex> kell haszn\u00e1lnunk a maxim\u00e1lis p\u00e1ros\u00edt\u00e1s megtal\u00e1l\u00e1s\u00e1hoz, majd alkalmazni kell a K\u00f6nig-Egerv\u00e1ri t\u00e9tele<\/a><\/noindex>.<\/p>\n

      A line\u00e1ris mag \u00f6tlete a k\u00f6vetkez\u0151: el\u0151sz\u00f6r bipartit gr\u00e1fot k\u00e9sz\u00edt\u00fcnk, azaz minden cs\u00facs helyett v<\/i> k\u00e9t cs\u00facsot hozunk l\u00e9tre, \"Hogyan \u00e9s \"Hogyanm\u00edg minden \u00e9l helyett u \u2014 v<\/i> k\u00e9t \u00e9lt teremt\u00fcnk. \"Hogyan \u00e9s \"HogyanA kapott gr\u00e1f bipartit lesz. Megkeress\u00fck benne a minim\u00e1lis cs\u00facsbor\u00edt\u00e1st. N\u00e9h\u00e1ny cs\u00facs az eredeti gr\u00e1fban k\u00e9tszer, n\u00e9h\u00e1ny egyszer, m\u00edg n\u00e9h\u00e1ny egy\u00e1ltal\u00e1n nem ker\u00fcl be. A Nemhauser-Trotter-t\u00e9tel szerint ilyenkor elt\u00e1vol\u00edthatjuk azokat a cs\u00facsokat, amelyek egy\u00e1ltal\u00e1n nem szerepeltek, \u00e9s v\u00e1laszthatjuk azokat, amelyek k\u00e9tszer szerepeltek. Tov\u00e1bb\u00e1 azt is mondja, hogy a megmaradt cs\u00facsok k\u00f6z\u00fcl (azok, amelyek egyszer szerepeltek) legal\u00e1bb a fel\u00e9t v\u00e1lasszuk ki a v\u00e1laszban.<\/p>\n

      Most tanultuk meg, hogy a gr\u00e1fban nem hagyunk t\u00f6bb mint 2k<\/i> cs\u00facsot. Igaz, ha a v\u00e1laszban legal\u00e1bb a cs\u00facsok fele benne van, akkor az \u00f6sszes cs\u00facs sz\u00e1ma nem lehet t\u00f6bb mint 2k<\/i>.<\/p>\n

      Itt siker\u00fclt egy kis el\u0151rel\u00e9p\u00e9st tennem. Nyilv\u00e1nval\u00f3, hogy \u00edgy \u00e9p\u00edtett mag egy\u00e1ltal\u00e1n att\u00f3l f\u00fcgg, hogy melyik minim\u00e1lis cs\u00facsbor\u00edt\u00e1st v\u00e1lasztottuk a bipartit gr\u00e1fban. Azt szeretn\u00e9nk, ha a megmaradt cs\u00facsok sz\u00e1ma minim\u00e1lis lenne. Eddig ezt csak \"Hogyanid\u0151 alatt tudt\u00e1k megoldani. \u00c9n azonban kidolgoztam ennek az algoritmusnak a megval\u00f3s\u00edt\u00e1s\u00e1t \"Hogyanid\u0151 alatt, \u00edgy ezt a magot ak\u00e1r sz\u00e1zezres cs\u00facs\u00fa gr\u00e1fokban is kereshetj\u00fck a branchenk minden egyes l\u00e9p\u00e9s\u00e9ben.<\/p>\n

      Eredm\u00e9ny<\/h3>\n

      A gyakorlat azt mutatja, hogy a megold\u00e1som j\u00f3l m\u0171k\u00f6dik n\u00e9h\u00e1ny sz\u00e1z cs\u00facs \u00e9s n\u00e9h\u00e1ny ezer \u00e9l tesztjein. Ilyen tesztekn\u00e9l teljesen elv\u00e1rhat\u00f3, hogy a megold\u00e1s f\u00e9l \u00f3ra alatt megtal\u00e1lhat\u00f3 legyen. A v\u00e1lasz megtal\u00e1l\u00e1s\u00e1nak es\u00e9lye alapvet\u0151en n\u0151, ha a gr\u00e1fban sok a nagy fok\u00fa cs\u00facs, p\u00e9ld\u00e1ul 10-es \u00e9s ann\u00e1l nagyobb fok\u00fa.<\/p>\n

      A versenyhez a megold\u00e1sokat be kellett k\u00fcldeni a optil.io<\/a><\/noindex>. A bemutatott t\u00e1bl\u00e1zat<\/a><\/noindex>, a megold\u00e1som a ny\u00edlt teszteken a h\u00faszb\u00f3l a harmadik helyen \u00e1ll, nagy k\u00fcl\u00f6nbs\u00e9ggel a m\u00e1sodik ut\u00e1n. Ha teljesen \u0151szinte akarok lenni, akkor nem teljesen vil\u00e1gos, hogyan fogj\u00e1k \u00e9rt\u00e9kelni a megold\u00e1sokat mag\u00e1n a versenyen: p\u00e9ld\u00e1ul az \u00e9n megold\u00e1som kevesebb teszten teljes\u00edt, mint a negyedik helyezett\u00e9, de azokban, amelyeket siker\u00fclt megoldania, gyorsabban dolgozik.<\/p>\n

      A z\u00e1rt teszteken el\u00e9rt eredm\u00e9nyek j\u00falius elsej\u00e9n v\u00e1lnak ismertt\u00e9.<\/p>\n

      Forr\u00e1s: 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\udd47Hogyan oldjunk meg NP-nehezen megoldhat\u00f3 feladatokat param\u00e9terezett algoritmusokkal | ProHoster","description":"A tudom\u00e1nyos kutat\u00f3munka val\u00f3sz\u00edn\u0171leg a leg\u00e9rdekesebb r\u00e9sze a tanulm\u00e1nyainknak. Az \u00f6tlet az, hogy m\u00e1r az egyetemen kipr\u00f3b\u00e1ljuk magunkat a kiv\u00e1lasztott ter\u00fcleten.","canonical_url":"https:\/\/prohoster.info\/hu\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"hu_HU","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\/hu\/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\/hu\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}