{"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\/novosti-interneta\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Si si t\u00eb zgjidhni probleme NP-t\u00eb v\u00ebshtira duke p\u00ebrdorur algoritme parametrike","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Puna k\u00ebrkimore \u00ebsht\u00eb ndoshta pjesa m\u00eb interesante e studimeve tona. Ideja \u00ebsht\u00eb q\u00eb q\u00eb n\u00eb universitet t\u00eb provoni veten n\u00eb drejtimin e p\u00ebrzgjedhur. P\u00ebr shembull, student\u00ebt q\u00eb studiojn\u00eb Inxhinieri Softuer\u00ebsh dhe M\u00ebsimin e Makinerive shpesh angazhohen n\u00eb k\u00ebrkime n\u00eb kompani (shumica n\u00eb JetBrains ose Yandex, por jo vet\u00ebm).<\/p>\n

N\u00eb k\u00ebt\u00eb post, do t\u00eb flas p\u00ebr projektin tim n\u00eb drejtimin e Shkenc\u00ebs Kompjuterike. Gjat\u00eb pun\u00ebs, kam studiuar dhe zbatuar n\u00eb praktik\u00eb qasje p\u00ebr zgjidhjen e nj\u00eb prej problemeve m\u00eb t\u00eb njohura NP-t\u00eb v\u00ebshtira: problemin e mbulimit t\u00eb pikave<\/b>.<\/p>\n

Aktualisht, nj\u00eb qasje interesante \u00ebsht\u00eb duke u zhvilluar shum\u00eb shpejt p\u00ebr problemet NP-t\u00eb v\u00ebshtira \u2014 algoritmet parametrike. Do t\u00eb p\u00ebrpiqem t'ju fut n\u00eb informacion, t\u00eb flas p\u00ebr disa algoritme parametrike t\u00eb thjeshta dhe t\u00eb p\u00ebrshkruaj nj\u00eb metod\u00eb t\u00eb fuqishme q\u00eb m\u00eb ndihmoi shum\u00eb. Rezultatet e mia i paraqita n\u00eb gar\u00ebn PACE Challenge: pas testeve t\u00eb hapura, zgjidhja ime z\u00eb vendin e tret\u00eb, nd\u00ebrsa rezultatet p\u00ebrfundimtare do t\u00eb b\u00ebhen t\u00eb njohura m\u00eb 1 Korrik.<\/p>\n

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

Rreth meje<\/h3>\n

M\u00eb quajn\u00eb Vasiliy Alfyorov, tani po p\u00ebrfundoj vitin e tret\u00eb n\u00eb HSE \u2014 Sh\u00ebn Petersburg. Un\u00eb merrem me algoritme q\u00eb nga koha e shkoll\u00ebs, kur studioja n\u00eb shkoll\u00ebn 179 t\u00eb Mosk\u00ebs dhe kam marr\u00eb pjes\u00eb me sukses n\u00eb olimpiadat e informatik\u00ebs.<\/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

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

Imagjinoni q\u00eb jeni roje i barit 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, e kjo ju shkakton shum\u00eb shqet\u00ebsime: duhet t\u00eb dilni nga bari vizitor\u00ebt problematik\u00eb p\u00ebr t\u00eb parandaluar p\u00ebrleshjet. N\u00eb fund t\u00eb fundit, ju m\u00ebrzitet dhe vendosni t\u00eb merrni masa parandaluese.<\/p>\n

Duke qen\u00eb se qyteti juaj \u00ebsht\u00eb i vog\u00ebl, e dini sakt\u00ebsisht se cilat pal\u00eb vizitor\u00ebsh kan\u00eb nj\u00eb probabilitet t\u00eb madh t\u00eb p\u00ebrleshen n\u00ebse hyjn\u00eb n\u00eb bar s\u00eb bashku. Keni nj\u00eb list\u00eb prej n<\/i> njer\u00ebzish q\u00eb do t\u00eb vijn\u00eb sonte n\u00eb bar. Vendosni t\u00eb mos lejoni ndonj\u00eb qytetar n\u00eb bar, n\u00eb m\u00ebnyr\u00eb q\u00eb askush t\u00eb mos p\u00ebrleshet. N\u00eb t\u00eb nj\u00ebjt\u00ebn koh\u00eb, drejtuesit tuaj nuk duan t\u00eb humbasin fitimin dhe do t\u00eb jen\u00eb t\u00eb pak\u00ebnaqur n\u00ebse nuk lejoni m\u00eb shum\u00eb se k<\/i> njer\u00ebz.<\/p>\n

Fatkeq, detyra q\u00eb keni p\u00ebrpara \u00ebsht\u00eb nj\u00eb detyr\u00eb klasike NP-e v\u00ebshtir\u00eb. Mund t\u00eb keni njohuri p\u00ebr t\u00eb si Mbulimi i Shenjave<\/a><\/noindex>, ose si problemi i mbulimit t\u00eb pikave. P\u00ebr k\u00ebto probleme, n\u00eb p\u00ebrgjith\u00ebsi nuk dihen algoritme q\u00eb punojn\u00eb brenda nj\u00eb kohe t\u00eb pranueshme. N\u00ebse jemi t\u00eb sakt\u00eb, nj\u00eb hipotez\u00eb e fort\u00eb e paprovuar ETH (Hipoteza e Koh\u00ebs Eksponenciale) thot\u00eb se ky problem nuk mund t\u00eb zgjidhet n\u00eb m\u00ebnyr\u00eb \"Si, dometh\u00ebn\u00eb se nuk mund t\u00eb mendoni asgj\u00eb q\u00eb punon duksh\u00ebm m\u00eb mir\u00eb se shflektimi i plot\u00eb. P\u00ebr shembull, supozoni se n\u00eb barin tuaj do t\u00eb vijn\u00eb n = 1000<\/i> njer\u00ebz. K\u00ebshtu q\u00eb shflektimi i plot\u00eb do t\u00eb ket\u00eb \"Si opsione, e cila \u00ebsht\u00eb af\u00ebrsisht \"Si \u2014 jasht\u00ebzakonisht shum\u00eb. P\u00ebr fat t\u00eb mir\u00eb, drejtimi juaj ka vendosur nj\u00eb kufizim 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 prej dhjet\u00eb elementesh \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 eliminuar mund\u00ebsin\u00eb e nj\u00eb z\u00ebnke n\u00eb nj\u00eb konfigurat\u00eb t\u00eb till\u00eb t\u00eb tensioneve midis vizitor\u00ebve t\u00eb barit, duhet t\u00eb mos lejoni Bobin, Danielin dhe Fyodorin. Zgjidhja, n\u00eb t\u00eb cil\u00ebn mbeten jasht\u00eb vet\u00ebm dy, nuk ekziston.<\/p>\n

A do t\u00eb thot\u00eb kjo se \u00ebsht\u00eb koha p\u00ebr t'u dor\u00ebzuar dhe p\u00ebr t\u00eb l\u00ebn\u00eb t\u00eb gjith\u00eb t\u00eb hyjn\u00eb? Le t\u00eb shqyrtojm\u00eb opsione t\u00eb tjera. P.sh., mund t\u00eb mos lejoni t\u00eb hyjn\u00eb ata q\u00eb po e b\u00ebjn\u00eb k\u00ebt\u00eb me shum\u00eb njer\u00ebz. N\u00ebse dikush mund t\u00eb p\u00ebrfshihet n\u00eb nj\u00eb rrahje me t\u00eb pakt\u00ebn k + 1<\/i> n\u00eb nj\u00eb person tjet\u00ebr, at\u00ebher\u00eb nuk duhet ta lejoni t\u00eb hyj\u00eb \u2014 p\u00ebrndryshe do t\u00eb duhet t\u00eb mos lejoni t\u00eb hyjn\u00eb t\u00eb gjith\u00eb k + 1<\/i> banor\u00ebt me t\u00eb cil\u00ebt ai mund t\u00eb rrihen, q\u00eb do t\u00eb shqet\u00ebsoj\u00eb menaxhmentin.<\/p>\n

Supozojm\u00eb se i keni hequr t\u00eb gjith\u00eb ata q\u00eb mundet, sipas k\u00ebtij parimi. At\u00ebher\u00eb t\u00eb gjith\u00eb t\u00eb tjer\u00ebt mund t\u00eb p\u00ebrfshihen n\u00eb konflikte me m\u00eb shum\u00eb se k<\/i> njer\u00ebz. Duke hequr nga ata k<\/i> njer\u00ebz, mund t\u00eb parandaloni m\u00eb shum\u00eb se \"Si konflikte. K\u00ebshtu q\u00eb, n\u00ebse m\u00eb shum\u00eb se \"Si njer\u00ebz jan\u00eb t\u00eb p\u00ebrfshir\u00eb n\u00eb t\u00eb pakt\u00ebn nj\u00eb konflikt, at\u00ebher\u00eb me siguri nuk do t\u00eb keni mund\u00ebsi t'i parandaloni t\u00eb gjitha. Duke pasur parasysh se, natyrisht, do t\u00eb lejoni ata q\u00eb nuk jan\u00eb konfliktual\u00eb, duhet t\u00eb kontrolloni t\u00eb gjitha n\u00ebngrupet me madh\u00ebsi dhjet\u00eb nga dyqind njer\u00ebz. Jan\u00eb af\u00ebrsisht \"Si, dhe nj\u00eb num\u00ebr i till\u00eb operacionesh mund t\u00eb shqyrtohet n\u00eb nj\u00eb klaster.<\/p>\n

N\u00ebse \u00ebsht\u00eb e mundur t\u00eb marrim individ\u00eb t\u00ebr\u00ebsisht jo konfliktual\u00eb, \u00e7far\u00eb ndodh me ata q\u00eb p\u00ebrfshihen n\u00eb vet\u00ebm nj\u00eb konflikt? N\u00eb t\u00eb v\u00ebrtet\u00eb, ata gjithashtu mund t\u00eb lejohet, duke mbyllur dyert para kund\u00ebrshtar\u00ebve t\u00eb tyre. E v\u00ebrteta \u00ebsht\u00eb, n\u00ebse Alisa ka nj\u00eb konflikt vet\u00ebm me Bobin, at\u00ebher\u00eb n\u00ebse e lejojm\u00eb Alis\u00ebn, ne nuk do t\u00eb humbasim: Bobi mund t\u00eb ket\u00eb konflikte t\u00eb tjera, nd\u00ebrsa Alisa absolutisht nuk ka asnj\u00eb. Sidomos, \u00ebsht\u00eb pa kuptim t\u00eb mos lejojm\u00eb asnj\u00eb prej tyre. Pas k\u00ebtyre operacioneve mbeten jo m\u00eb shum\u00eb se \"Si vizitor\u00eb me fat t\u00eb paqart\u00eb: n\u00eb total kemi \"Si konflikte, secili me nga dy pjes\u00ebmarr\u00ebs dhe \u00e7do nj\u00eb prej tyre merr pjes\u00eb n\u00eb t\u00eb pakt\u00ebn dy. K\u00ebshtu, na mbetet t\u00eb kalojm\u00eb vet\u00ebm \"Si mund\u00ebsi, q\u00eb padyshim mund t\u00eb p\u00ebrballet p\u00ebr nj\u00eb gjysm\u00eb dit\u00eb 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 t\u00ebrheq\u00ebse. Vini re se duhet t\u00eb zgjidhim t\u00eb gjitha mosmarr\u00ebveshjet, dometh\u00ebn\u00eb nga \u00e7do \u00e7ift konfliktues t\u00eb zgjedhim t\u00eb pakt\u00ebn nj\u00eb person q\u00eb nuk do ta lejojm\u00eb. Le t\u00eb shqyrtojm\u00eb nj\u00eb algoritem t\u00eb till\u00eb: t\u00eb marrim \u00e7do konflikt, t\u00eb eliminojm\u00eb nj\u00eb pjes\u00ebmarr\u00ebs dhe t\u00eb vazhdojm\u00eb rekurivisht me t\u00eb tjer\u00ebt, pastaj t\u00eb eliminojm\u00eb tjetrin dhe gjithashtu t\u00eb vazhdojm\u00eb rekurivisht. Duke qen\u00eb se n\u00eb \u00e7do hap heqim dik\u00eb, pem\u00ebn e rekursis\u00eb s\u00eb k\u00ebtij algoritmi - nj\u00eb pem\u00eb binar\u00eb t\u00eb thell\u00ebsis\u00eb k<\/i>, prandaj algoritmi funksionon p\u00ebr \"Si, ku n<\/i> \u2014 numri i vendeve, dhe m<\/i> \u2014 numri i rubrikave. N\u00eb shembullin ton\u00eb, kjo \u00ebsht\u00eb rreth dhjet\u00eb milion\u00eb, t\u00eb cilat llogariten p\u00ebr disa sekonda jo vet\u00ebm n\u00eb nj\u00eb laptop, por madje edhe n\u00eb nj\u00eb telefon mobil.<\/p>\n

Shembulli i lartp\u00ebrmendur \u00ebsht\u00eb nj\u00eb shembull i algoritmit t\u00eb parametrizuar<\/b>. Algoritmet e parametrizuara jan\u00eb algoritme q\u00eb funksionojn\u00eb p\u00ebr koh\u00eb f(k) poly(n)<\/i>, ku p<\/i> \u2014 polinom, f<\/i> \u2014 funksion i llogaritur, dhe k<\/i> \u2014 nj\u00eb parametr q\u00eb, shum\u00eb mund\u00ebsisht, do t\u00eb jet\u00eb shum\u00eb m\u00eb i vog\u00ebl se madh\u00ebsia e problemit.<\/p>\n

T\u00eb gjitha arsyetimet deri n\u00eb k\u00ebt\u00eb algoritem tregojn\u00eb shembullin e kernelizimit<\/b> \u2014 nj\u00eb nga teknikat e zakonshme p\u00ebr krijimin e algoritmeve t\u00eb parametrizuar. Kernelizimi \u00ebsht\u00eb reduktimi i madh\u00ebsis\u00eb s\u00eb problemit n\u00eb nj\u00eb vler\u00eb t\u00eb kufizuar nga funksioni i parametrave. Problemi i marr\u00eb shpesh quhet b\u00ebrtham\u00eb. K\u00ebshtu, me argumentet e thjeshta mbi grad\u00ebt e majave, kemi marr\u00eb b\u00ebrthamin katror p\u00ebr problemin e Vertex Cover, t\u00eb parametrizuar sipas madh\u00ebsis\u00eb s\u00eb p\u00ebrgjigjes. Ekzistojn\u00eb edhe parametro t\u00eb tjer\u00eb q\u00eb mund t\u00eb zgjidhen p\u00ebr k\u00ebt\u00eb problem (p.sh., Vertex Cover Above LP), por ne do t\u00eb diskutojm\u00eb pik\u00ebrisht at\u00eb parametrin.<\/p>\n

Pace Challenge<\/h3>\n

Sfid\u00eb PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) filloi n\u00eb vitin 2015 p\u00ebr t\u00eb krijuar lidhje midis algoritmeve t\u00eb parametrizuara dhe qasjeve t\u00eb p\u00ebrdorura n\u00eb praktik\u00eb p\u00ebr zgjidhjen e problemeve t\u00eb llogaritjes. Tre sfidat e para ishin dedikuar gjetjes s\u00eb gjer\u00ebsis\u00eb s\u00eb pem\u00ebs t\u00eb grafik\u00ebve (Treewidth<\/a><\/noindex>), gjetjes s\u00eb pem\u00ebs s\u00eb Steinerit (Steiner Tree<\/a><\/noindex>) dhe gjetjes s\u00eb nj\u00eb grupi majash q\u00eb prishin ciklet (Feedback Vertex Set<\/a><\/noindex>). N\u00eb k\u00ebt\u00eb vit, nj\u00eb nga problemet ku mund t\u00eb provoni aft\u00ebsit\u00eb tuaja ishte problemi i p\u00ebrmendur m\u00eb lart i mbulimit t\u00eb majave.<\/p>\n

