Teadustöö on võib-olla meie koolituse kõige huvitavam osa. Mõte seisneb selles, et proovite end valitud suunas veel ülikooli ajal. Näiteks tarkvaratehnika ja masinõppe valdkondade tudengid käivad sageli ettevõtetes (peamiselt JetBrainsis või Yandexis, aga mitte ainult) uurimistööd tegemas.
Selles postituses räägin oma projektist arvutiteaduses. Osana oma tööst õppisin ja rakendasin praktikas lähenemisviise ühe kuulsaima NP-raske probleemi lahendamiseks: tipu katmise probleem.
Tänapäeval areneb väga kiiresti huvitav lähenemine NP-rasketele probleemidele – parameetritega algoritmid. Püüan teid kurssi viia, räägin teile lihtsatest parameetritega algoritmidest ja kirjeldan ühte võimsat meetodit, mis mind palju aitas. Esitasin oma tulemusi PACE Challenge võistlusel: avatud testide tulemuste järgi saavutab minu lahendus kolmanda koha ning lõplikud tulemused selguvad 1. juulil.
Minust
Minu nimi on Vassili Alferov, lõpetan praegu kolmandat aastat Peterburi riiklikus teadusülikooli kõrgemas majanduskoolis. Algoritmid on mind huvitanud juba kooliajast, kui õppisin Moskva koolis nr 179 ja osalesin edukalt informaatikaolümpiaadidel.
Ribale siseneb piiratud arv parameetritega algoritmide spetsialiste...
Näide võetud raamatust
Kujutage ette, et olete väikelinna baari turvamees. Igal reedel tuleb pool linna sinu baari puhkama, mis tekitab sulle palju tüli: tülide ärahoidmiseks tuleb baarist välja visata käratsevad kliendid. Lõpuks tüdinete ja otsustate võtta ennetavaid meetmeid.
Kuna teie linn on väike, teate täpselt, millised patroonide paarid tõenäoliselt kaklevad, kui nad koos baari satuvad. Kas teil on nimekiri n inimesed, kes täna õhtul baari tulevad. Otsustad mõned linnainimesed baarist eemale hoida, ilma et keegi tülli läheks. Samal ajal ei taha teie ülemused kasumit kaotada ja on õnnetud, kui te ei lase rohkem kui k inimesed.
Kahjuks on teie ees olev probleem klassikaline NP-raske probleem. Võib-olla tunnete teda kui , või tippude katmise probleemina. Selliste probleemide puhul üldiselt pole algoritme, mis töötavad vastuvõetava aja jooksul. Kui täpne olla, siis tõestamata ja üsna tugev hüpotees ETH (Exponential Time Hypothesis) ütleb, et seda probleemi ei saa õigeaegselt lahendada , see tähendab, et te ei suuda mõelda midagi märgatavalt paremat kui täielik otsing. Oletame näiteks, et keegi tuleb teie baari n = 1000 Inimene. Siis toimub täielik otsing valikuid, mis on ligikaudu olemas - hull summa. Õnneks on teie juhtkond andnud teile piiri k = 10 XNUMX XNUMX, seega on kombinatsioonide arv, mida peate kordama, palju väiksem: kümne elemendi alamhulkade arv on . See on parem, kuid seda ei arvestata päevaga isegi võimsas klastris.
Kakluse võimaluse välistamiseks sellises baarikülastajate pingeliste suhete konfiguratsioonis peate Bobi, Danieli ja Fedori eemal hoidma. Ei ole lahendust, kus maha jäävad vaid kaks.
Kas see tähendab, et on aeg järele anda ja kõik sisse lasta? Kaaluge muid võimalusi. Noh, näiteks ei saa sisse lasta ainult neid, kes tõenäoliselt võitlevad väga paljude inimestega. Kui keegi suudab vähemalt võidelda k+1 teisele inimesele, siis kindlasti ei saa te teda sisse lasta – muidu peate kõik eemale hoidma k+1 linnarahvas, kellega ta saab tülitseda, mis kindlasti juhtkonna pahaseks ajab.
Laske teil selle põhimõtte kohaselt välja visata kõik, kes saate. Siis saavad kõik teised võidelda mitte rohkemaga kui k inimesed. Nende väljaviskamine k mees, sa ei saa ennetada midagi enamat kui konfliktid. See tähendab, et kui on rohkem kui Kui inimene on seotud vähemalt ühes konfliktis, siis kindlasti ei saa te neid kõiki ära hoida. Kuna loomulikult lasete kindlasti sisse täiesti konfliktivabasid inimesi, peate läbima kõik alamhulgad, mille suurus on kümme kahesajast inimesest. Neid on ligikaudu , ja selle arvu toiminguid saab juba klastris sorteerida.
Kui võite julgelt võtta inimesi, kellel pole üldse konflikti, siis kuidas on lood nendega, kes osalevad ainult ühes konfliktis? Tegelikult saab neid sisse lasta ka siis, kui nad vastase ees ukse sulgevad. Tõepoolest, kui Alice on konfliktis ainult Bobiga, siis kui me Alice'i kahest välja laseme, me ei kaota: Bobil võib olla muid konflikte, kuid Alice'il neid kindlasti ei ole. Pealegi pole meil mõtet meid mõlemaid sisse lasta. Pärast selliseid toiminguid ei jää enam lahendamata saatusega külalised: meil on ainult konfliktid, millest igaühes on kaks osalejat ja igaüks on seotud vähemalt kahega. Seega jääb üle vaid sorteerida valikuid, mida saab hõlpsasti pidada pooleks päevaks sülearvutiga.
Tegelikult saate lihtsa arutluskäiguga saavutada veelgi atraktiivsemad tingimused. Pane tähele, et kõik vaidlused tuleb kindlasti lahendada ehk igast konfliktis olevast paarist tuleb valida vähemalt üks inimene, keda me sisse ei lase. Vaatleme järgmist algoritmi: võtame suvalise konflikti, millest eemaldame ühe osaleja ja alustame rekursiivselt ülejäänud osast, seejärel eemaldame teise ja alustame samuti rekursiivselt. Kuna me viskame igal sammul kellegi välja, on sellise algoritmi rekursioonipuuks sügavuse kahendpuu k, seega kokkuvõttes algoritm töötab Kus n on tippude arv ja m - ribide arv. Meie näites on see umbes kümme miljonit, mida saab sekundi murdosaga välja arvutada mitte ainult sülearvutis, vaid isegi mobiiltelefonis.
Ülaltoodud näide on näide parameetritega algoritm. Parameetrilised algoritmid on algoritmid, mis töötavad ajas f(k) polü(n)Kus p - polünoom, f on suvaline arvutatav funktsioon ja k - mõni parameeter, mis suure tõenäosusega on probleemi suurusest palju väiksem.
Kõik arutluskäigud enne seda algoritmi annavad näite kerneliseerimine on üks üldisi parameetritega algoritmide loomise tehnikaid. Kerneliseerimine on probleemi suuruse vähendamine väärtuseni, mis on piiratud parameetri funktsiooniga. Sellest tulenevat probleemi nimetatakse sageli tuumaks. Nii saime tippude astmete üle lihtsa arutlemise teel Vertex Cover'i ülesande ruuttuuma, mille parameetrid on määratud vastuse suurusega. Selle ülesande jaoks saate valida ka teisi seadeid (nt Vertex Cover Above LP), kuid see on seade, mida me arutame.
Tempo väljakutse
Konkurents (The Parameterized Algorithms and Computational Experiments Challenge) sündis 2015. aastal, et luua seos parametriseeritud algoritmide ja praktikas arvutusprobleemide lahendamiseks kasutatavate lähenemisviiside vahel. Esimesed kolm võistlust olid pühendatud graafiku puu laiuse leidmisele (), otsin Steineri puud () ja otsides tippude komplekti, mis lõikab tsükleid (). Sel aastal oli üheks probleemiks, milles sai kätt proovida, ülalkirjeldatud tipu katmise probleem.
Võistlus kogub iga aastaga populaarsust. Kui esialgseid andmeid uskuda, siis ainuüksi tipu katmise probleemi lahendamiseks osales tänavu 24 võistkonda. Tasub teada, et võistlus ei kesta mitu tundi ega isegi nädalat, vaid mitu kuud. Võistkondadel on võimalus tutvuda kirjandusega, tulla välja oma algse ideega ja proovida seda ellu viia. Sisuliselt on see konkurss uurimistöö. Ideed efektiivseimateks lahendusteks ja võitjate autasustamine toimub koos konverentsiga (Rahvusvaheline Parameterized and Exact Computation sümpoosion) osana Euroopa suurimast iga-aastasest algoritmilise kohtumisest . Täpsemat infot konkursi enda kohta leiab aadressilt , ja eelmiste aastate tulemused valetavad .
Lahendusskeem
Tippude katmise probleemi lahendamiseks proovisin kasutada parameetritega algoritme. Tavaliselt koosnevad need kahest osast: lihtsustamisreeglid (mis ideaaljuhul viivad kerneliseerimiseni) ja poolitusreeglid. Lihtsustusreeglid on sisendi eeltöötlus polünoomilises ajas. Selliste reeglite rakendamise eesmärk on taandada probleem samaväärseks väiksemaks probleemiks. Lihtsustamisreeglid on algoritmi kõige kallim osa ja selle osa rakendamine toob kaasa kogu tööaja lihtsa polünoomaja asemel. Meie puhul põhinevad jagamisreeglid sellel, et iga tipu jaoks tuleb vastuseks võtta kas see või selle naaber.
Üldine skeem on järgmine: rakendame lihtsustusreegleid, siis valime mõne tipu ja teeme kaks rekursiivset väljakutset: esimeses võtame selle vastuseks ja teises võtame kõik selle naabrid. Seda me nimetame poolitamiseks (hargnemiseks) piki seda tippu.
Järgmises lõigus tehakse sellele skeemile täpselt üks täiendus.
Ideid poolitamise (brunchimise) reeglite jaoks
Arutame, kuidas valida tipp, mida mööda poolitamine toimub.
Põhiidee on algoritmilises mõttes väga ahne: võtame maksimaalse astme tipu ja jagame seda mööda. Miks see parem tundub? Sest rekursiivse kõne teises harus eemaldame sel viisil palju tippe. Võite loota, et alles jääb väike graafik ja me saame sellega kiiresti töötada.
See lähenemine koos juba käsitletud lihtsate kerneliseerimistehnikatega näitab end hästi ja lahendab mõned mitme tuhande tipu suurused testid. Aga näiteks kuupgraafide puhul (st graafikute puhul, mille iga tipu aste on kolm) see hästi ei tööta.
On veel üks idee, mis põhineb üsna lihtsal ideel: kui graafik on lahti ühendatud, saab selle ühendatud komponentide probleemi lahendada iseseisvalt, kombineerides vastused lõpus. See on muide väike lubatud muudatus skeemis, mis kiirendab oluliselt lahendust: varem töötasime antud juhul komponentide vastuste arvutamisel aegade korrutise nimel, kuid nüüd töötame selle nimel, et summa. Ja hargnemise kiirendamiseks peate ühendatud graafiku muutma lahtiühendatuks.
Kuidas seda teha? Kui graafikul on liigenduspunkt, peate selle nimel võitlema. Liigestuspunkt on selline tipp, mille eemaldamisel kaotab graafik ühenduvuse. Kõik graafiku ristmikupunktid on võimalik leida klassikalise algoritmi abil lineaarses ajas. Selline lähenemine kiirendab oluliselt hargnemist.
Kui mõni valitud tippudest eemaldatakse, jagatakse graafik ühendatud komponentideks.
Me teeme seda, kuid tahame rohkem. Näiteks otsige graafikult väikseid tippude lõikeid ja lõigake sellest mööda tippe. Kõige tõhusam viis, mida ma tean minimaalse globaalse tipu lõike leidmiseks, on kasutada Gomori-Hu puud, mis on ehitatud kuupajaga. PACE Challenge'is on tüüpiline graafi suurus mitu tuhat tippu. Sellises olukorras tuleb rekursioonipuu igas tipus teha miljardeid toiminguid. Selgub, et probleemi on lihtsalt võimatu ettenähtud aja jooksul lahendada.
Proovime lahendust optimeerida. Tippude paari vahelise minimaalse tipulõike saab leida mis tahes algoritmiga, mis konstrueerib maksimaalse voolu. Saate selle sellisesse võrku lasta , praktikas töötab see väga kiiresti. Mul on kahtlus, et teoreetiliselt on võimalik tõestada arvestust tööaja kohta , mis on juba üsna vastuvõetav.
Proovisin mitu korda otsida lõikeid juhuslike tippude paaride vahel ja võtta kõige tasakaalustatum. Kahjuks andis see avatud PACE Challenge testimises kehvad tulemused. Võrdlesin seda algoritmiga, mis jagab maksimaalse astme tipud, käitades neid laskumissügavuse piiranguga. Algoritm, mis üritas sel viisil lõiget leida, jättis suuremad graafikud maha. Selle põhjuseks on asjaolu, et lõiked osutusid väga tasakaalustamata: pärast 5-10 tipu eemaldamist oli võimalik eraldada ainult 15-20.
Väärib märkimist, et teoreetiliselt kiireimaid algoritme käsitlevates artiklites kasutatakse poolitamiseks tippude valimiseks palju arenenumaid tehnikaid. Sellistel tehnikatel on väga keeruline teostus ja sageli kehv jõudlus aja ja mälu osas. Ma ei suutnud tuvastada neid, mis on praktikas üsna vastuvõetavad.
Kuidas rakendada lihtsustusreegleid
Meil on juba ideid kerneliseerimiseks. Lubage mul teile meelde tuletada:
- Kui on isoleeritud tipp, kustutage see.
- Kui on olemas 1. astme tipp, eemaldage see ja võtke vastuseks selle naaber.
- Kui on vähemalt astme tipp k+1, võtma tagasi.
Kahe esimesega on kõik selge, kolmandaga on üks nipp. Kui koomilises probleemis baari kohta anti meile ülempiir k, siis PACE Challenge'is tuleb lihtsalt leida minimaalse suurusega tipukate. See on tüüpiline otsinguprobleemide ümberkujundamine otsustusprobleemideks; sageli pole kahe tüüpi probleemide vahel vahet. Praktikas, kui kirjutame tipu katva ülesande lahendaja, võib erinevus olla. Näiteks nagu kolmandas punktis.
Rakendamise seisukohast on edasiminekuks kaks võimalust. Esimest lähenemist nimetatakse iteratiivseks süvenemiseks. See on järgmine: saame alustada vastusest mõne mõistliku piiranguga altpoolt ja seejärel käivitada oma algoritm, kasutades seda piirangut vastuse piiranguna ülalt, ilma et rekursioon oleks sellest piirangust madalamal. Kui oleme mingi vastuse leidnud, on see garanteeritult optimaalne, vastasel juhul võime seda limiiti ühe võrra suurendada ja uuesti alustada.
Teine võimalus on salvestada mõni praegune optimaalne vastus ja otsida väiksemat vastust, muutes seda parameetrit leidmisel k ebavajalike okste suuremaks lõikamiseks otsingul.
Pärast mitme igaõhtuse katse läbiviimist otsustasin nende kahe meetodi kombinatsiooni kasuks: esiteks käivitan oma algoritmi, mis piirab otsingusügavust (valin selle nii, et see võtab põhilahendusega võrreldes vähe aega) ja kasutan parimat. lahendus leitud ülempiirina vastusele - see tähendab samale asjale k.
2. astme tipud
Oleme käsitlenud 0 ja 1 astme tippe. Selgub, et seda saab teha 2. astme tippudega, kuid see nõuab graafilt keerukamaid tehteid.
Selle selgitamiseks peame tipud kuidagi määrama. Nimetame 2. astme tippu tipuks v, ja selle naabrid - tipud x и y. Järgmisena käsitleme kahte juhtumit.
- Millal x и y - naabrid. Siis saab vastata x и yJa v kustutada. Tõepoolest, sellest kolmnurgast tuleb vastutasuks võtta vähemalt kaks tippu ja me kindlasti ei kaota, kui võtame x и y: ilmselt on neil teisi naabreid ja v Neid pole siin.
- Millal x и y - mitte naabrid. Siis öeldakse, et kõik kolm tippu saab üheks liimida. Idee seisneb selles, et sel juhul on optimaalne vastus, mille puhul me võtame kumbagi v, või mõlemad tipud x и y. Veelgi enam, esimesel juhul peame vastuseks võtma kõik naabrid x и y, kuid teises pole see vajalik. See vastab täpselt juhtudele, kui me ei võta vastuseks liimitud tippu ja millal me seda teeme. Jääb vaid märkida, et mõlemal juhul väheneb sellise toimingu vastus ühe võrra.
Väärib märkimist, et seda lähenemist on üsna raske täpselt rakendada õiglase lineaarse aja jooksul. Tippude liimimine on keeruline toiming, peate kopeerima naabrite loendid. Kui seda teha hooletult, võib tulemuseks olla asümptootiliselt ebaoptimaalne tööaeg (näiteks kui kopeerite pärast iga liimimist palju servi). Otsustasin leida terved teed 2. astme tippudest ja analüüsida hunnikut erijuhtumeid, näiteks tsükleid sellistest tippudest või kõigist sellistest tippudest peale ühe.
Lisaks on vajalik, et see tehe oleks pööratav, et rekursioonilt naastes taastaksime graafiku algsel kujul. Selle tagamiseks ei tühjendanud ma liidetud tippude servaloendeid ja siis teadsin lihtsalt, millised servad peavad kuhugi minema. See graafikute rakendamine nõuab ka täpsust, kuid see annab õiglase lineaarse aja. Ja mitmekümne tuhande servaga graafikute puhul mahub see protsessori vahemällu, mis annab kiiruses suuri eeliseid.
Lineaarne tuum
Lõpuks kerneli kõige huvitavam osa.
Alustuseks tuletage meelde, et kahepoolsetes graafides saab minimaalse tipukatte leida kasutades . Selleks peate kasutama algoritmi et leida seal maksimaalne sobivus ja seejärel kasutada teoreemi .
Lineaarse tuuma idee on järgmine: kõigepealt jagame graafiku kaheks, st iga tipu asemel v lisame kaks tippu и , ja iga serva asemel u - v lisame kaks ribi и . Saadud graafik on kahepoolne. Leiame sellest minimaalse tipukatte. Mõned algse graafi tipud jõuavad sinna kaks korda, mõned ainult üks kord ja mõned mitte kunagi. Nemhauseri-Trotteri teoreem ütleb, et sel juhul saab eemaldada tipud, mis ei tabanud isegi üks kord, ja võtta tagasi need, mis tabasid kaks korda. Veelgi enam, ta ütleb, et ülejäänud tippudest (need, mis tabasid üks kord) peate võtma vastuseks vähemalt poole.
Oleme just õppinud lahkuma mitte rohkem kui 2k tipud Tõepoolest, kui ülejäänud vastus on vähemalt pool kõigist tippudest, siis pole tippe kokku rohkem kui 2k.
Siin sain teha väikese sammu edasi. On selge, et sel viisil konstrueeritud tuum sõltub sellest, millise minimaalse tipukatte me kahepoolses graafis võtsime. Tahaks ühe võtta, et allesjäänud tippude arv oleks minimaalne. Varem suutsid nad seda teha ainult õigel ajal . Ma mõtlesin selle algoritmi teostuse õigel ajal välja , seega saab seda tuuma otsida sadade tuhandete tippude graafikutest igas hargnemise etapis.
Tulemus
Praktika näitab, et minu lahendus töötab hästi mitmesaja tipu ja mitme tuhande servaga testides. Selliste testide puhul on täiesti võimalik eeldada, et poole tunniga leitakse lahendus. Vastuse leidmise tõenäosus vastuvõetava aja jooksul põhimõtteliselt suureneb, kui graafil on piisavalt palju kõrge astme tippe, näiteks aste 10 ja kõrgem.
Konkursil osalemiseks tuli lahendused saata aadressile . Otsustades seal esitatud teabe järgi , on minu lahendus avatud testides kahekümnest kolmandal kohal, suure vahega teisest. Kui päris aus olla, siis pole päris selge, kuidas konkursil endal lahendusi hinnatakse: näiteks minu lahendus läbib vähem teste kui neljanda koha lahendus, kuid läbinutel töötab see kiiremini.
Kinniste testide tulemused selguvad XNUMX. juulil.
Allikas: www.habr.com