Kuidas lahendada NP-raskusi parameetriliste algoritmidega

Teaduslik töö on ilmselt meie õpingute kõige huvitavam osa. Idee on proovida end valitud suunas juba ülikoolis. Näiteks lähevad tarkvaratehnika ja masinõppe erialade tudengid sageli tegema teadusprojekte (peamiselt JetBrainsis või Yandexis, kuid mitte ainult).

Selles postituses räägin oma projektist arvutiteaduse suunas. Projekti raames uurisin ja rakendasin praktikas lähenemisviise ühe tuntuma NP-raskete probleemide lahendamiseks: tipupakkumise probleem.

Praegu areneb väga kiiresti huvitav lähenemine NP-rasketele probleemidele — parameetrilised algoritmid. Püüan teid tutvustada, rääkida mõnest lihtsast parameetrilisest algoritmist ja kirjeldada üht võimsat meetodit, mis on mind palju aidanud. Oma tulemusi esitlesin PACE Challenge'i võistlusel: avatud testide põhjal hõivab minu lahendus kolmanda koha ja lõplikud tulemused avaldatakse 1. juulil.

Minust

Minu nimi on Vasili Alfjurov, hetkel lõpetan ma III kursust NIU HSE — Peterburis. Algoritmid huvitavad mind juba koolipäevist, kui õppisin Moskva 179. koolis ja osalesin edukalt informaatika olümpiaadidel.

Lõpmatu hulk spetsialiste parametriseeritud algoritmide kohta siseneb baari...

Näide on pärit raamatust «Parameterized algorithms»

Kujutage ette, et olete baari turvamees väikeses linnas. Igal reedel tuleb pool linna teie baari lõõgastuma, mis tekitab teile palju muret: peate välja viskama rahutud külastajad, et vältida kaklusi. Lõpuks hakkab see teile tüütuks, ja otsustate võtta ennetavaid meetmeid.

Kuna teie linn on väike, teate kindlasti, millised paarid külastajatest tõenäoliselt kaklevad, kui nad satuvad baari koos. Teil on nimekiri n inimestest, kes tulevad täna õhtul baari. Otsustate mitte lasta baari mingisuguseid linnaelanikke nii, et kedagi ei tekiks kaklusi. Samal ajal ei soovi teie ülemus kaotada tulu ja on nördinud, kui te ei lase baari rohkem kui k inimest.

Kahjuks on ees seispev ülesanne klassikaline NP-raskusi tekitav probleem. Te võisite seda teada ka kui Tipukaate, või tipukaate probleemina. Sellistele ülesannetele ei ole üldiselt teada algoritme, mis töötaksid mõistlikus ajas. Täpsemalt öeldes ütleb tõendamata ja üsna tugev hüpotees ETH (Exponential Time Hypothesis), et seda ülesannet ei saa lahendada ajaga , mis tähendab, et midagi märgatavalt paremat kui täielik läbiotsimine ei saa välja mõelda. Näiteks oletame, et teie baari on tulemas n = 1000 inimest. Siis sisaldab täielik läbiotsimine varianti, mis on umbes — uskumatult palju. Õnneks on teie juhatus kehtestanud teile piirangu k = 10, nii et kombinatsioonide arv, mida peate läbi otsima, on palju väiksem: kümne elemendi alamhulkade arv on . See on juba parem, kuid ikkagi ei suudeta seda päeva jooksul isegi võimsal klusteril lõpetada.

Kuna sellise pingestatud suhete konfiguratsiooniga baarikülastajate vahel kakluse tõenäosus väheneb, tuleb Bobi, Daniela ja Fjodorit sisse lasta. Lahendust, kus jääb vaid kaks välja, ei ole.

Kas see tähendab, et on aeg alla anda ja kõiki sisse lasta? Vaatame muid võimalusi. Näiteks võib mitte lasta sisse ainult neid, kes tõenäoliselt kaklevad väga suure hulga inimestega. Kui keegi suudab kakelda vähemalt ühe k + 1 teise inimesega, siis teda kindlasti ei tohi lasta sisse — vastasel juhul tuleb kõiki mitte lasta. k + 1 Kohalikud elanikud, kellega ta võib kakelda, ja see petab juhtkonna täiesti ära.

