{"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\/sq\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Si si zgjidhin problemet NP-t\u00eb v\u00ebshtira me algoritme parametrike","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Puna k\u00ebrkimore \u00ebsht\u00eb, ndoshta, pjesa m\u00eb interesante e edukimit ton\u00eb. Ideja \u00ebsht\u00eb q\u00eb edhe n\u00eb universitet t\u00eb provoni veten n\u00eb drejtim t\u00eb zgjedhur. P\u00ebr shembull, student\u00ebt nga deg\u00ebt Software Engineering dhe Machine Learning shpesh kryejn\u00eb k\u00ebrkime n\u00eb kompani (n\u00eb shumic\u00ebn e rasteve, JetBrains ose Yandex, por jo vet\u00ebm).<\/p>\n

N\u00eb k\u00ebt\u00eb postim do t\u00eb flas p\u00ebr projektin tim n\u00eb fush\u00ebn e Shkenc\u00ebs Kompjuterike. N\u00eb kuad\u00ebr t\u00eb pun\u00ebs, studova dhe implementova n\u00eb praktik\u00eb qasje p\u00ebr zgjidhjen e nj\u00eb prej problemeve m\u00eb t\u00eb njohura NP-t\u00eb v\u00ebshtira: problemi i mbulimit t\u00eb majave<\/b>.<\/p>\n

Aktualisht, nj\u00eb qasje interesante ndaj problemeve NP-t\u00eb v\u00ebshtira po zhvillohet shum\u00eb shpejt \u2014 algoritmet parametrike. Do t\u00eb p\u00ebrpiqem t'ju njoh me k\u00ebt\u00eb \u00e7\u00ebshtje, t\u00eb flas p\u00ebr disa algoritme parametrike t\u00eb thjeshta dhe t\u00eb p\u00ebrshkruaj nj\u00eb metod\u00eb t\u00eb fuqishme, e cila m\u00eb ka ndihmuar shum\u00eb. Rezultatet e mia i prezantova n\u00eb gar\u00ebn PACE Challenge: sipas testeve t\u00eb hapura, zgjidhja ime z\u00eb vendin e tret\u00eb, dhe rezultatet p\u00ebrfundimtare do t\u00eb njoftohen m\u00eb 1 korrik.<\/p>\n

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

P\u00ebr vet\u00eb<\/h3>\n

Jam Vasily Alf\u00ebrov, tani po p\u00ebrfundoj vitin e tret\u00eb n\u00eb HSE \u2014 Sh\u00ebn Petersburg. M\u00eb jan\u00eb p\u00eblqyer algoritmet q\u00eb nga koha e shkoll\u00ebs kur isha n\u00eb shkoll\u00ebn 179 t\u00eb Mosk\u00ebs dhe merrja pjes\u00eb me sukses n\u00eb olimpiada t\u00eb informatik\u00ebs.<\/p>\n

Nj\u00eb num\u00ebr i caktuar specialist\u00ebsh p\u00ebr algoritme t\u00eb parametrizuara hyjn\u00eb n\u00eb bar...<\/h3>\n

Shembulli \u00ebsht\u00eb marr\u00eb nga libri \u00abAlgoritmet parametrike\u00bb<\/a><\/noindex><\/i><\/p>\n

Imagjinoni se jeni roje n\u00eb nj\u00eb bar n\u00eb nj\u00eb qytet t\u00eb vog\u00ebl. \u00c7do t\u00eb premte, gjysma e qytetit vjen n\u00eb barin tuaj p\u00ebr t'u relaksuar, \u00e7ka ju shkakton shum\u00eb telashe: duhet t\u00eb nxirrni nga barra vizitor\u00ebt e trazuar p\u00ebr t\u00eb parandaluar ndodhit\u00eb. N\u00eb fund t\u00eb fundit, ju m\u00ebrzitet dhe vendosni t\u00eb merrni masa parandaluese.<\/p>\n

Duke qen\u00eb se qyteti \u00ebsht\u00eb i vog\u00ebl, ju e dini p\u00ebrfundimisht se cilat \u00e7ifte vizitor\u00ebsh me probabilitet t\u00eb lart\u00eb do t\u00eb grinden n\u00ebse hyn\u00eb n\u00eb bar s\u00eb bashku. Keni nj\u00eb list\u00eb t\u00eb n<\/i> personave q\u00eb do t\u00eb vijn\u00eb sonte n\u00eb bar. Vendosni t\u00eb mos i lejoni disa banor\u00eb n\u00eb bar n\u00eb nj\u00eb m\u00ebnyr\u00eb q\u00eb askush t\u00eb mos p\u00ebrfshihet n\u00eb nj\u00eb rrebesht. N\u00eb t\u00eb nj\u00ebjt\u00ebn koh\u00eb, shefi juaj nuk d\u00ebshiron t\u00eb humbas\u00eb fitimet dhe do t\u00eb jet\u00eb i pak\u00ebnaqur n\u00ebse nuk lejoni m\u00eb shum\u00eb se k<\/i> persona.<\/p>\n

Fatkeq\u00ebsisht, problemi q\u00eb keni p\u00ebrpara \u00ebsht\u00eb nj\u00eb problem klasik NP-t\u00eb v\u00ebshtir\u00eb. Mund t\u00eb ket\u00eb qen\u00eb e njohur si Mbulimi i Majave<\/a><\/noindex>, ose si p\u00ebr problemin e mbulimit t\u00eb pikave. P\u00ebr k\u00ebto lloje problemesh, n\u00eb p\u00ebrgjith\u00ebsi nuk dihen algoritma q\u00eb funksionojn\u00eb n\u00eb nj\u00eb koh\u00eb t\u00eb pranueshme. N\u00ebse jemi sakt\u00eb, hipoteza e pa provuar dhe mjaft e fort\u00eb ETH (Hipoteza e Koh\u00ebs Eksponenciale) thot\u00eb se ky problem nuk zgjidhet brenda nj\u00eb kohe \"Si, dmth nuk ka ndonj\u00eb zgjidhje q\u00eb \u00ebsht\u00eb duksh\u00ebm m\u00eb e mir\u00eb se sa p\u00ebrmbytja e plot\u00eb. P\u00ebr shembull, le t\u00eb supozojm\u00eb se do t\u00eb vij\u00eb n\u00eb barin tuaj n = 1000<\/i> njer\u00ebz. Pastaj, p\u00ebrmbytja e plot\u00eb do t\u00eb p\u00ebrmbante \"Si mund\u00ebsi, q\u00eb \u00ebsht\u00eb p\u00ebraf\u00ebrsisht \"Si \u2014 jasht\u00ebzakonisht shum\u00eb. P\u00ebr fat t\u00eb mir\u00eb, udh\u00ebheqja juaj ju ka v\u00ebn\u00eb nj\u00eb kufi k = 10<\/i>, k\u00ebshtu q\u00eb numri i kombinimeve q\u00eb duhet t\u00eb shqyrtoni \u00ebsht\u00eb shum\u00eb m\u00eb i vog\u00ebl: numri i n\u00ebngrupeve me dhjet\u00eb elemente \u00ebsht\u00eb \"Si. Kjo \u00ebsht\u00eb m\u00eb mir\u00eb, por p\u00ebrs\u00ebri nuk do t\u00eb num\u00ebrohet brenda nj\u00eb dite madje as n\u00eb nj\u00eb klaster t\u00eb fuqish\u00ebm.
\n\"Si
\nP\u00ebr t\u00eb p\u00ebrjashtuar mund\u00ebsin\u00eb e nj\u00eb rrethimi n\u00eb nj\u00eb konfigurim t\u00eb till\u00eb t\u00eb tensioneve nd\u00ebrmjet vizitor\u00ebve t\u00eb barit, duhet t\u00eb mos lejoni Bobin, Danielin dhe Fyodorin. Zgjidhjet, ku ngel\u00ebn vet\u00ebm dy, nuk ekzistojn\u00eb.<\/p>\n

A do t\u00eb thot\u00eb kjo se \u00ebsht\u00eb koha t\u00eb dor\u00ebzoheni dhe t\u00eb lejoni t\u00eb gjith\u00eb? Le t\u00eb shqyrtojm\u00eb mund\u00ebsi t\u00eb tjera. Pra, p\u00ebr shembull, mund t\u00eb mos lejoni vet\u00ebm ata q\u00eb p\u00ebrballen me nj\u00eb num\u00ebr shum\u00eb t\u00eb madh njer\u00ebzish. N\u00ebse dikush mund t\u00eb p\u00ebrballet me t\u00eb pakt\u00ebn k + 1<\/i> njer\u00ebz t\u00eb tjer\u00eb, at\u00ebher\u00eb ai nuk duhet lejuar \u2014 p\u00ebrndryshe do t\u00eb duhet t\u00eb mos lejoni t\u00eb gjith\u00eb k + 1<\/i> banor\u00ebt, me t\u00eb cil\u00ebt mund t\u00eb p\u00ebrballet, q\u00eb do t\u00eb shqet\u00ebsoj\u00eb udh\u00ebheqjen.<\/p>\n

Le t\u00eb supozojm\u00eb se keni hequr t\u00eb gjith\u00eb ata q\u00eb mund\u00ebt me k\u00ebt\u00eb parim. Pastaj, t\u00eb gjith\u00eb t\u00eb tjer\u00ebt mund t\u00eb p\u00ebrballen me m\u00eb shum\u00eb se k<\/i> njer\u00ebz. Duke hequr prej tyre k<\/i> njer\u00ebz, mund t\u00eb parandaloni m\u00eb shum\u00eb se \"Si konflikte. K\u00ebshtu, n\u00ebse gjithsej m\u00eb shum\u00eb se \"Si njer\u00ebz marrin pjes\u00eb n\u00eb t\u00eb pakt\u00ebn nj\u00eb konflikt, at\u00ebher\u00eb me siguri nuk do t\u00eb mund t\u00eb parandaloni t\u00eb gjith\u00eb. Gjithashtu, \u00ebsht\u00eb e qart\u00eb se njer\u00ebzit q\u00eb fare nuk kan\u00eb konflikte duhet patjet\u00ebr t'i lejoni, k\u00ebshtu q\u00eb duhet t\u00eb shqyrtoni t\u00eb gjitha n\u00ebngrupet me madh\u00ebsi dhjet\u00eb nga dyqind njer\u00ebz. Ato jan\u00eb p\u00ebraf\u00ebrsisht \"Si, dhe nj\u00eb sasi e till\u00eb operimesh tashm\u00eb mund t\u00eb shqyrtohet n\u00eb nj\u00eb klaster.<\/p>\n

N\u00ebse mund t\u00eb marrim personalitete t\u00ebr\u00ebsisht jo konfliktuale, \u00e7far\u00eb ndodh me ata q\u00eb marrin pjes\u00eb vet\u00ebm n\u00eb nj\u00eb konflikt? N\u00eb t\u00eb v\u00ebrtet\u00eb, ata gjithashtu mund t\u00eb priten, duke mbyllur dyert p\u00ebrpara kund\u00ebrshtarit t\u00eb tyre. N\u00eb fakt, n\u00ebse Alicia ka nj\u00eb konflikt vet\u00ebm me Bobin, n\u00ebse pranojm\u00eb Alician nga ata dy, ne nuk do t\u00eb humbim: Bobi mund t\u00eb ket\u00eb konflikte t\u00eb tjera, nd\u00ebrsa Alicia sigurisht nuk ka. P\u00ebr m\u00eb tep\u00ebr, \u00ebsht\u00eb pa kuptim t\u00eb mos lejojm\u00eb asnj\u00ebrin. Pas k\u00ebtyre operacioneve, mbeten jo m\u00eb shum\u00eb se \"Si mysafir\u00eb me fatin e pazgjidhur: gjithsej kemi \"Si konflikte, ku secili ka dy pjes\u00ebmarr\u00ebs dhe secili merr pjes\u00eb t\u00eb pakt\u00ebn n\u00eb dy. Pra, mbetet t\u00eb zgjidhen vet\u00ebm \"Si mund\u00ebsi, q\u00eb mjafton p\u00ebr t\u00eb llogaritur brenda nj\u00eb gjysm\u00eb dite n\u00eb nj\u00eb laptop.<\/p>\n

N\u00eb t\u00eb v\u00ebrtet\u00eb, me arsyetim t\u00eb thjesht\u00eb mund t\u00eb arrijm\u00eb kushte edhe m\u00eb atraktive. V\u00ebrejm\u00eb se na nevojitet t\u00eb zgjidhim t\u00eb gjitha mosmarr\u00ebveshjet, pra nga \u00e7do \u00e7ift konfliktual t\u00eb zgjedhim t\u00eb pakt\u00ebn nj\u00eb njeri, q\u00eb nuk do ta pranojm\u00eb. Le t\u00eb shqyrtojm\u00eb nj\u00eb algorit\u00ebm t\u00eb till\u00eb: t\u00eb marrim ndonj\u00eb konflikt, nga i cili heqim nj\u00eb pjes\u00ebmarr\u00ebs dhe t\u00eb fillojm\u00eb rekursivisht nga pjesa q\u00eb mbetet, pastaj t\u00eb heqim tjetrin dhe gjithashtu t\u00eb fillojm\u00eb rekursivisht. Duke qen\u00eb se n\u00eb \u00e7do hap heqim dik\u00eb, struktura e rekursions s\u00eb k\u00ebtij algoritmi \u00ebsht\u00eb nj\u00eb pem\u00eb binar\u00eb me thell\u00ebsi k<\/i>, pra algoritmi punon p\u00ebr nj\u00eb total prej \"Siindex n<\/i> \u2013 numri i majave, dhe m<\/i> \u2013 numri i faltave. N\u00eb shembullin ton\u00eb, ky num\u00ebr \u00ebsht\u00eb rreth dhjet\u00eb milion\u00eb, q\u00eb llogaritet p\u00ebr shpejt\u00ebsi n\u00ebn sekonda jo vet\u00ebm n\u00eb laptop, por edhe n\u00eb nj\u00eb telefon mobil.<\/p>\n

Shembulli i m\u00ebsip\u00ebrm \u00ebsht\u00eb nj\u00eb shembull i algoritmit t\u00eb parametrizuar<\/b>. Algoritmet e parametrizuar jan\u00eb ato algoriteme q\u00eb punojn\u00eb n\u00eb koh\u00eb f(k) poly(n)<\/i>index p<\/i> \u2013 polinom, f<\/i> \u2013 funksion i llogaritsh\u00ebm, dhe k<\/i> \u2013 ndonj\u00eb parameter, i cili, \u00ebsht\u00eb tep\u00ebr mundsh\u00ebm, do t\u00eb jet\u00eb shum\u00eb her\u00eb m\u00eb i vog\u00ebl se madh\u00ebsia e problemit.<\/p>\n

T\u00eb gjitha arsyetimet deri n\u00eb k\u00ebt\u00eb algorit\u00ebm \u00e7ojn\u00eb n\u00eb shembullin k\u00ebrnelizimit<\/b> \u2014 nj\u00eb nga teknik\u00ebt e zakonshme p\u00ebr krijimin e algoritm\u00ebve t\u00eb parameterizuar. Kernelizimi \u00ebsht\u00eb zvog\u00eblimi i madh\u00ebsis\u00eb s\u00eb detyr\u00ebs n\u00eb nj\u00eb vler\u00eb t\u00eb kufizuar nga funksioni i parametrave. Detyra e marr\u00eb shpesh quhet b\u00ebrtham\u00eb. K\u00ebshtu, me arsyetime t\u00eb thjeshta mbi shkall\u00ebt e pik\u00ebve, arrit\u00ebm nj\u00eb b\u00ebrthame katrore p\u00ebr detyr\u00ebn e Vertex Cover, e parametrizuar sipas madh\u00ebsis\u00eb s\u00eb p\u00ebrgjigjes. Ekzistojn\u00eb edhe parametra t\u00eb tjer\u00eb q\u00eb mund t\u00eb zgjidhen p\u00ebr k\u00ebt\u00eb detyr\u00eb (p\u00ebr shembull, Vertex Cover Above LP), por ne do t\u00eb diskutojm\u00eb pik\u00ebrisht k\u00ebt\u00eb parametrin.<\/p>\n

Pace Challenge<\/h3>\n

Gar\u00eb PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) u themelua n\u00eb vitin 2015 p\u00ebr t\u00eb vendosur lidhjen midis algoritm\u00ebve t\u00eb parametrizuar dhe qasjeve q\u00eb p\u00ebrdoren n\u00eb praktik\u00eb p\u00ebr zgjidhjen e problemeve kompjuterike. Garat e para tre ishin t\u00eb dedikuara p\u00ebr k\u00ebrkimin e gjer\u00ebsi s\u00eb pem\u00ebs s\u00eb grafit (Treewidth<\/a><\/noindex>), k\u00ebrkimin e pem\u00ebs s\u00eb Steinert (Steiner Tree<\/a><\/noindex>) dhe k\u00ebrkimin e nj\u00eb grupi pikash q\u00eb prishin ciklet (Feedback Vertex Set<\/a><\/noindex>). N\u00eb k\u00ebt\u00eb vit, nj\u00eb nga detyrat n\u00eb t\u00eb cilat mund t\u00eb provoheshin aft\u00ebsit\u00eb ishte detyra e mbuluar nga pika e p\u00ebrmendur m\u00eb sip\u00ebr.<\/p>\n

