Puna kërkimore është ndoshta pjesa më interesante e trajnimit tonë. Ideja është të provoni veten në drejtimin tuaj të zgjedhur ndërsa jeni ende në universitet. Për shembull, studentët nga fushat e Inxhinierisë së Softuerit dhe Mësimit të Makinerisë shpesh shkojnë për të bërë kërkime në kompani (kryesisht JetBrains ose Yandex, por jo vetëm).
Në këtë postim do të flas për projektin tim në Shkenca Kompjuterike. Si pjesë e punës sime, kam studiuar dhe vënë në praktikë qasjet për zgjidhjen e një prej problemeve më të famshme të NP-të vështira: problemi i mbulimit të kulmeve.
Në ditët e sotme, një qasje interesante ndaj problemeve NP-hard po zhvillohet shumë shpejt - algoritmet e parametrizuar. Do të përpiqem t'ju bëj të shpejtë, t'ju tregoj disa algoritme të thjeshta të parametrizuara dhe të përshkruaj një metodë të fuqishme që më ndihmoi shumë. Unë i paraqita rezultatet e mia në konkursin e Sfidës së PACE: sipas rezultateve të testeve të hapura, zgjidhja ime zë vendin e tretë, dhe rezultatet përfundimtare do të dihen më 1 korrik.
Rreth vetes sime
Unë quhem Vasily Alferov, tani po mbaroj vitin e tretë në Shkollën e Lartë Ekonomike të Universitetit Kombëtar të Kërkimeve - Shën Petersburg. Unë kam qenë i interesuar për algoritmet që në ditët e shkollës, kur studiova në shkollën nr. 179 të Moskës dhe mora pjesë me sukses në olimpiadat e shkencave kompjuterike.
Një numër i kufizuar specialistësh në algoritme të parametrizuar hyjnë në shiritin...
Shembull i marrë nga libri
Imagjinoni që jeni një roje sigurie bari në një qytet të vogël. Çdo të premte, gjysma e qytetit vjen në lokalin tuaj për t'u çlodhur, gjë që ju sjell shumë telashe: duhet të largoni klientët e zhurmshëm nga lokali për të parandaluar grindjet. Përfundimisht, ju jeni të ngopur dhe vendosni të merrni masa parandaluese.
Meqenëse qyteti juaj është i vogël, ju e dini saktësisht se cilat çifte klientësh ka të ngjarë të luftojnë nëse përfundojnë në një lokal së bashku. A keni një listë të n njerëzit që do të vijnë në bar sonte. Ju vendosni të mbani disa banorë të qytetit jashtë lokalit pa u grindur askush. Në të njëjtën kohë, shefat tuaj nuk duan të humbasin fitime dhe do të jenë të pakënaqur nëse nuk lejoni më shumë se k njerëz.
Fatkeqësisht, problemi përpara jush është një problem klasik i NP-së. Ju mund ta njihni atë si , ose si një problem që mbulon kulmin. Për probleme të tilla, në rastin e përgjithshëm, nuk ka algoritme që funksionojnë në një kohë të pranueshme. Për të qenë të saktë, hipoteza e paprovuar dhe mjaft e fortë ETH (Hipoteza e kohës eksponenciale) thotë se ky problem nuk mund të zgjidhet në kohë. , domethënë, nuk mund të mendoni për ndonjë gjë dukshëm më të mirë se një kërkim i plotë. Për shembull, le të themi se dikush do të vijë në lokalin tuaj n = 1000 Njerëzore. Atëherë do të jetë kërkimi i plotë opsionet që ekzistojnë përafërsisht - sasi e çmendur. Për fat të mirë, menaxhmenti juaj ju ka dhënë një kufi k = 10, kështu që numri i kombinimeve që duhet të përsërisni është shumë më i vogël: numri i nëngrupeve prej dhjetë elementësh është . Kjo është më mirë, por gjithsesi nuk do të llogaritet në një ditë edhe në një grup të fuqishëm.
Për të eliminuar mundësinë e një zënke në këtë konfigurim të marrëdhënieve të tensionuara midis vizitorëve të lokalit, duhet të mbani jashtë Bob, Daniel dhe Fedor. Nuk ka zgjidhje në të cilën do të mbeten vetëm dy.
A do të thotë kjo se është koha për t'u dorëzuar dhe për t'i lënë të gjithë të hyjnë? Le të shqyrtojmë opsionet e tjera. Epo, për shembull, nuk mund të lejoni vetëm ata që ka të ngjarë të luftojnë me një numër shumë të madh njerëzish. Nëse dikush mund të luftojë të paktën me k+1 një person tjetër, atëherë definitivisht nuk mund ta lini të hyjë - përndryshe do t'ju duhet t'i mbani të gjithë jashtë k+1 banorë të qytetit, me të cilët ai mund të luftojë, gjë që patjetër do të shqetësojë udhëheqjen.
Le të flakësh të gjithë që mundesh sipas këtij parimi. Atëherë të gjithë të tjerët mund të luftojnë me jo më shumë se k njerëzit. Duke i hedhur jashtë k njeri, nuk mund të parandalosh asgjë më shumë se konfliktet. Kjo do të thotë se nëse ka më shumë se Nëse një person është i përfshirë në të paktën një konflikt, atëherë sigurisht që nuk mund t'i parandaloni të gjitha. Meqenëse, sigurisht, patjetër që do të lejoni të hyjnë njerëz plotësisht pa konflikt, duhet të kaloni nëpër të gjitha nëngrupet e madhësisë dhjetë nga dyqind njerëz. Ka afërsisht , dhe ky numër operacionesh tashmë mund të zgjidhet në grup.
Nëse mund të marrësh me siguri individë që nuk kanë fare konflikt, atëherë ç'të themi për ata që marrin pjesë vetëm në një konflikt? Në fakt, ata gjithashtu mund të lejohen duke i mbyllur derën kundërshtarit të tyre. Në të vërtetë, nëse Alice është në konflikt vetëm me Bobin, atëherë nëse e lëmë Alice-n nga ata të dy, ne nuk do të humbasim: Bob mund të ketë konflikte të tjera, por Alice sigurisht që nuk i ka. Për më tepër, nuk ka kuptim që ne të mos na lejojmë të dy të hyjmë. Pas operacioneve të tilla nuk mbetet më mysafirë me një fat të pazgjidhur: kemi vetëm konflikte, secili me dy pjesëmarrës dhe secili i përfshirë në të paktën dy. Pra, gjithçka që mbetet është të zgjidhet opsione, të cilat lehtë mund të konsiderohen gjysmë dite në një laptop.
Në fakt, me arsyetim të thjeshtë mund të arrini kushte edhe më tërheqëse. Vini re se ne patjetër duhet të zgjidhim të gjitha mosmarrëveshjet, domethënë, nga çdo palë konfliktuale, të zgjedhim të paktën një person të cilin nuk do ta lejojmë të hyjë. Le të shqyrtojmë algoritmin e mëposhtëm: marrim çdo konflikt, nga i cili heqim një pjesëmarrës dhe fillojmë në mënyrë rekursive nga pjesa e mbetur, pastaj heqim tjetrin dhe gjithashtu fillojmë në mënyrë rekursive. Meqenëse ne hedhim dikë jashtë në çdo hap, pema e rekursionit të një algoritmi të tillë është një pemë binare e thellësisë k, pra në total algoritmi funksionon Ku n është numri i kulmeve, dhe m - numri i brinjëve. Në shembullin tonë, kjo është rreth dhjetë milionë, të cilat mund të llogariten në një pjesë të sekondës jo vetëm në një laptop, por edhe në një telefon celular.
Shembulli i mësipërm është një shembull algoritmi i parametrizuar. Algoritmet e parametrizuar janë algoritme që funksionojnë në kohë f(k) poli(n)Ku p - polinom, f është një funksion i llogaritshëm arbitrar, dhe k - ndonjë parametër, i cili, me shumë mundësi, do të jetë shumë më i vogël se madhësia e problemit.
I gjithë arsyetimi para këtij algoritmi jep një shembull kernelizimi është një nga teknikat e përgjithshme për krijimin e algoritmeve të parametrizuara. Kernelizimi është zvogëlimi i madhësisë së problemit në një vlerë të kufizuar nga një funksion i një parametri. Problemi që rezulton shpesh quhet kernel. Kështu, duke arsyetuar thjesht për shkallët e kulmeve, përftuam një bërthamë kuadratike për problemin e mbulesës së kulmit, të parametrizuar nga madhësia e përgjigjes. Ka cilësime të tjera që mund të zgjidhni për këtë detyrë (si p.sh. Vertex Cover Above LP), por ky është cilësimi që do të diskutojmë.
Sfida e ritmit
Konkurs (Sfida e Algoritmeve të Parametizuara dhe Eksperimenteve Llogaritëse) lindi në vitin 2015 për të krijuar një lidhje midis algoritmeve të parametrizuara dhe qasjeve të përdorura në praktikë për zgjidhjen e problemeve llogaritëse. Tre konkurset e para iu kushtuan gjetjes së gjerësisë së pemës së një grafiku (), duke kërkuar për një pemë Steiner () dhe duke kërkuar për një grup kulmesh që shkurtojnë ciklet (). Këtë vit, një nga problemet në të cilat mund të provonit ishte problemi i mbulimit të kulmit të përshkruar më sipër.
Konkursi po fiton popullaritet çdo vit. Nëse u besoni të dhënave paraprake, këtë vit 24 skuadra morën pjesë në garë për të zgjidhur vetëm problemin e mbulimit të kulmit. Vlen të theksohet se konkursi zgjat jo disa orë apo edhe një javë, por disa muaj. Ekipet kanë mundësinë të studiojnë literaturën, të dalin me idenë e tyre origjinale dhe të përpiqen ta zbatojnë atë. Në thelb, ky konkurs është një projekt kërkimor. Idetë për zgjidhjet më efektive dhe çmimet e fituesve do të mbahen së bashku me konferencën (Simpoziumi Ndërkombëtar mbi llogaritjen e parametrizuar dhe të saktë) si pjesë e takimit më të madh vjetor algoritmik në Evropë . Informacione më të hollësishme rreth vetë konkursit mund të gjenden në , dhe rezultatet e viteve të mëparshme gënjejnë .
Diagrami i zgjidhjes
Për të zgjidhur problemin e mbulimit të kulmit, u përpoqa të përdor algoritme të parametrizuara. Ato zakonisht përbëhen nga dy pjesë: rregullat e thjeshtimit (të cilat në mënyrë ideale çojnë në kernelizimin) dhe rregullat e ndarjes. Rregullat e thjeshtimit janë parapërpunimi i hyrjes në kohë polinomiale. Qëllimi i zbatimit të rregullave të tilla është reduktimi i problemit në një problem ekuivalent më të vogël. Rregullat e thjeshtimit janë pjesa më e shtrenjtë e algoritmit, dhe aplikimi i kësaj pjese çon në kohën totale të funksionimit në vend të kohës së thjeshtë polinomiale. Në rastin tonë, rregullat e ndarjes bazohen në faktin se për secilën kulm duhet të merrni ose atë ose fqinjin e tij si përgjigje.
Skema e përgjithshme është kjo: zbatojmë rregullat e thjeshtimit, më pas zgjedhim një kulm dhe bëjmë dy thirrje rekursive: në të parën e marrim si përgjigje dhe në tjetrën marrim të gjithë fqinjët e saj. Kjo është ajo që ne e quajmë ndarje (degëzim) përgjatë këtij kulmi.
Pikërisht një shtesë do t'i bëhet kësaj skeme në paragrafin tjetër.
Ide për rregullat e ndarjes (brunching).
Le të diskutojmë se si të zgjedhim një kulm përgjatë së cilës do të ndodhë ndarja.
Ideja kryesore është shumë e pangopur në kuptimin algoritmik: le të marrim një kulm të shkallës maksimale dhe të ndajmë përgjatë tij. Pse duket më mirë? Sepse në degën e dytë të thirrjes rekursive do të heqim shumë kulme në këtë mënyrë. Mund të mbështeteni në një grafik të vogël të mbetur dhe ne mund të punojmë shpejt me të.
Kjo qasje, me teknikat e thjeshta të kernelizimit të diskutuara tashmë, shfaqet mirë dhe zgjidh disa teste me madhësi disa mijëra kulmesh. Por, për shembull, nuk funksionon mirë për grafikët kub (d.m.th., grafikët, shkalla e të cilëve e çdo kulmi është tre).
Ekziston një ide tjetër e bazuar në një ide mjaft të thjeshtë: nëse grafiku shkëputet, problemi në përbërësit e tij të lidhur mund të zgjidhet në mënyrë të pavarur, duke kombinuar përgjigjet në fund. Ky, meqë ra fjala, është një modifikim i vogël i premtuar në skemë, i cili do të përshpejtojë ndjeshëm zgjidhjen: më parë, në këtë rast, ne kemi punuar për produktin e kohës për llogaritjen e përgjigjeve të përbërësve, por tani punojmë për Shuma. Dhe për të shpejtuar degëzimin, duhet të ktheni një grafik të lidhur në një të shkëputur.
Si ta bëjmë atë? Nëse ka një pikë artikulimi në grafik, duhet të luftoni për të. Një pikë artikulimi është një kulm i tillë që kur hiqet, grafiku humbet lidhjen e tij. Të gjitha pikat e kryqëzimit në një grafik mund të gjenden duke përdorur një algoritëm klasik në kohë lineare. Kjo qasje shpejton ndjeshëm degëzimin.
Kur hiqet ndonjë nga kulmet e zgjedhura, grafiku do të ndahet në komponentë të lidhur.
Ne do ta bëjmë këtë, por duam më shumë. Për shembull, shikoni për prerje të vogla të kulmeve në grafik dhe ndani përgjatë kulmeve prej tij. Mënyra më efikase që di për të gjetur prerjen minimale globale të kulmit është të përdor një pemë Gomori-Hu, e cila është ndërtuar në kohë kub. Në sfidën PACE, madhësia tipike e grafikut është disa mijëra kulme. Në këtë situatë, miliarda operacione duhet të kryhen në çdo kulm të pemës së rekursionit. Rezulton se është thjesht e pamundur të zgjidhet problemi në kohën e caktuar.
Le të përpiqemi të optimizojmë zgjidhjen. Prerja minimale e kulmit ndërmjet një çifti kulmesh mund të gjendet nga çdo algoritëm që ndërton një rrjedhë maksimale. Ju mund ta lini atë në një rrjet të tillë , në praktikë funksionon shumë shpejt. Unë kam një dyshim se teorikisht është e mundur të vërtetohet një vlerësim për kohën e funksionimit , e cila tashmë është mjaft e pranueshme.
U përpoqa disa herë të kërkoja prerje midis çifteve të kulmeve të rastësishme dhe të merrja atë më të ekuilibruar. Fatkeqësisht, kjo prodhoi rezultate të dobëta në testimin e hapur të Sfidës së PACE. E krahasova me një algoritëm që ndan kulmet e shkallës maksimale, duke i drejtuar ato me një kufizim në thellësinë e zbritjes. Një algoritëm që përpiqet të gjejë një prerje në këtë mënyrë la pas grafikë më të mëdhenj. Kjo për faktin se shkurtimet rezultuan të ishin shumë të pabalancuara: duke hequr 5-10 kulme, ishte e mundur të ndaheshin vetëm 15-20.
Vlen të përmendet se artikujt rreth algoritmeve teorikisht më të shpejta përdorin teknika shumë më të avancuara për zgjedhjen e kulmeve për ndarje. Teknika të tilla kanë zbatim shumë kompleks dhe shpesh performancë të dobët për sa i përket kohës dhe kujtesës. Nuk isha në gjendje të identifikoja ato që janë mjaft të pranueshme për praktikë.
Si të aplikoni rregullat e thjeshtimit
Tashmë kemi ide për kernelizimin. Më lejoni t'ju kujtoj:
- Nëse ka një kulm të izoluar, fshijeni atë.
- Nëse ka një kulm të shkallës 1, hiqeni atë dhe merrni fqinjin e tij si përgjigje.
- Nëse ka të paktën një kulm të shkallës k+1, merre mbrapsht.
Me dy të parat gjithçka është e qartë, me të tretën ka një mashtrim. Nëse në një problem komik për një lokal na jepej një kufi i sipërm i k, atëherë në Sfidën PACE ju duhet vetëm të gjeni një mbulesë kulmore të madhësisë minimale. Ky është një transformim tipik i Problemeve të Kërkimit në Probleme Vendimi; shpesh nuk ka asnjë ndryshim midis dy llojeve të problemeve. Në praktikë, nëse po shkruajmë një zgjidhës për problemin e mbulimit të kulmit, mund të ketë një ndryshim. Për shembull, si në pikën e tretë.
Nga pikëpamja e zbatimit, ekzistojnë dy mënyra për të vazhduar. Qasja e parë quhet Thellimi Iterativ. Është si më poshtë: ne mund të fillojmë me një kufizim të arsyeshëm nga poshtë për përgjigjen, dhe më pas të ekzekutojmë algoritmin tonë duke përdorur këtë kufizim si kufizim për përgjigjen nga lart, pa shkuar më poshtë në rekursion se ky kufizim. Nëse kemi gjetur ndonjë përgjigje, është e garantuar të jetë optimale, përndryshe mund ta rrisim këtë kufi me një dhe të fillojmë përsëri.
Një qasje tjetër është ruajtja e disa përgjigjeve aktuale optimale dhe kërkimi i një përgjigjeje më të vogël, duke ndryshuar këtë parametër kur gjendet k për prerje më të madhe të degëve të panevojshme në kërkim.
Pas kryerjes së disa eksperimenteve gjatë natës, u vendosa në një kombinim të këtyre dy metodave: së pari, ekzekutoj algoritmin tim me një lloj kufiri në thellësinë e kërkimit (duke e zgjedhur atë në mënyrë që të marrë kohë të papërfillshme në krahasim me zgjidhjen kryesore) dhe përdor më të mirën. zgjidhja e gjetur si kufi i sipërm i përgjigjes - domethënë për të njëjtën gjë k.
Kulmet e shkallës 2
Kemi trajtuar kulme të shkallës 0 dhe 1. Rezulton se kjo mund të bëhet me kulme të shkallës 2, por kjo do të kërkojë operacione më komplekse nga grafiku.
Për ta shpjeguar këtë, ne duhet të përcaktojmë disi kulmet. Le ta quajmë kulm të shkallës 2 kulm v, dhe fqinjët e saj - kulmet x и y. Më pas do të kemi dy raste.
- Kur x и y - fqinjët. Atëherë mund të përgjigjeni x и yDhe v fshij. Në të vërtetë, nga ky trekëndësh duhet të merren të paktën dy kulme në këmbim dhe ne patjetër nuk do të humbasim nëse marrim x и y: ata ndoshta kanë fqinjë të tjerë, dhe v ata nuk janë të.
- Kur x и y - jo fqinjët. Pastaj thuhet se të tre kulmet mund të ngjiten në një. Ideja është që në këtë rast ka një përgjigje optimale, në të cilën ne marrim ose v, ose të dyja kulmet x и y. Për më tepër, në rastin e parë do të duhet të marrim të gjithë fqinjët si përgjigje x и y, por në të dytën nuk është e nevojshme. Kjo përkon saktësisht me rastet kur nuk e marrim kulmin e ngjitur në përgjigje dhe kur e marrim. Mbetet vetëm të theksohet se në të dyja rastet përgjigja nga një operacion i tillë zvogëlohet me një.
Vlen të përmendet se kjo qasje është mjaft e vështirë për t'u zbatuar me saktësi në kohë të drejtë lineare. Ngjitja e kulmeve është një operacion kompleks; ju duhet të kopjoni listat e fqinjëve. Nëse kjo bëhet pa kujdes, mund të përfundoni me kohë pune asimptotike jo optimale (për shembull, nëse kopjoni shumë skaje pas çdo ngjitjeje). U vendosa të gjeja shtigje të tëra nga kulmet e shkallës 2 dhe të analizoja një sërë rastesh të veçanta, si cikle nga kulme të tilla ose nga të gjitha kulmet e tilla përveç njërit.
Përveç kësaj, është e nevojshme që ky operacion të jetë i kthyeshëm, në mënyrë që kur të kthehemi nga rekursioni ta kthejmë grafikun në formën e tij origjinale. Për ta siguruar këtë, nuk i pastrova listat e skajeve të kulmeve të bashkuara dhe më pas e dija se cilat skaje duhej të shkonin ku. Ky zbatim i grafikëve kërkon gjithashtu saktësi, por siguron një kohë të drejtë lineare. Dhe për grafikët e disa dhjetëra mijëra skajeve, ai përshtatet në cache të procesorit, i cili jep avantazhe të mëdha në shpejtësi.
Bërthama lineare
Më në fund, pjesa më interesante e kernelit.
Për të filluar, kujtoni se në grafikët dypalësh, mbulesa minimale e kulmit mund të gjendet duke përdorur . Për ta bërë këtë ju duhet të përdorni algoritmin në mënyrë që të gjeni përputhjen maksimale atje, dhe më pas përdorni teoremën .
Ideja e një kerneli linear është kjo: së pari ne bifurkojmë grafikun, domethënë në vend të çdo kulmi. v le të shtojmë dy maja и , dhe në vend të çdo skaji u - v le të shtojmë dy brinjë и . Grafiku që rezulton do të jetë dypalësh. Le të gjejmë mbulesën minimale të kulmit në të. Disa kulme të grafikut origjinal do të arrijnë atje dy herë, disa vetëm një herë dhe disa kurrë. Teorema Nemhauser-Trotter thotë se në këtë rast mund të hiqen kulmet që nuk kanë goditur as një herë dhe të kthehen ato që kanë goditur dy herë. Për më tepër, ajo thotë se nga kulmet e mbetura (ato që godasin një herë) duhet të marrësh të paktën gjysmën si përgjigje.
Ne sapo kemi mësuar të largohemi jo më shumë se 2k majat Në të vërtetë, nëse përgjigja e mbetur është të paktën gjysma e të gjitha kulmeve, atëherë nuk ka më shumë kulme në total se 2k.
Këtu munda të bëja një hap të vogël përpara. Është e qartë se kerneli i ndërtuar në këtë mënyrë varet nga lloji i mbulesës minimale të kulmit që kemi marrë në grafikun dypalësh. Do të doja të merrja një në mënyrë që numri i kulmeve të mbetura të jetë minimal. Më parë, ata ishin në gjendje ta bënin këtë vetëm në kohë . Unë dola me një implementim të këtij algoritmi në atë kohë , pra, kjo bërthamë mund të kërkohet në grafikët e qindra mijëra kulmeve në çdo fazë degëzimi.
Result
Praktika tregon se zgjidhja ime funksionon mirë në testet e disa qindra kulmeve dhe disa mijëra skajeve. Në teste të tilla është mjaft e mundur të pritet që një zgjidhje të gjendet në gjysmë ore. Probabiliteti për të gjetur një përgjigje në një kohë të pranueshme, në parim, rritet nëse grafiku ka një numër mjaft të madh kulmesh të shkallës së lartë, për shembull, shkalla 10 dhe më e lartë.
Për të marrë pjesë në konkurs, duhet të dërgoheshin zgjidhje . Duke gjykuar nga informacioni i paraqitur atje , zgjidhja ime në testet e hapura renditet e treta nga njëzet, me një diferencë të madhe nga e dyta. Për të qenë plotësisht i sinqertë, nuk është plotësisht e qartë se si do të vlerësohen zgjidhjet në vetë konkursin: për shembull, zgjidhja ime kalon më pak teste se zgjidhja në vendin e katërt, por në ato që kalojnë, funksionon më shpejt.
Rezultatet e testeve të mbyllura do të bëhen të ditura më XNUMX korrik.
Burimi: www.habr.com