Oletame, et olete kõik, keda saite, selle põhimõtte kohaselt välja visanud. Siis võivad kõik ülejäänud kakelda mitte rohkem kui k inimestega. Nende seast välja viskades k inimest, saate vältida mitte rohkem kui konflikti. Seega, kui rohkem kui inimest osaleb vähemalt ühes konfliktis, siis te ei suuda neid kindlasti kõiki ära hoida. Kuna on selge, et täiesti konfliktituks inimesi te kindlasti sisse lasete, peate uurima kõiki alamhulgi, mille suurus on kümme, kahesajast inimesest. Nende arv on umbes , ja sellise hulga operatsioone on juba võimalik läbi vaadata klastris.

Kui on võimalik sisse lasta täiesti konflikti puudutavaid isikuid, siis kuidas on nende suhtes, kes osalevad vaid ühes konfliktis? Tegelikult võib neid ka sisse lasta, sulgedes ukse nende vastase ees. Ja tõepoolest, kui Alice on konfliktis vaid Bobiga, siis kui me laskme neist kahest sisse Alice'i, ei kaota me: Bobil võivad olla muud konfliktid, kuid Alicel neid kindlasti ei ole. Seetõttu pole meie jaoks mõttekas mitte lasta sisse kedagi kahest. Pärast selliseid operatsioone jääb meie ette mitte rohkem lahendamata saatusega külalisi: kokku on meil konflikte, igas osaleb kaks osalist ja igaühel on vähemalt kaks osalust. See tähendab, et jääb kaaluda vaid varianti, mis võib kindlasti arvestada pool päeva sülearvutil.

Tegelikult saab lihtsate mõttekäikude abil saavutada veelgi soodsamaid tingimusi. Tuleb märkida, et meil on hädasti vaja lahendada kõik vaidlused, st igast konflikti paarist valida vähemalt üks inimene, keda me ei lase sisse. Vaatame järgmist algoritmi: võtame mistahes konflikti, kust eemaldame ühe osalise ja käivitame rekursiivselt ülejäänud osaliste põhjal, seejärel eemaldame teise ja käivitame ka rekursiivselt. Kuna iga sammu juures eemaldame kellegi, on sellise algoritmi rekursioonipuu binaarne puu sügavusega k, seega töötab algoritm kokku , kus n — tipude arv, ja m — servade arv. Meie näites on see umbes kümme miljonit, mis arvutatakse sekundite murdosa jooksul mitte ainult sülearvutis, vaid isegi mobiiltelefonis.

Ülaltoodud näide on näide parameetrilisest algoritmist. Parameetrilised algoritmid on algoritmid, mis töötavad ajaga f(k) poly(n), kus p — polünoom, f — suvaline arvutatav funktsioon, ja k — mingi parameeter, mis võib olla palju väiksem ülesande suurusest.

Kuni selle algoritmini viivad kõik mõttekäigud näitavad näidet kerneldamisest — üks üldtehnikaid parameetriseeritud algoritmide loomisel. Kerneldamine tähendab ülesande suuruse vähendamist väärtuseni, mis on piiratud parameetri funktsiooniga. Saadud ülesannet nimetatakse sageli kerniks. Nii saime lihtsate mõtiskluste kaudu tippude asteid arvestades kvadratilise kerne Vertex Cover'i probleemile, mis on parameetriseeritud vastuse suurusega. On olemas ka teisi parameetreid, mille saab selle ülesande jaoks valida (näiteks Vertex Cover Above LP), kuid me arutame just sellist parameetrit.

Pace Challenge

Võistlus PACE Challenge (The Parameterized Algorithms and Computational Experiments Challenge) sai alguse 2015. aastal, et luua side parameetriseeritud algoritmide ja praktikates kasutatavate lähenemisviiside vahel, et lahendada arvutusprobleeme. Esimesed kolm võistlust keskendusid puu laius graafis (Treewidth), Šteineri puu leidmisele (Steiner Tree) ja tsüklite lõikavate tippude hulga leidmisele (Feedback Vertex Set). Sel aastal oli üks ülesanne, milles sai oma oskusi proovile panna, ülaltoodud tippude katte probleem.