Garancia e kompeticionit po fiton popullaritet \u00e7do vit. N\u00ebse besojm\u00eb t\u00eb dh\u00ebnat paraprake, k\u00ebt\u00eb vit vet\u00ebm n\u00eb kompeticionin p\u00ebr zgjidhjen e problemit t\u00eb mbulimit t\u00eb pikave mor\u00ebn pjes\u00eb 24 ekipe. Vlen t\u00eb theksohet se gara zgjat jo 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 shpikin iden\u00eb e tyre origjinale dhe t\u00eb p\u00ebrpiqen ta realizojn\u00eb at\u00eb. N\u00eb thelb, ky kompeticion \u00ebsht\u00eb nj\u00eb pun\u00eb hulumtuese. Idet\u00eb p\u00ebr zgjidhjet m\u00eb efikase dhe shpallja e fituesve do t\u00eb zhvillohet s\u00eb bashku me konferenc\u00ebn IPEC<\/a><\/noindex> (Simpoziumi Nd\u00ebrkomb\u00ebtar mbi Komputimin e Parametrit dhe at\u00eb t\u00eb Sakt\u00eb) brenda mbledhjes m\u00eb t\u00eb madhe vjetore algoritmike n\u00eb Evrop\u00eb ALGO<\/a><\/noindex>. Informacione m\u00eb t\u00eb holl\u00ebsishme rreth kompeticionit mund t\u00eb gjenden n\u00eb t\u00eb internetit<\/a><\/noindex>, nd\u00ebrsa rezultatet e viteve t\u00eb kaluara ndodhen k\u00ebtu<\/a><\/noindex>.<\/p>\n

