{"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\/et\/blog\/novosti-interneta\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Kuidas lahendada NP-raskusi parameetriliste algoritmidega","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Teaduslik t\u00f6\u00f6 on ilmselt meie \u00f5pingute k\u00f5ige huvitavam osa. Idee on proovida end valitud suunas juba \u00fclikoolis. N\u00e4iteks l\u00e4hevad tarkvaratehnika ja masin\u00f5ppe erialade tudengid sageli tegema teadusprojekte (peamiselt JetBrainsis v\u00f5i Yandexis, kuid mitte ainult).<\/p>\n

Selles postituses r\u00e4\u00e4gin oma projektist arvutiteaduse suunas. Projekti raames uurisin ja rakendasin praktikas l\u00e4henemisviise \u00fche tuntuma NP-raskete probleemide lahendamiseks: tipupakkumise probleem<\/b>.<\/p>\n

Praegu areneb v\u00e4ga kiiresti huvitav l\u00e4henemine NP-rasketele probleemidele \u2014 parameetrilised algoritmid. P\u00fc\u00fcan teid tutvustada, r\u00e4\u00e4kida m\u00f5nest lihtsast parameetrilisest algoritmist ja kirjeldada \u00fcht v\u00f5imsat meetodit, mis on mind palju aidanud. Oma tulemusi esitlesin PACE Challenge'i v\u00f5istlusel: avatud testide p\u00f5hjal h\u00f5ivab minu lahendus kolmanda koha ja l\u00f5plikud tulemused avaldatakse 1. juulil.<\/p>\n

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

Minust<\/h3>\n

Minu nimi on Vasili Alfjurov, hetkel l\u00f5petan ma III kursust NIU HSE \u2014 Peterburis. Algoritmid huvitavad mind juba koolip\u00e4evist, kui \u00f5ppisin Moskva 179. koolis ja osalesin edukalt informaatika ol\u00fcmpiaadidel.<\/p>\n

L\u00f5puks j\u00f5uab rikkaid spetsialiste parametriseeritud algoritmide kohta baari…<\/h3>\n

N\u00e4ide on p\u00e4rit raamatust \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

Kujutage ette, et olete baari turvamees v\u00e4ikeses linnas. Igal reedel tuleb pool linna teie baari l\u00f5\u00f5gastuma, mis tekitab teile palju muret: peate v\u00e4lja viskama rahutud k\u00fclastajad, et v\u00e4ltida kaklusi. L\u00f5puks hakkab see teile t\u00fc\u00fctuks, ja otsustate v\u00f5tta ennetavaid meetmeid.<\/p>\n

Kuna teie linn on v\u00e4ike, teate kindlasti, millised paarid k\u00fclastajatest t\u00f5en\u00e4oliselt kaklevad, kui nad satuvad baari koos. Teil on nimekiri n<\/i> inimestest, kes tulevad t\u00e4na \u00f5htul baari. Otsustate mitte lasta baari mingisuguseid linnaelanikke nii, et kedagi ei tekiks kaklusi. Samal ajal ei soovi teie \u00fclemus kaotada tulu ja on n\u00f6rdinud, kui te ei lase baari rohkem kui k<\/i> inimest.<\/p>\n

Kahjuks on ees seispev \u00fclesanne klassikaline NP-raskusi tekitav probleem. Te v\u00f5isite seda teada ka kui Tipukaate<\/a><\/noindex>, v\u00f5i tipukaate probleemina. Sellistele \u00fclesannetele ei ole \u00fcldiselt teada algoritme, mis t\u00f6\u00f6taksid m\u00f5istlikus ajas. T\u00e4psemalt \u00f6eldes \u00fctleb t\u00f5endamata ja \u00fcsna tugev h\u00fcpotees ETH (Exponential Time Hypothesis), et seda \u00fclesannet ei saa lahendada ajaga \"Kuidas, mis t\u00e4hendab, et midagi m\u00e4rgatavalt paremat kui t\u00e4ielik l\u00e4biotsimine ei saa v\u00e4lja m\u00f5elda. N\u00e4iteks oletame, et teie baari on tulemas n = 1000<\/i> inimest. Siis sisaldab t\u00e4ielik l\u00e4biotsimine \"Kuidas varianti, mis on umbes \"Kuidas \u2014 uskumatult palju. \u00d5nneks on teie juhatus kehtestanud teile piirangu k = 10<\/i>, nii et kombinatsioonide arv, mida peate l\u00e4bi otsima, on palju v\u00e4iksem: k\u00fcmne elemendi alamhulkade arv on \"Kuidas. See on juba parem, kuid ikkagi ei suudeta seda p\u00e4eva jooksul isegi v\u00f5imsal klusteril l\u00f5petada.
\n\"Kuidas
\nKuna sellise pingestatud suhete konfiguratsiooniga baarik\u00fclastajate vahel kakluse t\u00f5en\u00e4osus v\u00e4heneb, tuleb Bobi, Daniela ja Fjodorit sisse lasta. Lahendust, kus j\u00e4\u00e4b vaid kaks v\u00e4lja, ei ole.<\/p>\n

Kas see t\u00e4hendab, et on aeg alla anda ja k\u00f5iki sisse lasta? Vaatame muid v\u00f5imalusi. N\u00e4iteks v\u00f5ib mitte lasta sisse ainult neid, kes t\u00f5en\u00e4oliselt kaklevad v\u00e4ga suure hulga inimestega. Kui keegi suudab kakelda v\u00e4hemalt \u00fche k + 1<\/i> teise inimesega, siis teda kindlasti ei tohi lasta sisse \u2014 vastasel juhul tuleb k\u00f5iki mitte lasta. k + 1<\/i> Kohalikud elanikud, kellega ta v\u00f5ib kakelda, ja see petab juhtkonna t\u00e4iesti \u00e4ra.<\/p>\n

Oletame, et olete k\u00f5ik, keda saite, selle p\u00f5him\u00f5tte kohaselt v\u00e4lja visanud. Siis v\u00f5ivad k\u00f5ik \u00fclej\u00e4\u00e4nud kakelda mitte rohkem kui k<\/i> inimestega. Nende seast v\u00e4lja viskades k<\/i> inimest, saate v\u00e4ltida mitte rohkem kui \"Kuidas konflikti. Seega, kui rohkem kui \"Kuidas inimest osaleb v\u00e4hemalt \u00fches konfliktis, siis te ei suuda neid kindlasti k\u00f5iki \u00e4ra hoida. Kuna on selge, et t\u00e4iesti konfliktituks inimesi te kindlasti sisse lasete, peate uurima k\u00f5iki alamhulgi, mille suurus on k\u00fcmme, kahesajast inimesest. Nende arv on umbes \"Kuidas, ja sellise hulga operatsioone on juba v\u00f5imalik l\u00e4bi vaadata klastris.<\/p>\n

Kui on v\u00f5imalik sisse lasta t\u00e4iesti konflikti puudutavaid isikuid, siis kuidas on nende suhtes, kes osalevad vaid \u00fches konfliktis? Tegelikult v\u00f5ib neid ka sisse lasta, sulgedes ukse nende vastase ees. Ja t\u00f5epoolest, kui Alice on konfliktis vaid Bobiga, siis kui me laskme neist kahest sisse Alice'i, ei kaota me: Bobil v\u00f5ivad olla muud konfliktid, kuid Alicel neid kindlasti ei ole. Seet\u00f5ttu pole meie jaoks m\u00f5ttekas mitte lasta sisse kedagi kahest. P\u00e4rast selliseid operatsioone j\u00e4\u00e4b meie ette mitte rohkem \"Kuidas lahendamata saatusega k\u00fclalisi: kokku on meil \"Kuidas konflikte, igas osaleb kaks osalist ja iga\u00fchel on v\u00e4hemalt kaks osalust. See t\u00e4hendab, et j\u00e4\u00e4b kaaluda vaid \"Kuidas varianti, mis v\u00f5ib kindlasti arvestada pool p\u00e4eva s\u00fclearvutil.<\/p>\n

Tegelikult saab lihtsate m\u00f5ttek\u00e4ikude abil saavutada veelgi soodsamaid tingimusi. Tuleb m\u00e4rkida, et meil on h\u00e4dasti vaja lahendada k\u00f5ik vaidlused, st igast konflikti paarist valida v\u00e4hemalt \u00fcks inimene, keda me ei lase sisse. Vaatame j\u00e4rgmist algoritmi: v\u00f5tame mistahes konflikti, kust eemaldame \u00fche osalise ja k\u00e4ivitame rekursiivselt \u00fclej\u00e4\u00e4nud osaliste p\u00f5hjal, seej\u00e4rel eemaldame teise ja k\u00e4ivitame ka rekursiivselt. Kuna iga sammu juures eemaldame kellegi, on sellise algoritmi rekursioonipuu binaarne puu s\u00fcgavusega k<\/i>, seega t\u00f6\u00f6tab algoritm kokku \"Kuidas, kus n<\/i> \u2014 tipude arv, ja m<\/i> \u2014 servade arv. Meie n\u00e4ites on see umbes k\u00fcmme miljonit, mis arvutatakse sekundite murdosa jooksul mitte ainult s\u00fclearvutis, vaid isegi mobiiltelefonis.<\/p>\n

\u00dclaltoodud n\u00e4ide on n\u00e4ide parameetrilisest algoritmist<\/b>. Parameetrilised algoritmid on algoritmid, mis t\u00f6\u00f6tavad ajaga f(k) poly(n)<\/i>, kus p<\/i> \u2014 pol\u00fcnoom, f<\/i> \u2014 suvaline arvutatav funktsioon, ja k<\/i> \u2014 mingi parameeter, mis v\u00f5ib olla palju v\u00e4iksem \u00fclesande suurusest.<\/p>\n

Kuni selle algoritmini viivad k\u00f5ik m\u00f5ttek\u00e4igud n\u00e4itavad n\u00e4idet kerneldamisest<\/b> \u2014 \u00fcks \u00fcldtehnikaid parameetriseeritud algoritmide loomisel. Kerneldamine t\u00e4hendab \u00fclesande suuruse v\u00e4hendamist v\u00e4\u00e4rtuseni, mis on piiratud parameetri funktsiooniga. Saadud \u00fclesannet nimetatakse sageli kerniks. Nii saime lihtsate m\u00f5tiskluste kaudu tippude asteid arvestades kvadratilise kerne Vertex Cover'i probleemile, mis on parameetriseeritud vastuse suurusega. On olemas ka teisi parameetreid, mille saab selle \u00fclesande jaoks valida (n\u00e4iteks Vertex Cover Above LP), kuid me arutame just sellist parameetrit.<\/p>\n

Pace Challenge<\/h3>\n

V\u00f5istlus PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) sai alguse 2015. aastal, et luua side parameetriseeritud algoritmide ja praktikates kasutatavate l\u00e4henemisviiside vahel, et lahendada arvutusprobleeme. Esimesed kolm v\u00f5istlust keskendusid puu laius graafis (Treewidth<\/a><\/noindex>), \u0160teineri puu leidmisele (Steiner Tree<\/a><\/noindex>) ja ts\u00fcklite l\u00f5ikavate tippude hulga leidmisele (Feedback Vertex Set<\/a><\/noindex>). Sel aastal oli \u00fcks \u00fclesanne, milles sai oma oskusi proovile panna, \u00fclaltoodud tippude katte probleem.<\/p>\n