Gara po fiton popullaritet \u00e7do vit. N\u00ebse besoni t\u00eb dh\u00ebnat paraprak, k\u00ebt\u00eb vit n\u00eb gar\u00ebn p\u00ebr zgjidhjen e detyr\u00ebs s\u00eb mbulimit t\u00eb pikave mor\u00ebn pjes\u00eb 24 ekipe. Vlen t\u00eb theksohet se gara nuk zgjat disa or\u00eb dhe as nj\u00eb jav\u00eb, por disa muaj. Ekipet kan\u00eb mund\u00ebsin\u00eb t\u00eb studiojn\u00eb literatur\u00ebn, t\u00eb mendojn\u00eb nj\u00eb ide origjinale dhe t\u00eb p\u00ebrpiqen ta realizojn\u00eb at\u00eb. N\u00eb thelb, kjo gar\u00eb p\u00ebrfaq\u00ebson nj\u00eb pun\u00eb k\u00ebrkimore. Ideja e zgjidhjeve m\u00eb efektive dhe shpallja e fituesve do t\u00eb ndodhin s\u00eb bashku me konferenc\u00ebn IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) brenda mbledhjes m\u00eb t\u00eb madhe vjetore algorithmi n\u00eb Europ\u00eb ALGO<\/a><\/noindex>. Informacione m\u00eb t\u00eb holl\u00ebsishme mbi gar\u00ebn vet\u00eb mund t\u00eb gjenden n\u00eb website<\/a><\/noindex>, dhe rezultatet e viteve t\u00eb kaluara jan\u00eb t\u00eb vendosura k\u00ebtu<\/a><\/noindex>.<\/p>\n