Schemi i zgjidhjes<\/h3>\n

P\u00ebr t\u00eb p\u00ebrballuar detyr\u00ebn e mbulimit t\u00eb kulm\u00ebve, fillova t\u00eb aplikoj algoritme parametrizuese. Ato zakonisht p\u00ebrb\u00ebhen nga dy pjes\u00eb: rregullat e thjeshtimit (t\u00eb cilat idealisht \u00e7ojn\u00eb n\u00eb kernelizim) dhe rregullat e ndarjes. Rregullat e thjeshtimit jan\u00eb nj\u00eb p\u00ebrpunim i inputit n\u00eb koh\u00eb polinomiale. Q\u00ebllimi i aplikimit t\u00eb k\u00ebtyre rregullave \u00ebsht\u00eb reduktimi i detyr\u00ebs n\u00eb nj\u00eb detyr\u00eb ekuivalente t\u00eb madh\u00ebsis\u00eb m\u00eb t\u00eb vog\u00ebl. Rregullat e thjeshtimit jan\u00eb pjesa m\u00eb e shtrenjt\u00eb e algoritmit, dhe aplikimi i k\u00ebsaj pjese nxit koh\u00ebn totale t\u00eb funksionimit. \"Si n\u00eb vend t\u00eb nj\u00eb kohe t\u00eb thjesht\u00eb polinomiale. N\u00eb rastin ton\u00eb, rregullat e ndarjes bazohen n\u00eb faktin se p\u00ebr \u00e7do kulm duhet t\u00eb marrim n\u00eb p\u00ebrgjigje ose at\u00eb, ose fqinj\u00ebn e tij.<\/p>\n

