Tutkimustyö on ehkä mielenkiintoisin osa koulutustamme. Ajatuksena on kokeilla itseäsi valitsemallasi suunnalla vielä yliopistossa. Esimerkiksi ohjelmistotekniikan ja koneoppimisen alan opiskelijat käyvät usein tutkimuksissa yrityksissä (lähinnä JetBrainsissa tai Yandexissä, mutta ei vain).
Tässä postauksessa kerron projektistani tietojenkäsittelytieteen alalla. Osana työtäni opiskelin ja toteutin lähestymistapoja yhden kuuluisimmista NP-kovista ongelmista: vertexin peittoongelma.
Nykyään erittäin nopeasti kehittyy mielenkiintoinen lähestymistapa NP-koviin ongelmiin - parametroidut algoritmit. Yritän saada sinut vauhtiin, kertoa sinulle yksinkertaisia parametroituja algoritmeja ja kuvailla yhtä tehokasta menetelmää, joka auttoi minua paljon. Esittelin tulokset PACE Challenge -kilpailussa: avoimien testien tulosten mukaan ratkaisuni on kolmas ja lopulliset tulokset selviävät 1. heinäkuuta.
Tietoja minusta
Nimeni on Vasily Alferov, olen nyt lopettamassa kolmatta vuotta Kansallisen tutkimusyliopiston kauppakorkeakoulussa - Pietarissa. Olen ollut kiinnostunut algoritmeista koulupäivistäni, jolloin opiskelin Moskovan koulussa nro 179 ja osallistuin menestyksekkäästi tietojenkäsittelytieteen olympialaisiin.
Rajallinen määrä parametroitujen algoritmien asiantuntijoita astuu baariin...
Esimerkki otettu kirjasta
Kuvittele, että olet baarin vartija pienessä kaupungissa. Joka perjantai puolet kaupungista tulee baariisi rentoutumaan, mikä aiheuttaa sinulle paljon vaivaa: sinun täytyy heittää riehakkaat asiakkaat ulos baarista estääksesi tappelut. Lopulta kyllästyt ja päätät ryhtyä ehkäiseviin toimiin.
Koska kaupunkisi on pieni, tiedät tarkalleen, mitkä asiakasparit todennäköisesti taistelevat, jos he päätyvät yhdessä baariin. Onko sinulla listaa n ihmisiä, jotka tulevat baariin tänä iltana. Päätät pitää jotkut kaupunkilaiset poissa baarista ilman, että kukaan joutuu riitaan. Samaan aikaan pomosi eivät halua menettää voittoja ja ovat tyytymättömiä, jos et anna enempää kuin k ihmisiä.
Valitettavasti edessäsi oleva ongelma on klassinen NP-kova ongelma. Saatat tuntea hänet nimellä , tai kärkipisteen peittoongelmana. Tällaisille ongelmille ei yleensä ole olemassa algoritmeja, jotka toimisivat hyväksyttävässä ajassa. Tarkemmin sanottuna todistamaton ja melko vahva hypoteesi ETH (Exponential Time Hypothesis) sanoo, että tätä ongelmaa ei voida ratkaista ajoissa , eli et voi ajatella mitään huomattavasti parempaa kuin täydellinen haku. Oletetaan esimerkiksi, että joku tulee baariisi n = 1000 Ihmisen. Sitten on täydellinen haku vaihtoehtoja, joita on suunnilleen - hullu määrä. Onneksi johtosi on antanut sinulle rajan k = 10, joten iteroitavien yhdistelmien määrä on paljon pienempi: kymmenen elementin osajoukkojen määrä on . Tämä on parempi, mutta sitä ei silti lasketa päiväksi edes tehokkaassa klusterissa.
Välttääksesi taistelun mahdollisuuden tässä baarin vierailijoiden välisissä kireissä suhteissa, sinun on pidettävä Bob, Daniel ja Fedor poissa. Ei ole ratkaisua, jossa vain kaksi jää jäljelle.
Tarkoittaako tämä, että on aika antaa periksi ja päästää kaikki sisään? Mietitään muita vaihtoehtoja. No, esimerkiksi, et voi päästää sisään vain niitä, jotka todennäköisesti taistelevat erittäin suuren määrän ihmisiä vastaan. Jos joku jaksaa taistella ainakin k+1 toiselle henkilölle, et todellakaan voi päästää häntä sisään - muuten joudut pitämään kaikki poissa k+1 kaupunkilaisia, joiden kanssa hän voi taistella, mikä varmasti järkyttää johtoa.
Heittäkää pois kaikki, jotka voitte tämän periaatteen mukaan. Sitten kaikki muut voivat taistella enintään k ihmiset. Heitä pois k mies, et voi estää muuta kuin konflikteja. Tämä tarkoittaa, että jos on enemmän kuin Jos henkilö on mukana ainakin yhdessä konfliktissa, et varmasti voi estää niitä kaikkia. Koska tietysti päästät sisään täysin konfliktittomia ihmisiä, sinun täytyy käydä läpi kaikki alajoukot, joiden koko on kymmenen kahdestasadasta ihmisestä. Niitä on noin , ja tämä määrä operaatioita voidaan jo selvittää klusterissa.
Jos voit turvallisesti ottaa henkilöitä, joilla ei ole lainkaan konfliktia, niin entä ne, jotka osallistuvat vain yhteen konfliktiin? Itse asiassa heidät voidaan päästää sisään myös sulkemalla ovi vastustajaltaan. Todellakin, jos Alice on ristiriidassa vain Bobin kanssa, niin jos päästämme Alicen ulos heistä kahdesta, emme häviä: Bobilla voi olla muita konflikteja, mutta Alicella ei todellakaan ole niitä. Lisäksi meillä ei ole mitään järkeä olla päästämättä meitä molempia sisään. Tällaisten toimenpiteiden jälkeen ei ole enää jäljellä vieraita, joilla on ratkaisematon kohtalo: meillä on vain konflikteja, joissa kussakin on kaksi osallistujaa ja jokaisessa vähintään kaksi. Joten ei jää muuta kuin lajitella vaihtoehtoja, joita voidaan helposti harkita puoli päivää kannettavalla tietokoneella.
Itse asiassa yksinkertaisella päättelyllä voit saavuttaa entistä houkuttelevampia olosuhteita. Huomaa, että meidän on ehdottomasti ratkaistava kaikki riidat, eli jokaisesta ristiriitaisesta parista on valittava vähintään yksi henkilö, jota emme päästä sisään. Tarkastellaan seuraavaa algoritmia: otetaan mikä tahansa ristiriita, josta poistamme yhden osallistujan ja aloitamme rekursiivisesti loppuosasta, poistamme sitten toisen ja aloitamme myös rekursiivisesti. Koska heitämme jonkun ulos joka askeleella, tällaisen algoritmin rekursiopuu on syvyyden binääripuu k, joten kaiken kaikkiaan algoritmi toimii Missä n on kärkien lukumäärä ja m - kylkiluiden lukumäärä. Esimerkissämme tämä on noin kymmenen miljoonaa, joka voidaan laskea sekunnin murto-osassa paitsi kannettavalla tietokoneella, myös matkapuhelimella.
Yllä oleva esimerkki on esimerkki parametrisoitu algoritmi. Parametriset algoritmit ovat algoritmeja, jotka suoritetaan ajassa f(k) poly(n)Missä p - polynomi, f on mielivaltainen laskettava funktio, ja k - jokin parametri, joka todennäköisesti on paljon pienempi kuin ongelman koko.
Kaikki tätä algoritmia edeltävä päättely antaa esimerkin kernelointi on yksi yleisistä tekniikoista parametroitujen algoritmien luomiseen. Kernelointi tarkoittaa ongelman koon pienentämistä parametrin funktion rajoittamaan arvoon. Tuloksena olevaa ongelmaa kutsutaan usein ytimeksi. Siten yksinkertaisella päättelyllä kärkiasteiden suhteen saimme Vertex Cover -ongelmalle neliöllisen ytimen, joka parametroitiin vastauksen koon mukaan. Voit valita tähän tehtävään muita asetuksia (kuten Vertex Cover Above LP), mutta tämä on asetus, josta keskustelemme.
Pace Challenge
kilpailu (The Parameterised Algorithms and Computational Experiments Challenge) syntyi vuonna 2015 luomaan yhteys parametroitujen algoritmien ja käytännössä laskentaongelmien ratkaisemiseen käytettävien lähestymistapojen välille. Kolme ensimmäistä kilpailua oli omistettu graafin puun leveyden löytämiseen (), etsii Steiner-puuta () ja etsitään kärkijoukkoa, joka leikkaa sykliä (). Tänä vuonna yksi niistä ongelmista, joissa voit kokeilla käsiäsi, oli yllä kuvattu huippupisteiden peittoongelma.
Kilpailun suosio kasvaa joka vuosi. Jos alustavia tietoja uskoo, niin tänä vuonna 24 joukkuetta osallistui kilpailuun, joka ratkaisi kärkipään peittoongelman yksin. On syytä huomata, että kilpailu ei kestä useita tunteja tai edes viikkoa, vaan useita kuukausia. Tiimeillä on mahdollisuus tutustua kirjallisuuteen, keksiä oma alkuperäinen idea ja yrittää toteuttaa sitä. Pohjimmiltaan tämä kilpailu on tutkimusprojekti. Konferenssin yhteydessä järjestetään ideoita tehokkaimmista ratkaisuista ja voittajien palkitsemisesta (International Symposium on Parameterized and Exact Computation) osana Euroopan suurinta vuotuista algoritmikokousta . Tarkempia tietoja itse kilpailusta löytyy osoitteesta , ja aikaisempien vuosien tulokset ovat .
Ratkaisukaavio
Vertex-peitto-ongelman ratkaisemiseksi yritin käyttää parametroituja algoritmeja. Ne koostuvat tyypillisesti kahdesta osasta: yksinkertaistamissäännöistä (jotka johtavat ihanteellisesti ytimeen) ja jakamissäännöistä. Yksinkertaistussäännöt ovat syötteen esikäsittelyä polynomiajassa. Tällaisten sääntöjen soveltamisen tarkoituksena on vähentää ongelma vastaavaksi pienemmäksi ongelmaksi. Yksinkertaistussäännöt ovat algoritmin kallein osa, ja tämän osan soveltaminen johtaa kokonaiskäyttöaikaan yksinkertaisen polynomiajan sijaan. Meidän tapauksessamme jakosäännöt perustuvat siihen, että jokaiselle kärkipisteelle on otettava joko se tai sen naapuri vastaukseksi.
Yleinen kaava on seuraava: sovellemme yksinkertaistamissääntöjä, valitsemme sitten jonkin huippupisteen ja teemme kaksi rekursiivista kutsua: ensimmäisessä otamme sen vastauksena ja toisessa otamme sen kaikki naapurit. Tätä kutsutaan jakamiseksi (haarautumiseksi) pitkin tätä kärkeä.
Tähän järjestelmään tehdään täsmälleen yksi lisäys seuraavassa kappaleessa.
Ideoita jakamiseen (brunssi) sääntöihin
Keskustellaan kuinka valita huippupiste, jota pitkin jako tapahtuu.
Pääidea on algoritmisessa mielessä hyvin ahne: otetaan maksimiasteen kärki ja jaetaan sitä pitkin. Miksi se näyttää paremmalta? Koska rekursiivisen kutsun toisessa haarassa poistamme tällä tavalla paljon kärkipisteitä. Voit luottaa siihen, että jäljellä on pieni kaavio, ja voimme käsitellä sitä nopeasti.
Tämä lähestymistapa, jo käsitellyillä yksinkertaisilla kernelointitekniikoilla, näyttää itsensä hyvin ja ratkaisee joitain useiden tuhansien pisteiden kokoisia testejä. Mutta esimerkiksi se ei toimi hyvin kuutiograafisille (eli kuvaajille, joiden kunkin kärjen aste on kolme).
On toinenkin ajatus, joka perustuu melko yksinkertaiseen ajatukseen: jos graafi irrotetaan, ongelma sen yhteydessä olevissa komponenteissa voidaan ratkaista itsenäisesti yhdistämällä vastaukset lopussa. Tämä on muuten pieni luvattu muutos kaavioon, joka nopeuttaa ratkaisua merkittävästi: aiemmin tässä tapauksessa työskentelimme komponenttien vasteiden laskennassa aikatulon puolesta, mutta nyt työskennellään summa. Ja nopeuttaaksesi haaroittumista, sinun on muutettava yhdistetty kaavio katkaistuksi.
Kuinka tehdä se? Jos kaaviossa on artikulaatiopiste, sinun on taisteltava sitä vastaan. Artikulaatiopiste on sellainen kärki, että kun se poistetaan, graafi menettää liitettävyytensä. Kaikki kaavion liitospisteet voidaan löytää klassisen algoritmin avulla lineaarisessa ajassa. Tämä lähestymistapa nopeuttaa merkittävästi haaroittumista.
Kun jokin valituista pisteistä poistetaan, graafi jaetaan yhdistetyiksi komponenteiksi.
Teemme tämän, mutta haluamme enemmän. Etsi esimerkiksi graafista pieniä kärkileikkauksia ja jaa siitä pisteitä pitkin. Tehokkain tapa, jonka tiedän löytää globaalin huippupisteen minimileikkaus, on käyttää Gomori-Hu-puuta, joka rakennetaan kuutioajassa. PACE Challenge -haasteessa graafin tyypillinen koko on useita tuhansia pisteitä. Tässä tilanteessa miljardeja operaatioita on suoritettava jokaisessa rekursiopuun kärjessä. Osoittautuu, että on yksinkertaisesti mahdotonta ratkaista ongelmaa määrätyssä ajassa.
Yritetään optimoida ratkaisu. Piikkiparin välisen minimipisteen leikkaus voidaan löytää millä tahansa algoritmilla, joka muodostaa maksimivirtauksen. Voit päästää sen tällaiseen verkkoon , käytännössä se toimii hyvin nopeasti. Epäilen, että toiminta-ajan arvio on teoriassa mahdollista todistaa , mikä on jo melko hyväksyttävää.
Yritin useita kertoja etsiä leikkauksia satunnaisten kärkiparien välillä ja ottaa tasapainoisimman. Valitettavasti tämä tuotti huonoja tuloksia avoimessa PACE Challenge -testauksessa. Vertasin sitä algoritmiin, joka jakaa maksimiasteen kärjet ja ajaen niitä laskeutumissyvyyden rajoituksella. Algoritmi, joka yrittää löytää leikkauksen tällä tavalla, jätti jälkeensä suurempia kuvaajia. Tämä johtuu siitä, että leikkaukset osoittautuivat erittäin epätasapainoisiksi: 5-10 kärjen poistamisen jälkeen oli mahdollista jakaa vain 15-20.
On syytä huomata, että teoreettisesti nopeimpia algoritmeja käsittelevissä artikkeleissa käytetään paljon kehittyneempiä tekniikoita kärkien valitsemiseen jakamista varten. Tällaisilla tekniikoilla on erittäin monimutkainen toteutus ja usein huono suorituskyky ajan ja muistin suhteen. En pystynyt tunnistamaan niitä, jotka ovat täysin hyväksyttäviä harjoitteluun.
Yksinkertaistussääntöjen soveltaminen
Meillä on jo ideoita kernelointiin. Haluan muistuttaa sinua:
- Jos on eristetty kärkipiste, poista se.
- Jos on asteen 1 kärki, poista se ja ota sen naapuri vastaukseksi.
- Jos on vähintään asteen kärki k+1, ota se takaisin.
Kahdella ensimmäisellä kaikki on selvää, kolmannella on yksi temppu. Jos meille annettiin baaria koskevassa sarjakuvassa yläraja k, niin PACE Challengessa sinun tarvitsee vain löytää minimikokoinen kärkikansi. Tämä on tyypillinen hakuongelmien muunnos päätösongelmiksi; usein näiden kahden ongelmatyypin välillä ei ole eroa. Käytännössä, jos kirjoitamme ratkaisijaa kärjen peittotehtävälle, siinä voi olla ero. Esimerkiksi, kuten kolmannessa kohdassa.
Toteutuksen kannalta on kaksi tapaa edetä. Ensimmäistä lähestymistapaa kutsutaan iteratiiviseksi syventämiseksi. Se on seuraava: voimme aloittaa jollain kohtuullisella rajoituksella vastauksen alhaalta ja suorittaa sitten algoritmimme käyttämällä tätä rajoitusta vastauksen rajoitteena ylhäältä, ilman että rekursio alenee tätä rajoitusta. Jos olemme löytäneet vastauksen, se on taatusti optimaalinen, muuten voimme nostaa tätä rajaa yhdellä ja aloittaa alusta.
Toinen tapa on tallentaa jokin nykyinen optimaalinen vastaus ja etsiä pienempi vastaus muuttamalla tätä parametria, kun se löytyy k tarpeettomien oksien suurempaa katkaisua etsinnässä.
Suoritettuani useita iltaisia kokeita päädyin näiden kahden menetelmän yhdistelmään: ensin suoritan algoritmini jonkinlaisella hakusyvyyden rajoituksella (valitsen sen niin, että se vie vähän aikaa pääratkaisuun verrattuna) ja käytän parasta. ratkaisu löytyy vastauksen ylärajaksi - eli samaan asiaan k.
Asteen 2 pisteet
Olemme käsitelleet asteen 0 ja 1 pisteitä. Osoittautuu, että tämä voidaan tehdä asteen 2 pisteillä, mutta tämä vaatii monimutkaisempia operaatioita graafista.
Tämän selittämiseksi meidän on jotenkin nimettävä kärjet. Kutsutaan asteen 2 kärkeä kärkipisteeksi v, ja sen naapurit - kärjet x и y. Seuraavaksi käsittelemme kaksi tapausta.
- Kun x и y - naapurit. Sitten voit vastata x и yJa v poistaa. Tästä kolmiosta on todellakin otettava vastineeksi vähintään kaksi kärkeä, emmekä varmasti häviä, jos otamme x и y: heillä on luultavasti muita naapureita ja v he eivät ole.
- Kun x и y - ei naapureita. Sitten todetaan, että kaikki kolme kärkeä voidaan liimata yhdeksi. Ajatuksena on, että tässä tapauksessa on optimaalinen vastaus, jossa otamme jommankumman v, tai molemmat kärjet x и y. Lisäksi ensimmäisessä tapauksessa meidän on otettava kaikki naapurit vastauksena x и y, mutta toisessa se ei ole välttämätöntä. Tämä vastaa täsmälleen niitä tapauksia, joissa emme ota liimattua kärkeä vastauksena ja milloin otamme. On vain huomattava, että molemmissa tapauksissa tällaisen toimenpiteen vaste pienenee yhdellä.
On syytä huomata, että tätä lähestymistapaa on melko vaikea toteuttaa tarkasti kohtuullisessa lineaarisessa ajassa. Huippupisteiden liimaus on monimutkainen toimenpide; sinun on kopioitava luettelot naapureista. Jos tämä tehdään huolimattomasti, voit päätyä asymptoottisesti epäoptimaaliseen ajoaikaan (esimerkiksi jos kopioit paljon reunoja jokaisen liimauksen jälkeen). Päädyin etsimään kokonaisia polkuja asteen 2 huipuista ja analysoimaan joukon erikoistapauksia, kuten sykliä sellaisista pisteistä tai kaikista sellaisista pisteistä yhtä lukuun ottamatta.
Lisäksi on välttämätöntä, että tämä operaatio on reversiibeli, jotta rekursiosta palatessa graafi palautetaan alkuperäiseen muotoonsa. Tämän varmistamiseksi en tyhjentänyt yhdistettyjen pisteiden reunaluetteloita, ja sitten tiesin vain, mitkä reunat pitivät mennä minne. Tämä kaavioiden toteutus vaatii myös tarkkuutta, mutta se tarjoaa reilun lineaarisen ajan. Ja useiden kymmenien tuhansien reunojen kuvaajille se sopii prosessorin välimuistiin, mikä antaa suuria etuja nopeudessa.
Lineaarinen ydin
Lopuksi ytimen mielenkiintoisin osa.
Aluksi on muistettava, että kaksiosaisissa graafisissa huippupisteiden minimipeite löytyy käyttämällä . Tätä varten sinun on käytettävä algoritmia löytääkseen sieltä maksimivastaavuuden ja käyttääkseen sitten lausetta .
Lineaarisen ytimen idea on tämä: ensin kahtiaamme graafin eli kunkin kärjen sijasta v lisätään kaksi huippua и , ja jokaisen reunan sijaan u - v lisätään kaksi kylkiluuta и . Tuloksena oleva graafi on kaksiosainen. Etsitään siitä minimipisteen peite. Jotkut alkuperäisen graafin kärjet pääsevät sinne kahdesti, jotkut vain kerran ja jotkut ei koskaan. Nemhauser-Trotter -lause sanoo, että tässä tapauksessa voidaan poistaa pisteitä, jotka eivät osuneet kertaakaan, ja ottaa takaisin ne, jotka osuivat kahdesti. Lisäksi hän sanoo, että jäljellä olevista pisteistä (niistä, jotka osuivat kerran) sinun on otettava vastauksena vähintään puolet.
Olemme juuri oppineet jättämään enintään 2k huiput Todellakin, jos lopun vastaus on vähintään puolet kaikista pisteistä, niin pisteitä ei ole enempää kuin 2k.
Tässä pääsin ottamaan pienen askeleen eteenpäin. On selvää, että tällä tavalla rakennettu ydin riippuu siitä, millaisen minimaalisen kärkipeitteen otimme kaksiosaiseen graafiin. Haluaisin ottaa yhden niin, että jäljellä olevien kärkien määrä on minimaalinen. Aiemmin he pystyivät tekemään tämän vain ajoissa . Keksin aikanaan tämän algoritmin toteutuksen , joten tätä ydintä voidaan etsiä satojen tuhansien kärkien graafista kussakin haarautumisvaiheessa.
Tulos
Käytäntö osoittaa, että ratkaisuni toimii hyvin useiden sadan kärjen ja useiden tuhansien reunojen testeissä. Tällaisissa testeissä on täysin mahdollista odottaa, että ratkaisu löydetään puolessa tunnissa. Todennäköisyys löytää vastaus hyväksyttävässä ajassa periaatteessa kasvaa, jos graafissa on riittävän suuri määrä korkean asteen pisteitä, esimerkiksi aste 10 tai korkeampi.
Kilpailuun osallistumiseksi ratkaisut piti lähettää osoitteeseen . Siellä esitetyistä tiedoista päätellen , ratkaisuni avoimissa testeissä sijoittuu kolmanneksi kahdestakymmenestä suurella erolla toisesta. Rehellisesti sanottuna ei ole täysin selvää, miten ratkaisuja arvostellaan itse kilpailussa: esimerkiksi ratkaisuni läpäisee vähemmän testejä kuin neljännen sijan ratkaisu, mutta läpäisevillä se toimii nopeammin.
Suljettujen testien tulokset selviävät XNUMX. heinäkuuta.
Lähde: will.com