Schemi i zgjidhjes<\/h3>\n

P\u00ebr t\u00eb p\u00ebrballuar detyr\u00ebn e mbulimit t\u00eb majave, provova t\u00eb aplikoj algoritme t\u00eb parametrizuara. Ato, n\u00eb p\u00ebrgjith\u00ebsi, p\u00ebrb\u00ebhen nga dy pjes\u00eb: rregullat e thjeshtimit (t\u00eb cilat n\u00eb m\u00ebnyr\u00eb ideale \u00e7ojn\u00eb n\u00eb kernelizim) dhe rregullat e ndarjes. Rregullat e thjeshtimit jan\u00eb nj\u00eb p\u00ebrgatitje e hyrjes n\u00eb koh\u00eb polinomiale. Q\u00ebllimi i aplikimit t\u00eb k\u00ebtyre rregullave \u00ebsht\u00eb t\u00eb reduktoj\u00eb detyr\u00ebn n\u00eb nj\u00eb detyr\u00eb ekuivalente me nj\u00eb madh\u00ebsi m\u00eb t\u00eb vog\u00ebl. Rregullat e thjeshtimit jan\u00eb pjesa m\u00eb e kushtueshme e algoritmit, dhe aplikimi i k\u00ebsaj pjes\u00eb \u00e7on n\u00eb nj\u00eb koh\u00eb totale t\u00eb funksionimit \"Si n\u00eb vend t\u00eb koh\u00ebs s\u00eb thjesht\u00eb polinomiale. N\u00eb rastin ton\u00eb, rregullat e ndarjes jan\u00eb t\u00eb bazuara n\u00eb faktin se p\u00ebr \u00e7do maj\u00eb duhet t\u00eb marrim si p\u00ebrgjigje ose at\u00eb, ose fqinj\u00ebn e saj.<\/p>\n

