Basa rekutsvakurudza zvichida ndiro rinonyanya kufadza chikamu chekudzidziswa kwedu. Pfungwa ndeyekuzviedza iwe munzira yako yaunosarudza uchiri kuyunivhesiti. Semuyenzaniso, vadzidzi vanobva kunzvimbo dzeSoftware Engineering uye Machine Learning vanowanzoenda kunotsvaga mumakambani (kunyanya JetBrains kana Yandex, asi kwete chete).
Mune ino post ini ndichataura nezve chirongwa changu muComputer Science. Sechikamu chebasa rangu, ndakadzidza nekushandisa nzira dzekugadzirisa imwe yeanonyanya kuzivikanwa NP-akaoma matambudziko: vertex kuvhara dambudziko.
Mazuva ano, nzira inonakidza yeNP-yakaoma matambudziko iri kukura nekukurumidza - parameterized algorithms. Ini ndichaedza kukuita kuti ukurumidze, ndikuudze imwe yakapusa parameterized algorithms uye tsanangura imwe ine simba nzira yakandibatsira zvakanyanya. Ndakaratidza mhedzisiro yangu kumakwikwi ePACE Challenge: zvinoenderana nemhedzisiro yebvunzo dzakavhurika, mhinduro yangu inotora nzvimbo yechitatu, uye mhedzisiro inozozivikanwa muna Chikunguru 1.
Nezvangu
Zita rangu ndiVasily Alferov, ndava kupedza gore rangu rechitatu paNational Research University Higher School of Economics - St. Ndave ndichifarira maalgorithms kubva pamazuva angu ekuchikoro, pandakadzidza pachikoro cheMoscow No.
Nhamba inogumira yenyanzvi mune parameterized algorithms inopinda mubhawa ...
Muenzaniso wakatorwa mubhuku
Fungidzira kuti uri murindi webhawa mutaundi duku. Chishanu chega chega, hafu yeguta inouya kubhawa yako kuzozorora, izvo zvinokupa iwe dambudziko rakawanda: unofanirwa kukanda vatengi vane ruzha kunze kwebhawa kudzivirira kurwa. Pakupedzisira, iwe unodyiswa uye unosarudza kutora matanho ekudzivirira.
Sezvo guta rako riri diki, iwe unonyatsoziva kuti ndeapi mapaya evatengi vanogona kurwa kana vakaguma vari mubhawa pamwechete. Une rondedzero ye n vanhu vachauya kubhawa manheru ano. Iwe unofunga kuti vamwe vanhu vemutaundi vasabude mubhawa pasina anopinda mukurwa. Panguva imwecheteyo, vashandi vako havadi kurasikirwa nepurofiti uye havazofari kana iwe usingaregi zvinopfuura. k vanhu.
Nehurombo, dambudziko pamberi pako ikirasi NP-yakaoma dambudziko. Unogona kumuziva sa , kana sedambudziko rekuvharisa vertex. Kune matambudziko akadai, mune zvakajairika, hapana algorithms inoshanda munguva inogamuchirwa. Kutaura chokwadi, iyo isina kuvimbiswa uye yakasimba fungidziro ETH (Exponential Time Hypothesis) inoti dambudziko iri harigone kugadziriswa nenguva. , ndiko kuti, haugone kufunga nezve chero chinhu chinooneka chiri nani pane kutsvaga kwakazara. Somuenzaniso, ngatiti mumwe munhu achauya kubhawa rako n = 1000 Munhu. Zvadaro kutsvaga kwakakwana kuchava sarudzo dziripo dzinenge - mari inopenga. Neraki, manejimendi ako akakupa muganhu k = zana, saka huwandu hwemisanganiswa yaunoda kudzokorora idiki kwazvo: huwandu hwezvikamu zvezvikamu gumi . Izvi zviri nani, asi hazvigone kuverengerwa muzuva rimwe kunyangwe pachikwata chine simba.
Kuti ubvise mukana wekurwa mukugadziriswa uku kwehukama hwakakanganisika pakati pevashanyi vebhawa, unofanirwa kuchengetedza Bob, Daniel naFedor kunze. Hapana mhinduro yekuti vaviri chete ndivo vachasiiwa.
Izvi zvinoreva here kuti inguva yekupa uye kurega munhu wese achipinda? Ngationei dzimwe nzira. Zvakanaka, semuenzaniso, haugone kutendera avo chete vanogona kurwa nenhamba yakakura kwazvo yevanhu. Kana munhu achigona kurwa at least with k +1 mumwe munhu, saka haugone kumutendera kuti apinde - zvikasadaro uchafanira kuchengetedza munhu wese kunze k +1 vanhu vemutaundi, vaanogona kurwa navo, izvo zvichagumbura hutungamiriri.
Rega iwe urase kunze wese waungagona maererano nemusimboti uyu. Ipapo vamwe vose vanogona kurwa pasina kupfuura k vanhu. Kudzikanda kunze k murume, hapana chaunogona kudzivirira kunze kwekunge kunetsana. Izvi zvinoreva kuti kana pane zvakawanda kupfuura Kana munhu akabatanidzwa mune imwe mhirizhonga, saka iwe zvechokwadi haugoni kuvadzivisa vose. Sezvo, hongu, iwe uchanyatso pinza vanhu vasina kupokana, iwe unofanirwa kupfuura nepakati pese zvidimbu zvehukuru gumi kubva pamazana maviri evanhu. Kune dzinenge , uye iyi nhamba yekushanda inogona kutogadziriswa pane cluster.
Kana iwe uchigona kutora zvakachengeteka vanhu vasina kupokana zvachose, ko zvakadini nevaya vanotora chikamu mukukonana kumwe chete? Muchokwadi, ivo vanogona zvakare kubvumidzwa nekuvhara musuwo kune wavanopikisa. Chokwadi, kana Alice achinetsana naBob chete, saka kana tikasiya Alice kubva pavaviri, isu hatingarasikirwe: Bob anogona kunge aine mamwe makakatanwa, asi Alice haana iwo. Uyezve, hazvina musoro kuti isu tisatibvumira kupinda. Mushure mekuvhiyiwa kwakadai hapachina vaenzi vane mugumo usina kugadziriswa: tine chete kunetsana, mumwe nemumwe aine vatori vechikamu vaviri uye mumwe nemumwe achibatanidzwa mune vangangoita vaviri. Saka chasara kugadzirisa sarudzo, iyo inogona kutorwa nyore nyore hafu yezuva pane laptop.
Muchokwadi, nekufunga kwakapfava iwe unogona kuwana zvakatonyanya kunaka mamiriro. Ziva kuti isu tinofanirwa kugadzirisa kusawirirana kwese, ndiko kuti, kubva kune vaviri vanopokana, sarudza munhu mumwe chete watisingabvumire kupinda. Ngatitarisei algorithm inotevera: tora chero kupokana, kwatinobvisa mumwe mutori wechikamu uye nekudzokorora kutanga kubva kune yasara, tobvisa imwe uye zvakare tanga kudzokorora. Sezvo isu tichikanda mumwe munhu kunze nhanho dzese, iyo yekudzoka muti weiyo algorithm ibhinari muti wekudzika k, saka muhuwandu iyo algorithm inoshanda mukati kupi n ndiyo nhamba ye vertices, uye m - nhamba yembabvu. Mumuenzaniso wedu, izvi zvinenge mamiriyoni gumi, izvo zvinogona kuverengwa muchikamu chechipiri kwete chete pa laptop, asi kunyange parunhare.
Muenzaniso uri pamusoro apa muenzaniso parameterized algorithm. Parameterized algorithms maalgorithms anomhanya nenguva f(k) poly(n)kupi p - polynomial, f ibasa rekuita computable, uye k - imwe parameter, iyo, zvichida, ichava duku kudarika ukuru hwedambudziko.
Kufunga kwese pamberi peiyi algorithm kunopa muenzaniso kernelization ndeimwe yeakajairika matekiniki ekugadzira parameterized algorithms. Kernelization ndiko kudzikiswa kwehukuru hwedambudziko kune kukosha kwakaganhurirwa nebasa reparameter. Dambudziko rinokonzera rinowanzonzi kernel. Nekudaro, nekufunga kwakapusa nezve madhigirii evertices, takawana quadratic kernel yeVertex Cover dambudziko, parametered nehukuru hwemhinduro. Pane mamwe marongero aungasarudze pabasa iri (seVertex Cover Above LP), asi iyi ndiyo marongero yatichakurukura.
Pace Dambudziko
Makwikwi (Iyo Parameterized Algorithms uye Computational Experiments Challenge) yakazvarwa muna 2015 kuti igadzirise hukama pakati peparameterized algorithms uye nzira dzinoshandiswa mukuita kugadzirisa matambudziko emakomputa. Makwikwi matatu ekutanga akazvipira kutsvaga hupamhi hwemuti wegirafu (), kutsvaga muti weSteiner () uye kutsvaga seti yema vertices inocheka matenderera () Gore rino, rimwe rematambudziko aungaedza ruoko rwako pariri raive dambudziko rekuvhara vertex rinotsanangurwa pamusoro.
Makwikwi aya ari kuita mukurumbira gore negore. Kana iwe uchitenda iyo yekutanga data, gore rino zvikwata makumi maviri nemana zvakatora chikamu mumakwikwi ekugadzirisa dambudziko rekuvhara vertex chete. Zvakakosha kuziva kuti makwikwi haatore maawa akawanda kana kunyange vhiki, asi mwedzi yakawanda. Mapoka ane mukana wekudzidza zvinyorwa, anouya nepfungwa yavo yepakutanga uye anoedza kuishandisa. Muchidimbu, makwikwi aya ipurojekiti yekutsvaga. Mazano emhinduro dzakanyanya kushanda uye kupihwa kwevanokunda kuchaitwa pamwe chete nemusangano. (International Symposium paParameterized uye Exact Computation) sechikamu chemusangano mukuru wepagore wealgorithmic muEurope. . Mamwe ruzivo rwakadzama nezvemakwikwi pachawo anogona kuwanikwa pa , uye migumisiro yemakore apfuura inhema .
Solution diagram
Kugadzirisa dambudziko rekuvhara vertex, ndakaedza kushandisa parameterized algorithms. Iwo anowanzo kuve nezvikamu zviviri: mitemo yekurerutsa (iyo inotungamira kune kernelization) uye kupatsanura mitemo. Mitemo yekurerutsa ndeye preprocessing yekuisa mune polynomial nguva. Chinangwa chekushandisa mitemo yakadai ndechekuderedza dambudziko kune rakaenzana dambudziko duku. Mitemo yekurerutsa ndiyo inonyanya kudhura chikamu chegorgorithm, uye kushandisa chikamu ichi kunotungamira kune yakazara nguva yekumhanya pane nyore polynomial nguva. Muchiitiko chedu, mitemo yekuparadzanisa inobva pakuti kune imwe neimwe vertex unofanira kutora kana iyo kana muvakidzani wayo semhinduro.
Iyo yakawanda chirongwa ndeichi: tinoshandisa mitemo yekurerutsa, zvino tinosarudza imwe vertex, uye tinoita nhare mbiri dzekudzokorora: mune yekutanga tinoitora mukupindura, uye mune imwe tinotora vese vavakidzani vayo. Uku ndiko kwatinodaidza kuti kupatsanura (branching) pamwe nemheto iyi.
Kuwedzera kumwe chete kuchaitwa kuchirongwa ichi mundima inotevera.
Mazano ekuparadzanisa (brunching) mitemo
Ngatikurukurei nzira yekusarudza vertex iyo iyo kupatsanurwa kuchaitika.
Pfungwa huru ine makaro mupfungwa yealgorithmic: ngatitorei vertex yedhigirii yakakura uye tipatsanure pairi. Nei zvichiita sezviri nani? Nekuti mubazi rechipiri rekudzokorodza kufona isu tichabvisa akawanda vertices nenzira iyi. Unogona kuvimba negirafu diki rasara uye tinogona kushanda pariri nekukurumidza.
Iyi nzira, neyakatokurukurwa yakapusa kernelization maitiro, inozviratidza zvakanaka uye inogadzirisa mimwe miedzo yezviuru zvakati wandei muhukuru. Asi, semuenzaniso, haishande zvakanaka kune cubic girafu (kureva, magirafu ane dhigirii yega yega vertex matatu).
Pane imwe pfungwa yakavakirwa papfungwa iri nyore: kana girafu ikabviswa, dambudziko pazvikamu zvaro zvakabatana rinogona kugadziriswa zvakazvimirira, kubatanidza mhinduro kumagumo. Izvi, nenzira, idiki yakavimbiswa kugadziridzwa muchirongwa, iyo ichakurumidza kukurumidzira mhinduro: kare, munyaya iyi, takashandira chigadzirwa chenguva yekuverenga mhinduro dzezvikamu, asi ikozvino tinoshandira. sum. Uye kuti ukurumidze branching, unoda kushandura girafu rakabatanidzwa kuita rakabviswa.
Kuzviita sei? Kana pane chirevo chekutaura mugirafu, unofanirwa kurwa pairi. Nzvimbo yekutaura ndeye vertex zvekuti kana yabviswa, girafu inorasikirwa nekubatana kwayo. Ese mapoinzi ekusangana mugirafu anogona kuwanikwa uchishandisa classical algorithm munguva yemutsara. Iyi nzira inokurumidza kukurumidza kuita branching.
Kana chero yeakasarudzwa vertices yabviswa, girafu inopatsanurwa kuita zvinhu zvakabatana.
Tichaita izvi, asi tinoda zvimwe. Semuenzaniso, tsvaga madiki vertex akachekwa mugirafu uye kupatsanurwa pamwe chete nema vertices kubva mairi. Nzira inonyanya kushanda yandinoziva yekuwana iyo yakaderera yepasi rose vertex yekucheka ndeye kushandisa muti weGomori-Hu, unovakwa mune cubic nguva. MuPACE Dambudziko, saizi yakajairika yegirafu zviuru zvakati wandei. Mumamiriro ezvinhu aya, mabhiriyoni ekuvhiya anofanirwa kuitwa pane imwe neimwe vertex yemuti wekudzoka. Zvinoitika kuti hazvigoneke kugadzirisa dambudziko munguva yakatarwa.
Ngatiedzei kugadzirisa mhinduro. Iyo shoma vertex yakachekwa pakati peviri ye vertices inogona kuwanikwa nechero algorithm inogadzira kuyerera kwakanyanya. Unogona kuisiya kune network yakadaro , mukuita inoshanda nekukurumidza. Ndine fungidziro yekuti zvinokwanisika kuratidza fungidziro yenguva yekushandisa , izvo zvinotogamuchirwa.
Ndakaedza kakawanda kuti nditarise kucheka pakati pemapeya ezvisina kurongeka vertices uye kutora yakanyanya kuenzana. Nehurombo, izvi zvakaburitsa mhedzisiro isina kunaka mukuvhurika kwePACE Dambudziko kuyedzwa. Ndakaienzanisa nealgorithm inopatsanura ma vertices ehupamhi dhigirii, ndichivamhanyisa nekudzikamisa pakadzika kwekudzika. Algorithm kuyedza kutsvaga kuchekwa nenzira iyi yakasiya kumashure magirafu akakura. Izvi zvinokonzerwa nekuti kucheka kwakave kusina kuenzana zvikuru: kubvisa 5-10 vertices, zvaikwanisika kuparadzanisa 15-20 chete.
Izvo zvakakosha kuti ticherechedze kuti zvinyorwa nezve theoretically inokurumidza algorithms inoshandisa zvakanyanya hunyanzvi matekiniki ekusarudza vertices yekutsemura. Matekinoroji akadaro ane kuomesesa kwakanyanya uye kazhinji kusashanda zvakanaka maererano nenguva uye ndangariro. Handina kukwanisa kuziva izvo zvinotenderwa kuita.
Maitiro Okushandisa Mitemo Yekurerutsa
Tatova nemazano ekuita kernelization. Rega ndikuyeuchidze:
- Kana paine vertex iri yega, ibvise.
- Kana paine vertex yedhigirii 1, ibvise uye utore muvakidzani wayo mukupindura.
- Kana paine vertex yedegree kanenge k +1, dzosera.
Nemaviri ekutanga zvinhu zvese zvakajeka, neyechitatu pane imwe trick. Kana mudambudziko remakomiki pamusoro pebhawa takapihwa muganho wepamusoro we k, ipapo muPACE Dambudziko iwe unongoda kutsvaga vertex kavha yehudiki saizi. Uku ndiko kushandura kwakajairwa kweMatambudziko eKutsvaga kuita Matambudziko eSarudzo; kazhinji hapana mutsauko pakati pemhando mbiri dzezvinetso. Mukuita, kana isu tichinyora solver ye vertex inovhara dambudziko, panogona kuve nemusiyano. Somuenzaniso, semupfungwa yechitatu.
Kubva pakuona kwekuita, kune nzira mbiri dzekuenderera mberi. Nzira yekutanga inonzi Iterative Deepening. Zvakaita sezvizvi: tinogona kutanga nekumwe kumanikidzika kubva pazasi pamhinduro, tobva tamhanyisa algorithm yedu tichishandisa ichi chinomanikidza sechisungo pamhinduro kubva kumusoro, pasina kudzika mukudzokororwa pane ichi chinomanikidza. Kana isu tawana imwe mhinduro, inovimbiswa kuve yakakwana, zvikasadaro tinogona kuwedzera iyi muganhu neimwe uye kutanga zvakare.
Imwe nzira ndeyekuchengetedza imwe yazvino mhinduro yakanaka uye kutsvaga mhinduro diki, kushandura iyi parameter kana yawanikwa k nokuda kwekucheka kukuru kwemapazi asina kufanira mukutsvaga.
Mushure mekuita ongororo dzakati wandei dzehusiku, ndakagara pane musanganiswa weiyi nzira mbiri: kutanga, ndinomhanyisa algorithm yangu neimwe mhando yekugumira pakudzika kwekutsvaga (kuisarudza kuitira kuti itore nguva isingatarisike kana ichienzaniswa nemhinduro huru) uye shandisa yakanakisa. mhinduro inowanikwa semuganho wepamusoro kune mhinduro - ndiko kuti, kune chinhu chimwe chete k.
Vertices yedhigirii 2
Isu takabata nemavertices edhigirii 0 uye 1. Zvinoitika kuti izvi zvinogona kuitwa nemavertices edhigirii 2, asi izvi zvinoda mamwe mabasa akaomarara kubva pagirafu.
Kuti titsanangure izvi, isu tinoda neimwe nzira kudoma vertices. Ngatidaidze vertex yedegree 2 vertex v, uye vavakidzani vayo - vertices x ΠΈ y. Tevere tichava nemakesi maviri.
- When x ΠΈ y - vavakidzani. Ipapo unogona kupindura x ΠΈ yuye v delete. Hongu, kubva kune iyi yegonyo inoda kutorwa mavertices maviri, uye isu hatingarasikirwe kana tikatora. x ΠΈ y: pamwe vane vamwe vavakidzani, uye v Havasi pano.
- When x ΠΈ y - kwete vavakidzani. Zvadaro zvinonzi vertices nhatu dzose dzinogona kunamirwa mune imwe. Pfungwa ndeyokuti munyaya iyi pane mhinduro yakakwana, iyo yatinotora kana v, kana kuti mavertices maviri x ΠΈ y. Uyezve, munyaya yekutanga tichafanira kutora vavakidzani vose mukupindura x ΠΈ y, asi muchipiri hazvidikanwi. Izvi zvinonyatsoenderana nemakesi kana isu tisingatore iyo glued vertex mukupindura uye patinoita. Izvo zvinongoramba zvichingoona kuti muzviitiko zviviri izvi mhinduro kubva pakuvhiya kwakadaro inoderera neimwe.
Zvinokosha kucherechedza kuti nzira iyi yakaoma chaizvo kushandisa nemazvo mutsetse mutsara nguva. Gluing vertices ibasa rakaoma; iwe unofanirwa kutevedzera rondedzero yevavakidzani. Kana izvi zvikaitwa nekusangwarira, unogona kupedzisira uine asymptotically suboptimal yekumhanya nguva (semuenzaniso, kana iwe ukakopa yakawanda mipendero mushure mekunamatira yega yega). Ndakagadzika pakutsvaga nzira dzese kubva kumavertices edhigirii 2 uye nekuongorora boka rezviitiko zvakakosha, senge matenderedzwa kubva kune akadaro vertices kana kubva kune ese mavertices kunze kweimwe.
Pamusoro pezvo, zvinodikanwa kuti oparesheni iyi idzokororwe, kuitira kuti kana tadzoka kubva kudzokororo tinodzosera girafu kune yayo yekutanga. Kuti ndive nechokwadi cheizvi, handina kujekesa zvinyorwa zvemavheti akasanganiswa, uye ndakabva ndangoziva kuti ndeapi mapendero aifanira kuenda kupi. Uku kuita kwemagirafu kunodawo kurongeka, asi kunopa yakaringana mutsara nguva. Uye kune magirafu emakumi emakumi ezviuru emapendero, inokodzera mu processor cache, iyo inopa mabhenefiti makuru mukumhanya.
Linear kernel
Pakupedzisira, chikamu chinonakidza che kernel.
Kutanga, yeuka kuti mubipartite girafu iyo shoma vertex kavha inogona kuwanikwa uchishandisa . Kuti uite izvi, iwe unofanirwa kushandisa iyo algorithm kuitira kuti uwane iyo yakanyanya kuenderana ipapo, wobva washandisa theorem .
Pfungwa yemutsara kernel ndeiyi: kutanga tinobifurcate girafu, ndiko kuti, panzvimbo yevheti yega yega. v ngatiwedzere nhongonya mbiri ΠΈ , uye panzvimbo pomupendero mumwe nomumwe iwe -v ngatiwedzere mbabvu mbiri ΠΈ . Iyo girafu inozobuda ichava bipartite. Ngatitsvagei shoma vertex kavha mairi. Mamwe mavertices egirafu yepakutanga achasvika ikoko kaviri, mamwe kamwe chete, uye mamwe haambofi. Dzidziso inonzi Nemhauser-Trotter inoti pakadai munhu anogona kubvisa matinji asina kurova kana kamwe chete odzosa arova kaviri. Uyezve, anoti pane asara vertices (iwo anorova kamwe) iwe unofanirwa kutora kanenge hafu semhinduro.
Isu takangodzidza kusiya kwete kupfuura 2k peaks Chokwadi, kana mhinduro yasara iri hafu yemavertices ese, saka hapasisina mamwe mavertices akazara kupfuura 2k.
Apa ndakakwanisa kukanda nhanho kumberi. Zviripachena kuti kernel yakavakwa nenzira iyi inoenderana nekuti ndeupi rudzi rwechifukidziro chevertex chatakatora mubipartite graph. Ndinoda kutora imwe kuitira kuti huwandu hwema vertices asara hushoma. Kare, vaikwanisa kuita izvi nokufamba kwenguva . Ini ndakauya nekuitwa kweiyi algorithm panguva , saka, musimboti uyu unogona kutsvagwa mumagrafu emazana ezviuru zvema vertices padanho rega rega rebazi.
mugumisiro
Kudzidzira kunoratidza kuti mhinduro yangu inoshanda nemazvo pakuyedzwa kwemazana akati wandei vertices uye zviuru zvakati wandei. Mune miedzo yakadaro zvinokwanisika kutarisira kuti mhinduro ichawanikwa muhafu yeawa. Mukana wekuwana mhinduro munguva inogamuchirika, mumusimboti, unowedzera kana girafu iine nhamba yakakura yakakwana yedhigirii yepamusoro, semuenzaniso, dhigirii gumi nepamusoro.
Kuti vatore chikamu mumakwikwi, mhinduro dzaifanira kutumirwa kune . Tichitarisa neruzivo rwunopihwa ipapo , mhinduro yangu mumiyedzo yakavhurika inokwira yechitatu kubva makumi maviri, ine gap rakakura kubva yechipiri. Kuve akatendeseka zvachose, hazvina kunyatsojeka kuti zvigadziriso zvichaongororwa sei pamakwikwi pachawo: semuenzaniso, mhinduro yangu inopfuura miedzo shoma pane mhinduro munzvimbo yechina, asi pane iyo inopfuura, inoshanda nekukurumidza.
Mhedzisiro yebvunzo dzakavharwa ichazivikanwa muna Chikunguru XNUMX.
Source: www.habr.com