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

Teadus- ja arendusprojekt on kahtlemata meie \u00f5ppe k\u00f5ige huvitavam osa. Idee on proovida oma valdkonnas k\u00e4tte saada juba \u00fclikoolis. N\u00e4iteks l\u00e4hevad tarkvaraarenduse ja masin\u00f5ppe eriate \u00fcli\u00f5pilased sageli tegema teadusprojekte ettev\u00f5tetesse (peamiselt JetBrainsisse v\u00f5i Yandexisse, kuid mitte ainult).<\/p>\n

Selles postituses r\u00e4\u00e4gin ma oma projektist infotehnoloogia valdkonnas. Projekti k\u00e4igus uurisin ja rakendasin praktikas l\u00e4henemisviise \u00fche k\u00f5ige tuntuma NP-raskete probleemide lahendamiseks: tippkatte probleem<\/b>.<\/p>\n

Praegu areneb kiiresti huvitav l\u00e4henemine NP-rasketele probleemidele \u2014 parametrisestumine algoritmid. \u00dcritan teid teemaga kursis hoida, r\u00e4\u00e4kida m\u00f5nest lihtsast parametrisest algoritmist ja kirjeldada \u00fcht v\u00f5imsat meetodit, mis on mulle v\u00e4ga abiks olnud. Oma tulemusi esitlesin PACE Challenge'i v\u00f5istlusel: avatud testide tulemuste p\u00f5hjal on minu lahendus kolmandal kohal ning l\u00f5plikud tulemused selguvad 1. juulil.<\/p>\n

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

Kohal<\/h3>\n

Minu nimi on Vassili Aljofirov, hetkel l\u00f5petan kolmandat kursust HSE (Rahvusvaheline \u00dclikool) Peterburis. Algoritmid huvitavad mind juba koolip\u00f5lvest saadik, kui \u00f5ppisin Moskvas 179. koolis ja osalesin edukalt infotehnoloogia ol\u00fcmpiaadidel.<\/p>\n

\u041a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0441\u0442\u043e\u0432 \u043f\u043e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0437\u0430\u0445\u043e\u0434\u044f\u0442 \u0432 \u0431\u0430\u0440…<\/h3>\n

N\u00e4ide on v\u00f5etud raamatust \u201eParameterized algorithms\u201c<\/a><\/noindex><\/i><\/p>\n

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

Kuna teie linn on v\u00e4ike, teate t\u00e4pselt, millised paarid k\u00fclastajat k\u00f5ige t\u00f5en\u00e4olisemalt omavahel t\u00fclitsevad, kui nad koos baari tulevad. Teil on nimekiri n<\/i> inimesest, kes tulnud t\u00e4na \u00f5htul baari. Otsustate mitte lasta baari mingisuguseid linnaelanikke nii, et keegi ei kakleks. Samas ei taha teie \u00fclemus kaotada tulu ja oleks pettunud, kui te ei lase baari rohkem kui k<\/i> inimest.<\/p>\n

Kahjuks on \u00fclesanne teie ees klassikaline NP-raskete probleem. Te v\u00f5isite seda teada kui tippkatte probleem<\/a><\/noindex>, v\u00f5i kuidas tippkatte \u00fclesanne. Selliste \u00fclesannete puhul ei ole \u00fcldjuhul teada algoritme, mis t\u00f6\u00f6tavad m\u00f5istliku aja jooksul. Kui olla t\u00e4pne, siis t\u00f5endamata ja \u00fcsna tugev h\u00fcpotees ETH (Exponential Time Hypothesis) \u00fctleb, et seda \u00fclesannet ei saa lahendada ajaga \"Kuidas, see t\u00e4hendab, et oluliselt paremat lahendust kui t\u00e4ielik proovimine pole v\u00f5imalik leida. N\u00e4iteks, oletame, et teie baari on tulemas n = 1000<\/i> inimest. Siis oleks t\u00e4ielik proovimine \"Kuidas v\u00f5imaluste arvu, mis on umbes \"Kuidas \u2014 meeletult palju. \u00d5nneks on teie juhtkond seadnud teile piirangu k = 10<\/i>, nii et kombinatsioonide arv, mida peate l\u00e4bi vaatama, on palju v\u00e4iksem: k\u00fcmne elemendi alamhulkade arvu on \"Kuidas. See on juba parem, kuid ikkagi ei j\u00f5ua te p\u00e4evaga isegi v\u00f5imsas klastris k\u00f5iki kokku lugeda.
\n\"Kuidas
\nKuna barik\u00fclastajate vahel on sellise pingelise suhte konfigureerimisega kakluste t\u00f5en\u00e4osus, ei tohi Bobi, Danieli ja Feodorit sisse lasta. Lahendus, kus j\u00e4\u00e4b v\u00e4lja vaid kaks inimest, ei ole olemas.<\/p>\n

