Rannsóknarvinna er kannski áhugaverðasti hluti þjálfunar okkar. Hugmyndin er að reyna sjálfan þig í þá átt sem þú velur meðan þú ert enn í háskóla. Til dæmis fara nemendur frá sviðum hugbúnaðarverkfræði og vélanáms oft til að gera rannsóknir í fyrirtækjum (aðallega JetBrains eða Yandex, en ekki bara).
Í þessari færslu mun ég tala um verkefnið mitt í tölvunarfræði. Sem hluti af starfi mínu lærði ég og setti í verk aðferðir til að leysa eitt af frægustu NP-harða vandamálunum: hornpunktsþekjuvandamál.
Nú á dögum er áhugaverð nálgun á NP-hörð vandamál að þróast mjög hratt - reiknirit með færibreytum. Ég mun reyna að hraða þér, segja þér nokkur einföld reiknirit með færibreytum og lýsa einni öflugri aðferð sem hjálpaði mér mikið. Ég kynnti niðurstöður mínar í PACE Challenge keppninni: Samkvæmt niðurstöðum opinna prófana er lausnin mín í þriðja sæti og lokaniðurstöður verða ljósar 1. júlí.
Um mig
Ég heiti Vasily Alferov, ég er núna að ljúka þriðja ári við National Research University Higher School of Economics - St. Petersburg. Ég hef haft áhuga á reikniritum frá skóladögum mínum, þegar ég lærði í Moskvuskóla nr. 179 og tók þátt í tölvunarfræðiólympíuleikum með góðum árangri.
Endanlegur fjöldi sérfræðinga í reikniritum með færibreytum kemur inn á stikuna...
Dæmi tekið úr bókinni
Ímyndaðu þér að þú sért baröryggisvörður í litlum bæ. Á hverjum föstudegi kemur hálf borgin á barinn þinn til að slaka á, sem veldur þér miklum vandræðum: þú þarft að henda ruddalegum viðskiptavinum út af barnum til að koma í veg fyrir slagsmál. Að lokum fær maður nóg og ákveður að grípa til fyrirbyggjandi aðgerða.
Þar sem borgin þín er lítil þá veistu nákvæmlega hvaða verndarapör eru líkleg til að berjast ef þau lenda saman á bar. Ertu með lista yfir n fólk sem kemur á barinn í kvöld. Þú ákveður að halda einhverjum bæjarbúum frá barnum án þess að nokkur lendi í átökum. Á sama tíma vilja yfirmenn þínir ekki tapa hagnaði og verða óánægðir ef þú leyfir ekki meira en k fólk.
Því miður er vandamálið á undan þér klassískt NP-hart vandamál. Þú gætir þekkt hana sem , eða sem hornpunktsþekjuvandamál. Fyrir slík vandamál, í almennu tilviki, eru engin reiknirit sem virka á viðunandi tíma. Til að vera nákvæmur segir hin ósannaða og nokkuð sterka tilgáta ETH (Exponential Time Hypothesis) að ekki sé hægt að leysa þetta vandamál í tíma , það er, þú getur ekki hugsað um neitt áberandi betra en fullkomna leit. Segjum til dæmis að einhver ætli að koma á barinn þinn n = 1000 Mannlegur. Þá verður fullkomin leit valkostir sem eru um það bil - geggjað magn. Sem betur fer hafa stjórnendur þínir gefið þér takmörk k = 10, þannig að fjöldi samsetninga sem þú þarft að endurtaka yfir er miklu minni: fjöldi undirmengi tíu þátta er . Þetta er betra, en það verður samt ekki talið á einum degi jafnvel á öflugum klasa.
Til að útiloka möguleikann á slagsmálum í þessari uppsetningu á þvinguðum samskiptum gesta á barnum þarftu að halda Bob, Daniel og Fedor frá. Það er engin lausn þar sem aðeins tveir verða skildir eftir.
Þýðir þetta að það sé kominn tími til að gefa eftir og hleypa öllum inn? Við skulum íhuga aðra valkosti. Jæja, til dæmis, þú getur ekki hleypt aðeins inn þeim sem eru líklegir til að berjast við mjög mikinn fjölda fólks. Ef einhver getur barist að minnsta kosti við k+1 annarri manneskju, þá geturðu örugglega ekki hleypt honum inn - annars verður þú að halda öllum úti k+1 bæjarbúa, sem hann getur barist við, sem mun örugglega koma forystunni í uppnám.
Leyfðu þér að henda öllum út sem þú gætir samkvæmt þessari reglu. Þá geta allir aðrir barist með ekki meira en k fólk. Að henda þeim út k maður, þú getur ekkert komið í veg fyrir meira en átök. Þetta þýðir að ef það er meira en Ef einstaklingur tekur þátt í að minnsta kosti einum átökum, þá geturðu örugglega ekki komið í veg fyrir þá alla. Þar sem þú munt örugglega hleypa fólki inn sem er algjörlega óáreittur, þú þarft að fara í gegnum öll undirmengi af stærð tíu af tvö hundruð manns. Það eru u.þ.b , og nú þegar er hægt að flokka þennan fjölda aðgerða á klasanum.
Ef þú getur örugglega tekið einstaklinga sem ekki eiga í neinum átökum, hvað þá með þá sem taka þátt í aðeins einum átökum? Reyndar er líka hægt að hleypa þeim inn með því að loka hurðinni á andstæðingnum. Reyndar, ef Alice er aðeins í átökum við Bob, þá munum við ekki tapa, ef við hleypum Alice út úr þeim tveimur: Bob gæti átt í öðrum átökum, en Alice hefur þau sannarlega ekki. Þar að auki, það þýðir ekkert fyrir okkur að hleypa okkur ekki báðum inn. Eftir slíkar aðgerðir er ekkert meira eftir gestir með óráðin örlög: við höfum aðeins átök, hver með tvo þátttakendur og hver þátttakandi í að minnsta kosti tveimur. Þannig að það eina sem er eftir er að redda þessu valmöguleikar, sem geta hæglega talist hálfur dagur á fartölvu.
Í raun, með einföldum rökum geturðu náð enn aðlaðandi skilyrðum. Athugaðu að við þurfum örugglega að leysa öll deilur, það er að velja úr hverju pari sem stangast á, að minnsta kosti einn mann sem við hleypum ekki inn. Við skulum íhuga eftirfarandi reiknirit: tökum hvaða átök sem er, þar sem við fjarlægjum einn þátttakanda og byrjum endurtekið á afganginum, fjarlægðum síðan hinn og byrjum einnig endurtekið. Þar sem við hendum einhverjum út í hverju skrefi, þá er endurkomutré slíks reiknirit tvíundartré af dýpt k, þannig að í heildina virkar reikniritið inn hvar n er fjöldi hornpunkta, og m - fjöldi rifbeina. Í okkar dæmi eru þetta um tíu milljónir, sem hægt er að reikna út á sekúndubroti, ekki bara á fartölvu, heldur jafnvel í farsíma.
Dæmið hér að ofan er dæmi breytu reiknirit. Parametrisized algrím eru reiknirit sem keyra í tíma f(k) fjöl(n)hvar p - margliða, f er handahófskennd reiknanleg fall, og k - einhver færibreyta, sem mun hugsanlega vera miklu minni en stærð vandamálsins.
Öll rök fyrir þessari reiknirit gefa dæmi kjarnavæðingu er ein af almennu aðferðunum til að búa til reiknirit með færibreytum. Kernelization er minnkun vandamálastærðarinnar í gildi sem takmarkast af fall af færibreytu. Vandamálið sem myndast er oft kallað kjarna. Þannig, með einföldum rökstuðningi um gráður hornpunkta, fengum við ferningskjarna fyrir Vertex Cover vandamálið, færibreytt eftir stærð svarsins. Það eru aðrir valkostir sem hægt er að velja fyrir þetta verkefni (til dæmis Vertex Cover Above LP), en þetta er valkosturinn sem við munum ræða.
Pace Challenge
Samkeppni (The Parameterized Algorithms and Computational Experiments Challenge) var fædd árið 2015 til að koma á tengingu milli breytugreindra reiknirita og aðferða sem notaðar eru í reynd til að leysa reiknivandamál. Fyrstu þrjár keppnirnar voru helgaðar því að finna trjábreidd línurits (), að leita að Steiner tré () og leita að mengi hornpunkta sem skera hringrás (). Á þessu ári var eitt af vandamálunum sem þú gætir reynt fyrir þér í hornpunktsþekjuvandamálinu sem lýst er hér að ofan.
Keppnin nýtur vinsælda með hverju ári. Ef þú trúir bráðabirgðagögnum, í ár tóku 24 lið þátt í keppninni til að leysa vandamálið með hornpunktaþekju eingöngu. Þess má geta að keppnin tekur ekki nokkra klukkutíma eða jafnvel viku, heldur nokkra mánuði. Teymi gefst kostur á að kynna sér bókmenntir, koma með sína eigin frumhugmynd og reyna að hrinda henni í framkvæmd. Í meginatriðum er þessi keppni rannsóknarverkefni. Hugmyndir um árangursríkustu lausnir og verðlaun vinningshafa verða haldnar í tengslum við ráðstefnuna (International Symposium on Parameterized and Exact Computation) sem hluti af stærsta árlega algrímifundi í Evrópu . Nánari upplýsingar um keppnina sjálfa má finna á , og niðurstöður fyrri ára liggja .
Skýringarmynd lausna
Til að leysa hornpunktsþekjuvandamálið reyndi ég að nota breytu reiknirit. Þær samanstanda venjulega af tveimur hlutum: einföldunarreglum (sem helst leiða til kjarnavæðingar) og skiptingarreglur. Einföldunarreglur eru forvinnsla á inntakinu í margliða tíma. Tilgangurinn með beitingu slíkra reglna er að minnka vandann niður í jafnmikið minna vandamál. Einföldunarreglur eru dýrasti hluti reikniritsins og að beita þessum hluta leiðir til heildar keyrslutíma í stað einfalds margliða tíma. Í okkar tilviki eru skiptingarreglurnar byggðar á því að fyrir hvern hornpunkt þarf að taka annað hvort hann eða nágranna hans sem svar.
Almenna kerfið er þetta: við beitum einföldunarreglunum, veljum síðan einhvern hornpunkt og gerum tvö endurkvæm köll: í því fyrra tökum við það sem svar og í hinu tökum við alla nágranna þess. Þetta er það sem við köllum klofning (kvísun) meðfram þessum hornpunkti.
Nákvæmlega ein viðbót verður bætt við þetta kerfi í næstu málsgrein.
Hugmyndir um að skipta (brunching) reglum
Við skulum ræða hvernig á að velja hornpunkt þar sem skiptingin mun eiga sér stað.
Meginhugmyndin er mjög gráðug í algóritmískum skilningi: tökum hámarks hornpunkt og skiptum eftir því. Hvers vegna virðist það betra? Vegna þess að í annarri grein endurkvæma kallsins munum við fjarlægja mikið af hornpunktum á þennan hátt. Þú getur treyst á að lítið graf sé eftir og við getum unnið í því fljótt.
Þessi nálgun, með einföldum kjarnatækni sem þegar hefur verið rædd, sýnir sig vel og leysir nokkur próf sem eru nokkur þúsund hornpunktar að stærð. En, til dæmis, það virkar ekki vel fyrir rúmlínurit (þ.e. línurit þar sem gráðu hvers hornpunkts er þrjú).
Það er önnur hugmynd sem byggir á frekar einfaldri hugmynd: ef grafið er aftengt er hægt að leysa vandamálið á tengdum hlutum þess sjálfstætt og sameina svörin í lokin. Þetta er, við the vegur, lítil lofað breyting á kerfinu, sem mun flýta verulega fyrir lausninni: áður, í þessu tilfelli, unnum við að afurð tímans til að reikna út svör íhlutanna, en nú vinnum við fyrir summan. Og til að flýta fyrir greiningu þarftu að breyta tengdu línuriti í ótengd.
Hvernig á að gera það? Ef það er liður í línuritinu þarftu að berjast við hann. Liðpunktur er hornpunktur þannig að þegar grafið er fjarlægt missir það tengingu sína. Hægt er að finna alla tengipunkta á línuriti með því að nota klassískt reiknirit í línulegum tíma. Þessi nálgun flýtir verulega fyrir greiningu.
Þegar einhver af völdum hornpunktum er fjarlægður mun grafið skiptast í tengda hluti.
Við munum gera þetta, en við viljum meira. Til dæmis, leitaðu að litlum hornpunktaskurðum í línuritinu og skiptu meðfram hornpunktunum frá því. Skilvirkasta leiðin sem ég veit til að finna lágmarksskurð á heimshorninu er að nota Gomori-Hu tré, sem er byggt á rúmtíma. Í PACE Challenge er dæmigerð grafastærð nokkur þúsund hornpunktar. Við þessar aðstæður þarf að framkvæma milljarða aðgerða á hverjum hornpunkti endurkomutrésins. Það kemur í ljós að það er einfaldlega ómögulegt að leysa vandamálið á tilsettum tíma.
Við skulum reyna að fínstilla lausnina. Lágmarks hornpunktaskerðingu milli hornpunktapars er hægt að finna með hvaða reiknirit sem er sem smíðar hámarksflæði. Þú getur hleypt því inn á slíkt net , í reynd virkar það mjög fljótt. Ég hef grun um að fræðilega sé hægt að sanna áætlun um rekstrartímann , sem er nú þegar alveg ásættanlegt.
Ég reyndi nokkrum sinnum að leita að skurðum á milli para af tilviljunarkenndum hornpunktum og taka þann sem er mest jafnvægi. Því miður skilaði þetta lélegum árangri í opnum PACE Challenge prófunum. Ég bar það saman við reiknirit sem skipti hornpunktum af hámarksgráðu, keyrir þá með takmörkun á dýpt niðurkomu. Reiknirit sem reynir að finna skurð á þennan hátt skildi eftir sig stærri línurit. Þetta er vegna þess að niðurskurðurinn reyndist vera mjög ójafnvægi: eftir að hafa fjarlægt 5-10 hornpunkta var aðeins hægt að skipta 15-20.
Það er athyglisvert að greinar um fræðilega hröðustu reiknirit nota mun fullkomnari tækni til að velja hornpunkta til skiptingar. Slík tækni hefur mjög flókna útfærslu og oft lélega frammistöðu hvað varðar tíma og minni. Ég gat ekki bent á þá sem eru alveg ásættanlegir fyrir æfingar.
Hvernig á að beita einföldunarreglum
Við höfum þegar hugmyndir um kjarnavæðingu. Leyfðu mér að minna þig á:
- Ef það er einangrað hornpunktur skaltu eyða því.
- Ef það er hornpunktur af gráðu 1, fjarlægðu það og taktu nágranna hans sem svar.
- Ef það er hornpunktur að minnsta kosti k+1, Taktu það til baka.
Með fyrstu tveimur er allt á hreinu, með því þriðja er eitt bragð. Ef í grínisti vandamál um bar við fengum efri mörk á k, þá í PACE áskoruninni þarftu bara að finna hornpunktshlíf af lágmarksstærð. Þetta er dæmigerð umbreyting á leitarvandamálum í ákvörðunarvandamál; oft er enginn munur á þessum tveimur tegundum vandamála. Í reynd, ef við erum að skrifa leysi fyrir hornpunktsþekjuvandann, gæti verið munur. Til dæmis eins og í þriðja lið.
Frá útfærslusjónarmiði eru tvær leiðir færar. Fyrsta aðferðin er kölluð Iterative Deepening. Það er sem hér segir: við getum byrjað með einhverri skynsamlegri þvingun að neðan á svarinu og keyrt síðan reiknirit okkar með því að nota þessa þvingun sem þvingun á svarið að ofan, án þess að fara lægra í endurkomu en þessa þvingun. Ef við höfum fundið eitthvert svar, þá er það tryggt að það sé ákjósanlegt, annars getum við hækkað þessi mörk um eitt og byrjað aftur.
Önnur aðferð er að geyma eitthvað núverandi ákjósanlegt svar og leita að smærra svari, breyta þessari færibreytu þegar hún er fundin k fyrir meiri klippingu á óþarfa greinum í leitinni.
Eftir að hafa gert nokkrar tilraunir seint á kvöldin ákvað ég að blanda af þessum tveimur aðferðum: Í fyrsta lagi keyri ég reikniritið mitt með einhverri takmörkun á leitardýptinni (vel það þannig að það taki óverulegan tíma miðað við aðallausnina) og nota þá bestu lausn fundin sem efri mörk svarsins - það er að segja við það sama k.
Hönpunktar gráðu 2
Við höfum tekist á við hornpunkta 0 og 1. Það kemur í ljós að þetta er hægt að gera með hornpunktum 2, en þetta mun krefjast flóknari aðgerða af línuritinu.
Til að útskýra þetta þurfum við einhvern veginn að tilgreina hornpunktana. Köllum hornpunkt af 2 gráðu hornpunkt v, og nágranna þess - hornpunkta x и y. Næst munum við hafa tvö mál.
- Þegar x и y - nágrannar. Þá geturðu svarað x и yOg v eyða. Reyndar, frá þessum þríhyrningi þarf að taka að minnsta kosti tvo hornpunkta í staðinn, og við munum örugglega ekki tapa ef við tökum x и y: þeir eiga líklega aðra nágranna, og v þeir eru ekki.
- Þegar x и y - ekki nágrannar. Þá er tekið fram að hægt sé að líma alla þrjá hornpunkta í einn. Hugmyndin er sú að í þessu tilfelli sé ákjósanlegt svar, þar sem við tökum annað hvort v, eða báða hornpunktana x и y. Þar að auki, í fyrra tilvikinu verðum við að taka alla nágranna til að bregðast við x и y, en í seinni er það ekki nauðsynlegt. Þetta samsvarar nákvæmlega þeim tilvikum þegar við tökum ekki límda hornpunktinn sem svar og þegar við gerum það. Það er aðeins að taka fram að í báðum tilfellum minnkar svörun við slíkri aðgerð um eitt.
Það er athyglisvert að það er frekar erfitt að útfæra þessa nálgun nákvæmlega á sanngjörnum línulegum tíma. Að líma hornpunkta er flókin aðgerð; þú þarft að afrita lista yfir nágranna. Ef þetta er gert óvarlega geturðu endað með einkennalausan óákjósanlegan hlauptíma (til dæmis ef þú afritar margar brúnir eftir hverja límingu). Ég sætti mig við að finna heilu leiðirnar frá hornpunktum 2. stigs og greina fullt af sérstökum tilfellum, eins og hringrás frá slíkum hornpunktum eða frá öllum slíkum hornpunktum nema einum.
Að auki er nauðsynlegt að þessi aðgerð sé afturkræf, þannig að þegar við snúum aftur frá endurtekningu endurheimtum við grafið í upprunalegt form. Til að tryggja þetta hreinsaði ég ekki kantlistana yfir sameinuðu hornpunktana, svo ég vissi bara hvaða brúnir fóru hvar. Þessi útfærsla á línuritum krefst einnig nákvæmni, en hún veitir sanngjarnan línulegan tíma. Og fyrir línurit af nokkrum tugum þúsunda brúna, passar það inn í skyndiminni örgjörva, sem gefur mikla yfirburði í hraða.
Línulegur kjarni
Að lokum, áhugaverðasti hluti kjarnans.
Til að byrja með, mundu að í tvíhliða línuritum er hægt að finna lágmarkshlífina með því að nota . Til að gera þetta þarftu að nota reikniritið til að finna hámarks samsvörun þar og notaðu síðan setninguna .
Hugmyndin um línulegan kjarna er þessi: fyrst deildum við línuritinu, það er í stað hvers hornpunkts v bætum við tveimur toppum и , og í staðinn fyrir hverja brún u - v bætum við tveimur rifjum и . Grafið sem myndast verður tvíþætt. Við skulum finna lágmarkshlífina í því. Sumir hornpunktar upprunalega línuritsins munu komast þangað tvisvar, sumir aðeins einu sinni og aðrir aldrei. Nemhauser-Trotter setningin segir að í þessu tilviki megi fjarlægja hornpunkta sem slógu ekki einu sinni og taka aftur þá sem slógu tvisvar. Þar að auki segir hún að af þeim hornpunktum sem eftir eru (þeir sem hittu einu sinni) þurfir þú að taka að minnsta kosti helming sem svar.
Við höfum bara lært að fara ekki meira en 2k tinda Reyndar, ef afgangurinn svarar að minnsta kosti helmingur allra hornpunkta, þá eru ekki fleiri hornpunktar samtals en 2k.
Hér gat ég tekið smá skref fram á við. Það er ljóst að kjarninn sem er smíðaður á þennan hátt fer eftir því hvers konar lágmarkshjúp við tókum í tvíhliða línuritinu. Mig langar að taka einn þannig að fjöldi hornpunkta sem eftir eru sé í lágmarki. Áður gátu þeir gert þetta aðeins í tæka tíð . Ég kom með útfærslu á þessu reikniriti á sínum tíma , þannig er hægt að leita að þessum kjarna í línuritum af hundruðum þúsunda hornpunkta á hverju greiningarstigi.
Niðurstaðan
Æfingin sýnir að lausnin mín virkar vel á prófum með nokkur hundruð hornpunkta og nokkur þúsund brúnir. Í slíkum prófum er alveg hægt að búast við að lausn finnist eftir hálftíma. Líkurnar á að finna svar á ásættanlegum tíma aukast í grundvallaratriðum ef línuritið hefur nægilega marga hornpunkta af mikilli gráðu, til dæmis gráðu 10 og hærri.
Til að taka þátt í keppninni þurfti að senda lausnir á . Miðað við þær upplýsingar sem þar koma fram , lausn mín í opnum prófum er í þriðja sæti af tuttugu, með miklu bili frá öðru. Ef ég á að vera alveg heiðarlegur er ekki alveg ljóst hvernig lausnir verða metnar í keppninni sjálfri: til dæmis stenst lausnin mín færri próf en lausnin í fjórða sæti, en á þeim sem standast virkar hún hraðar.
Niðurstöður lokaðra prófa liggja fyrir XNUMX. júlí.
Heimild: www.habr.com