Võistlus muutub iga aastaga üha populaarsemaks. Eelärvete kohaselt osales sel aastal ainult tippkatteprobleemi lahendamise võistlusel 24 meeskonda. Tuleb märkida, et võistlus kestab mitte paar tundi ega isegi nädalat, vaid mitu kuud. Meeskondadel on võimalus uurida kirjandust, välja mõelda originaalne idee ja proovida see ellu viia. Tegelikult esindab see võistlus uurimistööd. Kõige tõhusamate lahenduste ideed ning võitjate auhindamine toimub koos konverentsiga IPEC (Rahvusvaheline Parametriseeritud ja Täpsete Arvutuste Sümposium) Euroopa suurima ig השנה algoritmilise kogunemise raames ALGO. Täiendavat teavet võistluse enda kohta leiate veebilehel, samas kui eelmiste aastate tulemused on saadaval siin.

Lahenduse skeem

Tippude katmiseks olen proovinud rakendada parameetrilisi algoritme. Need koosnevad tavaliselt kahest osast: lihtsustamise reeglitest (mis ideaalis viivad kerneldamiseni) ja jagamisreeglitest. Lihtsustamise reeglid on sisendi eeltöötlus polünoomse ajaga. Nende reeglite eesmärk on viia probleem võrreldava väiksema suurusega probleemini. Lihtsustamise reeglid on algoritmi kõige kulukam osa ja nende rakendamine viib üldise tööajani mitte lihtsalt polünoomse ajani. Meie puhul põhinevad jagamisreeglid sellel, et iga tipu puhul tuleb vastuseks võtta kas see või tema naaber.

Üldine skeem on järgmine: rakendame lihtsustamise reegleid, siis valime mingi tipu ja teeme kaks rekursiivset kutset: esimeses me võtame selle vastuseks ja teises me võtame kõik tema naabrid. Seda nimetame selle tipu jagamiseks (branching).

Sellesse skeemi lisatakse täpselt üks täiendav element järgmises lõigus.

Ideed jagamisreeglite (branching) jaoks

Räägime, kuidas valida tippu, mille kaudu jagunemine toimub.
Põhikontseptsioon on väga ahne algoritmilises mõttes: valime maksimaalse astmega tipu ja jaguneme just selle kaudu. Miks tundub, et see on parem? Sest rekursiivse kõne teises harus eemaldasime sel viisil väga palju tippe. Võime loota, et jääb väike graaf, mille kallal saame kiiresti töötada.

See lähenemine, koos juba arutletud lihtsate kerneldamistehnikatega, ei toimi halvasti, lahendab testid, mille suurus on mitu tuhat tippu. Kuid näiteks kuubiliste graafide (st selliste graafide, kus iga tipu aste on kolm) puhul ei toimi see hästi.
On veel üks idee, mis põhineb üsna lihtsalt mõttel: kui graaf on mitteühendatud, saab selle komponentide ühenduvuse ülesande lahendada iseseisvalt, ühendades vastused lõpuks. See on muide see väike lubatud muudatus skeemis, mis kiirendab lahendust: varem töötasime sellisel juhul komponentide vastuste arvu ajakulu korrutisega, nüüd aga summa põhjal. Ja branshingu kiirendamiseks tuleb muuta ühendatud graaf mitteühendatud graafiks.

Kuidas seda teha? Kui graafis on liitumispunkt, tuleb teha branshing just selle kaudu. Liitumispunkt on selline tipp, mille eemaldamisel graaf kaotab ühenduvuse. Kõik liitumispunktid graafis saab leida klassikalise algoritmiga lineaarajas. Selline lähenemine kiirendab branshingut märkimisväärselt.

Iga valitud tipu eemaldamisel laguneb graaf ühenduvuse komponentideks.

Me teeme nii, kuid soovime rohkem. Näiteks otsida graafis väikseid tippude lõikeid ja teha nende põhjal lõhustamist. Tõhusaim tuntud viis, kuidas leida minimaalne globaalne tippude lõige, on kasutada Gomori-Hu puud, mille ehitamine võtab kubikulise aja. PACE Challenge'i tüüpiline graafi suurus on mitu tuhat tippu. Sellises olukorras peab rekursioonipuus igas tipus teostama miljardeid operatsioone. Seega on ülesande lahendamine ettenähtud ajaks lihtsalt võimatu.