Kas see t\u00e4hendab, et on aeg alla anda ja k\u00f5ik sisse lasta? Vaadakem teisi v\u00f5imalusi. N\u00e4iteks, v\u00f5ib mitte lasta sisse ainult neid, kes v\u00f5ivad kakelda v\u00e4ga paljude inimestega. Kui keegi suudab kakelda v\u00e4hemalt k + 1<\/i> teise inimesega, siis teda kindlasti ei tohi sisse lasta \u2014 vastasel juhul tuleb k\u00f5ik k + 1<\/i> linnaelanikud, kellega ta kakelda v\u00f5iks, v\u00e4lja j\u00e4tta, mis kindlasti h\u00e4irib juhtkonda.<\/p>\n

Oletame, et olete v\u00e4lja visanud k\u00f5ik, keda v\u00f5isite, selle p\u00f5him\u00f5tte j\u00e4rgi. Siis saavad k\u00f5ik teised kakelda mitte rohkem kui k<\/i> inimesega. Neist v\u00e4lja visates k<\/i> inimest, saate \u00e4ra hoida mitte rohkem kui \"Kuidas konflikti. Seega, kui rohkem kui \"Kuidas inimest osaleb v\u00e4hemalt \u00fches konfliktis, siis ei suuda te neid k\u00f5iki \u00e4ra hoida. Kuna, nagu selge, lastakse te kindlasti sisse t\u00e4iesti konfliktitud inimesi, peate l\u00e4bi vaatama k\u00f5ik k\u00fcmne suurused alamhulga kaheksast inimesest. Nende arv on umbes \"Kuidas, ja see operatsioonide arv on juba klastris iesp\u0113jams l\u00e4bi vaadata.<\/p>\n

Kui on v\u00f5imalik ohutult v\u00f5tta v\u00e4ga kokkusobivad inimesi, siis mis saab neist, kes osalevad vaid \u00fches konfliktis? Tegelikult saab ka neid lasta sisse, sulgedes ukse nende vastase ees. T\u00f5si, kui Alice on konfliktis ainult Bobiga, siis kui me lubame sisse ainult Alice, ei kaota me midagi: Bobil v\u00f5ivad olla teised konfliktid ja Alicel ei ole neid kindlasti. Veelgi enam, pole m\u00f5tet mitte lubada m\u00f5lemat. P\u00e4rast selliseid operatsioone j\u00e4\u00e4b j\u00e4rele mitte rohkem \"Kuidas k\u00fclalisi lahendamata saatusega: kokku on meil \"Kuidas konflikti, igas osalevad kaks osalist ja iga\u00fcks osaleb v\u00e4hemalt kahel. See t\u00e4hendab, et j\u00e4\u00e4b vaid l\u00e4bi t\u00f6\u00f6tada \"Kuidas varianti, mis v\u00f5iks piisata poole p\u00e4eva jooksul s\u00fclearvutis.<\/p>\n

