Hogyan lehet NP-nehezen megoldható feladatokat paraméterezett algoritmusokkal megoldani

A tudományos kutatás talán a legizgalmasabb része a tanulmányainknak. Az ötlet az, hogy még az egyetemen próbáljuk ki magunkat a választott irányban. Például a Software Engineering és Machine Learning szakos hallgatók gyakran végeznek kutatási projekteket különböző cégeknél (főként a JetBrainsnél vagy a Yandexnél, de nem csak ott).

Ebben a bejegyzésben a Computer Science irányú projektemről fogok beszélni. A munka keretében megvizsgáltam és gyakorlatba ültettem a megoldások megközelítéseit az egyik legismertebb NP-nehéz feladatban: a csúcsborítással kapcsolatos feladatban.

Jelenleg rendkívül gyorsan fejlődik egy érdekes megközelítés az NP-nehéz problémákhoz — a paraméterezett algoritmusok. Megpróbálom bevezetni önöket a témába, mesélni néhány egyszerű paraméterezett algoritmusról, és egy hatékony módszert bemutatni, amely nagyon segített nekem. Az eredményeimet a PACE Challenge versenyen mutattam be: a nyílt tesztek eredményei szerint a megoldásom a harmadik helyen áll, és a végső eredményekre július 1-jén derül fény.

Rólam

Vasiliy Alferov vagyok, jelenleg a harmadik évet végzem a HSE - Szentpétervári Egyetemen. Az algoritmusok iránti érdeklődésem még iskolás koromban kezdődött, amikor a moszkvai 179. iskolába jártam, és sikeresen részt vettem informatikai versenyeken.

Véges számú szakértő a paraméterezett algoritmusokról bemegy a bárba...

A példa a könyvből származik «Parameterized algorithms»

Képzelje el, hogy ön a bár biztonsági őre egy kisvárosban. Minden pénteken a város fele a bárjába jön lazítani, ami sok gondot okoz önnek: ki kell dobnia a rekedtes látogatókat, hogy elkerülje a verekedéseket. Végül már eleged van, és úgy döntesz, hogy megelőző intézkedéseket teszel.

Mivel a város kicsi, pontosan tudja, hogy kik azok a látogatók, akik nagy valószínűséggel össze fognak verekedni, ha együtt kerülnek a bárba. Van egy listája n emberekről, akik ma este a bárba jönnek. Úgy dönt, hogy nem enged be bizonyos városbelieket, úgy, hogy senki se verekedjen meg. Közben a főnöke nem szeretne profitot veszíteni, és elégedetlen lesz, ha nem enged be több mint k embert.

Sajnos a feladat, amely előtt áll, klasszikus NP-nehéz feladat. Talán ismeri ezt mint Vertex Cover, vagyis a csúcsborítással kapcsolatos feladat. Az ilyen feladatokra általánosságban nem ismertek olyan algoritmusok, amelyek elfogadható idő alatt működnek. Pontosan megfogalmazva, a nem bizonyított és meglehetősen erős ETH (Exponenciális Időhipotézis) azt állítja, hogy ezt a feladatot nem lehet megoldani , vagyis hogy nem létezik szignifikánsan jobb megoldás, mint a teljes keresés. Például, tegyük fel, hogy a bárba n = 1000 ember készül érkezni. Akkor a teljes keresés kukucskálásra — őrült sok. Szerencsére, az irányítás korlátozást állított fel Ön számára k = 10, így a kombinációk száma sokkal kevesebb: tíz elem részhalmazainak száma . Ez már jobb, de még mindig nem lehet nap alatt kiszámolni még egy erőteljes klaszteren sem.

Annak érdekében, hogy kizárjuk a verekedés lehetőségét a látogatók közötti ilyen feszültséges konfiguáció esetén, Bobot, Danielt és Fyodorot nem szabad beengedni. Olyan megoldás, amelyben csak ketten maradnak kinn, nem létezik.

Jelenti ez, hogy fel kell adnunk és be kell engednünk mindenkit? Vizsgáljunk meg más lehetőségeket. Például, talán nem engedhetnénk be csak azokat, akik valószínűleg sok emberrel fognak verekedni. Ha valaki legalább k + 1 másik emberrel viaskodhat, akkor őt biztosan nem szabad beengedni — különben minden olyan k + 1 városit ki kell zárnunk, akivel összeütközésbe léphet, ami már biztosan felbosszantja az irányítást.