Proovime lahendust optimeerida. Minimaalne tippude lõige kahe tipu vahel saab leida mis tahes algoritmiga, mis loob maksimaalse voolu. Saame sellele võrgule rakendada Dinitzi algoritmi, praktikas töötab see väga kiiresti. Mul on kahtlus, et teoreetiliselt saab tõendada tööaja hinnangut , mis on juba täiesti vastuvõetav.

Olen proovinud mitu korda otsida lõikeid juhuslike tippude paaride vahel ja valida neist kõige tasakaalustatum. Kahjuks andis see avatud PACE Challenge testides halbu tulemusi. Võrreldes tipptasemel tippude põhjal töötava algoritmiga, kus rakendatakse sügava langemise piirangut, jäid pärast lõike otsimist suurem graaf. See on tingitud sellest, et lõiked osutusid väga tasakaalustamatuks: eemaldades 5-10 tippu, õnnestus eraldada vaid 15-20.

Väärib märkimist, et teoreetiliselt kiiremate algoritmide artiklites kasutatakse palju keerukamaid tehnikaid tippude eraldamiseks. Need tehnikad omavad väga keerukat rakendust ning sageli halbu tulemusi aja ja mälu osas. Mul ei õnnestunud neist leida praktikaks piisavalt vastuvõetavaid lahendusi.

Kuidas rakendada lihtsustamise reegleid

Meil on juba ideed kerneldamise osas. Tuletan meelde:

1. Kui on isolatsioonis tip, siis eemaldage see.
2. Kui on tipu kraad 1, eemaldage see ja võtke tema naaber vastuseks.
3. Kui vähemalt on tippu kraad k + 1, võtke see vastuseks.

Esimese kahega on kõik selge, kolmandaga on üks nip. Kui naljaka ülesande puhul baarist oli meil ülemine piir, k, siis PACE Challenge'is peame lihtsalt leidma minimaalse suurusega tipuka覆盖。 see on iseloomulik muundumine otsinguülesannetest (Search Problem) lahendusülesanneteks (Decision Problem), sageli ei tehta kahe ülesande vahel vahet. Praktikas, kui kirjutame tipu katte lahendaja, võib vahe olla. Näiteks nagu kolmandas punktis.

Rakenduse seisukohalt on kaks lähenemisviisi. Esimene meetod nimetatakse Iterative Deepening'iks. See seisneb järgmisest: võime alustada mingist mõistlikust alumisest piirist vastusele ja seejärel käivitada oma algoritmi, kasutades seda piiri ülemise piirina, mitte laskumata rekursiooni madalamale kui see piir. Kui leidsime mingi vastuse, on see garanteeritud optimeeritud, vastasel juhul saame seda piiri ühe võrra suurendada ja uuesti käivitada.

Teine lähenemine on hoida mingit praegust optimaalselt vastust ja otsida väiksema suurusega vastust, muutma seda parameetrit leides k lisakäikude eemaldamiseks otsingus.

Pärast mitmeid öiseid katsetusi otsustasin nende kahe meetodi kombinatsiooni kasuks: esmalt käivitan oma algoritmi mõne sügavuse piiranguga (seades selle nii, et see võtaks tühise aja võrreldes põhilahendusega) ja kasutan parimat leitud lahendust kui ülemist piiri vastusele — see tähendab just seda k.

2. astme tipud

Oleme 0. ja 1. astme tipudega saanud hakkama. Selgub, et seda saab teha ka 2. astme tippudega, kuid selle jaoks on graafilt vaja keerukamaid operatsioone.

Selle selgitamiseks tuleb kuidagi tähistada tippe. Nimeta 2. astme tipp tippuks v, ja tema naabreid — tipud x ja y. Edasi läheb meil kaks juhtumit.

1. Kui x ja y — naabrid. Siis võib vastuseks võtta x ja y, ja v eemaldada. Tõepoolest, sellest kolmnurgast peab vähemalt kaks tippu vastuseks võtma ja me ei kaota, kui võtame x ja y: neil on ilmselt veel naabreid, aga v nendel ei ole.
2. Kui x ja y — mitte naabrid. Siis väidetakse, et kõik kolm tippu saab kokku liita üheks. Idee on see, et sellisel juhul on optimaalne vastus, kus me võtame kas v, või mõlemad tipud x ja y. Esiteks peame vastuseks võtma kõik naabrid x ja y, ja teises ei ole see tingimata vajalik. See vastab täpselt olukordadele, kus me ei arvesta kokku pandud tippu vastusesse ja kus me seda teeme. Jääb vaid märkida, et mõlemal juhul väheneb sellise operatsiooni tulemus ühiku võrra.