Schemi i p\u00ebrgjithsh\u00ebm \u00ebsht\u00eb ky: aplikojm\u00eb rregullat e thjeshtimit, pastaj zgjedhim ndonj\u00eb maj\u00eb dhe b\u00ebjm\u00eb dy thirrje_recursive: n\u00eb t\u00eb par\u00ebn ne e marrim at\u00eb si p\u00ebrgjigje, nd\u00ebrsa n\u00eb t\u00eb dyt\u00ebn marrim t\u00eb gjith\u00eb fqinj\u00ebt e saj. Kjo e quajm\u00eb ndarje (brancho) n\u00ebp\u00ebrmjet k\u00ebsaj maje.<\/p>\n

N\u00eb k\u00ebt\u00eb skem\u00eb do t\u00eb b\u00ebhet pik\u00ebrisht nj\u00eb shtes\u00eb n\u00eb paragrafin e ardhsh\u00ebm.<\/p>\n

Ide p\u00ebr rregullat e ndarjes (brancho)<\/h3>\n

Le t\u00eb diskutojm\u00eb si t\u00eb zgjedhim nj\u00eb maj\u00eb, p\u00ebr t\u00eb cil\u00ebn do t\u00eb ndodh\u00eb ndarja.
\nIdeja kryesore \u00ebsht\u00eb shum\u00eb lakmitare n\u00eb kuptimin algoritmik: le t\u00eb marr\u00eb nj\u00eb maj\u00eb me grad\u00eb maksimale dhe t\u00eb ndajm\u00eb p\u00ebrmes saj. Pse duket se k\u00ebshtu \u00ebsht\u00eb m\u00eb mir\u00eb? Sepse n\u00eb deg\u00ebn e dyt\u00eb t\u00eb thirrjes_recursive ne n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb do t\u00eb heqim shum\u00eb maja. Mund t\u00eb presim se do t\u00eb mbeten nj\u00eb grafik i vog\u00ebl dhe mbi t\u00eb do t\u00eb punojm\u00eb shpejt.<\/p>\n