Tegyük fel, hogy eltávolította az összes olyan embert, akit csak tudott, ezen elv alapján. Akkor a többiek legfeljebb k emberekkel fognak viaskodni. Ha közülük k embert kiszór, akkor legfeljebb konfliktust tud megelőzni. Tehát, ha több mint ember részese bármely konfliktusnak, akkor biztosan nem tudja megelőzni mindet. Mivel nyilvánvaló, hogy a teljesen konfliktusmentes embereket biztosan be fogja engedni, ezért át kell nézni az összes tíz elemű részhalmazt a kétszáz emberből. Ezek körülbelül , és ezt a műveletszámot már meg lehet dolgozni egy klaszteren.

Ha biztonságosan be tudunk engedni teljesen konfliktusmentes személyeket, akkor mit mondhatunk azokkal, akik csak egy konfliktusban vesznek részt? Valójában őket is be lehet engedni, ha bezárjuk a kaput az ellenfelük előtt. Igaz, ha Alice csak Bobbal konfliktál, ha közülük Alice-t engedjük be, nem veszítünk: Bobnak lehetnek más konfliktusai, míg Alice-nak biztosan nincsenek. Különösen értelmetlen nem engedni be őket kettesével. Ilyen műveletek után nem marad több vendég megoldatlan sorssal: összesen konfliktusunk van, mindegyikben két résztvevővel, és mindenki legalább kettőben részt vesz. Tehát csak annyit kell átvizsgálni, hogy variációt, ami egy fél napra elegendő lehet egy laptopon.

Valójában egyszerű érvelésekkel még vonzóbb feltételeket is elérhetünk. Vegyük észre, hogy mindenképpen meg kell oldanunk minden vitát, tehát minden konfliktáló párból legalább egy embert ki kell választanunk, akit nem engedünk be. Vegyünk egy algoritmust: vegyünk egy konfliktust, amelyből eltávolítunk egy résztvevőt, és rekurzívan folytatjuk a maradékkal, majd távolítsuk el a másikat, és szintén rekurzívan folytatjuk. Mivel minden lépésben valakit eltávolítunk, az ilyen algoritmus rekurziós fája bináris fa mélysége k, ezért az algoritmus összességében , ahol n — a csúcsok száma, és m — az élek száma. A mi példánk szerint ez körülbelül tíz millió, ami néhány másodperc alatt kiszámítható nemcsak egy laptopon, de még egy mobiltelefonon is.

A fent említett példa egy parametrikus algoritmus. A parametrikus algoritmusok olyan algoritmusok, amelyek f(k) poly(n), ahol p — polinom, f — tetszőleges számítható függvény, és k — valamilyen paraméter, amely lehet, hogy sokkal kisebb, mint a feladat mérete.

Minden eddigi érvelés a kernelizációra vezet. — az egyik általános technika a paraméterezett algoritmusok létrehozására. A kernelizáció a feladat méretének csökkentése egy paramétertől függő értékre. A kapott feladatot gyakran a kernel néven nevezik. Így, egyszerű érveléssel a csúcsok fokainál négyzetes kernelt kaptunk a Vertex Cover problémához, amely a válasz méretéhez van paraméterezve. Vannak más paraméterek is, amelyeket választhatunk ehhez a feladathoz (például Vertex Cover Above LP), de mi pontosan ezt a paramétert fogjuk megvitatni.

Pace Challenge

Verseny PACE Challenge (A Paraméterezett Algoritmusok és Számítástechnikai Kísérletek Versenye) 2015-ben indult, hogy kapcsolatot teremtsen a paraméterezett algoritmusok és a gyakorlatban alkalmazott megoldási megközelítések között a számítástechnikai problémák megoldásához. Az első három verseny a gráf fája szélességének keresésére, (Treewidth) a Steiner-fának keresésére (Steiner Tree) és a visszajelző csúcs halmaz keresésére (Feedback Vertex Set). Idén egy olyan feladat volt, amelyre próbálhatták a képességeiket, a fent leírt csúcsborítási feladat.

A verseny évről évre népszerűbb. Ha a prelimináris adatoknak hihetünk, idén a csúcsborítási probléma megoldó versenyén 24 csapat vett részt. Érdemes megjegyezni, hogy a verseny nem néhány óráig, sőt nem is egy hétig, hanem több hónapig tart. A csapatoknak lehetőségük van áttekinteni az irodalmat, kitalálni saját eredeti ötleteiket és megpróbálni megvalósítani azokat. Lényegében ez a verseny kutatómunkának minősül. A legjobb megoldások ötletei és a győztesek díjazása egyidejűleg zajlik az IPEC (Nemzetközi Szimpózium a Paraméterezett és Pontos Számításról) keretein belül, amely Europa legnagyobb éves algoritmikai összejövetelén zajlik ALGO. A verseny részleteiről további információt találhatunk a weboldalon, a korábbi évek eredményei pedig az alábbi helyen érhetők el itt.