V\u00f5istlus muutub iga aastaga \u00fcha populaarsemaks. Eel\u00e4rvete kohaselt osales sel aastal ainult tippkatteprobleemi lahendamise v\u00f5istlusel 24 meeskonda. Tuleb m\u00e4rkida, et v\u00f5istlus kestab mitte paar tundi ega isegi n\u00e4dalat, vaid mitu kuud. Meeskondadel on v\u00f5imalus uurida kirjandust, v\u00e4lja m\u00f5elda originaalne idee ja proovida see ellu viia. Tegelikult esindab see v\u00f5istlus uurimist\u00f6\u00f6d. K\u00f5ige t\u00f5husamate lahenduste ideed ning v\u00f5itjate auhindamine toimub koos konverentsiga IPEC<\/a><\/noindex> (Rahvusvaheline Parametriseeritud ja T\u00e4psete Arvutuste S\u00fcmposium) Euroopa suurima ig \u05d4\u05e9\u05e0\u05d4 algoritmilise kogunemise raames ALGO<\/a><\/noindex>. T\u00e4iendavat teavet v\u00f5istluse enda kohta leiate veebilehel<\/a><\/noindex>, samas kui eelmiste aastate tulemused on saadaval siin<\/a><\/noindex>.<\/p>\n

Lahenduse skeem<\/h3>\n