Ky qasje me teknikat e thjeshta t\u00eb diskutuar p\u00ebr kernelizimin tregon rezultate t\u00eb mira, zgjidh disa teste me mij\u00ebra maja. Por, p\u00ebr shembull, nuk funksionon mir\u00eb p\u00ebr grafikat kubike (dometh\u00ebn\u00eb grafikat, ku grada e \u00e7do maje \u00ebsht\u00eb e barabart\u00eb me tre).
\nKa nj\u00eb ide tjet\u00ebr, e bazuar n\u00eb nj\u00eb mendim mjaft t\u00eb thjesht\u00eb: n\u00ebse grafiku \u00ebsht\u00eb i palidhur, detyr\u00ebn mbi komponent\u00ebt e tij lidhur mund ta zgjidhim n\u00eb m\u00ebnyr\u00eb t\u00eb pavarur, duke kombinuar p\u00ebrgjigjet n\u00eb fund. Kjo, p\u00ebr fat t\u00eb keq, \u00ebsht\u00eb nj\u00eb modifikim i vog\u00ebl i premtuar n\u00eb skem\u00eb, q\u00eb do t\u00eb p\u00ebrshpejtoj\u00eb zgjidhjen: m\u00eb par\u00eb n\u00eb nj\u00eb rast t\u00eb till\u00eb ne punonim me shum\u00ebn e koh\u00ebve t\u00eb llogaritjes s\u00eb p\u00ebrgjigjeve t\u00eb komponent\u00ebve, nd\u00ebrsa tani punojm\u00eb me shifr\u00ebn e tyre. Dhe p\u00ebr t\u00eb p\u00ebrshpejtuar ndarjen, duhet t\u00eb kthejm\u00eb grafikun e lidhur n\u00eb nj\u00eb grafik t\u00eb palidhur.<\/p>\n

Si si e b\u00ebr\u00eb? N\u00ebse grafi ka nj\u00eb pik\u00eb bashkimi, duhet t\u00eb branchojm\u00eb pik\u00ebrisht aty. Pika e bashkimin \u00ebsht\u00eb maja e till\u00eb, me zhdukje t\u00eb s\u00eb cil\u00ebs grafi humbet lidhshm\u00ebrin\u00eb. T\u00eb gjitha pik\u00ebt e bashkimit n\u00eb graf mund t\u00eb gjenden me nj\u00eb algorit\u00ebm klasik n\u00eb koh\u00eb lineare. Ky qasje ndjesh\u00ebm p\u00ebrshpejton branchoimin.
\n\"Si
\nMe heqjen e cil\u00ebsdo prej kulm\u00ebve t\u00eb ve\u00e7uara, grafi do t\u00eb shp\u00ebrb\u00ebhet n\u00eb componente lidhshm\u00ebrie.<\/p>\n

K\u00ebt\u00eb do ta b\u00ebjm\u00eb, por d\u00ebshirojm\u00eb m\u00eb shum\u00eb. P\u00ebr shembull, t\u00eb k\u00ebrkojm\u00eb n\u00eb graf prerje t\u00eb vogla kulmore dhe t\u00eb kryejm\u00eb ndarje sipas kulm\u00ebve n\u00eb t\u00eb. M\u00ebnyra m\u00eb efikase q\u00eb e njoh p\u00ebr t\u00eb gjetur prerjen minimale globale kulmore \u00ebsht\u00eb t\u00eb p\u00ebrdorim pem\u00ebn Gomori-Hu, e cila nd\u00ebrtohet n\u00eb koh\u00eb kubike. N\u00eb PACE Challenge, p\u00ebrmasat tipike t\u00eb grafit jan\u00eb disa mij\u00ebra kulme. N\u00eb k\u00ebt\u00eb rast, n\u00eb secil\u00ebn kulm t\u00eb recursit duhen kryer miliarda operacione. K\u00ebshtu, zgjidhja e problemit brenda koh\u00ebs s\u00eb caktuar \u00ebsht\u00eb thjesht e pamundur.<\/p>\n

Le t\u00eb p\u00ebrpiqemi t\u00eb optimizojm\u00eb zgjidhjen. Prerja minimale kulmore midis nj\u00eb \u00e7ifti kulmesh mund t\u00eb gjendet me ndihm\u00ebn e \u00e7do algoritmi q\u00eb nd\u00ebrton fluks maksimal. Mund t\u00eb p\u00ebrdorim n\u00eb nj\u00eb rrjet t\u00eb till\u00eb algoritmin e Dinic<\/a><\/noindex>, n\u00eb praktik\u00eb ai punon shum\u00eb shpejt. Kam dyshime se teorikisht \u00ebsht\u00eb e mundur t\u00eb provohet nj\u00eb vler\u00ebsim p\u00ebr koh\u00ebn e funksionimit \"Si, q\u00eb \u00ebsht\u00eb tashm\u00eb mjaft e pranueshme.<\/p>\n

Kam provuar disa her\u00eb t\u00eb k\u00ebrkoj prerje midis \u00e7ifteve t\u00eb kulmeve t\u00eb rast\u00ebsishme dhe t\u00eb marr nga ato m\u00eb t\u00eb balancuara. Fatkeq\u00ebsisht, n\u00eb provat e hapura t\u00eb PACE Challenge, kjo jap nj\u00eb rezultat t\u00eb keq. Kam krahasuar me algoritmin q\u00eb ndan n\u00eb kulmet me grad\u00ebn maksimale, duke i drejtuar ato me nj\u00eb kufizim n\u00eb thell\u00ebsin\u00eb e zbritjes. Pas algoritmit q\u00eb p\u00ebrpiqet t\u00eb gjej\u00eb prerjen n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb, mbet\u00ebn grafe t\u00eb m\u00ebdha. Kjo \u00ebsht\u00eb p\u00ebr shkak se prerjet ishin shum\u00eb t\u00eb pap\u00ebrshtatshme: duke hequr 5-10 kulme, arrinim t\u00eb izolojm\u00eb vet\u00ebm 15-20.<\/p>\n

