Ix-xogħol ta 'riċerka huwa forsi l-aktar parti interessanti tat-taħriġ tagħna. L-idea hi li tipprova lilek innifsek fid-direzzjoni magħżula tiegħek waqt li tkun għadha l-università. Pereżempju, studenti mill-oqsma tal-Inġinerija tas-Softwer u tat-Tagħlim tal-Magni spiss imorru jagħmlu riċerka fil-kumpaniji (prinċipalment JetBrains jew Yandex, iżda mhux biss).
F'din il-post ser nitkellem dwar il-proġett tiegħi fix-Xjenza tal-Kompjuter. Bħala parti mix-xogħol tiegħi, studjajt u poġġiet fil-prattika approċċi biex issolvi waħda mill-aktar problemi NP-hard famużi: problema tal-kisi tal-vertiċi.
Illum il-ġurnata, approċċ interessanti għal problemi NP-hard qed jiżviluppa malajr ħafna - algoritmi parametrizzati. Se nipprova nġibek aġġornat, ngħidlek xi algoritmi parametrizzati sempliċi u niddeskrivi metodu wieħed qawwi li għenni ħafna. Ippreżentajt ir-riżultati tiegħi fil-kompetizzjoni PACE Challenge: skont ir-riżultati tat-testijiet miftuħa, is-soluzzjoni tiegħi tieħu t-tielet post, u r-riżultati finali jkunu magħrufa fl-1 ta’ Lulju.
Dwar lili nnifsi
Jisimni Vasily Alferov, issa qed nispiċċa t-tielet sena fl-Iskola Għolja tal-Ekonomija tal-Università Nazzjonali tar-Riċerka - San Pietruburgu. Ilni interessat fl-algoritmi minn żmien l-iskola tiegħi, meta studjajt fl-iskola Nru 179 ta 'Moska u pparteċipajt b'suċċess fl-Olympiads tax-xjenza tal-kompjuter.
Numru finit ta' speċjalisti f'algoritmi parametrizzati jidħlu fil-bar...
Eżempju meħud mill-ktieb
Immaġina li inti gwardjan tas-sigurtà tal-bar f'belt żgħira. Kull nhar ta' Ġimgħa, nofs il-belt tiġi fil-bar tiegħek biex tirrilassa, u dan jagħtik ħafna inkwiet: għandek bżonn tarmi klijenti rawdy barra mill-bar biex tevita ġlied. Eventwalment, tiddejjaq u tiddeċiedi li tieħu miżuri preventivi.
Peress li l-belt tiegħek hija żgħira, taf eżattament liema pari ta 'patruni x'aktarx jiġġieldu jekk jispiċċaw f'bar flimkien. Għandek lista ta ' n nies li se jiġu l-bar illejla. Inti tiddeċiedi li żżomm xi nies tal-belt barra mill-bar mingħajr ħadd ma jidħol fil-ġlieda. Fl-istess ħin, il-kapijiet tiegħek ma jridux jitilfu l-profitt u ma jkunux kuntenti jekk ma tħallix aktar minn k nies.
Sfortunatament, il-problema quddiemek hija problema klassika NP-hard. Inti tista 'taf tagħha bħala , jew bħala problema li tkopri l-vertiċi. Għal problemi bħal dawn, fil-każ ġenerali, m'hemm l-ebda algoritmi li jaħdmu fi żmien aċċettabbli. Biex tkun preċiża, l-ipoteżi mhux ippruvata u pjuttost qawwija ETH (Exponential Time Hypothesis) tgħid li din il-problema ma tistax tiġi solvuta fil-ħin , jiġifieri, ma tistax taħseb f'xi ħaġa notevoli aħjar minn tfittxija sħiħa. Per eżempju, ejja ngħidu li xi ħadd se jiġi fil-bar tiegħek n = 1000 Bniedem. Imbagħad it-tfittxija kompluta tkun għażliet li hemm bejn wieħed u ieħor - ammont miġnun. Fortunatament, il-maniġment tiegħek tak limitu k = 10, għalhekk in-numru ta 'kombinazzjonijiet li għandek bżonn biex itenni fuq huwa ħafna iżgħar: in-numru ta' sottosettijiet ta 'għaxar elementi huwa . Dan huwa aħjar, iżda xorta mhux se jingħadd f'ġurnata anke fuq cluster qawwi.
Biex telimina l-possibbiltà ta 'ġlieda f'din il-konfigurazzjoni ta' relazzjonijiet tensjoni bejn il-viżitaturi tal-bar, għandek bżonn iżżomm lil Bob, Daniel u Fedor barra. M'hemm l-ebda soluzzjoni li fiha tnejn biss se jitħallew lura.
Dan ifisser li wasal iż-żmien li nċedu u nħallu lil kulħadd jidħol? Ejja nikkunsidraw għażliet oħra. Ukoll, per eżempju, ma tistax tħalli biss lil dawk li x'aktarx jiġġieldu ma 'numru kbir ħafna ta' nies. Jekk xi ħadd jista’ jiġġieled mill-inqas ma’ k+1 persuna oħra, allura żgur ma tistax tħallih jidħol - inkella jkollok iżżomm lil kulħadd barra k+1 nies tal-belt, li magħhom jista’ jiġġieled, li żgur se jħarbat it-tmexxija.
Ħallik tarmi lil kulħadd li tista' skont dan il-prinċipju. Imbagħad kulħadd jista 'jiġġieled b'mhux aktar minn k nies. Jarmihom barra k bniedem, inti tista 'tipprevjeni xejn aktar minn kunflitti. Dan ifisser li jekk ikun hemm aktar minn Jekk persuna tkun involuta f'mill-inqas kunflitt wieħed, allura żgur li ma tistax tipprevjenihom kollha. Peress li, ovvjament, żgur li se tħalli nies kompletament mhux ta 'kunflitt, għandek bżonn tgħaddi minn kull sottogrupp ta' daqs għaxra minn mitejn ruħ. Hemm bejn wieħed u ieħor , u dan in-numru ta 'operazzjonijiet diġà jistgħu jiġu solvuti fuq il-cluster.
Jekk tista 'tieħu b'mod sikur individwi li m'għandhom l-ebda kunflitt, allura xi ngħidu dwar dawk li jipparteċipaw f'kunflitt wieħed biss? Fil-fatt, jistgħu wkoll jitħallew jidħlu billi jagħlqu l-bieb fuq l-avversarju tagħhom. Tabilħaqq, jekk Alice tkun f’kunflitt ma’ Bob biss, allura jekk inħallu lil Alice toħroġ mit-tnejn, ma nitilfux: Bob jista’ jkollu kunflitti oħra, imma Alice żgur li m’għandhiex. Barra minn hekk, ma jagħmilx sens għalina li ma nħallux lilna t-tnejn nidħlu. Wara operazzjonijiet bħal dawn ma jibqax aktar mistednin b'destin mhux solvut: għandna biss kunflitti, kull wieħed b’żewġ parteċipanti u kull wieħed involut f’mill-inqas tnejn. Allura dak kollu li jibqa 'huwa li tissortja għażliet, li faċilment jistgħu jitqiesu bħala nofs ta’ nhar fuq laptop.
Fil-fatt, b'raġunament sempliċi tista 'tikseb kundizzjonijiet saħansitra aktar attraenti. Innota li definittivament għandna bżonn insolvu t-tilwim kollu, jiġifieri, minn kull par konfliġġenti, agħżel mill-inqas persuna waħda li mhux se nħalluha tidħol. Ejja nikkunsidraw l-algoritmu li ġej: ħu kwalunkwe kunflitt, li minnu nneħħi parteċipant wieħed u nibdew b'mod rikorsiv mill-bqija, imbagħad neħħi l-ieħor u nibdew ukoll b'mod rikorsiv. Peress li nefgħu lil xi ħadd f'kull pass, is-siġra tar-rikorsi ta 'algoritmu bħal dan hija siġra binarja ta' fond k, għalhekk b'kollox l-algoritmu jaħdem fi fejn n huwa n-numru ta' vertiċi, u m - numru ta' kustilji. Fl-eżempju tagħna, dan huwa madwar għaxar miljun, li jista 'jiġi kkalkulat f'qasma ta' sekonda mhux biss fuq laptop, iżda anke fuq mowbajl.
L-eżempju ta 'hawn fuq huwa eżempju algoritmu parametrizzat. Algoritmi parametrizzati huma algoritmi li jimxu fil-ħin f(k) poli(n)fejn p - polinomjali, f hija funzjoni komputabbli arbitrarja, u k - xi parametru, li, possibilment, se jkun ħafna iżgħar mid-daqs tal-problema.
Ir-raġunament kollu qabel dan l-algoritmu jagħti eżempju kernelization hija waħda mit-tekniki ġenerali għall-ħolqien ta 'algoritmi parametrizzati. Kernelization hija t-tnaqqis tad-daqs tal-problema għal valur limitat minn funzjoni ta 'parametru. Il-problema li tirriżulta ħafna drabi tissejjaħ kernel. Għalhekk, b'raġunament sempliċi dwar il-gradi tal-vertiċi, ksibna qalba kwadratika għall-problema tal-Vertex Cover, parametrizzata mid-daqs tat-tweġiba. Hemm settings oħra li tista 'tagħżel għal dan il-kompitu (bħal Vertex Cover Above LP), iżda dan huwa l-issettjar li ser niddiskutu.
Pace Challenge
Kompetizzjoni (The Parameterized Algorithms and Computational Experiments Challenge) twieldet fl-2015 biex tistabbilixxi konnessjoni bejn algoritmi parametrizzati u approċċi użati fil-prattika biex isolvu problemi ta 'komputazzjoni. L-ewwel tliet kompetizzjonijiet kienu ddedikati biex tinstab il-wisa' tas-siġra ta' graff (), tfittex siġra Steiner () u tiftix għal sett ta’ vertiċi li jaqtgħu ċ-ċikli (). Din is-sena, waħda mill-problemi li fiha tista' tipprova idejk kienet il-problema tal-kisi tal-vertiċi deskritta hawn fuq.
Il-kompetizzjoni qed tikseb popolarità kull sena. Jekk temmen id-dejta preliminari, din is-sena 24 tim ħadu sehem fil-kompetizzjoni biex isolvu l-problema tal-kisi tal-vertiċi biss. Ta 'min jinnota li l-kompetizzjoni ma ddumx diversi sigħat jew saħansitra ġimgħa, iżda diversi xhur. It-timijiet għandhom l-opportunità li jistudjaw il-letteratura, joħorġu bl-idea oriġinali tagħhom stess u jippruvaw jimplimentawha. Essenzjalment, din il-kompetizzjoni hija proġett ta 'riċerka. Ideat għall-aktar soluzzjonijiet effettivi u l-għoti tar-rebbieħa se jsiru flimkien mal-konferenza (International Symposium on Parameterized and Exact Computation) bħala parti mill-akbar laqgħa algoritmika annwali fl-Ewropa . Informazzjoni aktar dettaljata dwar il-kompetizzjoni nnifisha tista' ssibu fuq , u r-riżultati tas-snin preċedenti jinsabu .
Dijagramma tas-soluzzjoni
Biex issolvi l-problema tal-kisi tal-vertiċi, ippruvajt nuża algoritmi parametrizzati. Tipikament jikkonsistu f'żewġ partijiet: regoli ta' simplifikazzjoni (li idealment iwasslu għal kernelization) u regoli ta' qsim. Ir-regoli ta' simplifikazzjoni huma l-ipproċessar minn qabel tal-input f'ħin polinomjali. L-iskop tal-applikazzjoni ta' regoli bħal dawn huwa li titnaqqas il-problema għal problema iżgħar ekwivalenti. Ir-regoli tas-simplifikazzjoni huma l-aktar parti għalja tal-algoritmu, u l-applikazzjoni ta 'din il-parti twassal għall-ħin totali ta' tħaddim minflok ħin polinomjali sempliċi. Fil-każ tagħna, ir-regoli tal-qsim huma bbażati fuq il-fatt li għal kull vertiċi għandek bżonn tieħu jew lilu jew lill-proxxmu tiegħu bħala tweġiba.
L-iskema ġenerali hija din: napplikaw ir-regoli tas-simplifikazzjoni, imbagħad nagħżlu xi vertiċi, u nagħmlu żewġ sejħiet rikorsivi: fl-ewwel nieħuha bi tweġiba, u fl-oħra nieħdu l-ġirien kollha tagħha. Dan huwa dak li nsejħu qsim (fergħat) tul dan il-vertiċi.
Se ssir eżattament żieda waħda għal din l-iskema fil-paragrafu li jmiss.
Ideat għall-qsim (brunching) tar-regoli
Ejja niddiskutu kif tagħżel vertiċi li matulu se jseħħ il-qsim.
L-idea ewlenija hija greedy ħafna fis-sens algoritmiku: ejja nieħdu vertiċi ta 'grad massimu u naqsmu tulha. Għaliex jidher aħjar? Għax fit-tieni fergħa tas-sejħa rikorsiv se nneħħu ħafna vertiċi b'dan il-mod. Tista 'toqgħod fuq graff żgħir li fadal u nistgħu naħdmu fuqha malajr.
Dan l-approċċ, bit-tekniki sempliċi ta 'kernelization diġà diskussi, juri lilu nnifsu tajjeb u jsolvi xi testijiet ta' diversi eluf ta 'vertiċi fid-daqs. Iżda, pereżempju, ma taħdimx tajjeb għal graffs kubi (jiġifieri, graffs li l-grad tagħhom ta 'kull vertiċi huwa tlieta).
Hemm idea oħra bbażata fuq idea pjuttost sempliċi: jekk il-graff ikun skonnettjat, il-problema fuq il-komponenti konnessi tagħha tista 'tiġi solvuta b'mod indipendenti, u tgħaqqad it-tweġibiet fl-aħħar. Din, bil-mod, hija modifika żgħira mwiegħda fl-iskema, li se tħaffef b'mod sinifikanti s-soluzzjoni: qabel, f'dan il-każ, ħdimna għall-prodott taż-żminijiet għall-kalkolu tar-risponsi tal-komponenti, iżda issa naħdmu għal is-somma. U biex tħaffef il-fergħat, trid iddawwar graff konness f'wieħed skonnettjat.
Kif tagħmel dan? Jekk hemm punt ta 'artikolazzjoni fil-graff, għandek bżonn tiġġieled għalih. Punt ta' artikolazzjoni huwa vertiċi tali li meta jitneħħa, il-graff jitlef il-konnettività tiegħu. Il-punti ta' junction kollha f'graff jistgħu jinstabu bl-użu ta' algoritmu klassiku f'ħin lineari. Dan l-approċċ iħaffef b'mod sinifikanti l-fergħat.
Meta jitneħħa xi wieħed mill-vertiċi magħżula, il-graff jinqasam f'komponenti konnessi.
Dan se nagħmluh, imma rridu aktar. Pereżempju, fittex qatgħat żgħar tal-vertiċi fil-graff u aqsam tul il-vertiċi minnha. L-aktar mod effiċjenti li naf biex insib il-qatgħa minima tal-vertiċi globali huwa li tuża siġra Gomori-Hu, li hija mibnija f'ħin kubu. Fl-Isfida PACE, id-daqs tipiku tal-graff huwa ta' diversi eluf ta' vertiċi. F'din is-sitwazzjoni, jeħtieġ li jsiru biljuni ta' operazzjonijiet f'kull vertiċi tas-siġra tar-rikorsi. Jirriżulta li huwa sempliċement impossibbli li tissolva l-problema fiż-żmien allokat.
Ejja nippruvaw ottimizzaw is-soluzzjoni. Il-qtugħ minimu tal-vertiċi bejn par ta' vertiċi jista' jinstab minn kwalunkwe algoritmu li jibni fluss massimu. Tista 'tħalliha fuq tali netwerk , fil-prattika taħdem malajr ħafna. Għandi suspett li teoretikament huwa possibbli li nipprova l-istima għall-ħin operattiv , li diġà hija pjuttost aċċettabbli.
Ippruvajt diversi drabi biex infittex qatgħat bejn pari ta 'vertiċi każwali u nieħu l-aktar wieħed bilanċjat. Sfortunatament, dan ipproduċa riżultati ħżiena fl-ittestjar miftuħ tal-PACE Challenge. Qabbilha ma 'algoritmu li jaqsam vertiċi ta' grad massimu, u jmexxihom b'limitazzjoni fuq il-fond tad-dixxendenza. Algoritmu li jipprova jsib qatgħa b'dan il-mod ħalla warajh graffs akbar. Dan huwa dovut għall-fatt li l-qatgħat irriżultaw li kienu żbilanċjati ħafna: wara li neħħew 5-10 vertiċi, kien possibbli li jinqasam biss 15-20.
Ta 'min jinnota li l-artikoli dwar l-algoritmi teoretikament l-aktar mgħaġġla jużaw tekniki ħafna aktar avvanzati għall-għażla tal-vertiċi għall-qsim. Tekniki bħal dawn għandhom implimentazzjoni kumplessa ħafna u ħafna drabi prestazzjoni fqira f'termini ta 'ħin u memorja. Ma kontx kapaċi nidentifika dawk li huma pjuttost aċċettabbli għall-prattika.
Kif Applika Regoli ta' Simplifikazzjoni
Diġà għandna ideat għall-kernelization. Ħa nfakkarkom:
- Jekk hemm vertiċi iżolat, ħassarha.
- Jekk hemm vertiċi ta 'grad 1, neħħiha u ħu l-proxxmu tiegħu bħala tweġiba.
- Jekk ikun hemm vertiċi ta' grad mill-inqas k+1, ħudha lura.
Bl-ewwel tnejn kollox huwa ċar, mat-tielet hemm trick wieħed. Jekk fi problema komika dwar bar ingħatajna limitu massimu ta k, imbagħad fl-Isfida PACE għandek bżonn biss issib kopertura tal-vertiċi tad-daqs minimu. Din hija trasformazzjoni tipika ta' Problemi ta' Tiftix fi Problemi ta' Deċiżjoni; ħafna drabi ma jkun hemm l-ebda differenza bejn iż-żewġ tipi ta' problemi. Fil-prattika, jekk qed niktbu solver għall-problema tal-kisi tal-vertiċi, jista 'jkun hemm differenza. Per eżempju, bħal fit-tielet punt.
Mil-lat ta' implimentazzjoni, hemm żewġ modi kif tipproċedi. L-ewwel approċċ jissejjaħ Approfondiment Iterattiv. Huwa kif ġej: nistgħu nibdew b'xi restrizzjoni raġonevoli minn taħt fuq it-tweġiba, u mbagħad imexxu l-algoritmu tagħna billi tuża din ir-restrizzjoni bħala restrizzjoni fuq it-tweġiba minn fuq, mingħajr ma mmorru aktar baxxi fir-rikorsis minn dan ir-restrizzjoni. Jekk sibna xi tweġiba, huwa garantit li jkun ottimali, inkella nistgħu nżidu dan il-limitu b'wieħed u nibdew mill-ġdid.
Approċċ ieħor huwa li taħżen xi tweġiba ottimali attwali u tfittex tweġiba iżgħar, billi tbiddel dan il-parametru meta jinstab k għal qtugħ akbar ta 'fergħat mhux meħtieġa fit-tfittxija.
Wara li għamilt diversi esperimenti filgħaxija, għamilt taħlita ta 'dawn iż-żewġ metodi: l-ewwel, inmexxi l-algoritmu tiegħi b'xi tip ta' limitu fuq il-fond tat-tfittxija (nagħżel hekk li jieħu ħin negliġibbli meta mqabbel mas-soluzzjoni ewlenija) u nuża l-aħjar. soluzzjoni misjuba bħala limitu massimu għat-tweġiba - jiġifieri, għall-istess ħaġa k.
Vertiċi tal-grad 2
Imxejna ma 'vertiċi ta' grad 0 u 1. Jirriżulta li dan jista 'jsir b'punti ta' grad 2, iżda dan ikun jeħtieġ operazzjonijiet aktar kumplessi mill-graff.
Biex nispjegaw dan, irridu nnominaw b'xi mod il-vertiċi. Ejja nsejħu vertiċi ta' grad 2 vertiċi v, u l-ġirien tagħha - vertiċi x и y. Sussegwentement ikollna żewġ każijiet.
- Meta x и y - ġirien. Imbagħad tista’ twieġeb x и yU v ħassar. Tabilħaqq, minn dan it-trijangolu jeħtieġ li jittieħdu mill-inqas żewġ vertiċi bi tpattija, u żgur li mhux se nitilfu jekk nieħdu x и y: probabbilment għandhom ġirien oħra, u v Mhumiex hawn.
- Meta x и y - mhux ġirien. Imbagħad huwa ddikjarat li t-tliet vertiċi jistgħu jiġu inkollati f'wieħed. L-idea hija li f'dan il-każ hemm tweġiba ottimali, li fiha nieħdu jew v, jew iż-żewġ vertiċi x и y. Barra minn hekk, fl-ewwel każ ikollna nieħdu l-ġirien kollha bħala reazzjoni x и y, iżda fit-tieni mhux meħtieġ. Dan jikkorrispondi eżattament għall-każijiet meta ma nieħdux il-vertiċi inkollat bi tweġiba u meta nagħmlu. Jibqa' biss li wieħed jinnota li fiż-żewġ każijiet ir-rispons minn operazzjoni bħal din jonqos b'wieħed.
Ta 'min jinnota li dan l-approċċ huwa pjuttost diffiċli biex jiġi implimentat b'mod preċiż f'ħin lineari ġust. L-inkullar tal-vertiċi hija operazzjoni kumplessa; trid tikkopja listi tal-ġirien. Jekk dan isir b'mod traskurat, tista 'tispiċċa b'ħin ta' tħaddim asintotiku subottimali (per eżempju, jekk tikkopja ħafna truf wara kull inkullar). Iddeċidejt li nsib mogħdijiet sħaħ minn vertiċi ta 'grad 2 u tanalizza mazz ta' każijiet speċjali, bħal ċikli minn vertiċi bħal dawn jew minn vertiċi bħal dawn kollha ħlief wieħed.
Barra minn hekk, huwa meħtieġ li din l-operazzjoni tkun riversibbli, sabiex meta nirritornaw minn rikorsi nerġgħu nġibu l-graff għall-forma oriġinali tiegħu. Biex niżguraw dan, ma kontx ċara l-listi tat-tarf tal-vertiċi magħquda, u mbagħad kont naf biss liema truf kellhom bżonn imorru fejn. Din l-implimentazzjoni tal-graffs teħtieġ ukoll preċiżjoni, iżda tipprovdi ħin lineari ġust. U għal graffs ta 'diversi għexieren ta' eluf ta 'truf, tidħol fil-cache tal-proċessur, li tagħti vantaġġi kbar fil-veloċità.
Qalb lineari
Fl-aħħarnett, l-aktar parti interessanti tal-qalba.
Biex tibda, ftakar li fil-grafiċi bipartiti l-kopertura minima tal-vertiċi tista 'tinstab bl-użu . Biex tagħmel dan għandek bżonn tuża l-algoritmu sabiex issib it-tqabbil massimu hemm, u mbagħad uża t-teorema .
L-idea ta 'qalba lineari hija din: l-ewwel aħna nfirxu l-graff, jiġifieri, minflok kull vertiċi v ejja nżidu żewġ qċaċet и , u minflok kull tarf u - v ejja nżidu żewġ kustilji и . Il-graff li jirriżulta se jkun bipartit. Ejja nsibu l-kopertura minima tal-vertiċi fiha. Xi vertiċi tal-graff oriġinali se jaslu hemm darbtejn, xi wħud darba biss, u xi wħud qatt. It-teorema ta’ Nemhauser-Trotter jgħid li f’dan il-każ wieħed jista’ jneħħi vertiċi li lanqas darba ma laqtu u jieħu lura dawk li laqtu darbtejn. Barra minn hekk, tgħid li mill-vertiċi li fadal (dawk li jolqtu darba) trid tieħu mill-inqas nofs bħala tweġiba.
Għadna kif tgħallimna nħallu mhux aktar minn 2k qċaċet Tabilħaqq, jekk il-bqija tat-tweġiba hija mill-inqas nofs il-vertiċi kollha, allura m'hemmx aktar vertiċi b'kollox minn 2k.
Hawnhekk stajt nagħmel pass żgħir 'il quddiem. Huwa ċar li l-qalba mibnija b'dan il-mod tiddependi fuq x'tip ta 'kopertura minima tal-vertiċi ħadna fil-graff bipartite. Nixtieq nieħu waħda sabiex in-numru ta' vertiċi li fadal ikun minimu. Preċedentement, kienu kapaċi jagħmlu dan biss fil-ħin . Ħriġt b'implimentazzjoni ta 'dan l-algoritmu fil-ħin , għalhekk, din il-qalba tista' tiġi mfittxija fi graffs ta' mijiet ta' eluf ta' vertiċi f'kull stadju tal-fergħat.
Riżultat
Il-prattika turi li s-soluzzjoni tiegħi taħdem tajjeb fuq testijiet ta 'diversi mijiet ta' vertiċi u diversi eluf ta 'truf. F'testijiet bħal dawn huwa pjuttost possibbli li wieħed jistenna li soluzzjoni tinstab f'nofs siegħa. Il-probabbiltà li tinstab tweġiba fi żmien aċċettabbli, fil-prinċipju, tiżdied jekk il-graff ikollu numru kbir biżżejjed ta 'vertiċi ta' grad għoli, pereżempju, grad 10 u ogħla.
Biex tipparteċipa fil-kompetizzjoni, kellhom jintbagħtu s-soluzzjonijiet . Ġġudikat mill-informazzjoni ppreżentata hemmhekk , is-soluzzjoni tiegħi fit-testijiet miftuħa tikklassifika t-tielet minn għoxrin, b'distakk kbir mit-tieni. Biex inkun kompletament onest, mhuwiex ċar għal kollox kif is-soluzzjonijiet se jiġu evalwati fil-kompetizzjoni nnifisha: pereżempju, is-soluzzjoni tiegħi tgħaddi minn inqas testijiet mis-soluzzjoni fir-raba 'post, iżda fuq dawk li jgħaddu, taħdem aktar malajr.
Ir-riżultati tat-testijiet magħluqa se jkunu magħrufa fl-XNUMX ta’ Lulju.
Sors: www.habr.com