Puna kërkimore është ndoshta pjesa më interesante e studimeve tona. Ideja është që që në universitet të provoni veten në drejtimin e përzgjedhur. Për shembull, studentët që studiojnë Inxhinieri Softuerësh dhe Mësimin e Makinerive shpesh angazhohen në kërkime në kompani (shumica në JetBrains ose Yandex, por jo vetëm).
Në këtë post, do të flas për projektin tim në drejtimin e Shkencës Kompjuterike. Gjatë punës, kam studiuar dhe zbatuar në praktikë qasje për zgjidhjen e një prej problemeve më të njohura NP-të vështira: problemin e mbulimit të pikave.
Aktualisht, njĂ« qasje interesante Ă«shtĂ« duke u zhvilluar shumĂ« shpejt pĂ«r problemet NP-tĂ« vĂ«shtira â algoritmet parametrike. Do tĂ« pĂ«rpiqem t'ju fut nĂ« informacion, tĂ« flas pĂ«r disa algoritme parametrike tĂ« thjeshta dhe tĂ« pĂ«rshkruaj njĂ« metodĂ« tĂ« fuqishme qĂ« mĂ« ndihmoi shumĂ«. Rezultatet e mia i paraqita nĂ« garĂ«n PACE Challenge: pas testeve tĂ« hapura, zgjidhja ime zĂ« vendin e tretĂ«, ndĂ«rsa rezultatet pĂ«rfundimtare do tĂ« bĂ«hen tĂ« njohura mĂ« 1 Korrik.
Rreth meje
MĂ« quajnĂ« Vasiliy Alfyorov, tani po pĂ«rfundoj vitin e tretĂ« nĂ« HSE â ShĂ«n Petersburg. UnĂ« merrem me algoritme qĂ« nga koha e shkollĂ«s, kur studioja nĂ« shkollĂ«n 179 tĂ« MoskĂ«s dhe kam marrĂ« pjesĂ« me sukses nĂ« olimpiadat e informatikĂ«s.
Numri i fundshëm i specializuarve në algoritmet parametrike po hyjnë në bar...
Shembulli është marrë nga libri
Imagjinoni qĂ« jeni roje i barit nĂ« njĂ« qytet tĂ« vogĂ«l. Ădo tĂ« premte, gjysma e qytetit vjen nĂ« barin tuaj pĂ«r t'u relaksuar, e kjo ju shkakton shumĂ« shqetĂ«sime: duhet tĂ« dilni nga bari vizitorĂ«t problematikĂ« pĂ«r tĂ« parandaluar pĂ«rleshjet. NĂ« fund tĂ« fundit, ju mĂ«rzitet dhe vendosni tĂ« merrni masa parandaluese.
Duke qenë se qyteti juaj është i vogël, e dini saktësisht se cilat palë vizitorësh kanë një probabilitet të madh të përleshen nëse hyjnë në bar së bashku. Keni një listë prej n njerëzish që do të vijnë sonte në bar. Vendosni të mos lejoni ndonjë qytetar në bar, në mënyrë që askush të mos përleshet. Në të njëjtën kohë, drejtuesit tuaj nuk duan të humbasin fitimin dhe do të jenë të pakënaqur nëse nuk lejoni më shumë se k njerëz.
Fatkeq, detyra që keni përpara është një detyrë klasike NP-e vështirë. Mund të keni njohuri për të si , ose si problemi i mbulimit të pikave. Për këto probleme, në përgjithësi nuk dihen algoritme që punojnë brenda një kohe të pranueshme. Nëse jemi të saktë, një hipotezë e fortë e paprovuar ETH (Hipoteza e Kohës Eksponenciale) thotë se ky problem nuk mund të zgjidhet në mënyrë 
, domethënë se nuk mund të mendoni asgjë që punon dukshëm më mirë se shflektimi i plotë. Për shembull, supozoni se në barin tuaj do të vijnë n = 1000 njerëz. Kështu që shflektimi i plotë do të ketë 
opsione, e cila është afërsisht 
â jashtĂ«zakonisht shumĂ«. PĂ«r fat tĂ« mirĂ«, drejtimi juaj ka vendosur njĂ« kufizim k = 10, kĂ«shtu qĂ« numri i kombinimeve qĂ« duhet tĂ« shqyrtoni Ă«shtĂ« shumĂ« mĂ« i vogĂ«l: numri i nĂ«ngrupeve prej dhjetĂ« elementesh Ă«shtĂ« 
. Kjo është më mirë, por përsëri nuk do të numërohet brenda një dite, madje as në një klaster të fuqishëm.
Për të eliminuar mundësinë e një zënke në një konfiguratë të tillë të tensioneve midis vizitorëve të barit, duhet të mos lejoni Bobin, Danielin dhe Fyodorin. Zgjidhja, në të cilën mbeten jashtë vetëm dy, nuk ekziston.
A do tĂ« thotĂ« kjo se Ă«shtĂ« koha pĂ«r t'u dorĂ«zuar dhe pĂ«r tĂ« lĂ«nĂ« tĂ« gjithĂ« tĂ« hyjnĂ«? Le tĂ« shqyrtojmĂ« opsione tĂ« tjera. P.sh., mund tĂ« mos lejoni tĂ« hyjnĂ« ata qĂ« po e bĂ«jnĂ« kĂ«tĂ« me shumĂ« njerĂ«z. NĂ«se dikush mund tĂ« pĂ«rfshihet nĂ« njĂ« rrahje me tĂ« paktĂ«n k + 1 nĂ« njĂ« person tjetĂ«r, atĂ«herĂ« nuk duhet ta lejoni tĂ« hyjĂ« â pĂ«rndryshe do tĂ« duhet tĂ« mos lejoni tĂ« hyjnĂ« tĂ« gjithĂ« k + 1 banorĂ«t me tĂ« cilĂ«t ai mund tĂ« rrihen, qĂ« do tĂ« shqetĂ«sojĂ« menaxhmentin.
Supozojmë se i keni hequr të gjithë ata që mundet, sipas këtij parimi. Atëherë të gjithë të tjerët mund të përfshihen në konflikte me më shumë se k njerëz. Duke hequr nga ata k njerëz, mund të parandaloni më shumë se 
konflikte. Kështu që, nëse më shumë se 
njerëz janë të përfshirë në të paktën një konflikt, atëherë me siguri nuk do të keni mundësi t'i parandaloni të gjitha. Duke pasur parasysh se, natyrisht, do të lejoni ata që nuk janë konfliktualë, duhet të kontrolloni të gjitha nëngrupet me madhësi dhjetë nga dyqind njerëz. Janë afërsisht 
, dhe një numër i tillë operacionesh mund të shqyrtohet në një klaster.
Nëse është e mundur të marrim individë tërësisht jo konfliktualë, çfarë ndodh me ata që përfshihen në vetëm një konflikt? Në të vërtetë, ata gjithashtu mund të lejohet, duke mbyllur dyert para kundërshtarëve të tyre. E vërteta është, nëse Alisa ka një konflikt vetëm me Bobin, atëherë nëse e lejojmë Alisën, ne nuk do të humbasim: Bobi mund të ketë konflikte të tjera, ndërsa Alisa absolutisht nuk ka asnjë. Sidomos, është pa kuptim të mos lejojmë asnjë prej tyre. Pas këtyre operacioneve mbeten jo më shumë se 
vizitorë me fat të paqartë: në total kemi 
konflikte, secili me nga dy pjesëmarrës dhe çdo një prej tyre merr pjesë në të paktën dy. Kështu, na mbetet të kalojmë vetëm 
mundësi, që padyshim mund të përballet për një gjysmë ditë në një laptop.
Në të vërtetë, me arsyetim të thjeshtë mund të arrijmë kushte edhe më tërheqëse. Vini re se duhet të zgjidhim të gjitha mosmarrëveshjet, domethënë nga çdo çift konfliktues të zgjedhim të paktën një person që nuk do ta lejojmë. Le të shqyrtojmë një algoritem të tillë: të marrim çdo konflikt, të eliminojmë një pjesëmarrës dhe të vazhdojmë rekurivisht me të tjerët, pastaj të eliminojmë tjetrin dhe gjithashtu të vazhdojmë rekurivisht. Duke qenë se në çdo hap heqim dikë, pemën e rekursisë së këtij algoritmi - një pemë binarë të thellësisë k, prandaj algoritmi funksionon për 
, ku n â numri i vendeve, dhe m â numri i rubrikave. NĂ« shembullin tonĂ«, kjo Ă«shtĂ« rreth dhjetĂ« milionĂ«, tĂ« cilat llogariten pĂ«r disa sekonda jo vetĂ«m nĂ« njĂ« laptop, por madje edhe nĂ« njĂ« telefon mobil.
Shembulli i lartpĂ«rmendur Ă«shtĂ« njĂ« shembull i algoritmit tĂ« parametrizuar. Algoritmet e parametrizuara janĂ« algoritme qĂ« funksionojnĂ« pĂ«r kohĂ« f(k) poly(n), ku p â polinom, f â funksion i llogaritur, dhe k â njĂ« parametr qĂ«, shumĂ« mundĂ«sisht, do tĂ« jetĂ« shumĂ« mĂ« i vogĂ«l se madhĂ«sia e problemit.
TĂ« gjitha arsyetimet deri nĂ« kĂ«tĂ« algoritem tregojnĂ« shembullin e kernelizimit â njĂ« nga teknikat e zakonshme pĂ«r krijimin e algoritmeve tĂ« parametrizuar. Kernelizimi Ă«shtĂ« reduktimi i madhĂ«sisĂ« sĂ« problemit nĂ« njĂ« vlerĂ« tĂ« kufizuar nga funksioni i parametrave. Problemi i marrĂ« shpesh quhet bĂ«rthamĂ«. KĂ«shtu, me argumentet e thjeshta mbi gradĂ«t e majave, kemi marrĂ« bĂ«rthamin katror pĂ«r problemin e Vertex Cover, tĂ« parametrizuar sipas madhĂ«sisĂ« sĂ« pĂ«rgjigjes. EkzistojnĂ« edhe parametro tĂ« tjerĂ« qĂ« mund tĂ« zgjidhen pĂ«r kĂ«tĂ« problem (p.sh., Vertex Cover Above LP), por ne do tĂ« diskutojmĂ« pikĂ«risht atĂ« parametrin.
Pace Challenge
Sfidë (The Parameterized Algorithms and Computational Experiments Challenge) filloi në vitin 2015 për të krijuar lidhje midis algoritmeve të parametrizuara dhe qasjeve të përdorura në praktikë për zgjidhjen e problemeve të llogaritjes. Tre sfidat e para ishin dedikuar gjetjes së gjerësisë së pemës të grafikëve (), gjetjes së pemës së Steinerit () dhe gjetjes së një grupi majash që prishin ciklet (). Në këtë vit, një nga problemet ku mund të provoni aftësitë tuaja ishte problemi i përmendur më lart i mbulimit të majave.
Garancia e kompeticionit po fiton popullaritet çdo vit. Nëse besojmë të dhënat paraprake, këtë vit vetëm në kompeticionin për zgjidhjen e problemit të mbulimit të pikave morën pjesë 24 ekipe. Vlen të theksohet se gara zgjat jo disa orë dhe as një javë, por disa muaj. Ekipet kanë mundësinë të studiojnë literaturën, të shpikin idenë e tyre origjinale dhe të përpiqen ta realizojnë atë. Në thelb, ky kompeticion është një punë hulumtuese. Idetë për zgjidhjet më efikase dhe shpallja e fituesve do të zhvillohet së bashku me konferencën (Simpoziumi Ndërkombëtar mbi Komputimin e Parametrit dhe atë të Saktë) brenda mbledhjes më të madhe vjetore algoritmike në Evropë . Informacione më të hollësishme rreth kompeticionit mund të gjenden në , ndërsa rezultatet e viteve të kaluara ndodhen .
Schemi i zgjidhjes
Për të përballuar detyrën e mbulimit të kulmëve, fillova të aplikoj algoritme parametrizuese. Ato zakonisht përbëhen nga dy pjesë: rregullat e thjeshtimit (të cilat idealisht çojnë në kernelizim) dhe rregullat e ndarjes. Rregullat e thjeshtimit janë një përpunim i inputit në kohë polinomiale. Qëllimi i aplikimit të këtyre rregullave është reduktimi i detyrës në një detyrë ekuivalente të madhësisë më të vogël. Rregullat e thjeshtimit janë pjesa më e shtrenjtë e algoritmit, dhe aplikimi i kësaj pjese nxit kohën totale të funksionimit. 
në vend të një kohe të thjeshtë polinomiale. Në rastin tonë, rregullat e ndarjes bazohen në faktin se për çdo kulm duhet të marrim në përgjigje ose atë, ose fqinjën e tij.
Skema e përgjithshme është kështu: aplikojmë rregullat e thjeshtimit, pastaj zgjedhim një kulm dhe bëjmë dy thirrje rekurzive: në të parën e marrim në përgjigje, ndërsa në të dytën marrë të gjithë fqinjët e tij. Këtë e quajmë ndarjen (branching) sipas këtij kulmi.
Në këtë skemë do të bëhet vetëm një shtesë në paragrafit të ardhshëm.
Ide për rregullat e ndarjes (branching)
Le të flasim për mënyrën se si të zgjidhni kulmin në të cilin do të ndodhë ndarja.
Ideja kryesore është shumë lakmuese në kuptimin algoritmik: le të marrim kulmin me gradën maksimale dhe të ndajmë të saktë atë. Përse duket se kështu është më mirë? Sepse në degën e dytë të thirrjes rekursive, kështu do të heqim shumë kulme. Mund të pritet që të mbetet një grafik i vogël dhe në të do të punojmë shpejt.
Ky qasje me teknikat e thjeshta të diskutuara për kernelizimin tregon rezultate të mira, zgjidh disa teste me mijëra kulme. Por, për shembull, nuk punon mirë për grafet kubike (dmth, grafet ku gradë e çdo kulmi është e barabartë me tre).
Ekziston një ide tjetër, e cila bazohet në një mendim mjaft të thjeshtë: nëse grafiku është i çorganizuar, problemi i komponentëve të tij të lidhjes mund të zgjidhet në mënyrë të pavarur, duke bashkuar përgjigjet në fund. Kjo, për shënim, është një modifikim i vogël premtuar në skemë që do të përshpejtojë zgjidhjen: më parë në këtë rast ne punonim me produktin e kohëve të llogaritjes së përgjigjeve të komponentëve, tani punojmë me shumën. Për të përshpejtuar branchen, duhet ta kthejmë grafikun e lidhur në një të çorganizuar.
Si ta bëjmë këtë? Nëse në graf ekziston një pikë lidhjeje, ne duhet të branchojmë pikërisht mbi të. Pika e lidhjes është një kulm, të cilin nëse e heqim, grafiku humbet lidhjen. Gjetja e të gjitha pikave të lidhjes në graf mund të bëhet me një algoritëm klasik në kohë lineare. Ky qasje ndjeshëm e përshpejton branchen.
Në heqjen e cilitdo nga kulmat e veçuar, grafiku do të ndahet në komponentë lidhjeje.
Këto ne do t'i bëjmë, por dëshirojmë më shumë. Për shembull, të kërkojmë në graf për prerjet e vogla të pikave dhe të kryejmë ndarjen përmes pikave prej saj. Mënyra më efektive që di për të gjetur prerjen minimale globale të pikave është të përdorim pemën Gomori-Hu, e cila ndërtoset në kohë kubike. Në PACE Challenge, madhësia tipike e grafit është disa mijëra pika. Në këtë situatë, në çdo pikë të pemës së rekurzionit, duhet të kryhen miliarda operacione. Kështu, të zgjidhet problemi në kohën e caktuar është thjesht e pamundur.
Le të përpiqemi të optimizojmë zgjidhjen. Prerja minimale e pikave midis një çifti pikash mund të gjenden me çdo algoritëm që ndërtin fluksin maksimal. Mund të aplikojmë në një rrjet të tillë , në praktikë ai funksionon shumë shpejt. Kam dyshime se teorikisht mund të provohet një vlerësim mbi kohën e punës 
, që tashmë është mjaft e pranueshme.
Kam provova disa herë të gjej prerjet midis palëve rastësore të kulmëve dhe të marr më të balancuarin prej tyre. Fatkeqësisht, në testet e hapura të PACE Challenge, kjo dha rezultate të dobëta. Krahasova me një algorithëm që ndante kulmët e maksimumit, duke i ekzekutuar me një kufi në thellësinë e zbritjes. Pas algorithmit që përpiqej të gjente prerje në këtë mënyrë, mbetën grafe më të mëdha. Kjo ndodh sepse prerjet ishin shumë të pabalancuara: duke fshirë 5-10 kulme, arriti të ndante vetëm 15-20.
Duhet theksuar se në artikujt për algoritmet teorikisht më të shpejtë, përdoren teknika shumë më të avancuara për zgjedhjen e kulmëve për ndarje. Këto teknika kanë një realizim shumë të ndërlikuar dhe shpeshherë kanë vlerësime të dobëta për çështjet e kohës dhe memories. Nuk arrita të identifikoj ndonjë prej tyre që do të ishin mjaft të pranueshme për praktikën.
Si të aplikoni rregullat e thjeshtimit
Ne tashmë kemi ide për kernelizimin. Kujtoj:
- Nëse ka një kulm të izoluar, fshijeni atë.
- Nëse ka një kulm me gradë 1, fshijeni atë dhe merrni fqinjën e tij si përgjigje.
- Nëse ka një kulm me të paktën k + 1, merreni atë si përgjigje.
Me dy të parat gjithçka është e qartë, për të tretën ka një hile. Në problemin me barin, na është dhënë një kufizim të lartë në k, por në PACE Challenge duhet të gjeni thjesht një mbulim të majtë minimal të pikave. Ky është një transformim tipik i problemeve të kërkimit (Search Problem) në problemet e zgjidhjes (Decision Problem), shpesh nuk bëhet dallim mes dy llojeve të problemeve. Në praktikë, kur shkruajmë një zgjidhës për problemin e mbulimit të pikave, dallimi mund të jetë. Për shembull, siç është në pikën e tretë.
Nga pikëpamja e implementimit, mund të veprojmë në dy mënyra. Qasja e parë quhet Zgjatja Iterative. Ajo përbëhet në këtë mënyrë: ne mund të fillojmë me një kufizim të arsyeshëm të poshtëm për përgjigjen, dhe pastaj të nxjerrim algoritmin tonë, duke përdorur këtë kufizim si kufizim të lartë të përgjigjes, pa u zbritur në rekursivitet më poshtë se ky kufizim. Nëse gjejmë ndonjë përgjigje, ajo është garantuar të jetë optimale, përndryshe mund të rrisim këtë kufizim njësi dhe të fillojmë sërish.
Qasja tjetër është të mbajmë ndonjë përgjigje aktuale optimale dhe të kërkojmë një përgjigje më të vogël, duke e ndryshuar këtë parametër kur e gjejmë. k për të prerë më shumë degë të tepërta në kërkim.
Pas pasi disa eksperimente gjatĂ« natĂ«s, unĂ« u ndala nĂ« kombinimin e kĂ«tyre dy mĂ«nyrave: fillimisht e nis algoritmin tim me njĂ« kufizim mbi thellĂ«sinĂ« e kĂ«rkimit (duke e pĂ«rshtatur atĂ« nĂ« mĂ«nyrĂ« qĂ« tĂ« zĂ«rĂ« njĂ« kohĂ« tĂ« papĂ«rfillshme krahasuar me zgjidhjen kryesore) dhe e pĂ«rdor zgjidhjen mĂ« tĂ« mirĂ« tĂ« gjetur si kufizim tĂ« sipĂ«rm mbi pĂ«rgjigjen â dmth, mbi atĂ« tĂ« njĂ«jtĂ«n. k.
Majat e gradës 2
Me majat e gradës 0 dhe 1 u merakosëm. Doli që mund të bëhet kështu edhe me majat e gradës 2, por për këtë grafiku do të kërkojë operacione më të komplikuara.
Për ta shpjeguar këtë, duhet të shënohet siç duhet majat. Le të quhet maja e gradës 2 si maja v, dhe fqinjët e saj si maja x dhe y. Më pas do të kemi dy raste.
- Kur x dhe y â fqinjĂ«t. AtĂ«herĂ« mund tĂ« marrim nĂ« pĂ«rgjigje x dhe y, dhe v tĂ« eliminojmĂ«. Dhe vĂ«rtet, nga ky trekĂ«ndĂ«sh duhet tĂ« marrim tĂ« paktĂ«n dy maja nĂ« pĂ«rgjigje dhe ne nuk do tĂ« humbasim me tĂ« vĂ«rtetĂ«, nĂ«se marrim x dhe y: ndoshta ata kanĂ« ende fqinjĂ«, por v ata nuk i kanĂ«.
- Kur x dhe y â jo fqinjĂ«. AtĂ«herĂ« bĂ«het e qartĂ« se tĂ« gjitha tri majat mund tĂ« ngjiten nĂ« njĂ« tĂ« vetĂ«m. Ideja Ă«shtĂ« se nĂ« kĂ«tĂ« rast ka njĂ« pĂ«rgjigje optimale, nĂ« tĂ« cilĂ«n do tĂ« marrim ose v, ose tĂ« dy majat x dhe y. NĂ« fakt, nĂ« rastin e parĂ« do tĂ« detyrohemi tĂ« marrim nĂ« pĂ«rgjigje tĂ« gjithĂ« fqinjĂ«t. x dhe y, dhe nĂ« tĂ« dytĂ«n nuk Ă«shtĂ« e domosdoshme. Kjo pĂ«rputhet saktĂ«sisht me rastet kur ne nuk marrim majĂ«n e ngjitur nĂ« pĂ«rgjigje dhe kur e marrim. Duhet thĂ«nĂ« se nĂ« tĂ« dyja rastet pĂ«rgjigja nga njĂ« operacion i tillĂ« zvogĂ«lohet me njĂ« njĂ«sit.
Vlen të theksohet se ky qasje është mjaft e vështirë për t'u realizuar me saktësi në një kohë të ndershme lineare. Bashkimi i majave është një operacion kompleks; duhet kopjuar listat e fqinjëve. Nëse kjo bëhet gabimisht, mund të kemi një kohë funksionimi asimptotike jo optimale (p.sh., nëse pas çdo bashkimi kopjojmë shumë ribë). U ndala në kërkimin e rrugëve të plota nga majat me gradë 2 dhe analizimin e shumë rasteve të veçanta, si ciklet nga këto maja ose nga të gjitha këto maja përveç një.
Për më tepër, është e nevojshme që kjo operacion të jetë e kthyeshme, në mënyrë që gjatë kthimit nga rekursiviteti të rivendosim grafikën në gjendjen fillestare. Për ta siguruar këtë, nuk e pastruan listën e skajeve të shkarkuara, pas së cilës thjesht e dija se cilat skaje duheshin dërguar ku. Një zbatim i tillë i grafikëve gjithashtu kërkon kujdes, por kujdesi siguron një kohë të ndershme lineare. Për grafikët me disa dhjetëra mijë skaje, kjo përputhet në cache-in e procesorit, që ofron përfitime të mëdha në shpejtësi.
BĂ«rthama lineare
Së fundi, pjesa më interesante e bërthamës.
Për të filluar, le të kujtojmë se në grafikët bipartit, mbulimi minimal i majave mund të kërkohet për 
. Për këtë, duhet të përdorim algoritmin për të gjetur atje përputhjen maksimale, dhe pastaj të përdorim teoremën .
Ideja e bërthamës lineare është kështu: së pari do ta ndajmë grafikën, dmth në vend të çdo maje v do të vendosim dy maja 
dhe 
, dhe nĂ« vend tĂ« çdo skaje u â v do tĂ« vendosim dy skaje 
dhe 
. Grafi i marrë do të jetë dy-anësh. Ne do të gjejmë mbulimin minimal të pikave në të. Disa pika të grafit origjinal do të përfshihen aty dy herë, disa vetëm një herë, dhe disa asnjëherë. Teorema e Nemhauser-Trotter thotë se në këtë rast mund të fshijmë pikat që nuk u përfshinë asnjëherë dhe të marrim në përgjigje ato që u përfshinë dy herë. Më tej, ajo thotë se nga pikat e mbetura (ato që u përfshinë një herë) duhet të marrim në përgjigje të paktën gjysmën e tyre.
Sapo mësuam të lëmë në grafik jo më shumë se 2k pikë. Në fakt, nëse në mbetje përgjigjja është të paktën gjysma e të gjitha pikave, atëherë gjatësia e totalit atje nuk është më shumë se 2k.
KĂ«tu arrita tĂ« bĂ«j njĂ« hap tĂ« vogĂ«l pĂ«rpara. ĂshtĂ« e qartĂ« se bĂ«rthama e ndĂ«rtuar kĂ«shtu varet nga cilat mbulime minimale tĂ« pikave nĂ« grafikun dy-anĂ«sh kemi marrĂ«. Do tĂ« dĂ«shironim tĂ« merrnim njĂ« tĂ« tillĂ«, nĂ« mĂ«nyrĂ« qĂ« numri i pikave tĂ« mbetura tĂ« ishte minimal. MĂ« parĂ«, kĂ«tĂ« mund ta bĂ«nim vetĂ«m pĂ«r njĂ« kohĂ« 
. Unë kam menduar një implementim të këtij algoritmi për një kohë 
, kështu që kjo bërthamë mund të kërkohet në grafikët me qindra mijëra pikë në çdo hap të branchening.
Rezultati
Praktika tregon se zgjidhja ime funksionon mirë në teste me disa qindra kapituj dhe disa mijëra degë. Në këto teste, është e arsyeshme të pritet se zgjidhja do të gjendet brenda gjysmë ore. Mundësia e gjetjes së përgjigjes brenda një kohe të pranueshme në parim rritet nëse grafiku ka mjaft shumë kapituj me shkallë të lartë, për shembull shkallë 10 e më lart.
Për të marrë pjesë në garë, zgjidhjet duhej të dërgoheshin në . Sipas tabelës aty , zgjidhja ime në testet e hapura zë vendin e tretë nga vingtë me një diferencë të madhe nga vendi i dytë. Nëse duhet të jem plotësisht i sinqertë, nuk është krejtësisht e qartë se si do të vlerësohen zgjidhjet në vetë garën: për shembull, zgjidhja ime kalon më pak teste se ajo në vendin e katërt, por në ato që kalon, punon më shpejt.
Rezultatet në testet e mbyllura do të bëhen të njohura më parë të korrikut.
Burimi: habr.com