Tippude katmiseks olen proovinud rakendada parameetrilisi algoritme. Need koosnevad tavaliselt kahest osast: lihtsustamise reeglitest (mis ideaalis viivad kerneldamiseni) ja jagamisreeglitest. Lihtsustamise reeglid on sisendi eelt\u00f6\u00f6tlus pol\u00fcnoomse ajaga. Nende reeglite eesm\u00e4rk on viia probleem v\u00f5rreldava v\u00e4iksema suurusega probleemini. Lihtsustamise reeglid on algoritmi k\u00f5ige kulukam osa ja nende rakendamine viib \u00fcldise t\u00f6\u00f6ajani \"Kuidas mitte lihtsalt pol\u00fcnoomse ajani. Meie puhul p\u00f5hinevad jagamisreeglid sellel, et iga tipu puhul tuleb vastuseks v\u00f5tta kas see v\u00f5i tema naaber.<\/p>\n

\u00dcldine skeem on j\u00e4rgmine: rakendame lihtsustamise reegleid, siis valime mingi tipu ja teeme kaks rekursiivset kutset: esimeses me v\u00f5tame selle vastuseks ja teises me v\u00f5tame k\u00f5ik tema naabrid. Seda nimetame selle tipu jagamiseks (branching).<\/p>\n

Sellesse skeemi lisatakse t\u00e4pselt \u00fcks t\u00e4iendav element j\u00e4rgmises l\u00f5igus.<\/p>\n