A megoldás sémája

A csúcsborítási feladat megoldására megpróbáltam parametrikus algoritmusokat alkalmazni. Ezek általában két részből állnak: egyszerűsítési szabályokból (amelyek ideálisan kernalisáláshoz vezetnek) és osztási szabályokból. Az egyszerűsítési szabályok a bemenet előfeldolgozását jelentik polinomiális időben. Ezek célja a feladat átkonvertálása egy kisebb méretű, ekvivalens problémává. Az egyszerűsítési szabályok a legidőigényesebb része az algoritmusnak, és ennek a résznek a használata vezet az összes végrehajtási időhöz. ahelyett, hogy csak polinomiális időt igényelne. Ebben az esetben az osztási szabályok azon alapulnak, hogy minden csúcsra válasszunk a válaszba vagy magát a csúcsot, vagy annak szomszédját.

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 ezt a csúcsot vegyük figyelembe, a másodikban pedig minden szomszédját. Ezt nevezzük osztásnak (branching) ennek a csúcsnak az alapján.

Ehhez a sémához pontosan egy kiegészítést fogunk tenni a következő bekezdésben.

Az osztási (branching) szabályok ötletei

Beszéljük meg, hogyan válasszunk egy csúcsot, amin osztás fog történni.
A fő ötlet nagyon mohó algoritmikus értelemben: válasszunk egy maximális fokú csúcsot, és oszlassunk éppen ezen. Miért tűnik ez a legjobbnak? Mert a rekurzív hívás második ágában így nagyon sok csúcsot eltávolítunk. Számíthatunk arra, hogy egy kis grafikon marad, amin gyorsan tudunk dolgozni.

Ez a megközelítés, a már tárgyalt egyszerű kernalisálási technikákkal együtt, jól teljesít, néhány ezer csúcs méretű teszteket megold. De például rosszul működik a kubikus gráfokra (azaz azok gráfja, amelyeknek mindegyik csúcsának foka három).
Van egy újabb ötlet, amely egy elég egyszerű gondolaton alapul: ha a gráf nem összefüggő, a kapcsolatkomponensein a feladat függetlenül megoldható, és a válaszokat a végén össze lehet kombinálni. Ez egyébként a korábban ígért kis módosítás a sémában, amely jelentősen felgyorsítja a megoldást: korábban ilyen esetben az összes komponens válaszainak számolási idejének szorzataként dolgoztunk, most viszont az összegek szerint. Az osztás gyorsítása érdekében a kapcsolt gráfot szükséges átalakítani összefüggővé.

Hogyan kell ezt megtenni? Ha van egy grafikonban egy vágópont, akkor pontosan ott kell ágaznunk. A vágópont egy olyan csúcs, amelynek eltávolításakor a grafikon elveszíti a kapcsolatosságát. A grafikonban az összes vágópont megtalálható egy klasszikus algoritmus segítségével, lineáris idő alatt. Ez a megközelítés jelentősen felgyorsítja az ágakra bontást.

Bármelyik kiemelt csúcs eltávolításakor a grafikon eltávolítja a kapcsolatosságait.

Ezt meg fogjuk tenni, de többre vágyunk. Például, keresni a grafikonban kis csúcsvágásokat és a csúcsok mentén végezni az ágazást. A leghatékonyabb módszer, amit ismerek a globális minimális csúcsvágás megtalálására, a Gomori-Hu fa használata, amely kubikus idő alatt épül. A PACE Challenge-ben a tipikus grafikon mérete néhány ezer csúcs. Ilyen körülmények között a rekurszió fájának minden csúcsában milliárdnyi műveletet kell végrehajtani. Ezért a feladatot a rendelkezésre álló idő alatt egyszerűen lehetetlen megoldani.

Próbáljuk meg optimalizálni a megoldást. A pár csúcs közötti minimális csúcsvágás bármelyik maximális áramot építő algoritmussal megtalálható. Egy ilyen hálózatra rá lehet vezényelni Dinic algoritmusát, a gyakorlatban ez nagyon gyorsan működik. Gyanítom, hogy elméletileg bizonyítani lehet a futási időre vonatkozó becslést , ami már teljesen elfogadható.