Tegelikult on lihtsate arutluste kaudu v\u00f5imalik saavutada veelgi soodsamaid tingimusi. T\u00f5dedes, et me peame kindlasti lahendama k\u00f5ik vaidlused, st igast konfliktis osalevast paarist valima v\u00e4hemalt \u00fche, keda me ei luba sisse. Vaatame sellist algoritmi: v\u00f5tame mis tahes konflikti, kust eemaldame \u00fche osalise ja k\u00e4ivitame rekursiivselt \u00fclej\u00e4\u00e4nud, siis eemaldame teise ja k\u00e4ivitame samuti rekursiivselt. Kuna me igal sammul kedagi v\u00e4lja viskame, on algoritmi rekursiooni puu - binaarne puu s\u00fcgavusega k<\/i>, seega t\u00f6\u00f6tab algoritm kokku \"Kuidas, kus n<\/i> \u2014 harude arv, ja m<\/i> \u2014 servade arv. Meie n\u00e4ites on see umbes k\u00fcmme miljonit, mis arvutatakse mitte ainult s\u00fclearvutis, vaid isegi mobiiltelefonis sekundite jooksul.<\/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 m\u00f5ni parameeter, mis v\u00f5ib olla oluliselt v\u00e4iksem \u00fclesande suurusest.<\/p>\n

K\u00f5ik eelnevad arutelud viisid n\u00e4itena kerneliseerimiseni<\/b> \u2014 \u00fcks levinumaid tehnikaid parameetriseeritud algoritmide loomiseks. Kerneldamine on \u00fclesande suuruse v\u00e4hendamine v\u00e4\u00e4rtuseni, mis on piiratud parameetri funktsiooniga. Saadud \u00fclesannet nimetatakse sageli tervikuks. Nii saime lihtsaid m\u00f5tisklusi tippude astmete \u00fcle, et luua ruutjuur \u00fclesanne Vertex Cover, mis on parameetriseeritud vastuse suurusega. On olemas ka teisi parameetreid, mida selle \u00fclesande jaoks valida (nt Vertex Cover Above LP), kuid arutame just sellist parameetrit.<\/p>\n

Pace Challenge<\/h3>\n

V\u00f5istlus PACE Challenge<\/a><\/noindex> (Parameetriseeritud algoritmide ja arvutuskatsete v\u00e4ljakutse) sai alguse 2015. aastal, et luua link parameetriseeritud algoritmide ja praktikas kasutatavate l\u00e4henemisviiside vahel arvutusprobleemide lahendamiseks. Esimesed kolm v\u00f5istlust keskendusid puu laiuse leidmisele (Treewidth<\/a><\/noindex>), \u0160tejneri puu leidmisele (Steiner Tree<\/a><\/noindex>) ja tippude kogumite leidmisele, mis l\u00f5ikavad silmuseid (Feedback Vertex Set<\/a><\/noindex>). Sel aastal oli \u00fcheks \u00fclesande varasemate seas see, millele saime oma oskusi proovile panna, nimelt \u00fclaltoodud \u00fclesanne tippude katmiseks.<\/p>\n

V\u00f5istlus saavutab iga aastaga populaarsust. Eelinfo kohaselt osales sel aastal ainult tippude katmise probleemi lahendamise v\u00f5istlusel 24 meeskonda. Tuleb m\u00e4rkida, et v\u00f5istlus ei kesta mitte paar tundi ega isegi n\u00e4dalat, vaid mitu kuud. Meeskondadel on v\u00f5imalus uurida kirjandust, v\u00e4lja m\u00f5elda oma originaalne idee ja proovida see ellu viia. Sisuliselt kujutab see v\u00f5istlus endast uurimust\u00f6\u00f6d. K\u00f5ige t\u00f5husamate lahenduste ideed ja auhindade jagamine toimub koos konverentsiga IPEC<\/a><\/noindex> (Rahvusvaheline parameetriseeritud ja t\u00e4pse arvutuse s\u00fcmpoosion) Euroopa suurima ig\u5e74\u5ea6 algoritmilise kokkusaamise raames ALGO<\/a><\/noindex>. T\u00e4iendavat teavet v\u00f5istluse kohta leiate veebisaidil<\/a><\/noindex>, ja varasemate aastate tulemused on saadaval siit<\/a><\/noindex>.<\/p>\n

Lahenduse skeem<\/h3>\n