Skema e p\u00ebrgjithshme \u00ebsht\u00eb k\u00ebshtu: aplikojm\u00eb rregullat e thjeshtimit, pastaj zgjedhim nj\u00eb kulm dhe b\u00ebjm\u00eb dy thirrje rekurzive: n\u00eb t\u00eb par\u00ebn e marrim n\u00eb p\u00ebrgjigje, nd\u00ebrsa n\u00eb t\u00eb dyt\u00ebn marr\u00eb t\u00eb gjith\u00eb fqinj\u00ebt e tij. K\u00ebt\u00eb e quajm\u00eb ndarjen (branching) sipas k\u00ebtij kulmi.<\/p>\n

N\u00eb k\u00ebt\u00eb skem\u00eb do t\u00eb b\u00ebhet vet\u00ebm nj\u00eb shtes\u00eb n\u00eb paragrafit t\u00eb ardhsh\u00ebm.<\/p>\n

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

Le t\u00eb flasim p\u00ebr m\u00ebnyr\u00ebn se si t\u00eb zgjidhni kulmin n\u00eb t\u00eb cilin do t\u00eb ndodh\u00eb ndarja.
\nIdeja kryesore \u00ebsht\u00eb shum\u00eb lakmuese n\u00eb kuptimin algoritmik: le t\u00eb marrim kulmin me grad\u00ebn maksimale dhe t\u00eb ndajm\u00eb t\u00eb sakt\u00eb at\u00eb. P\u00ebrse duket se k\u00ebshtu \u00ebsht\u00eb m\u00eb mir\u00eb? Sepse n\u00eb deg\u00ebn e dyt\u00eb t\u00eb thirrjes rekursive, k\u00ebshtu do t\u00eb heqim shum\u00eb kulme. Mund t\u00eb pritet q\u00eb t\u00eb mbetet nj\u00eb grafik i vog\u00ebl dhe n\u00eb t\u00eb do t\u00eb punojm\u00eb shpejt.<\/p>\n