Tuleb märkida, et sellise lähenemise rakendamine on ausalt öeldes üsna keeruline täpselt läbi viia. Tippude ühendamine on keeruline operatsioon, kuna tuleb kopeerida naabrite loendid. Kui seda ei tehta ettevaatlikult, võib saada asymptoottisesti mittesoovitava tööaja (näiteks kui pärast iga ühendamist kopeerida palju servi). Olen keskendunud täielike teede otsimisele kahe astmega tippude seas ja erinevate erijuhtude lahendamisele, näiteks tsüklitele, mis koosnevad sellistest tipudest või kõigist sellistest tipudest peale ühe.

Lisaks peab see operatsioon olema pööratav, et saaksime rekursioonist naastes grafi algsesse olekusse taastada. Selle tagamiseks ei kustutanud ma ühendatud tippude servade loendeid, seega teadsin lihtsalt, kuhu servad suunata. Selline graafide rakendus nõuab samuti ettevaatlikkust, kuid tagab ausalt lineaarsed ajad. Ja mitmekümne tuhande servaga graafid mahuvad täiesti protsessori vahemälu, mis annab suurima kiiruselise eelise.

Lineaarne ydur

Lõpuks, kõige huvitavam osa ydurist.

Alustuseks meenutame, et bipartiidsetes graafides saab minimaalset tippude katet otsida . Selleks tuleb rakendada algoritmi Hopcroft-Karpa et leida seal maksimaalne paaritus, ja seejärel rakendada Königi-Egervari teoreemi..

Lineaarse yduride idee on järgmine: esmalt jagame graafi, st iga tipu asemel v loome kaks tippu ja , ja iga serva asemel u — v loome kaks serva ja . Saadud graaf on kahekündaline. Leiame sellest minimaalse tippkatte. Mõned algse graafi tipud sattuvad sinna kaks korda, mõned vaid üks kord ja mõned ei satu sinna üldse. Nemhauseri-Trotteri teoreem väidab, et sellisel juhul võib eemaldada tipud, mis ei sattunud sinna kordagi, ja jätta alles need, mis sattusid kaks korda. Veelgi enam, see ütleb, et allesjäänud tipud (need, mis sattusid üks kord) tuleb vähemalt pooled võtta vastuseks.

Just õppisime graafis jätma mitte rohkem kui 2k tipu. Tõepoolest, kui vastuses on vähemalt pool kõigist tipudest, siis ei ole neid seal kokku rohkem kui 2k.

Siin suutsin teha väikese edusamme. On selge, et nii koostatud tuum sõltub sellest, milline minimaalne tippkate kahekündalises graafis me valisime. Sooviksin võtta sellise, et allesjäänud tipude arv oleks minimaalne. Varem osati seda teha vaid ajaga . Ma aga mõtlesin välja selle algoritmi rakenduse ajaga , seega on seda tuuma võimalik otsida graafides, mille suurus on sadade tuhandete tippude piires igas harutamisetapis.

Tulemus

Praktika näitab, et minu lahendus töötab hästi testides, kus on mitu sadat tippu ja mitu tuhat serva. Sellistes testides võib oodata, et lahendus leitakse poole tunni jooksul. Vastuse leidmise tõenäosus suureneb, kui graafikus on piisavalt palju tippusid suure astmega, näiteks astmega 10 ja rohkem.

Osalemiseks võistluses tuli lahendused saata aadressile optil.io. Seal esitatud andmete põhjal tabeli, minu lahendus avatud testides hoiab kolmandat kohta kahekümnest, olles selgelt ees teisest. Kui olla täiesti aus, siis ei ole täiesti selge, kuidas lahendusi võistluse jooksul hinnatakse: näiteks minu lahendus läbib vähem teste kui neljandal kohal olev lahendus, kuid töötab kiiremini nendes, mis tal on.

Suletud testide tulemused avaldatakse esimesel juulil.

Allikas: habr.com