Ettev\u00f5tmiseks tippkatte \u00fclesanne, olen proovinud rakendada parameetrilisi algoritme. Need koosnevad enamasti kahest osast: lihtsustamise reeglitest (mis ideaalis viivad kerneliseerimisele) ja jagamise reeglitest. Lihtsustamise reeglid on sisendi eelt\u00f6\u00f6tlus pol\u00fcnoomi ajas. Nende reeglite rakendamise eesm\u00e4rk on \u00fclesande v\u00e4hendamine ekvivalentseks v\u00e4iksema suurusega \u00fclesandeks. Lihtsustamise reeglid on algoritmi k\u00f5ige kulukam osa ja just selle osa rakendamine viib \u00fcldise t\u00f6\u00f6tamise ajani. \"Kuidas nagu tavaline pol\u00fcnoomi aeg. Meie puhul p\u00f5hinevad jagamise reeglid sellel, et iga tipu puhul tuleb v\u00f5tta kas see v\u00f5i tema naaber.<\/p>\n

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

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

Ideed jagamise (branching) reeglite jaoks<\/h3>\n

R\u00e4\u00e4kigem sellest, kuidas valida tipp, mille p\u00f5hjal toimib jagamine.
\nPeamine idee on algoritmilises m\u00f5ttes v\u00e4ga ahne: v\u00f5tame tipu maksimaalse astmega ja jagame selle j\u00e4rgi. Miks tundub, et see on parem? Sest teises rekurssi kutsumise haru me seel\u00e4bi eemaldame v\u00e4ga palju tippe. V\u00f5ime arvata, et j\u00e4\u00e4b v\u00e4ike graaf ja sellel me t\u00f6\u00f6tame kiiresti.<\/p>\n

See l\u00e4henemine, mis koosneb juba arutatud lihtsatest kerneliseerimise tehnikatest, n\u00e4itab end korralikult ja lahendab m\u00f5ningaid teste, mille suurus on mitu tuhat tippu. Kuid n\u00e4iteks t\u00f6\u00f6tab see halvasti kuup-graafide puhul (st graafide, mille iga tipu aste on kolm).
\nOn veel \u00fcks idee, mis p\u00f5hineb piisavalt lihtsal m\u00f5ttel: kui graaf on \u00fchendamata, saab selle sidususe komponente s\u00f5ltumatult lahendada, kombineerides vastused l\u00f5puks. See on muide v\u00e4ike lubatud modifikatsioon skeemis, mis kiirendab lahendust oluliselt: varem t\u00f6\u00f6tasime sellisel juhul vastuste komponentide loendamise aegade korrutise alusel, n\u00fc\u00fcd aga summeerime. Ja jagamise kiirendamiseks tuleb muuta \u00fchendatud graaf \u00fchendamatuks.<\/p>\n

Kuidas seda teha? Kui graafis on l\u00f5ikepunkt, tuleb just selle j\u00e4rgi jaguneda. L\u00f5ikepunkt on selline tipp, mille eemaldamisel kaotab graaf \u00fchenduvuse. K\u00f5iki l\u00f5ikepunkte graafis saab leida klassikalise algoritmi abil lineaarse ajaga. Selline l\u00e4henemine kiirendab oluliselt jagunemist.
\n\"Kuidas
\nIga v\u00e4lja toodud tipu eemaldamisel jaguneb graaf \u00fchenduvuseks komponentideks.<\/p>\n

Seda me teeme, kuid sooviksime rohkem. N\u00e4iteks otsida graafis v\u00e4ikseid tippude l\u00f5ikeid ja jagada nende j\u00e4rgi. K\u00f5ige t\u00f5husam tuntud viis minimaalse globaalse tippude l\u00f5ike leidmiseks on kasutada Gomori-Hu puud, mis ehitatakse kubikaajas. PACE Challenge'is on t\u00fc\u00fcpiline graafi suurus mitu tuhat tippu. Sellise olukorra puhul peab iga rekursiooni tipu juures sooritama miljardeid toiminguid. Tundub, et antud aja jooksul selle \u00fclesande lahendamine on lihtsalt v\u00f5imatu.<\/p>\n