Ideed jagamisreeglite (branching) jaoks<\/h3>\n

R\u00e4\u00e4gime, kuidas valida tippu, mille kaudu jagunemine toimub.
\nP\u00f5hikontseptsioon on v\u00e4ga ahne algoritmilises m\u00f5ttes: valime maksimaalse astmega tipu ja jaguneme just selle kaudu. Miks tundub, et see on parem? Sest rekursiivse k\u00f5ne teises harus eemaldasime sel viisil v\u00e4ga palju tippe. V\u00f5ime loota, et j\u00e4\u00e4b v\u00e4ike graaf, mille kallal saame kiiresti t\u00f6\u00f6tada.<\/p>\n

See l\u00e4henemine, koos juba arutletud lihtsate kerneldamistehnikatega, ei toimi halvasti, lahendab testid, mille suurus on mitu tuhat tippu. Kuid n\u00e4iteks kuubiliste graafide (st selliste graafide, kus iga tipu aste on kolm) puhul ei toimi see h\u00e4sti.
\nOn veel \u00fcks idee, mis p\u00f5hineb \u00fcsna lihtsalt m\u00f5ttel: kui graaf on mitte\u00fchendatud, saab selle komponentide \u00fchenduvuse \u00fclesande lahendada iseseisvalt, \u00fchendades vastused l\u00f5puks. See on muide see v\u00e4ike lubatud muudatus skeemis, mis kiirendab lahendust: varem t\u00f6\u00f6tasime sellisel juhul komponentide vastuste arvu ajakulu korrutisega, n\u00fc\u00fcd aga summa p\u00f5hjal. Ja branshingu kiirendamiseks tuleb muuta \u00fchendatud graaf mitte\u00fchendatud graafiks.<\/p>\n

Kuidas seda teha? Kui graafis on liitumispunkt, tuleb teha branshing just selle kaudu. Liitumispunkt on selline tipp, mille eemaldamisel graaf kaotab \u00fchenduvuse. K\u00f5ik liitumispunktid graafis saab leida klassikalise algoritmiga lineaarajas. Selline l\u00e4henemine kiirendab branshingut m\u00e4rkimisv\u00e4\u00e4rselt.
\n\"Kuidas
\nIga valitud tipu eemaldamisel laguneb graaf \u00fchenduvuse komponentideks.<\/p>\n

Me teeme nii, kuid soovime rohkem. N\u00e4iteks otsida graafis v\u00e4ikseid tippude l\u00f5ikeid ja teha nende p\u00f5hjal l\u00f5hustamist. T\u00f5husaim tuntud viis, kuidas leida minimaalne globaalne tippude l\u00f5ige, on kasutada Gomori-Hu puud, mille ehitamine v\u00f5tab kubikulise aja. PACE Challenge'i t\u00fc\u00fcpiline graafi suurus on mitu tuhat tippu. Sellises olukorras peab rekursioonipuus igas tipus teostama miljardeid operatsioone. Seega on \u00fclesande lahendamine etten\u00e4htud ajaks lihtsalt v\u00f5imatu.<\/p>\n