Ky qasje me teknikat e thjeshta t\u00eb diskutuara p\u00ebr kernelizimin tregon rezultate t\u00eb mira, zgjidh disa teste me mij\u00ebra kulme. Por, p\u00ebr shembull, nuk punon mir\u00eb p\u00ebr grafet kubike (dmth, grafet ku grad\u00eb e \u00e7do kulmi \u00ebsht\u00eb e barabart\u00eb me tre).
\nEkziston nj\u00eb ide tjet\u00ebr, e cila bazohet n\u00eb nj\u00eb mendim mjaft t\u00eb thjesht\u00eb: n\u00ebse grafiku \u00ebsht\u00eb i \u00e7organizuar, problemi i komponent\u00ebve t\u00eb tij t\u00eb lidhjes mund t\u00eb zgjidhet n\u00eb m\u00ebnyr\u00eb t\u00eb pavarur, duke bashkuar p\u00ebrgjigjet n\u00eb fund. Kjo, p\u00ebr sh\u00ebnim, \u00ebsht\u00eb nj\u00eb modifikim i vog\u00ebl premtuar n\u00eb skem\u00eb q\u00eb do t\u00eb p\u00ebrshpejtoj\u00eb zgjidhjen: m\u00eb par\u00eb n\u00eb k\u00ebt\u00eb rast ne punonim me produktin e koh\u00ebve t\u00eb llogaritjes s\u00eb p\u00ebrgjigjeve t\u00eb komponent\u00ebve, tani punojm\u00eb me shum\u00ebn. P\u00ebr t\u00eb p\u00ebrshpejtuar branchen, duhet ta kthejm\u00eb grafikun e lidhur n\u00eb nj\u00eb t\u00eb \u00e7organizuar.<\/p>\n

Si ta b\u00ebjm\u00eb k\u00ebt\u00eb? N\u00ebse n\u00eb graf ekziston nj\u00eb pik\u00eb lidhjeje, ne duhet t\u00eb branchojm\u00eb pik\u00ebrisht mbi t\u00eb. Pika e lidhjes \u00ebsht\u00eb nj\u00eb kulm, t\u00eb cilin n\u00ebse e heqim, grafiku humbet lidhjen. Gjetja e t\u00eb gjitha pikave t\u00eb lidhjes n\u00eb graf mund t\u00eb b\u00ebhet me nj\u00eb algorit\u00ebm klasik n\u00eb koh\u00eb lineare. Ky qasje ndjesh\u00ebm e p\u00ebrshpejton branchen.
\n\"Si
\nN\u00eb heqjen e cilitdo nga kulmat e ve\u00e7uar, grafiku do t\u00eb ndahet n\u00eb komponent\u00eb lidhjeje.<\/p>\n

K\u00ebto ne do t'i b\u00ebjm\u00eb, por d\u00ebshirojm\u00eb m\u00eb shum\u00eb. P\u00ebr shembull, t\u00eb k\u00ebrkojm\u00eb n\u00eb graf p\u00ebr prerjet e vogla t\u00eb pikave dhe t\u00eb kryejm\u00eb ndarjen p\u00ebrmes pikave prej saj. M\u00ebnyra m\u00eb efektive q\u00eb di p\u00ebr t\u00eb gjetur prerjen minimale globale t\u00eb pikave \u00ebsht\u00eb t\u00eb p\u00ebrdorim pem\u00ebn Gomori-Hu, e cila nd\u00ebrtoset n\u00eb koh\u00eb kubike. N\u00eb PACE Challenge, madh\u00ebsia tipike e grafit \u00ebsht\u00eb disa mij\u00ebra pika. N\u00eb k\u00ebt\u00eb situat\u00eb, n\u00eb \u00e7do pik\u00eb t\u00eb pem\u00ebs s\u00eb rekurzionit, duhet t\u00eb kryhen miliarda operacione. K\u00ebshtu, t\u00eb zgjidhet problemi n\u00eb koh\u00ebn e caktuar \u00ebsht\u00eb thjesht e pamundur.<\/p>\n

Le t\u00eb p\u00ebrpiqemi t\u00eb optimizojm\u00eb zgjidhjen. Prerja minimale e pikave midis nj\u00eb \u00e7ifti pikash mund t\u00eb gjenden me \u00e7do algorit\u00ebm q\u00eb nd\u00ebrtin fluksin maksimal. Mund t\u00eb aplikojm\u00eb n\u00eb nj\u00eb rrjet t\u00eb till\u00eb algoritmin e Dinitzit<\/a><\/noindex>, n\u00eb praktik\u00eb ai funksionon shum\u00eb shpejt. Kam dyshime se teorikisht mund t\u00eb provohet nj\u00eb vler\u00ebsim mbi koh\u00ebn e pun\u00ebs \"Si, q\u00eb tashm\u00eb \u00ebsht\u00eb mjaft e pranueshme.<\/p>\n

Kam provova disa her\u00eb t\u00eb gjej prerjet midis pal\u00ebve rast\u00ebsore t\u00eb kulm\u00ebve dhe t\u00eb marr m\u00eb t\u00eb balancuarin prej tyre. Fatkeq\u00ebsisht, n\u00eb testet e hapura t\u00eb PACE Challenge, kjo dha rezultate t\u00eb dob\u00ebta. Krahasova me nj\u00eb algorith\u00ebm q\u00eb ndante kulm\u00ebt e maksimumit, duke i ekzekutuar me nj\u00eb kufi n\u00eb thell\u00ebsin\u00eb e zbritjes. Pas algorithmit q\u00eb p\u00ebrpiqej t\u00eb gjente prerje n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb, mbet\u00ebn grafe m\u00eb t\u00eb m\u00ebdha. Kjo ndodh sepse prerjet ishin shum\u00eb t\u00eb pabalancuara: duke fshir\u00eb 5-10 kulme, arriti t\u00eb ndante vet\u00ebm 15-20.<\/p>\n

