Mokslinis darbas yra bene įdomiausia mūsų mokymo dalis. Idėja – išbandyti save pasirinkta kryptimi dar studijuojant universitete. Pavyzdžiui, programinės įrangos inžinerijos ir mašininio mokymosi sričių studentai dažnai eina atlikti tyrimų įmonėse (daugiausia JetBrains ar Yandex, bet ne tik).
Šiame įraše kalbėsiu apie savo projektą informatikos srityje. Vykdydamas savo darbą studijavau ir praktiškai taikiau būdus, kaip išspręsti vieną iš garsiausių NP sudėtingų problemų: viršūnių uždengimo problema.
Šiais laikais labai greitai vystosi įdomus požiūris į NP kietas problemas – parametrizuoti algoritmai. Pabandysiu jus pagreitinti, papasakosiu kelis paprastus parametrinius algoritmus ir apibūdinsiu vieną galingą metodą, kuris man labai padėjo. Savo rezultatus pristačiau PACE Challenge konkurse: pagal atvirų testų rezultatus mano sprendimas užima trečią vietą, o galutiniai rezultatai bus žinomi liepos 1 d.
Apie mane
Mano vardas Vasilijus Alferovas, dabar baigiu trečią kursą Nacionalinio tyrimų universiteto aukštojoje ekonomikos mokykloje – Sankt Peterburge. Algoritmais domėjausi nuo mokyklos laikų, kai mokiausi Maskvos 179 mokykloje ir sėkmingai dalyvavau informatikos olimpiadose.
Į juostą patenka ribotas skaičius parametrizuotų algoritmų specialistų...
Pavyzdys paimtas iš knygos
Įsivaizduokite, kad esate baro apsaugininkas mažame miestelyje. Kiekvieną penktadienį pusė miesto ateina į tavo barą atsipalaiduoti, o tai sukelia daug rūpesčių: norint išvengti muštynių, reikia išmesti iš baro triukšmingus klientus. Galiausiai pavargstate ir nusprendžiate imtis prevencinių priemonių.
Kadangi jūsų miestas mažas, tiksliai žinote, kurios globėjų poros gali susimušti, jei kartu atsidurs bare. Ar turite sąrašą n žmonių, kurie šįvakar ateis į barą. Nusprendi neleisti kai kuriems miestiečiams patekti į barą, niekam neįsiveliant. Tuo pačiu metu jūsų viršininkai nenori prarasti pelno ir bus nepatenkinti, jei neleisite daugiau nei k žmonių.
Deja, problema prieš jus yra klasikinė NP problema. Galbūt jūs ją žinote kaip , arba kaip viršūnių uždengimo problemą. Tokioms problemoms spręsti paprastai nėra algoritmų, kurie veiktų per priimtiną laiką. Tiksliau tariant, neįrodyta ir gana tvirta hipotezė ETH (Exponential Time Hypothesis) teigia, kad šios problemos negalima išspręsti laiku. , tai yra, jūs negalite galvoti apie ką nors pastebimai geresnio už išsamią paiešką. Pavyzdžiui, tarkime, kad kažkas ateis į jūsų barą n = 1000 Žmogus. Tada bus baigta paieška variantų, kurių yra maždaug - beprotiška suma. Laimei, jūsų vadovybė nustatė jums ribą k = 10, todėl derinių, kuriuos reikia kartoti, skaičius yra daug mažesnis: dešimties elementų poaibių skaičius yra . Tai geriau, bet vis tiek nebus skaičiuojama per dieną net ir galingame klasteryje.
Kad išvengtumėte muštynių tokioje įtemptų baro lankytojų santykių konfigūracijoje, turite neleisti Bobui, Danieliui ir Fiodorui nuošalyje. Nėra sprendimo, kuriame liktų tik du.
Ar tai reiškia, kad laikas pasiduoti ir įsileisti visus? Apsvarstykime kitus variantus. Na, pavyzdžiui, negalima įsileisti tik tų, kurie gali kovoti su labai daugybe žmonių. Jei kas nors gali kovoti bent su k+1 kitą asmenį, tada jūs tikrai negalite jo įsileisti - kitaip turėsite visus neleisti k+1 miestiečiai, su kuriais jis gali kautis, o tai neabejotinai sutrikdys vadovybę.
Leiskite išmesti visus, kuriuos galite pagal šį principą. Tada visi kiti gali kovoti su ne daugiau kaip k žmonių. Juos išmetant k žmogau, tu negali nieko daugiau užkirsti kelio konfliktai. Tai reiškia, kad jei yra daugiau nei Jei žmogus yra įtrauktas į bent vieną konfliktą, tu tikrai negali užkirsti jiems visų. Kadangi, žinoma, jūs tikrai įsileisite visiškai nekonfliktiškus žmones, jums reikia pereiti visus dešimties dydžio pogrupius iš dviejų šimtų žmonių. Yra maždaug , ir šį skaičių operacijų jau galima surūšiuoti klasteryje.
Jei galite drąsiai paimti asmenis, kurie visai nekonfliktuoja, tai ką daryti su tais, kurie dalyvauja tik viename konflikte? Tiesą sakant, juos taip pat galima įleisti uždarius duris priešininkui. Iš tiesų, jei Alisa konfliktuoja tik su Bobu, tai jei išleisime Alisą iš jųdviejų, nepralaimėsime: Bobas gali turėti kitų konfliktų, bet Alisa jų tikrai neturi. Be to, nėra prasmės mūsų abiejų neįsileisti. Po tokių operacijų nebelieka svečiai, kurių likimas neišspręstas: turime tik konfliktai, kurių kiekviename yra du dalyviai ir kiekvienas dalyvauja bent dviejuose. Taigi belieka sutvarkyti parinktys, kurias nesunkiai galima laikyti puse dienos nešiojamajame kompiuteryje.
Tiesą sakant, paprastu samprotavimu galite pasiekti dar patrauklesnių sąlygų. Atkreipkite dėmesį, kad būtinai turime išspręsti visus ginčus, tai yra iš kiekvienos konfliktuojančios poros pasirinkti bent vieną žmogų, kurio neįleisime. Panagrinėkime tokį algoritmą: paimkite bet kokį konfliktą, iš kurio pašaliname vieną dalyvį ir rekursyviai pradedame nuo likusio, tada pašaliname kitą ir taip pat pradedame rekursyviai. Kadangi kiekviename žingsnyje mes ką nors išmetame, tokio algoritmo rekursijos medis yra dvejetainis gylio medis k, taigi iš viso algoritmas veikia Kur n yra viršūnių skaičius ir m - šonkaulių skaičius. Mūsų pavyzdyje tai yra apie dešimt milijonų, kuriuos per sekundės dalį galima apskaičiuoti ne tik nešiojamajame kompiuteryje, bet net ir mobiliajame telefone.
Aukščiau pateiktas pavyzdys yra pavyzdys parametrizuotas algoritmas. Parametrizuoti algoritmai yra algoritmai, kurie veikia laiku f(k) poli(n)Kur p - daugianaris, f yra savavališkai apskaičiuojama funkcija ir k - tam tikras parametras, kuris, tikėtina, bus daug mažesnis už problemos dydį.
Visi samprotavimai prieš šį algoritmą pateikia pavyzdį kernelizacija yra viena iš bendrųjų parametrizuotų algoritmų kūrimo metodų. Branduolys yra problemos dydžio sumažinimas iki vertės, kurią riboja parametro funkcija. Atsiradusi problema dažnai vadinama branduoliu. Taigi, paprastai samprotaudami apie viršūnių laipsnius, gavome kvadratinį viršūnės viršelio uždavinio branduolį, parametruotą pagal atsakymo dydį. Yra ir kitų nustatymų, kuriuos galite pasirinkti šiai užduočiai atlikti (pvz., „Vertex Cover Above LP“), tačiau tai yra nustatymas, kurį aptarsime.
Tempo iššūkis
Konkurencija (The Parameterized Algorithms and Computational Experiments Challenge) gimė 2015 m., siekiant nustatyti ryšį tarp parametrizuotų algoritmų ir praktikoje naudojamų metodų sprendžiant skaičiavimo problemas. Pirmosios trys varžybos buvo skirtos grafiko medžio pločiui rasti (), ieškau Steinerio medžio () ir ieškoti viršūnių rinkinio, kuris supjausto ciklus (). Šiais metais viena iš problemų, kurią galėjai išmėginti, buvo aukščiau aprašyta viršūnių uždengimo problema.
Konkursas kasmet populiarėja. Jei tikėti preliminariais duomenimis, šiemet vien viršūnių uždengimo problemos sprendimo konkurse dalyvavo 24 komandos. Verta paminėti, kad varžybos trunka ne kelias valandas ar net savaitę, o kelis mėnesius. Komandos turi galimybę studijuoti literatūrą, sugalvoti savo originalią idėją ir bandyti ją įgyvendinti. Iš esmės šis konkursas yra mokslinis projektas. Kartu su konferencija bus rengiamos idėjos efektyviems sprendimams ir nugalėtojų apdovanojimas (Tarptautinis parametrinio ir tikslaus skaičiavimo simpoziumas) kaip didžiausio kasmetinio algoritminio susitikimo Europoje dalis. . Išsamesnę informaciją apie patį konkursą rasite adresu , o ankstesnių metų rezultatai lie .
Sprendimo schema
Norėdami išspręsti viršūnių uždengimo problemą, bandžiau naudoti parametrizuotus algoritmus. Paprastai jas sudaro dvi dalys: supaprastinimo taisyklės (kurios idealiu atveju veda prie branduolio) ir padalijimo taisyklių. Supaprastinimo taisyklės yra išankstinis įvesties apdorojimas daugianario laiku. Tokių taisyklių taikymo tikslas – sumažinti problemą iki lygiavertės mažesnės problemos. Supaprastinimo taisyklės yra brangiausia algoritmo dalis, o pritaikius šią dalį gaunamas bendras veikimo laikas vietoj paprasto daugianario laiko. Mūsų atveju padalijimo taisyklės yra pagrįstos tuo, kad kiekvienos viršūnės atsakymui reikia priimti arba ją, arba jos kaimyną.
Bendra schema yra tokia: taikome supaprastinimo taisykles, tada pasirenkame kokią nors viršūnę ir atliekame du rekursinius iškvietimus: pirmajame paimame jį kaip atsaką, o kitame – visus jos kaimynus. Tai mes vadiname padalijimu (išsišakojimu) išilgai šios viršūnės.
Kitoje pastraipoje ši schema bus papildyta tiksliai.
Idėjos skaidymo (brunčo) taisyklėms
Aptarkime, kaip pasirinkti viršūnę, išilgai kurios įvyks padalijimas.
Pagrindinė mintis algoritmine prasme labai godi: paimkime maksimalaus laipsnio viršūnę ir suskilkime išilgai jos. Kodėl tai atrodo geriau? Nes antroje rekursinio skambučio šakoje tokiu būdu pašalinsime daug viršūnių. Galite tikėtis, kad liks mažas grafikas, ir mes galime greitai su ja dirbti.
Šis metodas, naudojant jau aptartus paprastus branduolio sudarymo būdus, puikiai pasirodo ir išsprendžia kai kuriuos kelių tūkstančių viršūnių dydžio testus. Bet, pavyzdžiui, jis netinka kubiniams grafams (tai yra grafikams, kurių kiekvienos viršūnės laipsnis yra trys).
Yra dar viena idėja, pagrįsta gana paprasta idėja: jei grafikas yra atjungtas, jo prijungtų komponentų problemą galima išspręsti savarankiškai, sujungiant atsakymus pabaigoje. Tai, beje, nedidelis žadėtas schemos pakeitimas, kuris gerokai paspartins sprendimą: anksčiau šiuo atveju komponentų atsakymams skaičiuoti dirbome laiko sandaugai, o dabar dirbame suma. O norint pagreitinti išsišakojimą, susietą grafiką reikia paversti atjungtu.
Kaip tai padaryti? Jei grafike yra artikuliacijos taškas, reikia su juo kovoti. Artikuliacijos taškas yra tokia viršūnė, kurią pašalinus grafikas praranda ryšį. Visus grafiko sandūros taškus galima rasti naudojant klasikinį algoritmą tiesiniu laiku. Šis metodas žymiai pagreitina šakojimą.
Kai kuri nors iš pasirinktų viršūnių pašalinama, grafikas bus padalintas į sujungtus komponentus.
Mes tai padarysime, bet norime daugiau. Pavyzdžiui, grafike ieškokite mažų viršūnių pjūvių ir iš jo padalinkite išilgai viršūnių. Veiksmingiausias mano žinomas būdas rasti minimalų pasaulinės viršūnės pjūvį yra naudoti Gomori-Hu medį, kuris sukuriamas per kubinį laiką. PACE Challenge tipinis grafiko dydis yra keli tūkstančiai viršūnių. Esant tokiai situacijai, kiekvienoje rekursijos medžio viršūnėje reikia atlikti milijardus operacijų. Pasirodo, per skirtą laiką problemos išspręsti tiesiog neįmanoma.
Pabandykime optimizuoti sprendimą. Minimalų viršūnių pjūvį tarp viršūnių poros galima rasti bet kuriuo algoritmu, kuris sukuria didžiausią srautą. Galite leisti jį į tokį tinklą , praktiškai tai veikia labai greitai. Turiu įtarimą, kad teoriškai įmanoma įrodyti darbo laiko sąmatą , o tai jau visai priimtina.
Kelis kartus bandžiau ieškoti pjūvių tarp atsitiktinių viršūnių porų ir paimti labiausiai subalansuotą. Deja, tai davė prastus rezultatus atviro PACE Challenge testavimo metu. Aš palyginau jį su algoritmu, kuris padalijo didžiausio laipsnio viršūnes, paleidžiant jas ribojant nusileidimo gylį. Algoritmas, bandantis tokiu būdu rasti pjūvį, paliko didesnius grafikus. Taip yra dėl to, kad pjūviai pasirodė labai nesubalansuoti: pašalinus 5-10 viršūnių, buvo galima atskirti tik 15-20.
Verta pažymėti, kad straipsniuose apie teoriškai greičiausius algoritmus naudojami daug pažangesni viršūnių atskyrimo būdai. Tokie metodai yra labai sudėtingi ir dažnai prastai veikia laiko ir atminties atžvilgiu. Man nepavyko nustatyti tų, kurie yra gana priimtini praktikai.
Kaip taikyti supaprastinimo taisykles
Jau turime idėjų branduoliui. Leiskite man jums priminti:
- Jei yra izoliuota viršūnė, ištrinkite ją.
- Jei yra 1 laipsnio viršūnė, pašalinkite ją ir paimkite jos kaimyną.
- Jei yra bent laipsnio viršūnė k+1, atsiimk.
Su pirmaisiais dviem viskas aišku, su trečiuoju yra vienas triukas. Jei komiškoje užduotyje apie juostą mums buvo suteikta viršutinė riba k, tada PACE Challenge tereikia rasti minimalaus dydžio viršūnių viršūnę. Tai yra tipiškas paieškos problemų pavertimas sprendimų problemomis; dažnai nėra skirtumo tarp dviejų problemų tipų. Praktiškai, jei rašome viršūnių aprėpties uždavinio sprendiklį, gali būti skirtumas. Pavyzdžiui, kaip trečiame punkte.
Įgyvendinimo požiūriu yra du būdai tęsti. Pirmasis metodas vadinamas kartotiniu gilinimu. Tai yra taip: galime pradėti nuo tam tikro pagrįsto atsakymo apribojimo iš apačios, o tada paleisti savo algoritmą naudodami šį apribojimą kaip atsakymo apribojimą iš viršaus, rekursija nenusileidžiant žemiau šio apribojimo. Jei radome kokį nors atsakymą, jis garantuotai bus optimalus, kitu atveju galime padidinti šią ribą vienu ir pradėti iš naujo.
Kitas būdas yra išsaugoti tam tikrą dabartinį optimalų atsakymą ir ieškoti mažesnio atsakymo, kai randamas, pakeisti šį parametrą k didesniam nereikalingų šakų pjovimui paieškoje.
Atlikęs keletą naktinių eksperimentų, apsisprendžiau šių dviejų metodų deriniu: pirma, paleidžiu savo algoritmą su tam tikru paieškos gylio apribojimu (pasirinkdamas jį taip, kad tai užtruktų nežymiai, palyginti su pagrindiniu sprendimu) ir naudoju geriausią. sprendimas rastas kaip viršutinė atsakymo riba – tai yra, į tą patį dalyką k.
2 laipsnio viršūnės
Mes nagrinėjome 0 ir 1 laipsnių viršūnes. Pasirodo, tai galima padaryti su 2 laipsnio viršūnėmis, tačiau tam reikės sudėtingesnių grafiko operacijų.
Norėdami tai paaiškinti, turime kažkaip pažymėti viršūnes. 2 laipsnio viršūnę vadinkime viršūne v, o jo kaimynai – viršūnės x и y. Toliau turėsime du atvejus.
- Kai x и y - kaimynai. Tada galite atsakyti x и yIr v Ištrinti. Iš šio trikampio mainais reikia paimti bent dvi viršūnes ir tikrai neprarasime, jei paimsime x и y: jie tikriausiai turi kitų kaimynų ir v Jų čia nėra.
- Kai x и y - ne kaimynai. Tada teigiama, kad visas tris viršūnes galima suklijuoti į vieną. Idėja yra ta, kad šiuo atveju yra optimalus atsakymas, kurį mes priimame bet kurį v, arba abi viršūnes x и y. Be to, pirmuoju atveju turėsime atsakyti į visus kaimynus x и y, bet antroje tai nėra būtina. Tai tiksliai atitinka tuos atvejus, kai atsakydami nepaimame suklijuotos viršūnės ir kai imame. Belieka tik pastebėti, kad abiem atvejais atsakas iš tokios operacijos sumažėja vienu.
Verta paminėti, kad šį metodą gana sunku tiksliai įgyvendinti teisingu tiesiniu laiku. Viršūnių klijavimas yra sudėtinga operacija, reikia nukopijuoti kaimynų sąrašus. Jei tai daroma neatsargiai, gali baigtis asimptotiškai neoptimali veikimo trukmė (pavyzdžiui, jei po kiekvieno klijavimo nukopijuosite daug kraštų). Aš nusprendžiau rasti ištisus kelius iš 2 laipsnio viršūnių ir išanalizuoti daugybę ypatingų atvejų, pavyzdžiui, ciklus iš tokių viršūnių arba iš visų tokių viršūnių, išskyrus vieną.
Be to, būtina, kad ši operacija būtų grįžtama, kad grįžus iš rekursijos atkurtume grafiką į pradinę formą. Siekdamas tai užtikrinti, aš neišvaliau sujungtų viršūnių briaunų sąrašų ir tada tiesiog žinojau, kurios briaunos turi būti kur. Šis grafikų įgyvendinimas taip pat reikalauja tikslumo, tačiau jis suteikia teisingą tiesinį laiką. O kelių dešimčių tūkstančių briaunų grafikams jis telpa į procesoriaus talpyklą, o tai suteikia didelių greičio pranašumų.
Linijinis branduolys
Galiausiai įdomiausia branduolio dalis.
Pirmiausia atminkite, kad dvišaliuose grafikuose mažiausią viršūnių viršūnę galima rasti naudojant . Norėdami tai padaryti, turite naudoti algoritmą norėdami rasti maksimalų atitikimą, tada naudokite teoremą .
Linijinio branduolio idėja yra tokia: pirmiausia padaliname grafiką, ty vietoj kiekvienos viršūnės v pridėkime dvi smailes и , o vietoj kiekvieno krašto u - v pridėkime du šonkaulius и . Gautas grafikas bus dvišalis. Raskime jame mažiausią viršūnės viršūnę. Kai kurios pradinio grafiko viršūnės ten pateks du kartus, kai kurios tik vieną kartą, o kitos niekada. Nemhauzerio-Troterio teorema teigia, kad tokiu atveju galima pašalinti viršūnes, kurios nepataikė net vieną kartą, ir atsiimti tas, kurios pataikė du kartus. Be to, ji sako, kad iš likusių viršūnių (tų, kurios pataikė vieną kartą) reikia priimti bent pusę atsakymo.
Mes ką tik išmokome palikti ne daugiau nei 2k viršūnės Iš tiesų, jei likęs atsakymas yra bent pusė visų viršūnių, tada iš viso viršūnių nėra daugiau nei 2k.
Čia galėjau žengti mažą žingsnelį į priekį. Akivaizdu, kad tokiu būdu sukonstruotas branduolys priklauso nuo to, kokį minimalų viršūnių dangtį paėmėme dvišaliame grafe. Norėčiau paimti vieną, kad likusių viršūnių skaičius būtų minimalus. Anksčiau jie tai galėjo padaryti tik laiku . Per tą laiką sugalvojau įgyvendinti šį algoritmą , taigi šio šerdies galima ieškoti šimtų tūkstančių viršūnių grafikuose kiekviename šakojimo etape.
Rezultatas
Praktika rodo, kad mano sprendimas gerai veikia kelių šimtų viršūnių ir kelių tūkstančių briaunų testuose. Tokiuose bandymuose visiškai įmanoma tikėtis, kad sprendimas bus rastas per pusvalandį. Tikimybė rasti atsakymą per priimtiną laiką iš esmės didėja, jei grafas turi pakankamai daug aukšto laipsnio viršūnių, pavyzdžiui, 10 ir aukštesnio laipsnio.
Norint dalyvauti konkurse, sprendimus reikėjo siųsti adresu . Sprendžiant iš ten pateiktos informacijos , mano sprendimas atviruose testuose užima trečią vietą iš dvidešimties, su dideliu skirtumu nuo antrosios. Atvirai kalbant, nėra iki galo aišku, kaip sprendimai bus vertinami pačiame konkurse: pavyzdžiui, mano sprendimas išlaiko mažiau testų nei ketvirtoje vietoje esantis sprendimas, tačiau išlaikiusiuosius veikia greičiau.
Uždarų testų rezultatai bus žinomi liepos XNUMX d.
Šaltinis: www.habr.com