Proovime lahendust optimeerida. Minimaalne tippude l\u00f5ige kahe tipu vahel saab leida mis tahes algoritmiga, mis loob maksimaalse voolu. Saame sellele v\u00f5rgule rakendada Dinitzi algoritmi<\/a><\/noindex>, praktikas t\u00f6\u00f6tab see v\u00e4ga kiiresti. Mul on kahtlus, et teoreetiliselt saab t\u00f5endada t\u00f6\u00f6aja hinnangut \"Kuidas, mis on juba t\u00e4iesti vastuv\u00f5etav.<\/p>\n

Olen proovinud mitu korda otsida l\u00f5ikeid juhuslike tippude paaride vahel ja valida neist k\u00f5ige tasakaalustatum. Kahjuks andis see avatud PACE Challenge testides halbu tulemusi. V\u00f5rreldes tipptasemel tippude p\u00f5hjal t\u00f6\u00f6tava algoritmiga, kus rakendatakse s\u00fcgava langemise piirangut, j\u00e4id p\u00e4rast l\u00f5ike otsimist suurem graaf. See on tingitud sellest, et l\u00f5iked osutusid v\u00e4ga tasakaalustamatuks: eemaldades 5-10 tippu, \u00f5nnestus eraldada vaid 15-20.<\/p>\n

V\u00e4\u00e4rib m\u00e4rkimist, et teoreetiliselt kiiremate algoritmide artiklites kasutatakse palju keerukamaid tehnikaid tippude eraldamiseks. Need tehnikad omavad v\u00e4ga keerukat rakendust ning sageli halbu tulemusi aja ja m\u00e4lu osas. Mul ei \u00f5nnestunud neist leida praktikaks piisavalt vastuv\u00f5etavaid lahendusi.<\/p>\n

Kuidas rakendada lihtsustamise reegleid<\/h3>\n