Duhet t\u00eb theksohet se n\u00eb artikujt q\u00eb flasin p\u00ebr algoritmet m\u00eb t\u00eb shpejta teorike, p\u00ebrdoren teknika shum\u00eb m\u00eb t\u00eb avancuara p\u00ebr zgjedhjen e kulmeve p\u00ebr ndarje. K\u00ebto teknika kan\u00eb nj\u00eb realizim shum\u00eb t\u00eb komplikuar dhe shpesh ofrojn\u00eb vler\u00ebsime t\u00eb dob\u00ebta p\u00ebr koh\u00ebn dhe kujtes\u00ebn. Nuk arrita t\u00eb theksoj ndonj\u00eb nga to si mjaft t\u00eb pranueshme p\u00ebr praktik\u00ebn.<\/p>\n

Si t\u00eb aplikoni rregullat e thjeshtimit<\/h3>\n

Kemi tashm\u00eb ide p\u00ebr kernelizimin. M\u00eb kujtohet:<\/p>\n

    \n
  1. N\u00ebse ka nj\u00eb kulm t\u00eb izoluar, hiqeni at\u00eb.<\/li>\n
  2. N\u00ebse ka nj\u00eb kulm me grad\u00eb 1, hiqeni at\u00eb dhe merrni fqinjit e saj si p\u00ebrgjigje.<\/li>\n
  3. N\u00ebse ka nj\u00eb kulm me grad\u00eb t\u00eb pakt\u00ebn k + 1<\/i>, merreni at\u00eb si p\u00ebrgjigje.<\/li>\n<\/ol>\n

    Me dy t\u00eb parat gjith\u00e7ka \u00ebsht\u00eb e qart\u00eb, me t\u00eb tretin ka nj\u00eb hile. N\u00ebse n\u00eb problemin e humorit rreth barit na u dha nj\u00eb kufizim t\u00eb sip\u00ebrm p\u00ebr k<\/i>, n\u00eb PACE Challenge thjesht duhet t\u00eb gjejm\u00eb nj\u00eb mbulim kulmor t\u00eb madh\u00ebsis\u00eb minimale. Ky \u00ebsht\u00eb nj\u00eb transformim tipik i problemeve t\u00eb k\u00ebrkimit (Search Problem) n\u00eb problemet e zgjidhjes (Decision Problem), shpesh nuk b\u00ebhet ndonj\u00eb dallim midis dy llojeve t\u00eb problemeve. N\u00eb praktik\u00eb, n\u00ebse ne shkruajm\u00eb nj\u00eb zgjidh\u00ebs p\u00ebr problemin e mbulimit kulmor, dallimi mund t\u00eb ekzistoj\u00eb. P\u00ebr shembull, si\u00e7 \u00ebsht\u00eb n\u00eb pik\u00ebn e tret\u00eb.<\/p>\n

    Nga pik\u00ebpamja e zbatimit, mund t\u00eb veprohet n\u00eb dy m\u00ebnyra. Qasja e par\u00eb quhet Iterative Deepening. Ajo p\u00ebrb\u00ebhet nga kjo: ne mund t\u00eb fillojm\u00eb me nj\u00eb kufizim t\u00eb arsyesh\u00ebm posht\u00eb p\u00ebr p\u00ebrgjigjen, dhe m\u00eb pas t\u00eb fillojm\u00eb algoritmin ton\u00eb duke p\u00ebrdorur k\u00ebt\u00eb kufizim si kufizim t\u00eb sip\u00ebrm p\u00ebr p\u00ebrgjigjen, pa shkuar n\u00eb rekursiv\u00eb m\u00eb posht\u00eb se ky kufizim. N\u00ebse kemi gjetur nj\u00eb p\u00ebrgjigje, ajo \u00ebsht\u00eb garantuar t\u00eb jet\u00eb optimale, ndryshe mund t\u00eb rrisim k\u00ebt\u00eb kufizim me nj\u00eb dhe t\u00eb fillojm\u00eb p\u00ebrs\u00ebri.<\/p>\n

    Qasja tjet\u00ebr \u00ebsht\u00eb t\u00eb mbajm\u00eb nj\u00eb ndonj\u00eb p\u00ebrgjigje aktuale optimale dhe t\u00eb k\u00ebrkojm\u00eb nj\u00eb p\u00ebrgjigje me nj\u00eb madh\u00ebsi m\u00eb t\u00eb vog\u00ebl, duke ndryshuar k\u00ebt\u00eb paramet\u00ebr kur e gjejm\u00eb k<\/i> p\u00ebr t\u00eb b\u00ebr\u00eb ndonj\u00eb prerje t\u00eb madhe t\u00eb deg\u00ebve t\u00eb kota n\u00eb k\u00ebrkim.<\/p>\n

    Pas disa eksperimenteve gjat\u00eb nat\u00ebs, u ndala te kombinimi i k\u00ebtyre dy m\u00ebnyrave: fillimisht e filloj algoritmin tim me nj\u00eb kufizim p\u00ebr thell\u00ebsin\u00eb e k\u00ebrkimit (duke e zgjedhur at\u00eb, q\u00eb t\u00eb marr\u00eb nj\u00eb koh\u00eb t\u00eb par\u00ebnd\u00ebsishme n\u00eb krahasim me zgjidhjen kryesore) dhe e p\u00ebrdor zgjidhjen m\u00eb t\u00eb mir\u00eb t\u00eb gjetur si kufizim t\u00eb sip\u00ebrm p\u00ebr p\u00ebrgjigjen \u2014 pra, p\u00ebr ate t\u00eb nj\u00ebjt\u00ebn k<\/i>.<\/p>\n

    Kulmet me grad\u00eb 2<\/h3>\n

    Me kulmet me grad\u00eb 0 dhe 1 e dim\u00eb. Raste q\u00eb kjo mund t\u00eb b\u00ebhet edhe me kulmet me grad\u00eb 2, por p\u00ebr k\u00ebt\u00eb do t\u00eb k\u00ebrkohen operacione m\u00eb t\u00eb nd\u00ebrlikuara n\u00eb graf.<\/p>\n

    P\u00ebr ta shpjeguar k\u00ebt\u00eb, duhet ndonj\u00ebher\u00eb t\u00eb sh\u00ebnohet kulmi. Le ta quajm\u00eb kulmin me grad\u00eb 2 si kulm v<\/i>, dhe fqinjit e tij si kulmet x<\/i> dhe y<\/i>. M\u00eb pas do t\u00eb kemi dy raste.<\/p>\n

      \n
    1. Kur x<\/i> dhe y<\/i> \u2014 fqinjit. At\u00ebher\u00eb mund t\u00eb marrim si p\u00ebrgjigje x<\/i> dhe y<\/i>, nd\u00ebrsa v<\/i> heqim. Dhe me t\u00eb v\u00ebrtet\u00eb, nga ky trek\u00ebnd\u00ebsh duhet t\u00eb marrim s\u00eb paku dy kulme n\u00eb p\u00ebrgjigje dhe ne me siguri nuk do t\u00eb humbasim, n\u00ebse marrim x<\/i> dhe y<\/i>: ndoshta kan\u00eb edhe fqinj tjet\u00ebr, nd\u00ebrsa v<\/i> ata nuk kan\u00eb.<\/li>\n
    2. Kur x<\/i> dhe y<\/i> \u2014 nuk jan\u00eb fqinj. At\u00ebher\u00eb pretendohet se t\u00eb tri majat mund t\u00eb ngjiten n\u00eb nj\u00eb. Ideja \u00ebsht\u00eb q\u00eb n\u00eb k\u00ebt\u00eb rast ka nj\u00eb odgovor optimal, n\u00eb t\u00eb cilin do t\u00eb marrim ose v<\/i>, ose t\u00eb dy majat x<\/i> dhe y<\/i>. Nd\u00ebrsa n\u00eb rastin e par\u00eb do t\u00eb duhet t\u00eb marrim n\u00eb p\u00ebrgjigje t\u00eb gjith\u00eb fqinj\u00ebt x<\/i> dhe y<\/i>, nd\u00ebrsa n\u00eb t\u00eb dytin nuk \u00ebsht\u00eb e domosdoshme. Kjo sakt\u00ebsisht p\u00ebrputhet me rastet kur ne nuk marrim maj\u00ebn e ngjitur n\u00eb p\u00ebrgjigje dhe kur marrim. Mbetet vet\u00ebm t\u00eb theksojm\u00eb se n\u00eb t\u00eb dy rastet, p\u00ebrgjigja nga nj\u00eb operacion i till\u00eb zvog\u00eblohet me nj\u00eb nj\u00ebsi.<\/li>\n<\/ol>\n

      \"Si<\/p>\n

      Duket se ky qasje \u00ebsht\u00eb mjaft e komplikuar p\u00ebr t'u realizuar me sakt\u00ebsi n\u00eb koh\u00eb lineare. Ngjitja e majave \u00ebsht\u00eb nj\u00eb operacion kompleks, duhet t\u00eb kopjoni listat e fqinj\u00ebve. N\u00ebse kjo nuk b\u00ebhet me kujdes, mund t\u00eb merrni nj\u00eb koh\u00eb funksionimi asimptotikisht jo optimale (p.sh., n\u00ebse pas \u00e7do ngjitjeje kopjoni shum\u00eb boshte). U ndala n\u00eb k\u00ebrkimin e rrug\u00ebve t\u00eb plota nga majat me grad\u00eb 2 dhe analizimin e shum\u00eb rasteve t\u00eb ve\u00e7anta, si ciklet nga k\u00ebto maja ose nga t\u00eb gjitha k\u00ebto maja p\u00ebrve\u00e7 nj\u00eb.<\/p>\n

      P\u00ebr m\u00eb tep\u00ebr, \u00ebsht\u00eb e nevojshme q\u00eb ky operacion t\u00eb jet\u00eb i kthyesh\u00ebm, n\u00eb m\u00ebnyr\u00eb q\u00eb gjat\u00eb kthimit nga rekursioni t\u00eb rikthejm\u00eb grafikun n\u00eb form\u00ebn e tij fillestare. P\u00ebr ta siguruar k\u00ebt\u00eb, nuk e pastruar listat e boshteve t\u00eb majave t\u00eb bashkuara, pasi e dija thjesht se cilat boshte duhej t\u00eb d\u00ebrgoheshin n\u00eb cilin drejtim. Kjo realizim e grafik\u00ebve gjithashtu k\u00ebrkon kujdes, por siguron koh\u00eb t\u00eb drejt\u00eb lineare. Dhe p\u00ebr grafik\u00ebt me disa dhjet\u00ebra mij\u00ebra boshte, ajo p\u00ebrshtatet mir\u00eb n\u00eb cache-in e procesorit, q\u00eb jep p\u00ebrpar\u00ebsi t\u00eb m\u00ebdha n\u00eb shpejt\u00ebsi.<\/p>\n

      Nukleusi lineare<\/h3>\n

      S\u00eb fundi, pjesa m\u00eb interesante e nukleusit.<\/p>\n

      P\u00ebr t\u00eb filluar, le t\u00eb kujtojm\u00eb se n\u00eb grafik\u00ebt bipartit minimal mbulimi i majave mund t\u00eb k\u00ebrkohet p\u00ebr \"Si. P\u00ebr k\u00ebt\u00eb nevojitet t\u00eb shfryt\u00ebzohet algoritmi Hopcroft-Karp<\/a><\/noindex> p\u00ebr t\u00eb gjetur aty p\u00ebrputhjen maksimale, dhe m\u00eb pas t\u00eb shfryt\u00ebzojm\u00eb teorem\u00ebn K\u00f6ning-Egervari<\/a><\/noindex>.<\/p>\n

      Ideja e nukleusit linear \u00ebsht\u00eb k\u00ebshtu: fillimisht e dyfishojm\u00eb grafik\u00ebn, dmth n\u00eb vend t\u00eb \u00e7do maja v<\/i> ngrem\u00eb dy maja \"Si dhe \"Si, dhe n\u00eb vend t\u00eb \u00e7do boshte u \u2014 v<\/i> ngrem\u00eb dy boshte \"Si dhe \"SiGrafiku i marr\u00eb do t\u00eb jet\u00eb dypartiak. Ne do t\u00eb gjejm\u00eb mbulimin minimal t\u00eb qosheve n\u00eb t\u00eb. Disa qoshe t\u00eb grafikut fillestar do t\u00eb bien aty dy her\u00eb, disa vet\u00ebm nj\u00eb her\u00eb, dhe disa asnj\u00ebher\u00eb. Teorema e Nemhauser-Trotter thot\u00eb se n\u00eb k\u00ebt\u00eb rast mund t\u00eb hiqen qoshet q\u00eb nuk kan\u00eb r\u00ebn\u00eb asnj\u00ebher\u00eb dhe t\u00eb merret si p\u00ebrgjigje atyre q\u00eb ra dy her\u00eb. M\u00eb shum\u00eb se kaq, ajo thot\u00eb se nga qoshet e mbetura (ato q\u00eb kan\u00eb r\u00ebn\u00eb nj\u00eb her\u00eb), duhet t\u00eb merret si p\u00ebrgjigje t\u00eb pakt\u00ebn gjysma.<\/p>\n

      Sapo m\u00ebsuam t\u00eb l\u00ebm\u00eb n\u00eb graf m\u00eb pak se 2k<\/i> qoshe. N\u00eb t\u00eb v\u00ebrtet\u00eb, n\u00ebse n\u00eb mbetje p\u00ebrgjigja \u00ebsht\u00eb t\u00eb pakt\u00ebn gjysma e t\u00eb gjitha qosheve, at\u00ebher\u00eb numri i p\u00ebrgjithsh\u00ebm i qosheve nuk \u00ebsht\u00eb m\u00eb shum\u00eb se 2k<\/i>.<\/p>\n

      K\u00ebtu arrita t\u00eb b\u00ebj nj\u00eb hap t\u00eb vog\u00ebl p\u00ebrpara. \u00cbsht\u00eb e qart\u00eb se b\u00ebrthama e nd\u00ebrtuar n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb varet nga cili mbulim minimal i qosheve n\u00eb grafikun dypartiak kemi marr\u00eb. D\u00ebshironi t\u00eb merrni nj\u00eb t\u00eb till\u00eb q\u00eb numri i qosheve t\u00eb mbetura t\u00eb jet\u00eb minimal. M\u00eb par\u00eb, kjo ka qen\u00eb e mundur t\u00eb b\u00ebhet vet\u00ebm p\u00ebr nj\u00eb koh\u00eb \"Si. Un\u00eb shpika nj\u00eb realizim t\u00eb k\u00ebtij algoritmi p\u00ebr nj\u00eb koh\u00eb \"Si, k\u00ebshtu q\u00eb kjo b\u00ebrtham\u00eb mund t\u00eb k\u00ebrkohet n\u00eb grafika me qindra mij\u00ebra qoshe n\u00eb \u00e7do etap\u00eb t\u00eb branchnimit.<\/p>\n

      Rezultati<\/h3>\n

      Praktika tregon se zgjidhja ime funksionon mir\u00eb n\u00eb testet me disa qindra qoshe dhe disa mij\u00ebra brezash. N\u00eb k\u00ebto teste, \u00ebsht\u00eb plot\u00ebsisht e mundur t\u00eb pritet q\u00eb zgjidhja t\u00eb gjendet brenda gjysm\u00eb ore. Shtysa p\u00ebr t\u00eb gjetur nj\u00eb p\u00ebrgjigje brenda nj\u00eb kohe t\u00eb pranueshme n\u00eb parim rritet n\u00ebse n\u00eb grafik ka mjaft qoshe me grado t\u00eb madhe, p\u00ebr shembull grado 10 dhe m\u00eb sip\u00ebr.<\/p>\n

      P\u00ebr t\u00eb marr\u00eb pjes\u00eb n\u00eb gar\u00eb, zgjidhjet duhej t\u00eb d\u00ebrgoheshin n\u00eb optil.io<\/a><\/noindex>. Duke gjykuar nga tabela e paraqitur atje tabel\u00eb<\/a><\/noindex>, zgjidhja ime n\u00eb testet e hapura z\u00eb vendin e tret\u00eb nga vinte me shum\u00eb distanc\u00eb nga vendi i dyt\u00eb. N\u00ebse t\u00eb jesh krejt\u00ebsisht i sinqert\u00eb, nuk \u00ebsht\u00eb krejt\u00ebsisht e qart\u00eb se si do t\u00eb vler\u00ebsohen zgjidhjet n\u00eb gar\u00ebn e v\u00ebrtet\u00eb: p\u00ebr shembull, zgjidhja ime kalon m\u00eb pak teste se zgjidhja e vendit t\u00eb kat\u00ebrt, por n\u00eb ato q\u00eb kalon, funksionon m\u00eb shpejt.<\/p>\n

      Rezultatet n\u00eb testet e mbyllura do t\u00eb b\u00ebhen t\u00eb njohura m\u00eb par\u00eb se 1 korriku.<\/p>\n

      Burimi: 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\udd47Si si zgjidhin detyrat NP-t\u00eb v\u00ebshtira me algoritme t\u00eb parametrizuara | ProHoster","description":"Puna k\u00ebrkimore \u00ebsht\u00eb ndoshta pjesa m\u00eb interesante e m\u00ebsimit ton\u00eb. Ideja \u00ebsht\u00eb q\u00eb gjat\u00eb universitetit t\u00eb provojm\u00eb vetveten n\u00eb drejtimin e zgjedhur.","canonical_url":"https:\/\/prohoster.info\/sq\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sq_AL","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\/sq\/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\/sq\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sq\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}