Proovime lahendust optimeerida. Minimaalne tippude l\u00f5ige kahe tipuu vahel saab leida igasuguste algoritmide abil, mis ehitavad maksimaalset voolu. Saame sellele v\u00f5rgule rakendada Dinitzi algoritmi<\/a><\/noindex>, mis praktikas t\u00f6\u00f6tab v\u00e4ga kiiresti. Mul on kahtlus, et teoreetiliselt on v\u00f5imalik t\u00f5estada ajakulu hindamist \"Kuidas, mis on juba t\u00e4iesti vastuv\u00f5etav.<\/p>\n

Olen proovinud mitu korda otsida l\u00f5ikeid juhuslike tipude vahel ja v\u00f5tta neist k\u00f5ige tasakaalustatum. Kahjuks andis see PACE Challenge'i avatud testides halbu tulemusi. V\u00f5rdlesin algoritmi, mis jagab maksimaalse astmega tipude j\u00e4rgi, k\u00e4ivitades neid s\u00fcvendi s\u00fcvenemise piiramisega. P\u00e4rast algoritmi, mis p\u00fc\u00fcdis leida l\u00f5iget sellisel viisil, j\u00e4i alles suuremate suurustega graaf.<\/p>\n

On t\u00e4helepanuv\u00e4\u00e4rne, et teoreetiliselt kiirete algoritmide artiklites kasutatakse palju arenenumaid tehnikaid tippude valimiseks jagamiseks. Need tehnikad on v\u00e4ga keerulise rakendusega ja neil on sageli halvad ajakulu ja m\u00e4lu hinnangud. Ma ei suutnud neist v\u00e4lja valida praktiliseks t\u00e4iesti vastuv\u00f5etavaid.<\/p>\n

