Képzésünk talán legérdekesebb része a kutatómunka. Az ötlet az, hogy még az egyetemen próbáld ki magad a választott irányba. Például a szoftverfejlesztés és a gépi tanulás területéről érkező hallgatók gyakran járnak kutatást végezni vállalatoknál (főleg JetBrains vagy Yandex, de nem csak).
Ebben a bejegyzésben a számítástechnikai projektemről fogok beszélni. Munkám részeként tanulmányoztam és gyakorlatba ültettem az egyik leghíresebb NP-nehéz probléma megoldásának megközelítéseit: csúcsfedő probléma.
Napjainkban nagyon gyorsan fejlődik az NP-kemény problémák érdekes megközelítése - a paraméterezett algoritmusok. Megpróbálom felgyorsítani, elmondok néhány egyszerű paraméterezett algoritmust, és leírok egy hatékony módszert, amely sokat segített. Eredményeimet a PACE Challenge versenyen mutattam be: nyílt tesztek eredménye alapján a megoldásom harmadik helyezést ér el, a végeredmény július 1-jén lesz ismert.
Magamról
A nevem Vaszilij Alferov, most fejezem be a harmadik évemet a Nemzeti Kutatóegyetem Közgazdaságtudományi Felsőiskoláján - Szentpéterváron. Iskolás korom óta érdekelnek az algoritmusok, amikor a 179. számú moszkvai iskolában tanultam, és sikeresen részt vettem számítástechnikai olimpiákon.
A paraméterezett algoritmusok véges számú szakembere lép be a bárba...
Példa a könyvből vett
Képzelje el, hogy Ön egy bár biztonsági őre egy kisvárosban. Minden pénteken a fél város eljön a bárodba pihenni, ami sok gondot okoz: ki kell dobnod a ripacskodó ügyfeleket a bárból, hogy megelőzd a verekedéseket. Végül elege lesz, és úgy dönt, hogy megelőző intézkedéseket tesz.
Mivel kicsi a városod, pontosan tudod, hogy melyik vendégpáros fog harcolni, ha együtt kötnek ki egy bárba. Van listája n emberek, akik ma este eljönnek a bárba. Úgy döntesz, hogy távol tartasz néhány városlakót a bártól anélkül, hogy bárki is összeveszne. Ugyanakkor a főnökei nem akarnak nyereséget veszíteni, és boldogtalanok lesznek, ha nem engednek többet k emberek.
Sajnos az Ön előtt álló probléma egy klasszikus NP-nehéz probléma. Lehet, hogy úgy ismered őt , vagy csúcsfedő problémaként. Az ilyen problémákra általában nincs olyan algoritmus, amely elfogadható időn belül működne. Pontosabban, a nem bizonyított és meglehetősen erős hipotézis, az ETH (Exponential Time Hypothesis) azt mondja, hogy ezt a problémát nem lehet időben megoldani. , vagyis a teljes keresésnél észrevehetően jobbat nem tudsz elképzelni. Tegyük fel például, hogy valaki bejön a bárjába n = 1000 Emberi. Ezután a teljes keresés lesz körülbelül a rendelkezésre álló lehetőségek közül - őrült mennyiség. Szerencsére a vezetősége határt szabott neked k = 10, így az ismétlendő kombinációk száma sokkal kisebb: tíz elemből álló részhalmazok száma . Ez jobb, de még egy erős klaszteren sem számítják bele egy napba.
Annak érdekében, hogy elkerülje a harc lehetőségét a bár látogatói közötti feszült viszonyban, távol kell tartania Bobot, Danielt és Fedort. Nincs olyan megoldás, amelyben csak ketten maradnak le.
Ez azt jelenti, hogy ideje engedni, és mindenkit beengedni? Tekintsünk más lehetőségeket. Nos, például nem lehet csak azokat beengedni, akik valószínűleg nagyon sok emberrel harcolnak. Ha valaki tud harcolni legalább k+1 egy másik személyt, akkor biztosan nem engedheti be – különben mindenkit kint kell tartania k+1 városlakók, akikkel harcolni tud, ami mindenképpen felzaklatja a vezetést.
Hadd dobj ki mindenkit, akit csak tudsz ezen elv szerint. Akkor mindenki más nem többel harcolhat k emberek. Kidobni őket k ember, semmi mást nem akadályozhatsz meg, mint konfliktusok. Ez azt jelenti, hogy ha több mint Ha egy személy legalább egy konfliktusban érintett, akkor biztosan nem akadályozhatja meg mindegyiket. Mivel természetesen teljesen konfliktusmentes embereket biztosan beenged, ezért kétszáz emberből minden tízes méretű részhalmazt végig kell mennie. Vannak kb , és ez a számú művelet már rendezhető a fürtön.
Ha nyugodtan el lehet fogadni azokat az egyéneket, akiknek egyáltalán nincs konfliktusa, akkor mi van azokkal, akik csak egy konfliktusban vesznek részt? Sőt, úgy is beengedhetik őket, hogy bezárják az ajtót ellenfelükre. Valóban, ha Alice csak Bobbal áll konfliktusban, akkor ha kiengedjük Alice-t kettejük közül, nem veszítünk: Bobnak lehetnek más konfliktusai, de Alice-nek biztosan nincsenek. Ráadásul semmi értelme, hogy ne engedjük be mindkettőnket. Az ilyen műveletek után nem marad több megoldatlan sorsú vendégek: nekünk csak konfliktusok, mindegyiknek két résztvevője van, és mindegyik legalább kettőben érintett. Tehát nincs más hátra, mint a rendezés opciók, ami egy laptopon nyugodtan fél napnak is tekinthető.
Valójában egyszerű érveléssel még vonzóbb feltételeket érhet el. Vedd figyelembe, hogy minden vitát mindenképpen meg kell oldanunk, vagyis minden ütköző párból válassz legalább egy olyan személyt, akit nem engedünk be. Tekintsük a következő algoritmust: vegyünk egy tetszőleges konfliktust, amelyből eltávolítjuk az egyik résztvevőt, és rekurzívan kezdjük a maradékból, majd eltávolítjuk a másikat, és szintén rekurzívan kezdjük. Mivel minden lépésnél kidobunk valakit, egy ilyen algoritmus rekurziós fája a mélység bináris fája k, tehát összességében az algoritmus működik Ahol n a csúcsok száma, és m - bordák száma. Példánkban ez körülbelül tízmillió, ami nem csak laptopon, hanem mobiltelefonon is a másodperc töredéke alatt kiszámolható.
A fenti példa egy példa paraméterezett algoritmus. A paraméterezett algoritmusok olyan algoritmusok, amelyek időben futnak f(k) poli(n)Ahol p - polinom, f egy tetszőleges kiszámítható függvény, és k - valamilyen paraméter, ami nagy valószínűséggel sokkal kisebb lesz, mint a probléma mérete.
Az algoritmus előtti összes érvelés példát ad kernelizálás a paraméterezett algoritmusok létrehozásának egyik általános technikája. A kernelizáció a probléma méretének csökkentése egy paraméter függvénye által korlátozott értékre. Az ebből eredő problémát gyakran kernelnek nevezik. Így a csúcsok fokaira vonatkozó egyszerű érveléssel a Vertex Cover probléma négyzetes magját kaptuk, a válasz méretével paraméterezve. Más beállítások is választhatók ehhez a feladathoz (például Vertex Cover Above LP), de erről a beállításról fogunk beszélni.
Pace Challenge
Verseny (The Parameterized Algorithms and Computational Experiments Challenge) 2015-ben született, hogy kapcsolatot teremtsen a paraméterezett algoritmusok és a számítási problémák megoldására a gyakorlatban alkalmazott megközelítések között. Az első három verseny egy grafikon faszélességének megállapítására irányult (), Steiner fát keresek () és olyan csúcskészlet keresése, amely ciklusokat vág (). Ebben az évben az egyik probléma, amiben kipróbálhatta magát, a fent leírt csúcsfedő probléma volt.
A verseny évről évre egyre népszerűbb. Ha hinni az előzetes adatoknak, idén 24 csapat vett részt a versenyen, amely egyedül oldotta meg a csúcsfedő feladatot. Érdemes megjegyezni, hogy a verseny nem több óráig tart, sőt nem is egy hétig, hanem több hónapig tart. A csapatoknak lehetőségük van a szakirodalom tanulmányozására, saját eredeti ötletük kidolgozására és annak megvalósítására. Ez a verseny lényegében egy kutatási projekt. A leghatékonyabb megoldások ötleteit és a nyertesek díjazását a konferenciával egy időben tartjuk (International Symposium on Parameterized and Exact Computation) a legnagyobb éves algoritmikus találkozó részeként Európában . Magáról a versenyről részletesebb információ a címen található , a korábbi évek eredményei pedig hazudnak .
Megoldási diagram
A csúcslefedési probléma megoldásához paraméterezett algoritmusokkal próbálkoztam. Általában két részből állnak: egyszerűsítési szabályokból (amelyek ideális esetben kernelizáláshoz vezetnek) és felosztási szabályokból. Az egyszerűsítési szabályok a bemenet polinomiális időben történő előfeldolgozása. Az ilyen szabályok alkalmazásának az a célja, hogy a problémát egy ezzel egyenértékű kisebb problémára redukálják. Az egyszerűsítési szabályok az algoritmus legdrágább része, és ennek a résznek az alkalmazása a teljes futási időt eredményezi egyszerű polinomiális idő helyett. Esetünkben a felosztási szabályok azon alapulnak, hogy minden csúcsra vagy azt, vagy a szomszédját kell válaszként venni.
Az általános séma a következő: alkalmazzuk az egyszerűsítési szabályokat, majd kiválasztunk egy csúcsot, és két rekurzív hívást végzünk: az elsőben válaszként fogadjuk, a másikban pedig az összes szomszédját. Ezt nevezzük e csúcs mentén hasadásnak (elágazásnak).
A következő bekezdésben pontosan egy kiegészítést teszünk ehhez a sémához.
Ötletek a felosztási (brunching) szabályokhoz
Beszéljük meg, hogyan válasszunk egy csúcsot, amely mentén a felosztás megtörténik.
A fő gondolat algoritmikus értelemben nagyon mohó: vegyünk egy maximális fokú csúcsot, és hasítsunk rajta. Miért tűnik jobbnak? Mert a rekurzív hívás második ágában sok csúcsot eltávolítunk így. Számíthat egy kis grafikonra, és gyorsan dolgozhatunk rajta.
Ez a megközelítés a már tárgyalt egyszerű kernelizációs technikákkal jól megmutatkozik, és megold néhány ezer csúcs méretű tesztet is. De például nem működik jól köbös gráfoknál (vagyis olyan gráfoknál, amelyeknek mindegyik csúcsának foka három).
Van egy másik ötlet is, amely egy meglehetősen egyszerű ötletre épül: ha a gráfot szétválasztjuk, a kapcsolódó komponensein a probléma önállóan is megoldható, a végén összevonva a válaszokat. Ez egyébként egy kis ígért módosítás a sémában, ami jelentősen felgyorsítja a megoldást: korábban ebben az esetben az idők szorzatára dolgoztunk a komponensek válaszainak számításakor, most viszont azon dolgozunk, hogy összege. Az elágazás felgyorsítása érdekében pedig egy összekapcsolt gráfot szétválasztottá kell alakítani.
Hogyan kell csinálni? Ha van artikulációs pont a grafikonon, akkor harcolni kell érte. Az artikulációs pont egy olyan csúcs, amelynek eltávolításakor a gráf elveszti kapcsolatát. A gráf összes csomópontja klasszikus algoritmussal lineáris időben megtalálható. Ez a megközelítés jelentősen felgyorsítja az elágazást.
Ha a kiválasztott csúcsok bármelyikét eltávolítjuk, a gráf összefüggő komponensekre válik szét.
Ezt megtesszük, de többet akarunk. Például keresse meg a kis csúcskivágásokat a gráfban, és válasszon ki belőle a csúcsok mentén. A leghatékonyabb módja annak, hogy megtaláljam a minimális globális csúcsvágást, egy Gomori-Hu fa használata, amely köbidőben épül fel. A PACE Challenge-ben a gráf tipikus mérete több ezer csúcs. Ebben a helyzetben több milliárd műveletet kell végrehajtani a rekurziós fa minden csúcsán. Kiderül, hogy egyszerűen lehetetlen megoldani a problémát a megadott időn belül.
Próbáljuk meg optimalizálni a megoldást. A csúcspárok közötti minimális csúcsvágás bármely olyan algoritmussal megtalálható, amely egy maximális áramlást konstruál. Beengedheti egy ilyen hálózatba , a gyakorlatban nagyon gyorsan működik. Az a gyanúm, hogy elméletileg be lehet bizonyítani az üzemidő becslését , ami már teljesen elfogadható.
Többször próbáltam vágásokat keresni a véletlen csúcspárok között, és a legkiegyensúlyozottabbat választani. Sajnos ez gyenge eredményeket hozott a nyílt PACE Challenge tesztelés során. Összehasonlítottam egy olyan algoritmussal, amely maximális fokú csúcsokat hasít fel, és a süllyedés mélységének korlátozásával futtatja őket. Egy algoritmus, amely így próbált vágást találni, nagyobb grafikonokat hagyott maga után. Ez annak köszönhető, hogy a vágások nagyon kiegyensúlyozatlannak bizonyultak: 5-10 csúcs eltávolítása után csak 15-20-at lehetett leválasztani.
Érdemes megjegyezni, hogy az elméletileg leggyorsabb algoritmusokról szóló cikkek sokkal fejlettebb technikákat alkalmaznak a csúcsok felosztáshoz való kiválasztására. Az ilyen technikák megvalósítása nagyon bonyolult, és gyakran gyenge teljesítményt nyújt az idő és a memória tekintetében. Nem tudtam beazonosítani azokat, amelyek teljesen elfogadhatóak a gyakorlatban.
Az egyszerűsítési szabályok alkalmazása
Már vannak ötleteink a kernelizálásra. Hadd emlékeztesselek:
- Ha van elszigetelt csúcs, törölje azt.
- Ha van 1-es fokú csúcs, távolítsuk el, és válaszul vegyük a szomszédját.
- Ha van legalább fokcsúcs k+1, Visszavonom.
Az első kettőnél minden világos, a harmadiknál egy trükk. Ha egy bárral kapcsolatos komikus feladatban megadtuk a felső határt k, akkor a PACE Challenge-ben már csak egy minimális méretű csúcsfedőt kell találni. Ez a keresési problémák tipikus átalakulása döntési problémákká; gyakran nincs különbség a két problématípus között. A gyakorlatban, ha a csúcslefedési feladathoz írunk egy megoldót, akkor lehet eltérés. Például, mint a harmadik pontban.
A megvalósítás szempontjából kétféleképpen lehet eljárni. Az első megközelítést iteratív elmélyülésnek hívják. Ez a következő: kiindulhatunk valamilyen ésszerű megszorítással alulról a válaszra, majd lefuttathatjuk az algoritmusunkat úgy, hogy ezt a megszorítást felülről a válaszra korlátozzuk, anélkül, hogy a rekurzióban ennél a kényszernél lejjebb mennénk. Ha valamilyen választ találtunk, az garantáltan optimális, ellenkező esetben ezt a határt megnövelhetjük eggyel, és újrakezdhetjük.
Egy másik megközelítés az aktuális optimális válasz tárolása, és egy kisebb válasz keresése, megváltoztatva ezt a paramétert, ha megtalálta k a felesleges ágak nagyobb levágásához a keresés során.
Több éjszakai kísérlet elvégzése után a két módszer kombinációja mellett döntöttem: először lefuttatom az algoritmusomat a keresési mélység valamilyen korlátozásával (úgy választom ki, hogy a fő megoldáshoz képest elhanyagolható időbe telik), és a legjobbat használom. megoldást a válasz felső határaként találták meg - vagyis ugyanarra k.
A 2. fokozat csúcsai
0 és 1 fokos csúcsokkal foglalkoztunk. Kiderült, hogy ez megtehető a 2-es fokú csúcsokkal, de ehhez bonyolultabb műveletekre lesz szükség a gráfból.
Ennek magyarázatához valahogy ki kell jelölnünk a csúcsokat. Nevezzünk egy 2. fokú csúcsot csúcsnak v, és szomszédai - csúcsok x и y. Ezután két esetünk lesz.
- Mikor x и y - szomszédok. Akkor lehet válaszolni x и yÉs v töröl. Valójában ebből a háromszögből legalább két csúcsot ki kell venni cserébe, és biztosan nem veszítünk, ha vesszük x и y: valószínűleg vannak más szomszédaik, és v Nincsenek itt.
- Mikor x и y - nem szomszédok. Ekkor ki van írva, hogy mindhárom csúcs egybe ragasztható. Az ötlet az, hogy ebben az esetben van egy optimális válasz, amelyben bármelyiket vesszük v, vagy mindkét csúcsot x и y. Sőt, az első esetben az összes szomszédot választ kell vennünk x и y, de a másodiknál nem szükséges. Ez pontosan megfelel azoknak az eseteknek, amikor nem vesszük válaszul a ragasztott csúcsot, és mikor vesszük. Csak annyit kell megjegyezni, hogy mindkét esetben az ilyen műveletből származó válasz eggyel csökken.
Érdemes megjegyezni, hogy ezt a megközelítést meglehetősen nehéz pontosan megvalósítani tisztességes lineáris időben. A csúcsok ragasztása összetett művelet, át kell másolnia a szomszédok listáját. Ha ezt hanyagul csinálják, akkor aszimptotikusan szuboptimális futási időhöz juthat (például ha sok élt másol le minden ragasztás után). Úgy döntöttem, hogy a 2. fokú csúcsokból egész útvonalakat keresek, és egy csomó speciális esetet elemzek, például az ilyen csúcsokból származó ciklusokat, vagy egy kivételével az összes ilyen csúcsból.
Ezenkívül szükséges, hogy ez a művelet reverzibilis legyen, hogy a rekurzióból visszatérve visszaállítsuk a gráfot az eredeti formájába. Ennek biztosítására nem töröltem az egyesített csúcsok éllistáit, és csak azt tudtam, hogy melyik élnek hova kell mennie. A grafikonok ilyen megvalósítása szintén pontosságot igényel, de tisztességes lineáris időt biztosít. A több tízezer éles grafikonok esetében pedig a processzor gyorsítótárába illeszkedik, ami nagy sebességelőnyt biztosít.
Lineáris kernel
Végül a kernel legérdekesebb része.
Először is emlékezzünk arra, hogy a bipartit gráfokban a minimális csúcsfedő a segítségével található meg . Ehhez az algoritmust kell használni hogy ott megtaláljuk a maximális egyezést, majd használjuk a tételt .
A lineáris kernel ötlete a következő: először kettéosztjuk a gráfot, azaz minden csúcs helyett v adjunk hozzá két csúcsot и , és az egyes élek helyett u - v adjunk hozzá két bordát и . Az eredményül kapott gráf kétrészes lesz. Keressük meg benne a minimális csúcsfedőt. Az eredeti gráf egyes csúcsai kétszer, mások csak egyszer, mások pedig soha. A Nemhauser-Trotter tétel kimondja, hogy ebben az esetben el lehet távolítani azokat a csúcsokat, amelyek még egyszer sem találtak el, és vissza lehet venni azokat, amelyek kétszer találtak. Sőt, azt mondja, hogy a fennmaradó csúcsok (azok, amelyek egyszer eltalálnak) legalább felét válasznak kell venni.
Most tanultuk meg, hogy nem hagyhatunk többet, mint 2k csúcsok Valójában, ha a maradék válasz legalább a fele az összes csúcsnak, akkor nincs több csúcs összesen, mint 2k.
Itt egy kis lépést tehettem előre. Jól látható, hogy az így megszerkesztett kernel attól függ, hogy milyen minimális csúcsfedőt vettünk a bipartit gráfban. Szeretnék venni egyet, hogy a maradék csúcsok száma minimális legyen. Korábban ezt csak időben tudták megtenni . Időközben kitaláltam ennek az algoritmusnak a megvalósítását , így ez a mag minden elágazási szakaszban több százezer csúcsból álló gráfokban kereshető.
Eredmény
A gyakorlat azt mutatja, hogy a megoldásom jól működik több száz csúcsból és több ezer élből álló teszteken. Az ilyen tesztek során arra számíthatunk, hogy fél óra múlva megoldást találnak. Annak a valószínűsége, hogy elfogadható időn belül választ találunk, elvileg növekszik, ha a gráfnak kellően sok magas fokú csúcsa van, például 10-es vagy magasabb.
A pályázaton való részvételhez a megoldásokat a címre kellett elküldeni . Az ott közölt információkból ítélve , megoldásom nyílt tesztekben a harmadik helyen áll a húsz közül, nagy különbséggel a másodiktól. Hogy őszinte legyek, nem egészen világos, hogy magán a versenyen hogyan értékelik a megoldásokat: például az én megoldásom kevesebb teszten megy át, mint a negyedik helyen álló, de a sikeresen gyorsabban működik.
A zárt tesztek eredményei július XNUMX-jén lesznek ismertek.
Forrás: will.com