Ang gawaing pananaliksik ay marahil ang pinakakawili-wiling bahagi ng aming pagsasanay. Ang ideya ay subukan ang iyong sarili sa iyong napiling direksyon habang nasa unibersidad. Halimbawa, ang mga mag-aaral mula sa mga larangan ng Software Engineering at Machine Learning ay madalas na nagsasaliksik sa mga kumpanya (pangunahin ang JetBrains o Yandex, ngunit hindi lamang).
Sa post na ito ay pag-uusapan ko ang aking proyekto sa Computer Science. Bilang bahagi ng aking trabaho, nag-aral ako at nagsagawa ng mga diskarte sa paglutas ng isa sa mga pinakatanyag na problema sa NP-hard: problema sa pagtatakip ng vertex.
Sa ngayon, ang isang kawili-wiling diskarte sa mga problema sa NP-hard ay mabilis na umuunlad - mga parameterized na algorithm. Susubukan kong pabilisin ka, sabihin sa iyo ang ilang simpleng parameterized algorithm at ilarawan ang isang makapangyarihang paraan na nakatulong sa akin ng malaki. Iniharap ko ang aking mga resulta sa kumpetisyon ng PACE Challenge: ayon sa mga resulta ng mga bukas na pagsubok, ang aking solusyon ay nasa ikatlong pwesto, at ang mga huling resulta ay malalaman sa Hulyo 1.
Tungkol sa aking sarili
Ang pangalan ko ay Vasily Alferov, tinatapos ko na ngayon ang aking ikatlong taon sa National Research University Higher School of Economics - St. Petersburg. Interesado ako sa mga algorithm mula noong mga araw ng aking pag-aaral, noong nag-aral ako sa Moscow school No. 179 at matagumpay na lumahok sa mga Olympiad ng computer science.
Ang isang tiyak na bilang ng mga espesyalista sa mga parameterized na algorithm ay pumasok sa bar...
Halimbawang kinuha mula sa aklat
Isipin na ikaw ay isang bar security guard sa isang maliit na bayan. Tuwing Biyernes, kalahati ng lungsod ang pumupunta sa iyong bar upang mag-relax, na nagbibigay sa iyo ng maraming problema: kailangan mong itapon ang mga maingay na customer sa bar para maiwasan ang mga away. Sa kalaunan, magsawa ka at magpasya na gumawa ng mga hakbang sa pag-iwas.
Dahil maliit ang iyong lungsod, alam mo nang eksakto kung aling mga pares ng mga parokyano ang malamang na mag-away kung mapupunta sila sa isang bar nang magkasama. Mayroon ka bang listahan ng n mga taong pupunta sa bar ngayong gabi. Nagpasya kang panatilihin ang ilang taong bayan sa labas ng bar nang walang sinumang nakikipag-away. Kasabay nito, ang iyong mga amo ay hindi gustong mawalan ng kita at hindi sila magiging masaya kung hindi mo hahayaan ang higit sa k tao.
Sa kasamaang palad, ang problema bago ka ay isang klasikong NP-hard na problema. Maaaring kilala mo siya bilang , o bilang isang vertex na sumasaklaw sa problema. Para sa mga ganitong problema, sa pangkalahatang kaso, walang mga algorithm na gumagana sa isang katanggap-tanggap na oras. Upang maging tumpak, ang hindi napatunayan at medyo malakas na hypothesis na ETH (Exponential Time Hypothesis) ay nagsasabi na ang problemang ito ay hindi malulutas sa oras. , ibig sabihin, wala kang maiisip na mas mahusay kaysa sa kumpletong paghahanap. Halimbawa, sabihin nating may pupunta sa iyong bar n = 1000 Tao. Pagkatapos ang kumpletong paghahanap ay magiging mga opsyon na mayroong humigit-kumulang - nakakabaliw ang dami. Sa kabutihang palad, binigyan ka ng iyong pamamahala ng limitasyon k = 10, kaya ang bilang ng mga kumbinasyon na kailangan mong ulitin ay mas maliit: ang bilang ng mga subset ng sampung elemento ay . Mas mabuti ito, ngunit hindi pa rin ito mabibilang sa isang araw kahit na sa isang malakas na kumpol.
Upang maalis ang posibilidad ng isang away sa ganitong pagsasaayos ng mga pilit na relasyon sa pagitan ng mga bisita ng bar, kailangan mong pigilan sina Bob, Daniel at Fedor. Walang solusyon kung saan dalawa lang ang maiiwan.
Nangangahulugan ba ito na oras na para sumuko at hayaan ang lahat? Isaalang-alang natin ang iba pang mga pagpipilian. Buweno, halimbawa, hindi mo maaaring ipasok lamang ang mga malamang na makipaglaban sa napakaraming tao. Kung may makakalaban man lang k+1 ibang tao, kung gayon tiyak na hindi mo siya mapapasok - kung hindi, kailangan mong pigilan ang lahat k+1 mga taong bayan, na makakalaban niya, na tiyak na magpapagulo sa pamunuan.
Hayaan mong itapon ang lahat ng iyong makakaya ayon sa prinsipyong ito. Pagkatapos lahat ng iba ay maaaring lumaban ng hindi hihigit sa k mga tao. Pagtatapon sa kanila k tao, wala kang mapipigilan kundi mga salungatan. Nangangahulugan ito na kung mayroong higit sa Kung ang isang tao ay kasangkot sa hindi bababa sa isang salungatan, tiyak na hindi mo mapipigilan silang lahat. Dahil, siyempre, tiyak na papasukin mo ang ganap na hindi magkasalungat na mga tao, kailangan mong dumaan sa lahat ng subset na may sukat na sampu sa dalawang daang tao. Mayroong humigit-kumulang , at ang bilang ng mga pagpapatakbong ito ay maaari nang ayusin sa cluster.
Kung maaari mong ligtas na kunin ang mga indibidwal na walang anumang salungatan, paano naman ang mga lumalahok sa isang tunggalian lamang? Sa katunayan, maaari rin silang papasukin sa pamamagitan ng pagsasara ng pinto sa kanilang kalaban. Sa katunayan, kung si Alice ay salungat lamang kay Bob, kung gayon kung hahayaan natin si Alice na lumabas sa kanilang dalawa, hindi tayo mawawala: Maaaring may iba pang mga salungatan si Bob, ngunit tiyak na wala sila ni Alice. At saka, walang saysay para sa aming dalawa na hindi kami papasukin. Pagkatapos ng mga naturang operasyon ay wala na mga bisita na may hindi nalutas na kapalaran: mayroon lamang kami mga salungatan, bawat isa ay may dalawang kalahok at bawat isa ay kasangkot sa hindi bababa sa dalawa. Kaya ang natitira na lang ay ang pag-aayos mga pagpipilian, na madaling ituring na kalahating araw sa isang laptop.
Sa katunayan, sa simpleng pangangatwiran ay makakamit mo ang mas kaakit-akit na mga kondisyon. Tandaan na talagang kailangan nating lutasin ang lahat ng hindi pagkakaunawaan, ibig sabihin, mula sa bawat magkasalungat na pares, pumili ng kahit isang tao na hindi natin papapasukin. Isaalang-alang natin ang sumusunod na algorithm: kumuha ng anumang salungatan, kung saan aalisin natin ang isang kalahok at paulit-ulit na magsisimula sa natitira, pagkatapos ay alisin ang isa pa at magsisimula rin nang recursively. Dahil nagtatapon kami ng isang tao sa bawat hakbang, ang recursion tree ng naturang algorithm ay isang binary tree ng depth k, kaya sa kabuuan ay gumagana ang algorithm Saan n ay ang bilang ng mga vertex, at m - bilang ng mga tadyang. Sa aming halimbawa, ito ay halos sampung milyon, na maaaring kalkulahin sa isang split second hindi lamang sa isang laptop, kundi maging sa isang mobile phone.
Ang halimbawa sa itaas ay isang halimbawa naka-parameter na algorithm. Ang mga naka-parameter na algorithm ay mga algorithm na tumatakbo sa oras f(k) poly(n)Saan p - polinomyal, f ay isang arbitrary na computable function, at k - ilang parameter, na, malamang, ay magiging mas maliit kaysa sa laki ng problema.
Ang lahat ng pangangatwiran bago ang algorithm na ito ay nagbibigay ng isang halimbawa kernelization ay isa sa mga pangkalahatang pamamaraan para sa paglikha ng mga parameterized na algorithm. Ang Kernelization ay ang pagbabawas ng laki ng problema sa isang halaga na nililimitahan ng isang function ng isang parameter. Ang resultang problema ay madalas na tinatawag na kernel. Kaya, sa pamamagitan ng simpleng pangangatwiran tungkol sa mga antas ng vertices, nakakuha kami ng quadratic kernel para sa problema sa Vertex Cover, na na-parameter ayon sa laki ng sagot. May iba pang mga setting na maaari mong piliin para sa gawaing ito (tulad ng Vertex Cover Above LP), ngunit ito ang setting na tatalakayin natin.
Pace Challenge
Kumpetisyon (Ang Parameterized Algorithms and Computational Experiments Challenge) ay ipinanganak noong 2015 upang magtatag ng koneksyon sa pagitan ng mga parameterized na algorithm at mga diskarte na ginagamit sa pagsasanay upang malutas ang mga problema sa computational. Ang unang tatlong kumpetisyon ay nakatuon sa paghahanap ng lapad ng puno ng isang graph (), naghahanap ng isang Steiner tree () at paghahanap ng isang hanay ng mga vertex na pumuputol ng mga cycle (). Sa taong ito, ang isa sa mga problema kung saan maaari mong subukan ang iyong kamay ay ang problema na sumasaklaw sa tuktok na inilarawan sa itaas.
Ang kumpetisyon ay nakakakuha ng katanyagan bawat taon. Kung naniniwala ka sa paunang data, sa taong ito 24 na mga koponan ang nakibahagi sa kumpetisyon upang lutasin ang problema na sumasaklaw sa tuktok nang mag-isa. Kapansin-pansin na ang kumpetisyon ay tumatagal ng hindi ilang oras o kahit isang linggo, ngunit ilang buwan. Ang mga koponan ay may pagkakataong pag-aralan ang panitikan, makabuo ng kanilang sariling orihinal na ideya at subukang ipatupad ito. Sa esensya, ang kumpetisyon na ito ay isang proyekto sa pananaliksik. Ang mga ideya para sa pinakamabisang solusyon at pagbibigay ng parangal sa mga nanalo ay gaganapin kasabay ng kumperensya (International Symposium on Parameterized and Exact Computation) bilang bahagi ng pinakamalaking taunang algorithmic meeting sa Europe . Ang mas detalyadong impormasyon tungkol sa mismong kumpetisyon ay matatagpuan sa , at ang mga resulta ng mga nakaraang taon ay kasinungalingan .
Diagram ng solusyon
Upang malutas ang problema na sumasaklaw sa vertex, sinubukan kong gumamit ng mga parameterized na algorithm. Karaniwang binubuo ang mga ito ng dalawang bahagi: mga panuntunan sa pagpapasimple (na perpektong humahantong sa kernelization) at mga panuntunan sa paghahati. Ang mga panuntunan sa pagpapasimple ay ang preprocessing ng input sa polynomial time. Ang layunin ng paglalapat ng mga naturang patakaran ay upang bawasan ang problema sa isang katumbas na mas maliit na problema. Ang mga panuntunan sa pagpapasimple ay ang pinakamahal na bahagi ng algorithm, at ang paglalapat ng bahaging ito ay humahantong sa kabuuang oras ng pagpapatakbo sa halip na simpleng polynomial time. Sa aming kaso, ang mga panuntunan sa paghahati ay batay sa katotohanan na para sa bawat vertex kailangan mong kunin ito o ang kapitbahay nito bilang sagot.
Ang pangkalahatang pamamaraan ay ito: inilalapat namin ang mga panuntunan sa pagpapasimple, pagkatapos ay pumili kami ng ilang vertex, at gumawa ng dalawang recursive na tawag: sa una ay kinuha namin ito bilang tugon, at sa isa pa ay kinuha namin ang lahat ng mga kapitbahay nito. Ito ang tinatawag nating splitting (branching) kasama ang vertex na ito.
Eksaktong isang karagdagan ang gagawin sa scheme na ito sa susunod na talata.
Mga ideya para sa mga panuntunan sa paghahati (brunching).
Talakayin natin kung paano pumili ng vertex kung saan magaganap ang paghahati.
Ang pangunahing ideya ay napaka sakim sa algorithmic na kahulugan: kumuha tayo ng isang vertex ng pinakamataas na antas at hatiin ito. Bakit parang mas maganda? Dahil sa pangalawang sangay ng recursive na tawag ay aalisin natin ang maraming vertice sa ganitong paraan. Makakaasa ka sa isang maliit na graph na natitira at magagawa namin ito nang mabilis.
Ang diskarte na ito, kasama ang napag-usapan na mga simpleng pamamaraan ng kernelization, ay nagpapakita ng sarili nitong mabuti at nalulutas ang ilang mga pagsubok na ilang libong vertices ang laki. Ngunit, halimbawa, hindi ito gumagana nang maayos para sa mga cubic graph (iyon ay, mga graph na ang antas ng bawat vertex ay tatlo).
May isa pang ideya batay sa isang medyo simpleng ideya: kung ang graph ay hindi nakakonekta, ang problema sa mga konektadong bahagi nito ay maaaring malutas nang nakapag-iisa, na pinagsasama ang mga sagot sa dulo. Ito, sa pamamagitan ng paraan, ay isang maliit na ipinangakong pagbabago sa scheme, na makabuluhang mapabilis ang solusyon: dati, sa kasong ito, nagtrabaho kami para sa produkto ng mga oras para sa pagkalkula ng mga tugon ng mga bahagi, ngunit ngayon ay nagtatrabaho kami para sa ang kabuuan. At para mapabilis ang pagsasanga, kailangan mong gawing nakadiskonekta ang konektadong graph.
Paano ito gagawin? Kung mayroong isang articulation point sa graph, kailangan mong labanan ito. Ang articulation point ay isang vertex na kapag inalis, mawawala ang pagkakakonekta ng graph. Ang lahat ng junction point sa isang graph ay makikita gamit ang isang classical na algorithm sa linear time. Ang diskarte na ito ay makabuluhang nagpapabilis ng pagsanga.
Kapag naalis ang alinman sa mga napiling vertex, hahatiin ang graph sa mga konektadong bahagi.
Gagawin namin ito, ngunit gusto namin ng higit pa. Halimbawa, maghanap ng maliliit na hiwa ng vertex sa graph at hatiin ang mga vertex mula dito. Ang pinakamabisang paraan na alam ko upang mahanap ang minimum na global vertex cut ay ang paggamit ng Gomori-Hu tree, na binuo sa cubic time. Sa PACE Challenge, ang karaniwang laki ng graph ay ilang libong vertex. Sa sitwasyong ito, bilyun-bilyong operasyon ang kailangang isagawa sa bawat tuktok ng recursion tree. Lumalabas na imposibleng malutas ang problema sa inilaang oras.
Subukan nating i-optimize ang solusyon. Ang pinakamababang hiwa ng vertex sa pagitan ng isang pares ng mga vertex ay makikita ng anumang algorithm na bumubuo ng maximum na daloy. Maaari mong ipaalam ito sa naturang network , sa pagsasanay ito ay gumagana nang napakabilis. Mayroon akong hinala na sa teoryang posible na patunayan ang isang pagtatantya para sa oras ng pagpapatakbo , na medyo katanggap-tanggap na.
Ilang beses kong sinubukang maghanap ng mga hiwa sa pagitan ng mga pares ng random na vertices at kunin ang pinakabalanseng isa. Sa kasamaang palad, nagbunga ito ng hindi magandang resulta sa bukas na pagsubok sa PACE Challenge. Inihambing ko ito sa isang algorithm na naghahati sa mga vertex ng pinakamataas na antas, na nagpapatakbo ng mga ito nang may limitasyon sa lalim ng pagbaba. Ang isang algorithm na sumusubok na maghanap ng hiwa sa ganitong paraan ay naiwan sa mas malalaking graph. Ito ay dahil sa ang katunayan na ang mga pagbawas ay naging napaka hindi balanse: sa pag-alis ng 5-10 vertices, posible na hatiin lamang ang 15-20.
Ito ay nagkakahalaga ng pagpuna na ang mga artikulo tungkol sa theoretically pinakamabilis na algorithm ay gumagamit ng mas advanced na mga diskarte para sa pagpili ng mga vertex para sa paghahati. Ang ganitong mga diskarte ay may napakakomplikadong pagpapatupad at kadalasan ay hindi magandang pagganap sa mga tuntunin ng oras at memorya. Hindi ko natukoy ang mga medyo katanggap-tanggap para sa pagsasanay.
Paano Mag-apply ng Mga Panuntunan sa Pagpapasimple
Mayroon na kaming mga ideya para sa kernelization. Hayaan mong ipaalala ko sa iyo:
- Kung mayroong nakahiwalay na vertex, tanggalin ito.
- Kung mayroong vertex ng degree 1, alisin ito at kunin ang kapitbahay nito bilang tugon.
- Kung mayroong isang vertex ng degree ng hindi bababa sa k+1, bawiin mo.
Sa unang dalawa ang lahat ay malinaw, sa pangatlo ay may isang lansihin. Kung sa isang comic problem tungkol sa isang bar ay binigyan tayo ng upper limit ng k, pagkatapos ay sa PACE Challenge kailangan mo lang maghanap ng vertex cover na may pinakamababang laki. Ito ay isang tipikal na pagbabago ng Mga Problema sa Paghahanap sa Mga Problema sa Pagpapasya; kadalasan ay walang pagkakaiba sa pagitan ng dalawang uri ng mga problema. Sa pagsasagawa, kung nagsusulat tayo ng solver para sa vertex na sumasaklaw sa problema, maaaring may pagkakaiba. Halimbawa, tulad ng sa ikatlong punto.
Mula sa pananaw ng pagpapatupad, mayroong dalawang paraan upang magpatuloy. Ang unang diskarte ay tinatawag na Iterative Deepening. Ito ay ang mga sumusunod: maaari tayong magsimula sa ilang makatwirang pagpilit mula sa ibaba sa sagot, at pagkatapos ay patakbuhin ang ating algorithm gamit ang pagpilit na ito bilang isang hadlang sa sagot mula sa itaas, nang hindi bumababa sa recursion kaysa sa pagpilit na ito. Kung nakahanap kami ng ilang sagot, ito ay garantisadong pinakamainam, kung hindi, maaari naming taasan ang limitasyong ito ng isa at magsimulang muli.
Ang isa pang diskarte ay ang pag-imbak ng ilang kasalukuyang pinakamainam na sagot at maghanap ng mas maliit na sagot, binabago ang parameter na ito kapag natagpuan k para sa higit na pagputol ng mga hindi kinakailangang sangay sa paghahanap.
Pagkatapos magsagawa ng ilang gabi-gabi na mga eksperimento, nagpasya ako sa isang kumbinasyon ng dalawang pamamaraang ito: una, pinapatakbo ko ang aking algorithm na may ilang uri ng limitasyon sa lalim ng paghahanap (pinili ito nang sa gayon ay tumagal ito ng hindi gaanong oras kumpara sa pangunahing solusyon) at ginagamit ang pinakamahusay solusyon na natagpuan bilang isang pinakamataas na limitasyon sa sagot - iyon ay, sa parehong bagay k.
Vertices ng degree 2
Nakipag-usap kami sa mga vertex ng degree 0 at 1. Lumalabas na maaari itong gawin sa mga vertex ng degree 2, ngunit mangangailangan ito ng mas kumplikadong mga operasyon mula sa graph.
Upang ipaliwanag ito, kailangan nating italaga ang mga vertex. Tawagin natin ang vertex ng degree 2 bilang vertex v, at mga kapitbahay nito - mga vertex x ΠΈ y. Susunod na magkakaroon tayo ng dalawang kaso.
- Kapag x ΠΈ y - mga kapitbahay. Pagkatapos ay maaari mong sagutin x ΠΈ yAt v tanggalin. Sa katunayan, mula sa tatsulok na ito, hindi bababa sa dalawang vertice ang kailangang kunin bilang kapalit, at tiyak na hindi tayo matatalo kung kukuha tayo x ΠΈ y: malamang may iba silang kapitbahay, at v Wala sila dito.
- Kapag x ΠΈ y - hindi kapitbahay. Pagkatapos ito ay nakasaad na ang lahat ng tatlong vertices ay maaaring nakadikit sa isa. Ang ideya ay na sa kasong ito ay may pinakamainam na sagot, kung saan kami ay kukuha ng alinman v, o parehong vertex x ΠΈ y. Bukod dito, sa unang kaso kailangan nating kunin ang lahat ng mga kapitbahay bilang tugon x ΠΈ y, ngunit sa pangalawa ito ay hindi kinakailangan. Ito ay eksaktong tumutugma sa mga kaso kapag hindi namin kinuha ang nakadikit na vertex bilang tugon at kapag ginawa namin. Nananatili lamang na tandaan na sa parehong mga kaso ang tugon mula sa naturang operasyon ay bumababa ng isa.
Kapansin-pansin na ang diskarte na ito ay medyo mahirap na tumpak na ipatupad sa patas na linear na oras. Ang gluing vertices ay isang kumplikadong operasyon; kailangan mong kopyahin ang mga listahan ng mga kapitbahay. Kung ito ay ginagawa nang walang ingat, maaari kang magkaroon ng asymptotically suboptimal na oras ng pagtakbo (halimbawa, kung kumopya ka ng maraming mga gilid pagkatapos ng bawat gluing). Nag-ayos ako sa paghahanap ng buong mga landas mula sa mga vertices ng degree 2 at pagsusuri ng isang grupo ng mga espesyal na kaso, tulad ng mga cycle mula sa naturang mga vertices o mula sa lahat ng naturang vertices maliban sa isa.
Bilang karagdagan, kinakailangan na ang operasyong ito ay maibabalik, upang kapag bumalik mula sa recursion ay ibinalik namin ang graph sa orihinal nitong anyo. Upang matiyak ito, hindi ko na-clear ang mga listahan ng gilid ng pinagsamang vertices, at pagkatapos ay alam ko lang kung aling mga gilid ang kailangang pumunta kung saan. Ang pagpapatupad na ito ng mga graph ay nangangailangan din ng katumpakan, ngunit nagbibigay ito ng patas na linear na oras. At para sa mga graph ng ilang sampu-sampung libong mga gilid, umaangkop ito sa cache ng processor, na nagbibigay ng mahusay na mga pakinabang sa bilis.
Linear na kernel
Sa wakas, ang pinaka-kagiliw-giliw na bahagi ng kernel.
Upang magsimula, alalahanin na sa mga bipartite na graph ang pinakamababang vertex cover ay makikita gamit . Upang gawin ito kailangan mong gamitin ang algorithm upang mahanap ang maximum na pagtutugma doon, at pagkatapos ay gamitin ang theorem .
Ang ideya ng isang linear kernel ay ito: una nating pinaghiwa-hiwalay ang graph, iyon ay, sa halip na bawat tuktok v magdagdag tayo ng dalawang peak ΠΈ , at sa halip ng bawat gilid ikaw - v dagdagan natin ang dalawang tadyang ΠΈ . Ang magreresultang graph ay magiging bipartite. Hanapin natin ang pinakamababang vertex cover dito. Ang ilang mga vertex ng orihinal na graph ay darating doon ng dalawang beses, ang ilan ay isang beses lamang, at ang ilan ay hindi kailanman. Ang Nemhauser-Trotter theorem ay nagsasaad na sa kasong ito ay maaaring alisin ng isang tao ang mga vertex na hindi tumama kahit isang beses at bawiin ang mga tumama nang dalawang beses. Bukod dito, sinabi niya na sa natitirang mga vertices (mga natamaan nang isang beses) kailangan mong kunin ang hindi bababa sa kalahati bilang isang sagot.
Natuto lang kaming umalis ng hindi hihigit sa 2k mga taluktok Sa katunayan, kung ang natitirang sagot ay hindi bababa sa kalahati ng lahat ng vertices, kung gayon wala nang mga vertex sa kabuuan kaysa sa 2k.
Dito ako nakagawa ng kaunting hakbang pasulong. Malinaw na ang kernel na binuo sa ganitong paraan ay depende sa kung anong uri ng minimal na vertex cover na kinuha namin sa bipartite graph. Gusto kong kumuha ng isa upang ang bilang ng natitirang mga vertex ay minimal. Dati, nagagawa nila ito sa tamang panahon . Nakagawa ako ng pagpapatupad ng algorithm na ito sa oras , kaya, ang core na ito ay maaaring hanapin sa mga graph ng daan-daang libong vertices sa bawat branching stage.
Resulta
Ipinapakita ng pagsasanay na gumagana nang maayos ang aking solusyon sa mga pagsubok ng ilang daang vertices at ilang libong mga gilid. Sa ganitong mga pagsubok, posible na asahan na ang isang solusyon ay matatagpuan sa kalahating oras. Ang posibilidad na makahanap ng sagot sa isang katanggap-tanggap na oras, sa prinsipyo, ay tumataas kung ang graph ay may sapat na malaking bilang ng mga vertex na may mataas na antas, halimbawa, degree 10 at mas mataas.
Upang lumahok sa kumpetisyon, ang mga solusyon ay kailangang ipadala sa . Sa paghusga sa impormasyong ipinakita doon , ang aking solusyon sa mga bukas na pagsubok ay pumapangatlo sa dalawampu, na may malaking agwat mula sa pangalawa. Upang maging ganap na tapat, hindi lubos na malinaw kung paano susuriin ang mga solusyon sa mismong kumpetisyon: halimbawa, ang aking solusyon ay pumasa sa mas kaunting pagsubok kaysa sa solusyon sa ikaapat na lugar, ngunit sa mga pumasa, ito ay mas mabilis na gumagana.
Malalaman ang mga resulta ng mga closed test sa ika-XNUMX ng Hulyo.
Pinagmulan: www.habr.com