Ikerketa lana da beharbada gure prestakuntzaren zatirik interesgarriena. Ideia zure burua aukeratutako norabidean saiatzea da unibertsitatean oraindik. Esaterako, Software Ingeniaritza eta Machine Learning arloetako ikasleak maiz joaten dira enpresetan ikerketa egitera (batez ere JetBrains edo Yandex, baina ez bakarrik).
Sarrera honetan Informatikako nire proiektuari buruz hitz egingo dut. Nire lanaren baitan, NP-gogor problema ospetsuenetako bat konpontzeko planteamenduak aztertu eta praktikan jarri nituen: erpinaren estalduraren arazoa.
Gaur egun, NP-gogor arazoei buruzko ikuspegi interesgarri bat oso azkar garatzen ari da: algoritmo parametrizatuak. Abiadura jartzen saiatuko naiz, parametrizatutako algoritmo sinple batzuk kontatzen eta asko lagundu zidan metodo indartsu bat deskribatzen. Nire emaitzak PACE Challenge lehiaketan aurkeztu nituen: proba irekien emaitzen arabera, nire irtenbidea hirugarren postua hartzen du, eta azken emaitzak uztailaren 1ean ezagutuko dira.
Niri buruz
Nire izena Vasily Alferov da, hirugarren urtea amaitzen ari naiz National Research University Ekonomia Goi Eskolan - San Petersburgo. Algoritmoak interesatzen zaizkit nire eskola garaitik, Moskuko 179. zenbakian ikasi nuen eta informatika-olinpiadetan arrakastaz parte hartu nuenetik.
Algoritmo parametrizatuetan espezialista kopuru finitu bat sartzen da barran...
Liburutik hartutako adibidea
Imajinatu herri txiki bateko tabernako segurtasun zaindaria zarela. Ostiralero, hiri erdia etortzen da zure tabernara erlaxatzera, eta horrek arazo asko ematen dizkizu: bezero zalapartatsuak tabernatik bota behar dituzu liskarrak saihesteko. Azkenean, aspertu egiten zara eta prebentzio neurriak hartzea erabakitzen duzu.
Zure hiria txikia denez, zehatz-mehatz badakizu zein bikote bikotek borrokatuko duten taberna batean elkarrekin bukatzen badute. Zerrendarik baduzu n gaur gauean tabernara etorriko den jendea. Herritar batzuk tabernatik kanpo uztea erabakitzen duzu inor borrokan sartu gabe. Aldi berean, zure nagusiek ez dute irabazirik galdu nahi eta zorigaiztoko izango dira baino gehiago uzten ez baduzu. k dute.
Zoritxarrez, zure aurrean duzun arazoa NP-gogor arazo klasikoa da. Agian ezagutuko duzu , edo erpin estaltzeko problema gisa. Horrelako arazoetarako, kasu orokorrean, ez dago denbora onargarrian funtzionatzen duen algoritmorik. Zehazki, frogatu gabeko eta nahiko sendoa den ETH hipotesiak (Exponential Time Hypothesis) dio arazo hau ezin dela denboran konpondu. , hau da, ezin zaizu bururatu bilaketa osoa baino nabarmen hoberik. Adibidez, demagun norbait zure tabernara etorriko dela n = 1000 Gizakia. Orduan bilaketa osoa izango da gutxi gorabehera dauden aukerak - kopuru zoroa. Zorionez, zure kudeaketak muga bat eman dizu k = 10, beraz, errepikatu behar duzun konbinazio kopurua askoz txikiagoa da: hamar elementuren azpimultzo kopurua da . Hau hobea da, baina oraindik ez da egun batean zenbatuko kluster indartsu batean ere.
Tabernako bisitarien arteko harreman estuen konfigurazio honetan borrokaren aukera ezabatzeko, Bob, Daniel eta Fedor kanpoan utzi behar dituzu. Ez dago irtenbiderik zeinetan bi bakarrik geratuko diren atzean.
Horrek esan nahi du amore emateko eta denei sartzen uzteko garaia dela? Azter ditzagun beste aukera batzuk. Beno, adibidez, ezin diezu sartu jende kopuru handi batekin borrokatzeko aukera dutenei bakarrik. Norbaitekin gutxienez borrokatu ahal bada k+1 beste pertsona bat, orduan, zalantzarik gabe, ezin diozu sartzen utzi; bestela, denak kanpoan utzi beharko dituzu k+1 herritarrak, zeinekin borrokatu ahal izateko, eta horrek behin betiko aztoratuko du lidergoa.
Bota dezazula printzipio honen arabera ahal dituzun guztiak. Orduan, beste guztiek baino gehiagorekin borrokatu ahal izango dute k jendea. Kanpora botatzea k gizona, ezin duzu ezer baino gehiago eragotzi gatazkak. Horrek esan nahi du baino gehiago badago Pertsona bat gutxienez gatazka batean parte hartzen badu, ezin dituzu guztiak saihestu. Noski, erabat gatazkarik gabeko jendea sartzen utziko duzunez, berrehun pertsonatik hamarreko azpimultzo guztiak pasatu behar dituzu. Badira gutxi gorabehera , eta eragiketa kopuru hori dagoeneko ordenatu daiteke klusterrean.
Gatazkarik ez duten pertsonak segurtasunez har ditzakezu, orduan zer gertatzen da gatazka bakarrean parte hartzen dutenekin? Izan ere, aurkariari atea itxita ere sar daitezke. Izan ere, Alice Bobrekin bakarrik gatazkan badago, orduan Alice bietatik ateratzen uzten badugu, ez dugu galduko: Bobek beste gatazka batzuk izan ditzake, baina Alicek, zalantzarik gabe, ez ditu. Gainera, ez du zentzurik bioi sartzen ez uzteak. Horrelako operazioen ondoren ez da gehiago geratzen konpondu gabeko patua duten gonbidatuak: besterik ez dugu gatazkak, bakoitzak bi parte-hartzailerekin eta bakoitzak gutxienez bitan parte hartzen du. Beraz, ordenatzea besterik ez da geratzen aukerak, ordenagailu eramangarri batean egun erdi bat erraz har daitezkeenak.
Izan ere, arrazoiketa sinpleekin baldintza are erakargarriagoak lor ditzakezu. Kontuan izan gatazka guztiak konpondu behar ditugula behin betiko, hau da, bikote gatazkatsu bakoitzetik, aukeratu gutxienez sartzen utziko ez dugun pertsona bat. Demagun algoritmo hau: hartu edozein gatazka, zeinetatik parte-hartzaile bat kentzen dugu eta errekurtsiboki gainerakotik abiatzen gara, gero bestea kendu eta errekurtsiboki ere hasiko gara. Urrats bakoitzean norbait botatzen dugunez, halako algoritmo baten errekurtsio zuhaitza sakoneko zuhaitz bitarra da k, beraz, guztira algoritmoak funtzionatzen du Non n erpin kopurua da, eta m - saihets-kopurua. Gure adibidean, hamar milioi inguru dira, segundo zati batean kalkulatu daitekeena ordenagailu eramangarri batean ez ezik, telefono mugikorrean ere.
Goiko adibidea adibide bat da algoritmo parametrizatua. Algoritmo parametrizatuak denboran exekutatzen diren algoritmoak dira f(k) poli(n)Non p - polinomioa, f funtzio konputagarri arbitrarioa da, eta k - parametroren bat, seguru asko, arazoaren tamaina baino askoz txikiagoa izango dena.
Algoritmo honen aurreko arrazoiketa guztiek adibide bat ematen dute kernelizazioa algoritmo parametrizatuak sortzeko teknika orokorretako bat da. Kernelizazioa arazoaren tamaina parametro baten funtzio batek mugatutako balio batera murriztea da. Sortzen den arazoari nukleoa deitzen zaio. Horrela, erpinen graduei buruzko arrazoiketa errazen bidez, Vertex Cover problemarako nukleo koadratiko bat lortu dugu, erantzunaren tamainaren arabera parametrizatuta. Zeregin honetarako aukera ditzakezun beste ezarpen batzuk (adibidez, Vertex Cover Above LP), baina hau da eztabaidatuko dugun ezarpena.
Erritmo Erronka
Lehiaketa (The Parameterized Algorithms and Computational Experiments Challenge) 2015ean jaio zen, konputazio-problemak ebazteko praktikan erabiltzen diren algoritmo parametrizatuen eta planteamenduen arteko lotura ezartzeko. Lehenengo hiru lehiaketak grafiko baten zuhaitzaren zabalera aurkitzera bideratu ziren (), Steiner zuhaitz baten bila () eta zikloak mozten dituen erpin multzo baten bila (). Aurten probatu dezakezun arazoetako bat goian deskribatutako erpin estaldura arazoa izan da.
Lehiaketa ospea lortzen ari da urtero. Aurretiazko datuak sinesten badituzu, aurten 24 taldek hartu dute parte erpinaren estalduraren arazoa bakarrik konpontzeko lehiaketan. Aipatzekoa da lehiaketak ez duela hainbat ordu edo aste bat ere irauten, hainbat hilabete baizik. Taldeek literatura aztertzeko, beren ideia originala atera eta hura gauzatzen saiatzeko aukera dute. Funtsean, lehiaketa hau ikerketa proiektu bat da. Konponbide eraginkorrenen ideiak eta irabazleen sari banaketa hitzaldiarekin batera egingo dira. (International Symposium on Parameterized and Exact Computation) Europako urteko bilera algoritmiko handienaren barruan. . Lehiaketa berari buruzko informazio zehatzagoa helbidean aurki daiteke , eta aurreko urteetako emaitzak datza .
Soluzio-diagrama
Erpinaren estalduraren problema konpontzeko, algoritmo parametrizatuak erabiltzen saiatu nintzen. Normalean bi zati dituzte: sinplifikazio-arauak (egokiena kernelizazioa ekartzen dutenak) eta zatiketa-arauak. Sinplifikazio-arauak sarreraren aurreprozesatzea dira denbora polinomikoan. Arau horiek aplikatzearen helburua arazoa arazo txikiago baliokide batera murriztea da. Sinplifikazio-arauak algoritmoaren zatirik garestiena dira, eta zati hori aplikatzeak exekuzio-denbora osoa lortzen du. denbora polinomiko sinplearen ordez. Gure kasuan, zatiketa-arauak erpin bakoitzerako erantzun gisa hartu behar dituzula edo bere aldamenean oinarritzen dira.
Eskema orokorra hau da: sinplifikazio-arauak aplikatzen ditugu, gero erpin batzuk hautatzen ditugu eta bi dei errekurtsibo egiten ditugu: lehenengoan erantzun moduan hartzen dugu, eta bestean bere aldamen guztiak hartzen ditugu. Honi erpin honetan zehar zatitzea (adarkatzea) deitzen diogu.
Eskema honi gehiketa bat egingo zaio hurrengo paragrafoan.
Arauak banatzeko (brunching) ideiak
Azter dezagun nola aukeratu zatiketa gertatuko den erpin bat.
Ideia nagusia oso zikoitza da zentzu algoritmikoan: har dezagun gradu maximoko erpin bat eta zatitu dezagun. Zergatik dirudi hobea? Dei errekurtsiboaren bigarren adarrean erpin asko kenduko ditugulako horrela. Grafiko txiki bat geratzen zaizula konta dezakezu eta azkar lan egin dezakegu.
Ikuspegi honek, lehendik eztabaidatutako kernelizazio-teknikekin, ondo erakusten du eta hainbat mila erpin tamainako proba batzuk ebazten ditu. Baina, adibidez, ez du ondo funtzionatzen grafiko kubikoetarako (hau da, erpin bakoitzaren gradua hirukoa duten grafikoetarako).
Badago ideia nahiko sinple batean oinarritutako beste ideia bat: grafikoa deskonektatuta badago, bere osagai konektatuen arazoa modu independentean ebatzi daiteke, amaieran erantzunak konbinatuz. Hau, bide batez, eskeman agindutako aldaketa txiki bat da, eta horrek irtenbidea nabarmen azkartuko du: lehen, kasu honetan, osagaien erantzunak kalkulatzeko denboraren produktua lantzen genuen, baina orain lan egiten dugu. batura. Eta adarkatzea bizkortzeko, konektatutako grafiko bat deskonektatu bat bihurtu behar duzu.
Nola egin? Grafikoan artikulazio puntu bat badago, horretan borrokatu behar duzu. Artikulazio-puntua erpin bat da, ezen, kentzean, grafikoak konektibitatea galtzen duela. Grafiko bateko juntura puntu guztiak algoritmo klasiko bat erabiliz aurki daitezke denbora linealean. Planteamendu honek nabarmen bizkortzen du adarkatzea.
Hautatutako erpinetakoren bat kentzen denean, grafikoa loturiko osagaietan zatituko da.
Hau egingo dugu, baina gehiago nahi dugu. Adibidez, bilatu grafikoan erpin ebaketa txikiak eta zatitu bertatik erpinetan zehar. Gutxieneko erpin ebaketa globala aurkitzeko ezagutzen dudan modurik eraginkorrena Gomori-Hu zuhaitz bat erabiltzea da, denbora kubikoan eraikita dagoena. PACE Challenge-n, grafikoaren tamaina tipikoa hainbat mila erpin da. Egoera honetan, errekurtsio zuhaitzaren erpin bakoitzean milaka milioi eragiketa egin behar dira. Bihurtzen da, besterik gabe, ezinezkoa dela arazoa emandako denboran konpontzea.
Saia gaitezen irtenbidea optimizatzen. Erpin pare baten arteko gutxieneko erpin ebakia fluxu maximoa eraikitzen duen edozein algoritmoren bidez aurki daiteke. Horrelako sare batean utz dezakezu , praktikan oso azkar funtzionatzen du. Susmoa dut teorikoki posible dela funtzionamendu-denboraren estimazio bat frogatzea , dagoeneko nahiko onargarria dena.
Hainbat aldiz saiatu nintzen ausazko erpin pareen arteko mozketak bilatzen eta orekatuena hartzen. Zoritxarrez, honek emaitza txarrak eman zituen PACE Challenge proba irekietan. Gehieneko graduko erpinak zatitzen dituen algoritmo batekin alderatu nuen, jaitsieraren sakoneraren mugarekin exekutatuz. Modu honetan ebaki bat aurkitzen saiatzen den algoritmo batek grafiko handiagoak utzi zituen. Hau da, mozketak oso desorekatuak izan zirelako: 5-10 erpin kenduta, 15-20 bakarrik zatitzea posible zen.
Azpimarratzekoa da teorikoki algoritmo azkarrenei buruzko artikuluek askoz teknika aurreratuagoak erabiltzen dituztela zatitzeko erpinak hautatzeko. Horrelako teknikek inplementazio oso konplexua dute eta askotan errendimendu eskasa denbora eta memoria aldetik. Ezin izan ditut identifikatu praktikarako nahiko onargarriak direnak.
Sinplifikazio-arauak nola aplikatu
Dagoeneko baditugu kernelizaziorako ideiak. Gogorarazten dizut:
- Erpin isolatu bat badago, ezabatu.
- 1. graduko erpin bat badago, kendu eta bere aldamena hartu erantzunez.
- Graduko erpin bat baldin badago behintzat k+1, hartu atzera.
Lehenengo biekin dena argi dago, hirugarrenarekin trikimailu bat dago. Taberna bati buruzko komiki-arazo batean goi-muga bat ematen ziguten k, orduan PACE Challenge-n gutxieneko tamainako erpin-estalkia aurkitu besterik ez duzu behar. Hau Bilaketa-arazoen eraldaketa tipikoa da Erabaki-arazoetan; askotan ez dago bi arazo-moten arteko alderik. Praktikan, erpinaren estalduraren problemarako ebazlea idazten ari bagara, aldea egon daiteke. Adibidez, hirugarren puntuan bezala.
Ezarpenaren ikuspuntutik, aurrera egiteko bi modu daude. Lehenengo hurbilketa Iterative Deepening deitzen da. Honela da: erantzuna behetik arrazoizko murrizketa batekin has gaitezke, eta gero exekutatu gure algoritmoa muga hori goiko erantzunaren muga gisa erabiliz, murrizketa hau baino errekurtsioan baxuago joan gabe. Erantzunren bat aurkitu badugu, optimoa izango dela ziurtatuta dago, bestela muga hori bat handitu eta berriro hasteko.
Beste ikuspegi bat egungo erantzun optimoren bat gordetzea eta erantzun txikiagoa bilatzea da, parametro hau aurkitzen denean aldatuz k bilaketan beharrezkoak ez diren adarrak mozteko.
Gaueko hainbat esperimentu egin ondoren, bi metodo hauen konbinazio batekin finkatu nintzen: lehenik eta behin, nire algoritmoa bilaketa-sakoneraren nolabaiteko mugarekin exekutatzen dut (hautatuz, soluzio nagusiarekin alderatuta denbora gutxi behar izan dezan) eta onena erabiltzen dut. erantzunaren goiko muga gisa aurkitutako soluzioa, hau da, gauza berari k.
2. graduko erpinak
0 eta 1 graduko erpinez aritu gara. Ematen du hori 2. graduko erpinekin egin daitekeela, baina honek grafikotik eragiketa konplexuagoak beharko ditu.
Hori azaltzeko, erpinak nolabait izendatu behar ditugu. Dei diezaiogun 2 graduko erpin bati erpin v, eta bere ingurukoak - erpinak x ΠΈ y. Jarraian, bi kasu izango ditugu.
- Noiz x ΠΈ y - bizilagunak. Orduan erantzun dezakezu x ΠΈ yEta v ezabatu. Izan ere, triangelu honetatik gutxienez bi erpin hartu behar dira trukean, eta zalantzarik gabe ez dugu galduko hartzen badugu. x ΠΈ y: ziurrenik beste auzokide batzuk dituzte, eta v ez dira.
- Noiz x ΠΈ y - ez auzokoak. Orduan, hiru erpinak bakarrean itsatsi daitezkeela adierazten da. Ideia da kasu honetan erantzun optimo bat dagoela, zeinetan bai hartzen dugun v, edo bi erpinak x ΠΈ y. Gainera, lehenengo kasuan auzokide guztiak hartu beharko ditugu erantzuna x ΠΈ y, baina bigarrenean ez da beharrezkoa. Honek erantzun moduan itsatsitako erpina hartzen ez dugun kasuekin eta egiten dugunean dago. Kontuan izan behar da bi kasuetan eragiketa baten erantzuna bat jaisten dela.
Aipatzekoa da ikuspegi hau nahiko zaila dela denbora linealean zehaztasunez ezartzea. Erpinak itsastea eragiketa konplexua da; auzokideen zerrendak kopiatu behar dituzu. Axolagabekeriaz egiten bada, asintotikoki ez den exekuzio denborarekin amai dezakezu (adibidez, itsatsi bakoitzaren ondoren ertz asko kopiatzen badituzu). 2. graduko erpinetatik bide osoak bilatzea eta kasu berezi mordoa aztertzea erabaki nuen, hala nola, halako erpinetako zikloak edo bata izan ezik halako erpin guztietatik.
Horrez gain, beharrezkoa da eragiketa hau itzulgarria izatea, errekurtsiotik itzultzean grafikoa jatorrizko formara berreskuratzeko. Hori ziurtatzeko, ez ditut garbitu bateratutako erpinen ertz-zerrendak, eta orduan banekien zein ertz joan behar zen nora. Grafikoen ezarpen honek zehaztasuna ere eskatzen du, baina nahiko denbora lineala eskaintzen du. Eta hainbat hamarnaka ertzetako grafikoetarako, prozesadorearen cachean sartzen da, eta horrek abantaila handiak ematen ditu abiaduran.
Nukleo lineala
Azkenik, nukleoaren zatirik interesgarriena.
Hasteko, gogoratu grafiko bipartituetan erpin-estaldura minimoa erabiliz aurki daitekeela . Horretarako algoritmoa erabili behar duzu hor parekatze maximoa aurkitzeko, eta gero teorema erabili .
Nukleo lineal baten ideia hau da: lehenik grafikoa bifurkatzen dugu, hau da, erpin bakoitzaren ordez. v gehi ditzagun bi gailur ΠΈ , eta ertz bakoitzaren ordez u - v gehi ditzagun bi saiheski ΠΈ . Lortutako grafikoa bipartida izango da. Aurkitu dezagun bertan erpinaren estaldura minimoa. Jatorrizko grafikoaren erpin batzuk bi aldiz iritsiko dira bertara, batzuk behin bakarrik eta beste batzuk inoiz ez. Nemhauser-Trotter teoremak dio kasu honetan behin ere jo ez duten erpinak kendu eta bi aldiz jo dutenak kendu daitezkeela. Gainera, gainerako erpinetatik (behin jotzen dutenetatik) erantzun gisa gutxienez erdia hartu behar duzula dio.
Ez baino gehiago uzten ikasi berri dugu 2k gailurrak Izan ere, gainerako erantzuna erpin guztien erdia gutxienez bada, orduan ez dago guztira erpin gehiago 2k.
Hemen pauso txiki bat eman ahal izan nuen. Argi dago era honetan eraikitako nukleoa grafiko bipartiduan hartu dugun erpin-estaldura minimoaren araberakoa dela. Bat hartu nahiko nuke geratzen diren erpin kopurua minimoa izan dadin. Aurretik, denboran bakarrik egin ahal izan zuten . Garai hartan algoritmo honen inplementazio bat asmatu nuen , beraz, nukleo hori ehunka mila erpineko grafikoetan bila daiteke adarkatze fase bakoitzean.
Emaitza
Praktikak erakusten du nire soluzioak ondo funtzionatzen duela ehunka erpin eta hainbat milaka ertzetako probetan. Halako probetan nahiko posible da ordu erdian irtenbidea topatuko dela espero. Erantzuna denbora onargarrian aurkitzeko probabilitatea, printzipioz, handitu egiten da grafikoak maila handiko erpin kopuru aski handia badu, adibidez, 10. gradukoa eta handiagoa.
Lehiaketan parte hartzeko, irtenbideak bidali behar ziren . Bertan aurkeztutako informazioa ikusita , proba irekietan nire soluzioa hogeitatik hirugarren postuan kokatzen da, bigarrenarekiko tarte handi batekin. Erabat zintzoa izateko, ez dago guztiz argi konponbideak lehiaketan bertan nola baloratuko diren: adibidez, nire soluzioak laugarren postuan soluzioak baino proba gutxiago gainditzen ditu, baina gainditzen dutenetan azkarrago funtzionatzen du.
Proba itxien emaitzak uztailaren XNUMXean ezagutuko dira.
Iturria: www.habr.com