Kuidas rakendada lihtsustamise reegleid<\/h3>\n

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

    \n
  1. Kui on isoleeritud tipp, eemaldada see.<\/li>\n
  2. Kui on tipptase 1, eemaldage see ja v\u00f5tke selle naaber vastuseks.<\/li>\n
  3. Kui v\u00e4hemalt on tipptase k + 1<\/i>, v\u00f5tke see vastuseks.<\/li>\n<\/ol>\n

    Kahes esimeses on k\u00f5ik selge, kolmandaga on \u00fcks n\u00e4pukas. Kui naljaliselt \u00fclesandes baaris oli meil antud \u00fclempiir k<\/i>, siis PACE Challenge'is peame lihtsalt leidma minimaalsete tipup\u00f5hjendustega katte. See on t\u00fc\u00fcpiline otsimisprobleemide (Search Problem) ja lahendamisprobleemide (Decision Problem) \u00fcleminek, sageli kahe probleemi vahel ei tehta vahet. Praktikas, kui me kirjutame tipukatte lahendajat, v\u00f5ib vahe olla. N\u00e4iteks nagu kolmandas punktis.<\/p>\n

    Rakenduse seisukohalt on v\u00f5imalus l\u00e4heneda kahel viisil. Esimene l\u00e4henemine nimetatakse Iterative Deepening. See seisneb selles, et saame alustada m\u00f5nelt m\u00f5istlikult p\u00f5hjalikes piirangutest ja k\u00e4ivite edasi oma algoritmi, kasutades seda piirangut \u00fclempiirina, mitte laskudes rekursioonidesse madalamale, kui see piirang. Kui oleme leidnud mingi vastuse, on see garanteeritult optimaalselt, vastasel juhul saame seda piirangut \u00fche v\u00f5rra suurendada ja uuesti k\u00e4ivitada.<\/p>\n

    Teine l\u00e4henemine on hoida m\u00f5ningat praegust optimaalse vastuse ja otsida v\u00e4iksema suurusega vastust, muutes selle parameetri leides k<\/i> liigne jooksu harude kiireks k\u00e4rpimiseks.<\/p>\n

    P\u00e4rast mitmeid \u00f6iseid eksperimente j\u00e4in ma kahe meetodi kombinatsiooni juurde: k\u00f5igepealt k\u00e4ivitan oma algoritmi mingi otsimise s\u00fcgavuse piirangu (valides selle nii, et see v\u00f5taks v\u00f5rreldes peamise lahenduse absoluutselt aeglaselt) ja kasutan parimat leitud lahendust \u00fclempiirina - see t\u00e4hendab seda k<\/i>.<\/p>\n

    Tipud tasemel 2<\/h3>\n

    Tipude tasemetega 0 ja 1 oleme koos olnud. Selgub, et sellist saab teha ka tippude tasemel 2, kuid selle jaoks on graafilt vaja keerukamaid operatsioone.<\/p>\n

    Selle selgitamiseks tuleb kuidagi nimetada tipud. Nimetame tasemel 2 tipu 'tipuks' v<\/i>, ja selle naabriteks 'tipud' x<\/i> ja y<\/i>. Edasi on meil kaks juhtumit.<\/p>\n

      \n
    1. Kui x<\/i> ja y<\/i> \u2014 naabrid. Siis saab vastuseks v\u00f5tta x<\/i> ja y<\/i>, vaid v<\/i> eemaldada. Ja t\u00f5epoolest, sellest kolmnurgast tuleb v\u00e4hemalt kaks tippu v\u00f5tta vastuseks ja me ei kaota kindlasti, kui v\u00f5tame x<\/i> ja y<\/i>: neil on t\u00f5en\u00e4oliselt veel naabreid ja v<\/i> neil ei ole.<\/li>\n
    2. Kui x<\/i> ja y<\/i> \u2014 mitte naabritega. Siis v\u00e4idetakse, et k\u00f5ik kolm tippu on v\u00f5imalik kokku liita \u00fcheks. Idee on selles, et sel juhul on olemas optimaalne vastus, kuhu me v\u00f5tame kas v<\/i>, v\u00f5i m\u00f5lemad tippud x<\/i> ja y<\/i>. Tingimusel, et esimesel juhul peame v\u00f5tma vastuseks k\u00f5ik naabrid x<\/i> ja y<\/i>, aga teisel juhul ei ole see tingimata vajalik. See vastab t\u00e4pselt juhtumitele, kui me ei v\u00f5ta kokku liidetud tippu vastuseks ja kui v\u00f5tame. Peab vaid m\u00e4rkima, et m\u00f5lemal juhul v\u00e4heneb vastus p\u00e4rast seda operatsiooni \u00fche v\u00f5rra.<\/li>\n<\/ol>\n

      \"Kuidas<\/p>\n

      Tuleb m\u00e4rkida, et sellise l\u00e4henemise rakendamine ausalt lineaarses ajas on \u00fcsna keeruline. Tippude kokku liitmine on keeruline operatsioon, mille k\u00e4igus tuleb kopida naaberlistid. Kui seda ei tehta ettevaatlikult, v\u00f5ib tulemuseks olla as\u00fcmptootiliselt mitteoptimaalne t\u00f6\u00f6aeg (n\u00e4iteks, kui p\u00e4rast iga kokku liitmist kopeeritakse palju \u00e4\u00e4riseid). Olen peatunud kahe astmega tippudest tervete teede leidmisega ja paljude erijuhtumite, n\u00e4iteks ts\u00fcklite, anal\u00fc\u00fcsimisega nendest tippudest v\u00f5i k\u00f5igist neist, v\u00e4lja arvatud \u00fcks.<\/p>\n

      Lisaks peab see operatsioon olema p\u00f6\u00f6ratav, et saaksime rekursioonist v\u00e4lja naastes taastada graafi algse kujundi. Selle tagamiseks ei olen ma puhastanud kokku liidetud tippude \u00e4\u00e4riste listid, p\u00e4rast mida ma teadsin lihtsalt, kuhu \u00e4\u00e4riseid suunata. Selline graafide teostamine n\u00f5uab samuti ettevaatlikkust, kuid tagab ausa lineaarse aja. Ja paarik\u00fcmne tuhande \u00e4\u00e4risega graafid mahuvad suurep\u00e4raselt protsessori vahem\u00e4lu, mis annab kiirusel suured eelised.<\/p>\n

      Lineaarne s\u00fcdamik<\/h3>\n

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

      K\u00e4esolevalt tuletame meelde, et kahepoolsetes graafides saab minimaalset tipu katet otsida \"Kuidas. Selleks tuleb kasutada algoritmi Hopcroft-Karpa<\/a><\/noindex> , et leida sealt maksimaalne paaristamine, ja seej\u00e4rel kasutada K\u00f6nigi-Egervari teoreemi.<\/a><\/noindex>.<\/p>\n

      Lineaarse s\u00fcdamiku idee on j\u00e4rgmine: esmalt jagame graafi kaheks, see t\u00e4hendab, et iga tipu asemel v<\/i> loome kaks tippu \"Kuidas ja \"Kuidas, ja iga \u00e4\u00e4rise asemel u \u2014 v<\/i> loome kaks \u00e4\u00e4rist. \"Kuidas ja \"KuidasSaadud graaf on kahetipuline. Leiame selles minimaalset tipu katet. Osad algse graafi tipud satuvad sinna kaks korda, osad ainult korra ja m\u00f5ned \u2013 mitte kunagi. Nemhauseri-Trotteri teoreem v\u00e4idab, et sel juhul v\u00f5ib eemaldada tipud, mis ei sattunud kunagi, ja vastuseks v\u00f5tta need, mis sisenesid kaks korda. Veelgi enam, see \u00fctleb, et j\u00e4\u00e4nud tipud (need, mis sattusid \u00fcks kord) peavad vastusena andma v\u00e4hemalt poole.<\/p>\n

      Just \u00f5ppisime, kuidas j\u00e4tta graafikesse mitte rohkem kui 2k<\/i> tipu. Ja t\u00f5epoolest, kui j\u00e4\u00e4b vastuseks v\u00e4hemalt pool k\u00f5igist tipudest, siis ei ole seal tippe rohkem kui 2k<\/i>.<\/p>\n

      Siin olen suutnud teha v\u00e4ikese edusammu. On selge, et sellisel viisil koostatud s\u00fcda s\u00f5ltub sellest, milline minimaalne tipu kate kahetipulises graafis me valisime. Sooviksin valida sellise, et j\u00e4\u00e4nud tippude arv oleks minimaalne. Varem osati seda teha ainult ajaga \"Kuidas. Mina olen aga v\u00e4lja m\u00f5elnud selle algoritmi rakenduse ajaga \"Kuidas, seega saab seda s\u00fcda otsida graafides, kus on sadu tuhandeid tippe igal harutamisetapil.<\/p>\n

      Tulemus<\/h3>\n

      Praktika n\u00e4itab, et minu lahendus t\u00f6\u00f6tab h\u00e4sti testidel, kus on mitu sada tippu ja mitu tuhat serva. Sellistel testidel v\u00f5ib oodata, et lahendus leitakse poole tunni jooksul. Vastuse leidmise t\u00f5en\u00e4osus t\u00f5epoolest suureneb, kui graafis on piisavalt palju k\u00f5rge s\u00f5ltuvuse tippe, n\u00e4iteks s\u00f5ltuvus 10 ja rohkem.<\/p>\n

      V\u00f5istlusel osalemiseks tuli lahendused saata aadressile optil.io<\/a><\/noindex>. Kohtade tabeli p\u00f5hjal, mis seal esitatud on, moodustab minu lahendus avatud testidel kolmanda koha kahek\u00fcmnest suure eduga teisel kohal. Kui olla t\u00e4iesti aus, siis ei ole p\u00e4ris selge, kuidas lahendusi v\u00f5istluse ajal hinnatakse: n\u00e4iteks mu lahendus l\u00e4bib v\u00e4hem teste kui neljanda koha lahendus, kuid nendel, mis ta l\u00e4bib, t\u00f6\u00f6tab kiiremini.<\/a><\/noindex>Tulemused suletud testidel selguvad 1. juulil.<\/p>\n

      Teaduslik uurimist\u00f6\u00f6 on ilmselt k\u00f5ige huvitavam osa meie \u00f5pingutest. Idee on selles, et juba \u00fclikoolis proovida ennast valitud suunas.<\/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-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\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","description":"\ud83e\udd47Kuidas lahendada NP-raskusi, kasutades parametriseeritud algoritme | ProHoster","canonical_url":"https:\/\/prohoster.info\/et\/blog\/news\/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.","og:url":"https:\/\/prohoster.info\/et\/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\/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}]}}