Duhet theksuar se n\u00eb artikujt p\u00ebr algoritmet teorikisht m\u00eb t\u00eb shpejt\u00eb, p\u00ebrdoren teknika shum\u00eb m\u00eb t\u00eb avancuara p\u00ebr zgjedhjen e kulm\u00ebve p\u00ebr ndarje. K\u00ebto teknika kan\u00eb nj\u00eb realizim shum\u00eb t\u00eb nd\u00ebrlikuar dhe shpeshher\u00eb kan\u00eb vler\u00ebsime t\u00eb dob\u00ebta p\u00ebr \u00e7\u00ebshtjet e koh\u00ebs dhe memories. Nuk arrita t\u00eb identifikoj ndonj\u00eb prej tyre q\u00eb do t\u00eb ishin mjaft t\u00eb pranueshme p\u00ebr praktik\u00ebn.<\/p>\n

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

Ne tashm\u00eb kemi ide p\u00ebr kernelizimin. Kujtoj:<\/p>\n

    \n
  1. N\u00ebse ka nj\u00eb kulm t\u00eb izoluar, fshijeni at\u00eb.<\/li>\n
  2. N\u00ebse ka nj\u00eb kulm me grad\u00eb 1, fshijeni at\u00eb dhe merrni fqinj\u00ebn e tij si p\u00ebrgjigje.<\/li>\n
  3. N\u00ebse ka nj\u00eb kulm me 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, p\u00ebr t\u00eb tret\u00ebn ka nj\u00eb hile. N\u00eb problemin me barin, na \u00ebsht\u00eb dh\u00ebn\u00eb nj\u00eb kufizim t\u00eb lart\u00eb n\u00eb k<\/i>, por n\u00eb PACE Challenge duhet t\u00eb gjeni thjesht nj\u00eb mbulim t\u00eb majt\u00eb minimal t\u00eb pikave. 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 dallim mes dy llojeve t\u00eb problemeve. N\u00eb praktik\u00eb, kur shkruajm\u00eb nj\u00eb zgjidh\u00ebs p\u00ebr problemin e mbulimit t\u00eb pikave, dallimi mund t\u00eb jet\u00eb. P\u00ebr shembull, si\u00e7 \u00ebsht\u00eb n\u00eb pik\u00ebn e tret\u00eb.<\/p>\n

    Nga pik\u00ebpamja e implementimit, mund t\u00eb veprojm\u00eb n\u00eb dy m\u00ebnyra. Qasja e par\u00eb quhet Zgjatja Iterative. Ajo p\u00ebrb\u00ebhet n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb: ne mund t\u00eb fillojm\u00eb me nj\u00eb kufizim t\u00eb arsyesh\u00ebm t\u00eb posht\u00ebm p\u00ebr p\u00ebrgjigjen, dhe pastaj t\u00eb nxjerrim algoritmin ton\u00eb, duke p\u00ebrdorur k\u00ebt\u00eb kufizim si kufizim t\u00eb lart\u00eb t\u00eb p\u00ebrgjigjes, pa u zbritur n\u00eb rekursivitet m\u00eb posht\u00eb se ky kufizim. N\u00ebse gjejm\u00eb ndonj\u00eb p\u00ebrgjigje, ajo \u00ebsht\u00eb garantuar t\u00eb jet\u00eb optimale, p\u00ebrndryshe mund t\u00eb rrisim k\u00ebt\u00eb kufizim nj\u00ebsi dhe t\u00eb fillojm\u00eb s\u00ebrish.<\/p>\n

    Qasja tjet\u00ebr \u00ebsht\u00eb t\u00eb mbajm\u00eb ndonj\u00eb p\u00ebrgjigje aktuale optimale dhe t\u00eb k\u00ebrkojm\u00eb nj\u00eb p\u00ebrgjigje m\u00eb t\u00eb vog\u00ebl, duke e ndryshuar k\u00ebt\u00eb paramet\u00ebr kur e gjejm\u00eb. k<\/i> p\u00ebr t\u00eb prer\u00eb m\u00eb shum\u00eb deg\u00eb t\u00eb tep\u00ebrta n\u00eb k\u00ebrkim.<\/p>\n

    Pas pasi disa eksperimente gjat\u00eb nat\u00ebs, un\u00eb u ndala n\u00eb kombinimin e k\u00ebtyre dy m\u00ebnyrave: fillimisht e nis algoritmin tim me nj\u00eb kufizim mbi thell\u00ebsin\u00eb e k\u00ebrkimit (duke e p\u00ebrshtatur at\u00eb n\u00eb m\u00ebnyr\u00eb q\u00eb t\u00eb z\u00ebr\u00eb nj\u00eb koh\u00eb t\u00eb pap\u00ebrfillshme krahasuar me zgjidhjen kryesore) dhe e p\u00ebrdor zgjidhjen m\u00eb t\u00eb mir\u00eb t\u00eb gjetur si kufizim t\u00eb sip\u00ebrm mbi p\u00ebrgjigjen \u2014 dmth, mbi at\u00eb t\u00eb nj\u00ebjt\u00ebn. k<\/i>.<\/p>\n

    Majat e grad\u00ebs 2<\/h3>\n

    Me majat e grad\u00ebs 0 dhe 1 u merakos\u00ebm. Doli q\u00eb mund t\u00eb b\u00ebhet k\u00ebshtu edhe me majat e grad\u00ebs 2, por p\u00ebr k\u00ebt\u00eb grafiku do t\u00eb k\u00ebrkoj\u00eb operacione m\u00eb t\u00eb komplikuara.<\/p>\n

    P\u00ebr ta shpjeguar k\u00ebt\u00eb, duhet t\u00eb sh\u00ebnohet si\u00e7 duhet majat. Le t\u00eb quhet maja e grad\u00ebs 2 si maja v<\/i>, dhe fqinj\u00ebt e saj si maja 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 fqinj\u00ebt. At\u00ebher\u00eb mund t\u00eb marrim n\u00eb p\u00ebrgjigje x<\/i> dhe y<\/i>, dhe v<\/i> t\u00eb eliminojm\u00eb. Dhe v\u00ebrtet, nga ky trek\u00ebnd\u00ebsh duhet t\u00eb marrim t\u00eb pakt\u00ebn dy maja n\u00eb p\u00ebrgjigje dhe ne nuk do t\u00eb humbasim me t\u00eb v\u00ebrtet\u00eb, n\u00ebse marrim x<\/i> dhe y<\/i>: ndoshta ata kan\u00eb ende fqinj\u00eb, por v<\/i> ata nuk i kan\u00eb.<\/li>\n
    2. Kur x<\/i> dhe y<\/i> \u2014 jo fqinj\u00eb. At\u00ebher\u00eb b\u00ebhet e qart\u00eb se t\u00eb gjitha tri majat mund t\u00eb ngjiten n\u00eb nj\u00eb t\u00eb vet\u00ebm. Ideja \u00ebsht\u00eb se n\u00eb k\u00ebt\u00eb rast ka nj\u00eb p\u00ebrgjigje optimale, n\u00eb t\u00eb cil\u00ebn do t\u00eb marrim ose v<\/i>, ose t\u00eb dy majat x<\/i> dhe y<\/i>. N\u00eb fakt, n\u00eb rastin e par\u00eb do t\u00eb detyrohemi t\u00eb marrim n\u00eb p\u00ebrgjigje t\u00eb gjith\u00eb fqinj\u00ebt. x<\/i> dhe y<\/i>, dhe n\u00eb t\u00eb dyt\u00ebn nuk \u00ebsht\u00eb e domosdoshme. Kjo p\u00ebrputhet sakt\u00ebsisht me rastet kur ne nuk marrim maj\u00ebn e ngjitur n\u00eb p\u00ebrgjigje dhe kur e marrim. Duhet th\u00ebn\u00eb se n\u00eb t\u00eb dyja rastet p\u00ebrgjigja nga nj\u00eb operacion i till\u00eb zvog\u00eblohet me nj\u00eb nj\u00ebsit.<\/li>\n<\/ol>\n

      \"Si<\/p>\n

      Vlen t\u00eb theksohet se ky qasje \u00ebsht\u00eb mjaft e v\u00ebshtir\u00eb p\u00ebr t'u realizuar me sakt\u00ebsi n\u00eb nj\u00eb koh\u00eb t\u00eb ndershme lineare. Bashkimi i majave \u00ebsht\u00eb nj\u00eb operacion kompleks; duhet kopjuar listat e fqinj\u00ebve. N\u00ebse kjo b\u00ebhet gabimisht, mund t\u00eb kemi nj\u00eb koh\u00eb funksionimi asimptotike jo optimale (p.sh., n\u00ebse pas \u00e7do bashkimi kopjojm\u00eb shum\u00eb rib\u00eb). 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 kjo operacion t\u00eb jet\u00eb e kthyeshme, n\u00eb m\u00ebnyr\u00eb q\u00eb gjat\u00eb kthimit nga rekursiviteti t\u00eb rivendosim grafik\u00ebn n\u00eb gjendjen fillestare. P\u00ebr ta siguruar k\u00ebt\u00eb, nuk e pastruan list\u00ebn e skajeve t\u00eb shkarkuara, pas s\u00eb cil\u00ebs thjesht e dija se cilat skaje duheshin d\u00ebrguar ku. Nj\u00eb zbatim i till\u00eb i grafik\u00ebve gjithashtu k\u00ebrkon kujdes, por kujdesi siguron nj\u00eb koh\u00eb t\u00eb ndershme lineare. P\u00ebr grafik\u00ebt me disa dhjet\u00ebra mij\u00eb skaje, kjo p\u00ebrputhet n\u00eb cache-in e procesorit, q\u00eb ofron p\u00ebrfitime t\u00eb m\u00ebdha n\u00eb shpejt\u00ebsi.<\/p>\n

      B\u00ebrthama lineare<\/h3>\n

      S\u00eb fundi, pjesa m\u00eb interesante e b\u00ebrtham\u00ebs.<\/p>\n

      P\u00ebr t\u00eb filluar, le t\u00eb kujtojm\u00eb se n\u00eb grafik\u00ebt bipartit, mbulimi minimal i majave mund t\u00eb k\u00ebrkohet p\u00ebr \"Si. P\u00ebr k\u00ebt\u00eb, duhet t\u00eb p\u00ebrdorim algoritmin Hopcroft-Karp<\/a><\/noindex> p\u00ebr t\u00eb gjetur atje p\u00ebrputhjen maksimale, dhe pastaj t\u00eb p\u00ebrdorim teorem\u00ebn K\u00f6nig-Egervari<\/a><\/noindex>.<\/p>\n

      Ideja e b\u00ebrtham\u00ebs lineare \u00ebsht\u00eb k\u00ebshtu: s\u00eb pari do ta ndajm\u00eb grafik\u00ebn, dmth n\u00eb vend t\u00eb \u00e7do maje v<\/i> do t\u00eb vendosim dy maja \"Si dhe \"Si, dhe n\u00eb vend t\u00eb \u00e7do skaje u \u2014 v<\/i> do t\u00eb vendosim dy skaje \"Si dhe \"Si. Grafi i marr\u00eb do t\u00eb jet\u00eb dy-an\u00ebsh. Ne do t\u00eb gjejm\u00eb mbulimin minimal t\u00eb pikave n\u00eb t\u00eb. Disa pika t\u00eb grafit origjinal do t\u00eb p\u00ebrfshihen 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 fshijm\u00eb pikat q\u00eb nuk u p\u00ebrfshin\u00eb asnj\u00ebher\u00eb dhe t\u00eb marrim n\u00eb p\u00ebrgjigje ato q\u00eb u p\u00ebrfshin\u00eb dy her\u00eb. M\u00eb tej, ajo thot\u00eb se nga pikat e mbetura (ato q\u00eb u p\u00ebrfshin\u00eb nj\u00eb her\u00eb) duhet t\u00eb marrim n\u00eb p\u00ebrgjigje t\u00eb pakt\u00ebn gjysm\u00ebn e tyre.<\/p>\n

      Sapo m\u00ebsuam t\u00eb l\u00ebm\u00eb n\u00eb grafik jo m\u00eb shum\u00eb se 2k<\/i> pik\u00eb. N\u00eb fakt, n\u00ebse n\u00eb mbetje p\u00ebrgjigjja \u00ebsht\u00eb t\u00eb pakt\u00ebn gjysma e t\u00eb gjitha pikave, at\u00ebher\u00eb gjat\u00ebsia e totalit atje 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 k\u00ebshtu varet nga cilat mbulime minimale t\u00eb pikave n\u00eb grafikun dy-an\u00ebsh kemi marr\u00eb. Do t\u00eb d\u00ebshironim t\u00eb merrnim nj\u00eb t\u00eb till\u00eb, n\u00eb m\u00ebnyr\u00eb q\u00eb numri i pikave t\u00eb mbetura t\u00eb ishte minimal. M\u00eb par\u00eb, k\u00ebt\u00eb mund ta b\u00ebnim vet\u00ebm p\u00ebr nj\u00eb koh\u00eb \"Si. Un\u00eb kam menduar nj\u00eb implementim 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 grafik\u00ebt me qindra mij\u00ebra pik\u00eb n\u00eb \u00e7do hap t\u00eb branchening.<\/p>\n

      Rezultati<\/h3>\n

      Praktika tregon se zgjidhja ime funksionon mir\u00eb n\u00eb teste me disa qindra kapituj dhe disa mij\u00ebra deg\u00eb. N\u00eb k\u00ebto teste, \u00ebsht\u00eb e arsyeshme t\u00eb pritet se zgjidhja do t\u00eb gjendet brenda gjysm\u00eb ore. Mund\u00ebsia e gjetjes s\u00eb p\u00ebrgjigjes brenda nj\u00eb kohe t\u00eb pranueshme n\u00eb parim rritet n\u00ebse grafiku ka mjaft shum\u00eb kapituj me shkall\u00eb t\u00eb lart\u00eb, p\u00ebr shembull shkall\u00eb 10 e m\u00eb lart.<\/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>. Sipas tabel\u00ebs aty tabel\u00eb<\/a><\/noindex>, zgjidhja ime n\u00eb testet e hapura z\u00eb vendin e tret\u00eb nga vingt\u00eb me nj\u00eb diferenc\u00eb t\u00eb madhe nga vendi i dyt\u00eb. N\u00ebse duhet t\u00eb jem plot\u00ebsisht i sinqert\u00eb, nuk \u00ebsht\u00eb krejt\u00ebsisht e qart\u00eb se si do t\u00eb vler\u00ebsohen zgjidhjet n\u00eb vet\u00eb gar\u00ebn: p\u00ebr shembull, zgjidhja ime kalon m\u00eb pak teste se ajo n\u00eb vendin e kat\u00ebrt, por n\u00eb ato q\u00eb kalon, punon m\u00eb shpejt.<\/p>\n

      Rezultatet n\u00eb testet e mbyllura do t\u00eb b\u00ebhen t\u00eb njohura m\u00eb par\u00eb t\u00eb korrikut.<\/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-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\udd47Si t\u00eb zgjidhni problemet NP-t\u00eb v\u00ebshtira me ndihm\u00ebn e algoritmeve t\u00eb parametrizuar | ProHoster","description":"Puna shkencore \u00ebsht\u00eb ndoshta pjesa m\u00eb e interesante e m\u00ebsimit ton\u00eb. Ideja \u00ebsht\u00eb q\u00eb t\u00eb provojm\u00eb veten n\u00eb drejtimin e zgjedhur, q\u00eb para universitetit. P\u00ebr shembull, student\u00ebt nga deg\u00ebt e Inxhinieris\u00eb Softuerike dhe M\u00ebsimit t\u00eb Automatizuar shpesh shkojn\u00eb p\u00ebr t\u00eb b\u00ebr\u00eb projekte shkencore n\u00eb kompani (kryesisht, JetBrains ose Yandex, por jo vet\u00ebm). N\u00eb k\u00ebt\u00eb postim do t\u00eb flas p\u00ebr projektin tim n\u00eb drejtimin e Shkenc\u00ebs s\u00eb Kompjuterave.","canonical_url":"https:\/\/prohoster.info\/sq\/blog\/novosti-interneta\/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. \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\/sq\/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\/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}]}}