Többször megpróbáltam vágásokat keresni véletlenszerű csúcsok között és a legjobban kiegyensúlyozottakat választani. Sajnos a PACE Challenge nyílt tesztjein ez rossz eredményeket hozott. Összehasonlítottam a csúcsok maximális fokával foglalkozó algoritmussal, és korlátozva indítottam őket a merülési mélységre. Miután az algoritmus megpróbálta így megtalálni a vágást, a nagyobb méretű grafikonok maradtak. Ez azért van, mert a vágások nagyon kiegyensúlyozatlanok lettek: 5-10 csúcs eltávolításával csupán 15-20 tudott leválni.

Érdemes megjegyezni, hogy a leggyorsabb algoritmusokkal kapcsolatos cikkekben sokkal kifinomultabb technikákat használnak a vágásra szánt csúcsok kiválasztására. Ezek a technikák nagyon bonyolult megvalósítással rendelkeznek, és gyakran rossz idő- és memóriabecslésekkel bírnak. Nem tudtam belőlük kiemelni elfogadható megoldásokat a gyakorlat számára.

Hogyan alkalmazzuk az egyszerűsítési szabályokat

Már van ötletünk a kernelizációra. Emlékeztetek:

1. Ha van egy elszigetelt csúcs, távolítsuk el.
2. Ha van egy 1. fokú csúcs, töröljük, és vegyük a szomszédját válaszként.
3. Ha van legalább egy 2. fokú csúcs, vegyük azt válaszként. k + 1, vegyük válaszként.

Az első kettő tiszta, a harmadik esetében van egy trükk. Ha a vicces feladatban a bárra korlátozást adtunk meg, k, akkor a PACE Challenge-ban egyszerűen meg kell találni a lehető legkisebb csúcsborítást. Ez a keresési feladatok (Search Problem) megoldási feladatokká (Decision Problem) történő tipikus átalakítása, gyakran nem tesznek különbséget a kétféle feladat között. A gyakorlatban, ha csúcsborítási feladatot oldunk meg, a különbség számít. Például a harmadik pontban.

A megvalósítás szempontjából két módon járhatunk el. Az első megközelítés az Iteratív Mélyítés. Ez abban áll, hogy elkezdünk egy ésszerű alsó korláttal a válaszra, és ezután elindítjuk az algoritmusunkat, használva ezt a korlátozást felső korlátozásként, nem mélyedve el a rekurzióban az alsó határ alatt. Ha találunk valamilyen választ, az garantáltan optimális, különben növeljük ezt a korlátot egy egységgel és újra elindulunk.

A másik megközelítés az, hogy tárolunk egy aktuális optimális választ, és kisebb méretű választ keresünk, ha megtaláljuk, módosítva ezt a paramétert k a felesleges ágak levágásának érdekében a keresésben.

Miután néhány éjszakai kísérletet végeztem, egyesítettem ezeket a két módszert: először az algoritmusomat elindítom egy bizonyos keresési mélység korlátozással (úgy választva, hogy ez elhanyagolható időt vegyen igénybe a fő megoldáshoz képest), és a legjobb megtalált megoldást használom mint felső korlátozást – azaz ugyanezt k.

A 2. fokú csúcsok

A 0. és 1. fokú csúcsokkal tisztában vagyunk. Kiderül, hogy a 2. fokú csúcsokkal is megtehető, de ehhez összetettebb műveletek szükségesek a gráfban.

Ehhez valahogyan jelölnünk kell a csúcsokat. Nevezzük a 2. fokú csúcsot csúcsnak v, a szomszédait pedig csúcsoknak x és y. Ezután két esetben lesz dolgunk.

1. Amikor x és y — szomszédok. Ekkor válaszként elfogadhatjuk, hogy x és y, és v törölni kell. Valóban, ebből a háromszögből legalább két csúcsnak szerepelnie kell a válaszban, és biztosan nem veszítünk, ha választunk x és y: valószínűleg van még szomszédjuk, a v nincs.
2. Amikor x és y — nem szomszédok. Ekkor azt állítjuk, hogy mindhárom csúcsot össze lehet ragasztani egybe. Az ötlet az, hogy ilyenkor van egy optimális válasz, amibe vagy v, vagy mindkét csúcsot x és ybe kell vennünk. Ráadásul az első esetben az összes szomszédot is be kell vennünk x és y, míg a második esetben nem feltétlenül. Ez pontosan megfelel azoknak az eseteknek, amikor nem vesszük be a ragasztott csúcsot a válaszba, és amikor belefoglaljuk. Csak annyit kell megjegyezni, hogy mindkét esetben az ilyen művelet által adott válasz egy egységgel csökken.

