Výzkumná práce je možná nejzajímavější částí našeho školení. Myšlenka je vyzkoušet si svůj vybraný směr ještě na univerzitě. Například studenti z oblastí softwarového inženýrství a strojového učení často chodí dělat výzkum do firem (hlavně JetBrains nebo Yandex, ale nejen).
V tomto příspěvku budu hovořit o svém projektu v oblasti informatiky. V rámci své práce jsem studoval a uváděl do praxe přístupy k řešení jednoho z nejznámějších NP-hard problémů: problém pokrytí vrcholů.
V dnešní době se velmi rychle rozvíjí zajímavý přístup k NP-těžkým problémům - parametrizované algoritmy. Pokusím se vás dostat do rychlosti, řeknu vám pár jednoduchých parametrizovaných algoritmů a popíšu jednu mocnou metodu, která mi hodně pomohla. Prezentoval jsem své výsledky na soutěži PACE Challenge: podle výsledků otevřených testů je moje řešení na třetím místě a konečné výsledky budou známy 1. července.
O mně
Jmenuji se Vasilij Alferov, nyní končím třetí rok na Vysoké ekonomické škole National Research University - St. Petersburg. Algoritmy mě zajímají už od školních let, kdy jsem studoval na moskevské škole č. 179 a úspěšně se účastnil počítačových olympiád.
Konečný počet specialistů na parametrizované algoritmy vstupuje do baru...
Příklad převzatý z knihy
Představte si, že jste hlídač baru v malém městě. Každý pátek si do vašeho baru přijde odpočinout polovina města, což vám přináší spoustu problémů: musíte z baru vyhazovat hlučné zákazníky, abyste předešli rvačkám. Nakonec se nabažíte a rozhodnete se pro preventivní opatření.
Protože je vaše město malé, víte přesně, které dvojice patronů se pravděpodobně utkají, pokud spolu skončí v baru. Máte seznam n lidí, kteří dnes večer přijdou do baru. Rozhodnete se držet některé obyvatele města mimo bar, aniž by se někdo dostal do boje. Vaši šéfové zároveň nechtějí přijít o zisky a budou nešťastní, když jim nedovolíte více než k lidí.
Bohužel problém před vámi je klasický NP-těžký problém. Možná ji znáte jako nebo jako problém pokrývající vrchol. Pro takové problémy v obecném případě neexistují žádné algoritmy, které fungují v přijatelném čase. Abychom byli přesní, neprokázaná a poměrně silná hypotéza ETH (Exponential Time Hypothesis) říká, že tento problém nelze vyřešit včas , to znamená, že vás nenapadne nic výrazně lepšího než úplné vyhledávání. Řekněme například, že někdo přijde do vašeho baru n = 1000 Člověk. Pak bude kompletní hledání možností, kterých je přibližně - šílené množství. Naštěstí vám vaše vedení poskytlo limit k = 10, takže počet kombinací, které musíte iterovat, je mnohem menší: počet podmnožin deseti prvků je . To je lepší, ale stále to nebude započítáno za den ani na výkonném clusteru.
Abyste v této konfiguraci napjatých vztahů mezi návštěvníky baru eliminovali možnost rvačky, musíte držet Boba, Daniela a Fedora venku. Neexistuje řešení, ve kterém by zůstali pozadu jen dva.
Znamená to, že je čas vzdát se a nechat všechny dovnitř? Zvažme další možnosti. No, například nemůžete pustit dovnitř pouze ty, kteří pravděpodobně bojují s velmi velkým počtem lidí. Pokud někdo může bojovat alespoň s k+1 jiného člověka, pak ho rozhodně nemůžete pustit dovnitř - jinak budete muset všechny držet venku k+1 měšťané, se kterými se může poprat, což vedení rozhodně rozladí.
Kéž byste podle tohoto principu vyhodili každého, koho byste mohli. Všichni ostatní pak nemohou bojovat s více než k lidé. Vyhazovat je k člověče, nemůžeš zabránit ničemu jinému než konflikty. To znamená, že pokud je více než Pokud je člověk zapleten alespoň do jednoho konfliktu, pak rozhodně nemůžete zabránit všem. Jelikož samozřejmě zcela nekonfliktní lidi určitě pustíte dovnitř, je potřeba projít všechny podmnožiny velikosti deset ze dvou set lidí. Existuje přibližně a tento počet operací již lze na clusteru roztřídit.
Pokud můžete bezpečně vzít jednotlivce, kteří nemají vůbec žádný konflikt, co pak ti, kteří se účastní pouze jednoho konfliktu? Ve skutečnosti mohou být také vpuštěni zavřením dveří před svým protivníkem. Pokud je Alice v konfliktu pouze s Bobem, pak pokud Alici z nich dvou pustíme, neprohrajeme: Bob může mít jiné konflikty, ale Alice je rozhodně nemá. Navíc nedává smysl, abychom nás oba nepustili dovnitř. Po takových operacích už nic nezůstane hosté s nevyřešeným osudem: máme jen konflikty, z nichž každý má dva účastníky a každý se účastní alespoň dvou. Takže zbývá jen protřídit možnosti, což lze klidně považovat za půl dne na notebooku.
Ve skutečnosti můžete jednoduchým uvažováním dosáhnout ještě atraktivnějších podmínek. Všimněte si, že rozhodně musíme vyřešit všechny spory, čili z každé konfliktní dvojice vybrat alespoň jednoho člověka, kterého nepustíme dovnitř. Uvažujme následující algoritmus: vezměte jakýkoli konflikt, ze kterého odebereme jednoho účastníka a rekurzivně začneme od zbytku, poté odstraňte druhého a také začneme rekurzivně. Protože na každém kroku někoho vyhodíme, strom rekurze takového algoritmu je binární strom hloubky k, takže celkově algoritmus funguje Kde n je počet vrcholů a m - počet žeber. V našem příkladu jde o zhruba deset milionů, což lze spočítat ve zlomku vteřiny nejen na notebooku, ale dokonce i na mobilu.
Výše uvedený příklad je příkladem parametrizovaný algoritmus. Parametrizované algoritmy jsou algoritmy, které běží v čase f(k) poly(n)Kde p - polynom, f je libovolná vypočítatelná funkce a k - nějaký parametr, který bude dost možná mnohem menší než velikost problému.
Všechny úvahy před tímto algoritmem jsou příkladem kernelizace je jednou z obecných technik pro vytváření parametrizovaných algoritmů. Kernelizace je redukce velikosti problému na hodnotu omezenou funkcí parametru. Výsledný problém se často nazývá kernel. Jednoduchým uvažováním o stupních vrcholů jsme tedy získali kvadratické jádro pro problém Vertex Cover, parametrizované velikostí odpovědi. Pro tento úkol si můžete vybrat i jiná nastavení (například Vertex Cover Above LP), ale toto je nastavení, o kterém budeme diskutovat.
Tempová výzva
Konkurence (The Parameterized Algorithms and Computational Experiments Challenge) se zrodila v roce 2015, aby navázala spojení mezi parametrizovanými algoritmy a přístupy používanými v praxi k řešení výpočetních problémů. První tři soutěže byly věnovány zjištění šířky stromu grafu (), hledání Steinerova stromu () a hledání sady vrcholů, které ořezávají cykly (). Tento rok byl jedním z problémů, ve kterých jste si mohli vyzkoušet své síly, výše popsaný problém zakrývání vrcholů.
Soutěž si každým rokem získává na popularitě. Pokud věříte předběžným údajům, letos se soutěže o řešení problému pokrytí vrcholů zúčastnilo 24 týmů. Stojí za zmínku, že soutěž netrvá několik hodin nebo dokonce týden, ale několik měsíců. Týmy mají možnost studovat literaturu, přijít s vlastním originálním nápadem a pokusit se jej realizovat. Tato soutěž je v podstatě výzkumným projektem. Nápady na nejefektivnější řešení a ocenění vítězů se bude konat společně s konferencí (Mezinárodní symposium o parametrizovaných a exaktních výpočtech) jako součást největšího každoročního algoritmického setkání v Evropě . Podrobnější informace o samotné soutěži naleznete na , a výsledky minulých let lžou .
Schéma řešení
K vyřešení problému pokrytí vrcholů jsem zkusil použít parametrizované algoritmy. Obvykle se skládají ze dvou částí: pravidla pro zjednodušení (která v ideálním případě vedou k kernelizaci) a pravidla pro rozdělení. Zjednodušující pravidla jsou předzpracování vstupu v polynomiálním čase. Účelem použití takových pravidel je zredukovat problém na ekvivalentní menší problém. Zjednodušující pravidla jsou nejdražší částí algoritmu a aplikace této části vede k celkové době běhu místo jednoduchého polynomiálního času. V našem případě jsou pravidla rozdělení založena na tom, že pro každý vrchol je třeba vzít jako odpověď buď jej, nebo jeho souseda.
Obecné schéma je toto: použijeme pravidla zjednodušení, pak vybereme nějaký vrchol a provedeme dvě rekurzivní volání: v prvním jej vezmeme jako odpověď a ve druhém všechny jeho sousedy. Tomu říkáme rozdělení (větvení) podél tohoto vrcholu.
V následujícím odstavci bude k tomuto schématu přidán přesně jeden.
Nápady na rozdělení (brunching) pravidel
Pojďme diskutovat o tom, jak vybrat vrchol, podél kterého dojde k rozdělení.
Hlavní myšlenka je velmi chamtivá v algoritmickém smyslu: vezměme vrchol maximálního stupně a rozdělme se podle něj. Proč se to zdá lepší? Protože ve druhé větvi rekurzivního volání tímto způsobem odstraníme spoustu vrcholů. Můžete počítat s tím, že vám zbude malý graf a my na něm můžeme rychle pracovat.
Tento přístup s již diskutovanými jednoduchými kernelizačními technikami se dobře ukazuje a řeší některé testy o velikosti několika tisíc vrcholů. Ale například to nefunguje dobře pro kubické grafy (tedy grafy, jejichž stupeň každého vrcholu je tři).
Existuje další myšlenka založená na poměrně jednoduché myšlence: pokud je graf odpojen, problém na jeho připojených komponentách lze vyřešit nezávisle, přičemž odpovědi na konci se zkombinují. To je mimochodem malá slibovaná úprava ve schématu, která řešení výrazně urychlí: dříve jsme v tomto případě pracovali pro součin doby pro výpočet odezvy komponent, nyní však pracujeme pro součet. A pro urychlení větvení je potřeba přeměnit spojený graf na rozpojený.
Jak to udělat? Pokud je v grafu artikulační bod, musíte s ním bojovat. Artikulační bod je takový vrchol, že když se odstraní, graf ztratí svou konektivitu. Všechny spojovací body v grafu lze nalézt pomocí klasického algoritmu v lineárním čase. Tento přístup výrazně urychluje větvení.
Když je některý z vybraných vrcholů odstraněn, graf se rozdělí na připojené komponenty.
Uděláme to, ale chceme víc. Hledejte například malé vrcholové řezy v grafu a rozdělte je podél vrcholů z něj. Nejúčinnějším způsobem, který znám, jak najít minimální globální oříznutí vrcholu, je použít strom Gomori-Hu, který je postaven v krychlovém čase. V PACE Challenge je typická velikost grafu několik tisíc vrcholů. V této situaci je třeba provést miliardy operací v každém vrcholu rekurzního stromu. Ukazuje se, že je prostě nemožné vyřešit problém ve stanoveném čase.
Zkusme optimalizovat řešení. Minimální vrcholový řez mezi párem vrcholů lze nalézt jakýmkoliv algoritmem, který vytváří maximální tok. Můžete to pustit do takové sítě , v praxi to funguje velmi rychle. Mám podezření, že je teoreticky možné doložit odhad provozní doby , což je již celkem přijatelné.
Několikrát jsem se pokusil hledat řezy mezi dvojicemi náhodných vrcholů a vzít ten nejvyváženější. Bohužel to přineslo špatné výsledky v otevřeném testování PACE Challenge. Porovnal jsem to s algoritmem, který rozděluje vrcholy maximálního stupně a vede je s omezením hloubky sestupu. Poté, co se algoritmus snažil najít řez tímto způsobem, byly ponechány větší grafy. To je způsobeno skutečností, že řezy se ukázaly jako velmi nevyvážené: po odstranění 5-10 vrcholů bylo možné oddělit pouze 15-20.
Stojí za zmínku, že články o teoreticky nejrychlejších algoritmech používají mnohem pokročilejší techniky pro výběr vrcholů pro rozdělení. Takové techniky mají velmi složitou implementaci a často špatný výkon z hlediska času a paměti. Nepodařilo se mi identifikovat ty, které jsou pro praxi docela přijatelné.
Jak aplikovat pravidla zjednodušení
Nápady na kernelizaci už máme. Dovolte mi připomenout:
- Pokud existuje izolovaný vrchol, odstraňte jej.
- Pokud existuje vrchol stupně 1, odstraňte jej a vezměte jeho souseda jako odpověď.
- Pokud existuje alespoň vrchol stupně k+1, vezmi to zpět.
U prvních dvou je vše jasné, u třetího je jeden trik. Pokud jsme v komickém problému o baru dostali horní hranici k, pak v PACE Challenge stačí najít vertex cover minimální velikosti. Jedná se o typickou transformaci problémů hledání na problémy rozhodování; mezi těmito dvěma typy problémů často není žádný rozdíl. V praxi, pokud píšeme řešič pro problém pokrývající vrchol, může být rozdíl. Například jako ve třetím bodě.
Z hlediska implementace existují dva způsoby, jak postupovat. První přístup se nazývá Iterativní prohlubování. Je to takto: můžeme začít s nějakým rozumným omezením zdola na odpověď a pak spustit náš algoritmus s použitím tohoto omezení jako omezení na odpověď shora, aniž bychom šli v rekurzi níže než toto omezení. Pokud jsme našli nějakou odpověď, je zaručeně optimální, jinak můžeme tuto hranici zvýšit o jednu a začít znovu.
Dalším přístupem je uložit nějakou aktuální optimální odpověď a hledat menší odpověď a tento parametr po nalezení změnit k pro větší odřezávání nepotřebných větví při hledání.
Po provedení několika nočních experimentů jsem se rozhodl pro kombinaci těchto dvou metod: nejprve spustím svůj algoritmus s určitým omezením hloubky vyhledávání (vyberu ho tak, aby to ve srovnání s hlavním řešením zabralo zanedbatelnou dobu) a použiji nejlepší řešení nalezené jako horní hranice odpovědi – tedy na totéž k.
Vrcholy stupně 2
Zabývali jsme se vrcholy stupně 0 a 1. Ukazuje se, že to lze provést s vrcholy stupně 2, ale to bude vyžadovat složitější operace z grafu.
Abychom to vysvětlili, musíme nějak označit vrcholy. Nazvěme vrchol stupně 2 vrcholem v, a jeho sousedy - vrcholy x и y. Dále budeme mít dva případy.
- Kdy x и y - sousedé. Pak můžete odpovědět x и ya v vymazat. Z tohoto trojúhelníku je třeba vzít na oplátku alespoň dva vrcholy a rozhodně neprohrajeme, když vezmeme x и y: asi mají jiné sousedy, a v Nejsou tady.
- Kdy x и y - ne sousedi. Pak je uvedeno, že všechny tři vrcholy lze slepit do jednoho. Myšlenka je taková, že v tomto případě existuje optimální odpověď, kterou vezmeme buď vnebo oba vrcholy x и y. Navíc v prvním případě budeme muset vzít jako odpověď všechny sousedy x и y, ale ve druhém to není nutné. To přesně odpovídá případům, kdy slepený vrchol jako odpověď nebereme a kdy ano. Zbývá pouze poznamenat, že v obou případech se odezva na takovou operaci sníží o jednu.
Stojí za zmínku, že tento přístup je poměrně obtížné přesně implementovat ve spravedlivém lineárním čase. Lepení vrcholů je složitá operace, je potřeba zkopírovat seznamy sousedů. Pokud se to udělá nedbale, můžete skončit s asymptoticky suboptimální dobou běhu (například když po každém slepení zkopírujete hodně hran). Rozhodl jsem se najít celé cesty z vrcholů stupně 2 a analyzovat spoustu speciálních případů, jako jsou cykly z takových vrcholů nebo ze všech takových vrcholů kromě jednoho.
Navíc je nutné, aby tato operace byla vratná, abychom při návratu z rekurze obnovili graf do původní podoby. Abych to zajistil, nevymazával jsem seznamy hran sloučených vrcholů, a pak jsem jen věděl, které hrany musí kam jít. Tato implementace grafů také vyžaduje přesnost, ale poskytuje spravedlivý lineární čas. A pro grafy o několika desítkách tisíc hran se vejde do mezipaměti procesoru, což přináší velké výhody v rychlosti.
Lineární jádro
Nakonec nejzajímavější část jádra.
Pro začátek si připomeňme, že v bipartitních grafech lze minimální pokrytí vrcholů najít pomocí . Chcete-li to provést, musíte použít algoritmus abychom tam našli maximální shodu a pak použili větu .
Myšlenka lineárního jádra je tato: nejprve rozdvojíme graf, to znamená místo každého vrcholu v přidáme dva vrcholy и a místo každé hrany u - v přidáme dvě žebra и . Výsledný graf bude bipartitní. Najdeme v něm minimální pokrytí vrcholů. Některé vrcholy původního grafu se tam dostanou dvakrát, některé pouze jednou a některé nikdy. Nemhauser-Trotterova věta říká, že v tomto případě lze odstranit vrcholy, které nezasáhly ani jednou, a vzít zpět ty, které zasáhly dvakrát. Navíc říká, že ze zbývajících vrcholů (těch, které zasáhly jednou) musíte vzít alespoň polovinu jako odpověď.
Právě jsme se naučili odcházet maximálně 2k vrcholy Pokud je zbývající odpovědí alespoň polovina všech vrcholů, pak celkem neexistuje více vrcholů než 2k.
Zde jsem mohl udělat malý krok vpřed. Je jasné, že takto konstruované jádro závisí na tom, jaké minimální pokrytí vrcholů jsme v bipartitním grafu vzali. Chtěl bych vzít jeden, aby počet zbývajících vrcholů byl minimální. Dříve to dokázali jen včas . Časem jsem přišel s implementací tohoto algoritmu , takže toto jádro lze hledat v grafech stovek tisíc vrcholů v každé fázi větvení.
Výsledek
Praxe ukazuje, že mé řešení funguje dobře na testech několika stovek vrcholů a několika tisíc hran. V takových testech je docela možné očekávat, že řešení bude nalezeno do půl hodiny. Pravděpodobnost nalezení odpovědi v přijatelném čase se v zásadě zvyšuje, pokud má graf dostatečně velký počet vrcholů vysokého stupně, například stupně 10 a vyšší.
Pro účast v soutěži bylo nutné zaslat řešení . Soudě podle informací tam uvedených , mé řešení v otevřených testech je třetí z dvaceti, s velkým odstupem od druhého. Abych byl úplně upřímný, není úplně jasné, jak budou řešení hodnocena na samotné soutěži: moje řešení například projde méně testy než řešení na čtvrtém místě, ale na těch, které projdou, funguje rychleji.
Výsledky uzavřených testů budou známy XNUMX. července.
Zdroj: www.habr.com