Meil on juba ideed kerneldamise osas. Tuletan meelde:<\/p>\n

    \n
  1. Kui on isolatsioonis tip, siis eemaldage see.<\/li>\n
  2. Kui on tipu kraad 1, eemaldage see ja v\u00f5tke tema naaber vastuseks.<\/li>\n
  3. Kui v\u00e4hemalt on tippu kraad k + 1<\/i>, v\u00f5tke see vastuseks.<\/li>\n<\/ol>\n

    Esimese kahega on k\u00f5ik selge, kolmandaga on \u00fcks nip. Kui naljaka \u00fclesande puhul baarist oli meil \u00fclemine piir, k<\/i>, siis PACE Challenge'is peame lihtsalt leidma minimaalse suurusega tipuka\u8986\u76d6\u3002 see on iseloomulik muundumine otsingu\u00fclesannetest (Search Problem) lahendus\u00fclesanneteks (Decision Problem), sageli ei tehta kahe \u00fclesande vahel vahet. Praktikas, kui kirjutame tipu katte lahendaja, v\u00f5ib vahe olla. N\u00e4iteks nagu kolmandas punktis.<\/p>\n

    Rakenduse seisukohalt on kaks l\u00e4henemisviisi. Esimene meetod nimetatakse Iterative Deepening'iks. See seisneb j\u00e4rgmisest: v\u00f5ime alustada mingist m\u00f5istlikust alumisest piirist vastusele ja seej\u00e4rel k\u00e4ivitada oma algoritmi, kasutades seda piiri \u00fclemise piirina, mitte laskumata rekursiooni madalamale kui see piir. Kui leidsime mingi vastuse, on see garanteeritud optimeeritud, vastasel juhul saame seda piiri \u00fche v\u00f5rra suurendada ja uuesti k\u00e4ivitada.<\/p>\n

    Teine l\u00e4henemine on hoida mingit praegust optimaalselt vastust ja otsida v\u00e4iksema suurusega vastust, muutma seda parameetrit leides k<\/i> lisak\u00e4ikude eemaldamiseks otsingus.<\/p>\n

    P\u00e4rast mitmeid \u00f6iseid katsetusi otsustasin nende kahe meetodi kombinatsiooni kasuks: esmalt k\u00e4ivitan oma algoritmi m\u00f5ne s\u00fcgavuse piiranguga (seades selle nii, et see v\u00f5taks t\u00fchise aja v\u00f5rreldes p\u00f5hilahendusega) ja kasutan parimat leitud lahendust kui \u00fclemist piiri vastusele \u2014 see t\u00e4hendab just seda k<\/i>.<\/p>\n

    2. astme tipud<\/h3>\n

    Oleme 0. ja 1. astme tipudega saanud hakkama. Selgub, et seda saab teha ka 2. astme tippudega, kuid selle jaoks on graafilt vaja keerukamaid operatsioone.<\/p>\n

    Selle selgitamiseks tuleb kuidagi t\u00e4histada tippe. Nimeta 2. astme tipp tippuks v<\/i>, ja tema naabreid \u2014 tipud x<\/i> ja y<\/i>. Edasi l\u00e4heb meil kaks juhtumit.<\/p>\n

      \n
    1. Kui x<\/i> ja y<\/i> \u2014 naabrid. Siis v\u00f5ib vastuseks v\u00f5tta x<\/i> ja y<\/i>, ja v<\/i> eemaldada. T\u00f5epoolest, sellest kolmnurgast peab v\u00e4hemalt kaks tippu vastuseks v\u00f5tma ja me ei kaota, kui v\u00f5tame x<\/i> ja y<\/i>: neil on ilmselt veel naabreid, aga v<\/i> nendel ei ole.<\/li>\n
    2. Kui x<\/i> ja y<\/i> \u2014 mitte naabrid. Siis v\u00e4idetakse, et k\u00f5ik kolm tippu saab kokku liita \u00fcheks. Idee on see, et sellisel juhul on optimaalne vastus, kus me v\u00f5tame kas v<\/i>, v\u00f5i m\u00f5lemad tipud x<\/i> ja y<\/i>. Esiteks peame vastuseks v\u00f5tma k\u00f5ik naabrid x<\/i> ja y<\/i>, ja teises ei ole see tingimata vajalik. See vastab t\u00e4pselt olukordadele, kus me ei arvesta kokku pandud tippu vastusesse ja kus me seda teeme. J\u00e4\u00e4b vaid m\u00e4rkida, et m\u00f5lemal juhul v\u00e4heneb sellise operatsiooni tulemus \u00fchiku v\u00f5rra.<\/li>\n<\/ol>\n

      \"Kuidas<\/p>\n

      Tuleb m\u00e4rkida, et sellise l\u00e4henemise rakendamine on ausalt \u00f6eldes \u00fcsna keeruline t\u00e4pselt l\u00e4bi viia. Tippude \u00fchendamine on keeruline operatsioon, kuna tuleb kopeerida naabrite loendid. Kui seda ei tehta ettevaatlikult, v\u00f5ib saada asymptoottisesti mittesoovitava t\u00f6\u00f6aja (n\u00e4iteks kui p\u00e4rast iga \u00fchendamist kopeerida palju servi). Olen keskendunud t\u00e4ielike teede otsimisele kahe astmega tippude seas ja erinevate erijuhtude lahendamisele, n\u00e4iteks ts\u00fcklitele, mis koosnevad sellistest tipudest v\u00f5i k\u00f5igist sellistest tipudest peale \u00fche.<\/p>\n

      Lisaks peab see operatsioon olema p\u00f6\u00f6ratav, et saaksime rekursioonist naastes grafi algsesse olekusse taastada. Selle tagamiseks ei kustutanud ma \u00fchendatud tippude servade loendeid, seega teadsin lihtsalt, kuhu servad suunata. Selline graafide rakendus n\u00f5uab samuti ettevaatlikkust, kuid tagab ausalt lineaarsed ajad. Ja mitmek\u00fcmne tuhande servaga graafid mahuvad t\u00e4iesti protsessori vahem\u00e4lu, mis annab suurima kiiruselise eelise.<\/p>\n

      Lineaarne ydur<\/h3>\n

      L\u00f5puks, k\u00f5ige huvitavam osa ydurist.<\/p>\n

      Alustuseks meenutame, et bipartiidsetes graafides saab minimaalset tippude katet otsida \"Kuidas. Selleks tuleb rakendada algoritmi Hopcroft-Karpa<\/a><\/noindex> et leida seal maksimaalne paaritus, ja seej\u00e4rel rakendada K\u00f6nigi-Egervari teoreemi.<\/a><\/noindex>.<\/p>\n

      Lineaarse yduride idee on j\u00e4rgmine: esmalt jagame graafi, st iga tipu asemel v<\/i> loome kaks tippu \"Kuidas ja \"Kuidas, ja iga serva asemel u \u2014 v<\/i> loome kaks serva \"Kuidas ja \"Kuidas. Saadud graaf on kahek\u00fcndaline. Leiame sellest minimaalse tippkatte. M\u00f5ned algse graafi tipud sattuvad sinna kaks korda, m\u00f5ned vaid \u00fcks kord ja m\u00f5ned ei satu sinna \u00fcldse. Nemhauseri-Trotteri teoreem v\u00e4idab, et sellisel juhul v\u00f5ib eemaldada tipud, mis ei sattunud sinna kordagi, ja j\u00e4tta alles need, mis sattusid kaks korda. Veelgi enam, see \u00fctleb, et allesj\u00e4\u00e4nud tipud (need, mis sattusid \u00fcks kord) tuleb v\u00e4hemalt pooled v\u00f5tta vastuseks.<\/p>\n

      Just \u00f5ppisime graafis j\u00e4tma mitte rohkem kui 2k<\/i> tipu. T\u00f5epoolest, kui vastuses on v\u00e4hemalt pool k\u00f5igist tipudest, siis ei ole neid seal kokku rohkem kui 2k<\/i>.<\/p>\n

      Siin suutsin teha v\u00e4ikese edusamme. On selge, et nii koostatud tuum s\u00f5ltub sellest, milline minimaalne tippkate kahek\u00fcndalises graafis me valisime. Sooviksin v\u00f5tta sellise, et allesj\u00e4\u00e4nud tipude arv oleks minimaalne. Varem osati seda teha vaid ajaga \"Kuidas. Ma aga m\u00f5tlesin v\u00e4lja selle algoritmi rakenduse ajaga \"Kuidas, seega on seda tuuma v\u00f5imalik otsida graafides, mille suurus on sadade tuhandete tippude piires igas harutamisetapis.<\/p>\n

      Tulemus<\/h3>\n

      Praktika n\u00e4itab, et minu lahendus t\u00f6\u00f6tab h\u00e4sti testides, kus on mitu sadat tippu ja mitu tuhat serva. Sellistes testides v\u00f5ib oodata, et lahendus leitakse poole tunni jooksul. Vastuse leidmise t\u00f5en\u00e4osus suureneb, kui graafikus on piisavalt palju tippusid suure astmega, n\u00e4iteks astmega 10 ja rohkem.<\/p>\n

      Osalemiseks v\u00f5istluses tuli lahendused saata aadressile optil.io<\/a><\/noindex>. Seal esitatud andmete p\u00f5hjal tabeli<\/a><\/noindex>, minu lahendus avatud testides hoiab kolmandat kohta kahek\u00fcmnest, olles selgelt ees teisest. Kui olla t\u00e4iesti aus, siis ei ole t\u00e4iesti selge, kuidas lahendusi v\u00f5istluse jooksul hinnatakse: n\u00e4iteks minu lahendus l\u00e4bib v\u00e4hem teste kui neljandal kohal olev lahendus, kuid t\u00f6\u00f6tab kiiremini nendes, mis tal on.<\/p>\n

      Suletud testide tulemused avaldatakse esimesel juulil.<\/p>\n

      Allikas: 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-novosti-interneta"],"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\udd47Kuidas lahendada NP-raskusi parametriseeritud algoritmide abil | ProHoster","description":"Teaduslik uurimist\u00f6\u00f6 on ilmselt meie \u00f5ppe k\u00f5ige huvitavam osa. Idee on proovida end valitud suunal juba \u00fclikoolis. N\u00e4iteks l\u00e4hevad Software Engineering ja Machine Learning suunalised tudengid sageli teevad teadusprojekte (peamiselt JetBrainsis v\u00f5i Yandexis, kuid mitte ainult). Selles postituses r\u00e4\u00e4gin oma projektist, mis on seotud arvutiteadusega.","canonical_url":"https:\/\/prohoster.info\/et\/blog\/novosti-interneta\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"et_EE","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. \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.","og:url":"https:\/\/prohoster.info\/et\/blog\/novosti-interneta\/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\/et\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}