Érdemes megjegyezni, hogy az ilyen megközelítést tisztán lineáris idő alatt meglehetősen nehéz pontosan megvalósítani. A csúcsok összeragasztása bonyolult művelet, szükséges a szomszédok listáit lemásolni. Ha ezt nem figyelmesen csináljuk, akkor aszimptotikusan nem optimális működési időt kaphatunk (például ha minden egyes összeragasztás után sok élt másolunk). Leálltam a 2 fokú csúcsokból álló egész utak keresésén, és sok egyedi eset, például ilyen csúcsokból álló ciklusok vizsgálatánál.

Ezen kívül szükséges, hogy ez a művelet visszafordítható legyen, hogy a rekurzióból való visszatéréskor a gráfot az eredeti állapotába tudjuk helyreállítani. Ennek biztosítása érdekében nem töröltem az összeragasztott csúcsok éllistáit, így egyszerűen tudtam, hogy mely éleket hová kell irányítani. Az ilyen gráfok megvalósítása is óvatosságot igényel, viszont biztosítja a tisztán lineáris időt. A több tízezer élből álló gráfok pedig jól beleférnek a processzor gyorsítótárába, ami nagy sebességelőnyöket biztosít.

Lineáris mag

Végül, a mag legérdekesebb része.

Kezdetben emlékezzünk arra, hogy bipartit gráfokban a minimális csúcsborítást kereshetjük. Ehhez a Hopcroft-Karp algoritmust kell használnunk a maximális párosítás megtalálásához, majd alkalmazni kell a König-Egervári tétele.

A lineáris mag ötlete a következő: először bipartit gráfot készítünk, azaz minden csúcs helyett v két csúcsot hozunk létre, és míg minden él helyett u — v két élt teremtünk. és A kapott gráf bipartit lesz. Megkeressük benne a minimális csúcsborítást. Néhány csúcs az eredeti gráfban kétszer, néhány egyszer, míg néhány egyáltalán nem kerül be. A Nemhauser-Trotter-tétel szerint ilyenkor eltávolíthatjuk azokat a csúcsokat, amelyek egyáltalán nem szerepeltek, és választhatjuk azokat, amelyek kétszer szerepeltek. Továbbá azt is mondja, hogy a megmaradt csúcsok közül (azok, amelyek egyszer szerepeltek) legalább a felét válasszuk ki a válaszban.

Most tanultuk meg, hogy a gráfban nem hagyunk több mint 2k csúcsot. Igaz, ha a válaszban legalább a csúcsok fele benne van, akkor az összes csúcs száma nem lehet több mint 2k.

Itt sikerült egy kis előrelépést tennem. Nyilvánvaló, hogy így épített mag egyáltalán attól függ, hogy melyik minimális csúcsborítást választottuk a bipartit gráfban. Azt szeretnénk, ha a megmaradt csúcsok száma minimális lenne. Eddig ezt csak idő alatt tudták megoldani. Én azonban kidolgoztam ennek az algoritmusnak a megvalósítását idő alatt, így ezt a magot akár százezres csúcsú gráfokban is kereshetjük a branchenk minden egyes lépésében.

Eredmény

A gyakorlat azt mutatja, hogy a megoldásom jól működik néhány száz csúcs és néhány ezer él tesztjein. Ilyen teszteknél teljesen elvárható, hogy a megoldás fél óra alatt megtalálható legyen. A válasz megtalálásának esélye alapvetően nő, ha a gráfban sok a nagy fokú csúcs, például 10-es és annál nagyobb fokú.

A versenyhez a megoldásokat be kellett küldeni a optil.io. A bemutatott táblázat, a megoldásom a nyílt teszteken a húszból a harmadik helyen áll, nagy különbséggel a második után. Ha teljesen őszinte akarok lenni, akkor nem teljesen világos, hogyan fogják értékelni a megoldásokat magán a versenyen: például az én megoldásom kevesebb teszten teljesít, mint a negyedik helyezetté, de azokban, amelyeket sikerült megoldania, gyorsabban dolgozik.

A zárt teszteken elért eredmények július elsején válnak ismertté.

Forrás: habr.com