Tədqiqat işi bəlkə də təlimimizin ən maraqlı hissəsidir. İdeya hələ universitetdə olarkən seçdiyiniz istiqamətdə özünüzü sınamaqdır. Məsələn, Proqram Mühəndisliyi və Maşın Öyrənmə sahələrindən olan tələbələr tez-tez şirkətlərdə tədqiqat aparmağa gedirlər (əsasən JetBrains və ya Yandex, lakin təkcə deyil).
Bu yazıda Kompüter Elmləri üzrə layihəm haqqında danışacağam. İşimin bir hissəsi olaraq ən məşhur NP çətin problemlərindən birinin həllinə yanaşmaları öyrəndim və tətbiq etdim: vertex əhatə problemi.
Hal-hazırda, NP-çətin məsələlərə maraqlı bir yanaşma çox sürətlə inkişaf edir - parametrli alqoritmlər. Mən sizi sürətləndirməyə çalışacağam, sizə bir neçə sadə parametrli alqoritmləri izah edəcəyəm və mənə çox kömək edən bir güclü metodu təsvir edəcəyəm. Mən nəticələrimi PACE Challenge müsabiqəsində təqdim etdim: açıq testlərin nəticələrinə görə mənim həllim üçüncü yeri tutur və yekun nəticələr iyulun 1-də məlum olacaq.
About Me
Mənim adım Vasili Alferov, mən indi Milli Tədqiqat Universitetinin Ali İqtisadiyyat Məktəbində - Sankt-Peterburqda üçüncü kursumu bitirirəm. Məktəb vaxtlarımdan, Moskvanın 179 nömrəli məktəbində oxuduğum və informatika olimpiadalarında uğurla iştirak etdiyim vaxtdan alqoritmlərə marağım olub.
Parametrləşdirilmiş alqoritmlər üzrə məhdud sayda mütəxəssis bara daxil olur...
Nümunə kitabdan götürülmüşdür
Təsəvvür edin ki, siz kiçik bir şəhərdə barın mühafizəçisisiniz. Hər cümə günü şəhərin yarısı dincəlmək üçün barınıza gəlir ki, bu da sizə çox problem yaradır: dava-dalaşın qarşısını almaq üçün qəzəbli müştəriləri bardan bayıra atmaq lazımdır. Nəhayət, siz bezirsiniz və profilaktik tədbirlər görməyə qərar verirsiniz.
Şəhəriniz kiçik olduğundan, hansı cütlərin birlikdə bir bara girsələr, döyüşə biləcəyini dəqiq bilirsiniz. Siyahınız varmı n bu axşam bara gələcək insanlar. Siz heç kimin davasına girmədən bəzi şəhər sakinlərini bardan kənarda saxlamağa qərar verdiniz. Eyni zamanda, müdirləriniz qazanc itirmək istəmir və daha çox imkan verməsəniz, bədbəxt olacaqlar. k insanlar.
Təəssüf ki, qarşınızda duran problem klassik NP çətin problemdir. Onu tanıya bilərsən , və ya vertex əhatə edən problem kimi. Belə problemlər üçün, ümumi halda, məqbul vaxtda işləyən alqoritmlər yoxdur. Dəqiq desək, sübut olunmamış və kifayət qədər güclü hipotez ETH (Exponential Time Hypothesis) deyir ki, bu problemi vaxtında həll etmək mümkün deyil. , yəni tam axtarışdan nəzərəçarpacaq dərəcədə yaxşı bir şey düşünə bilməzsiniz. Məsələn, deyək ki, kimsə barınıza gələcək n = 1000 İnsan. Sonra tam axtarış olacaq təxminən mövcud olan variantlar - çılğın məbləğ. Xoşbəxtlikdən, rəhbərliyiniz sizə limit verib k = 10, buna görə təkrarlamalı olduğunuz birləşmələrin sayı daha azdır: on elementin alt çoxluqlarının sayı . Bu daha yaxşıdır, lakin hətta güclü klasterdə belə bir gündə hesablanmayacaq.
Barın ziyarətçiləri arasında gərgin münasibətlərin bu konfiqurasiyasında döyüş ehtimalını aradan qaldırmaq üçün Bob, Daniel və Fedoru kənarda saxlamaq lazımdır. Yalnız ikisinin geridə qalacağı bir həll yoxdur.
Bu, təslim olmaq və hamını içəri buraxmaq vaxtıdırmı? Digər variantları nəzərdən keçirək. Yaxşı, məsələn, yalnız çox sayda insanla döyüşmək ehtimalı olanları içəri buraxa bilməzsiniz. Kimsə ilə heç olmasa döyüşə bilsə k+1 başqa bir insan, onda siz mütləq onu içəri buraxa bilməzsiniz - əks halda hamını kənarda saxlamalı olacaqsınız k+1 döyüşə biləcəyi şəhərlilər, bu, mütləq rəhbərliyi pozacaq.
Bu prinsipə uyğun olaraq bacardığınız hər kəsi çölə atmağa icazə verin. Sonra hər kəs daha çox döyüşə bilməz k Xalq. Onları çölə atmaq k adam, bundan başqa heç bir şeyin qarşısını ala bilməzsən münaqişələr. Bu o deməkdir ki, əgər daha çox varsa Bir şəxs ən azı bir münaqişədə iştirak edirsə, əlbəttə ki, onların hamısının qarşısını ala bilməzsiniz. Əlbətdə ki, tamamilə münaqişəsiz insanları içəri buraxacağınızdan, iki yüz nəfərdən on ölçülü bütün alt qruplardan keçmək lazımdır. Təxminən var , və bu sayda əməliyyat artıq klasterdə sıralana bilər.
Əgər siz heç bir münaqişəsi olmayan şəxsləri təhlükəsiz şəkildə götürə bilirsinizsə, onda yalnız bir münaqişədə iştirak edənlər haqqında nə demək olar? Əslində, onlar da rəqibinin qapısını bağlamaqla içəri buraxıla bilərlər. Həqiqətən də, əgər Alisa yalnız Bob ilə münaqişədədirsə, o zaman Alisi onların ikisindən kənara qoysaq, uduzmayacağıq: Bobun başqa münaqişələri ola bilər, amma Alisdə əlbəttə ki, yoxdur. Üstəlik, ikimizi də içəri buraxmamağımızın mənası yoxdur. Belə əməliyyatlardan sonra artıq heç bir şey qalmır həll olunmamış taleyi olan qonaqlar: bizdə yalnız hər birində iki iştirakçı və ən azı iki iştirakçı olan münaqişələr. Beləliklə, qalan yalnız sıralamaqdır noutbukda yarım gün asanlıqla hesab edilə bilən variantlar.
Əslində, sadə əsaslandırma ilə daha cəlbedici şərtlərə nail ola bilərsiniz. Qeyd edək ki, biz mütləq bütün mübahisələri həll etməliyik, yəni hər bir ziddiyyətli cütlükdən içəri buraxmayacağımız ən azı bir nəfəri seçməliyik. Aşağıdakı alqoritmi nəzərdən keçirək: hər hansı bir münaqişəni götürün, ondan bir iştirakçını çıxarırıq və qalandan rekursiv başlayırıq, sonra digərini çıxarırıq və həmçinin rekursiv başlayırıq. Biz hər addımda birini atdığımız üçün belə bir alqoritmin rekursiya ağacı ikili dərinlik ağacıdır. k, buna görə də alqoritm ümumilikdə işləyir Hara n təpələrin sayıdır və m - qabırğaların sayı. Bizim nümunəmizdə bu, yalnız bir noutbukda deyil, hətta mobil telefonda da bir saniyədə hesablana bilən təxminən on milyondur.
Yuxarıdakı nümunə bir nümunədir parametrli alqoritm. Parametrləşdirilmiş alqoritmlər zamanla işləyən alqoritmlərdir f(k) poli(n)Hara p - çoxhədli, f ixtiyari hesablana bilən funksiyadır və k - çox güman ki, problemin ölçüsündən daha kiçik olacaq bəzi parametr.
Bu alqoritmdən əvvəl bütün əsaslandırmalar bir nümunə verir kernelizasiya parametrli alqoritmlərin yaradılması üçün ümumi üsullardan biridir. Kernelizasiya problem ölçüsünün parametrin funksiyası ilə məhdudlaşan dəyərə endirilməsidir. Yaranan problem çox vaxt nüvə adlanır. Beləliklə, təpələrin dərəcələri haqqında sadə mülahizələrlə biz Vertex Cover problemi üçün cavabın ölçüsü ilə parametrləşdirilmiş kvadrat nüvə əldə etdik. Bu tapşırıq üçün seçə biləcəyiniz başqa parametrlər də var (məsələn, Vertex Cover Above LP), lakin bu, müzakirə edəcəyimiz parametrdir.
Temp Challenge
Rəqabət (Parametrləşdirilmiş Alqoritmlər və Hesablama Təcrübələri Çağırışı) 2015-ci ildə hesablama problemlərini həll etmək üçün praktikada istifadə olunan parametrləşdirilmiş alqoritmlər və yanaşmalar arasında əlaqə yaratmaq üçün yaradılmışdır. İlk üç müsabiqə qrafikin ağac eninin tapılmasına həsr olunmuşdu (), bir Ştayner ağacı axtarır () və dövrləri kəsən təpələr toplusunun axtarışı (). Bu il əlinizi sınaya biləcəyiniz problemlərdən biri yuxarıda təsvir edilən təpə örtüyü problemi idi.
Müsabiqə hər il populyarlıq qazanır. İlkin məlumatlara inanırsınızsa, bu il yarışda təkbaşına zirvəni əhatə edən problemi həll etmək üçün 24 komanda iştirak edib. Qeyd etmək lazımdır ki, müsabiqə bir neçə saat, hətta bir həftə deyil, bir neçə ay davam edir. Komandaların ədəbiyyatı öyrənmək, öz orijinal ideyasını irəli sürmək və onu həyata keçirməyə çalışmaq imkanı var. Əslində bu müsabiqə bir tədqiqat layihəsidir. Ən effektiv həllər üçün ideyalar və qaliblərin mükafatlandırılması konfransla birlikdə keçiriləcək. (Parametrləşdirilmiş və Dəqiq Hesablama üzrə Beynəlxalq Simpozium) Avropanın ən böyük illik alqoritmik toplantısının bir hissəsi kimi . Müsabiqənin özü haqqında daha ətraflı məlumatı buradan əldə etmək olar , və əvvəlki illərin nəticələri yalan .
Həll diaqramı
Təpələri əhatə edən problemi həll etmək üçün parametrləşdirilmiş alqoritmlərdən istifadə etməyə çalışdım. Onlar adətən iki hissədən ibarətdir: sadələşdirmə qaydaları (ideal olaraq kernelləşdirməyə gətirib çıxarır) və bölmə qaydaları. Sadələşdirmə qaydaları çoxhədli zamanda girişin əvvəlcədən işlənməsidir. Bu cür qaydaların tətbiqində məqsəd problemi ekvivalent kiçik problemə endirməkdir. Sadələşdirmə qaydaları alqoritmin ən bahalı hissəsidir və bu hissənin tətbiqi ümumi işləmə müddətinə gətirib çıxarır. sadə çoxhədli vaxt əvəzinə. Bizim vəziyyətimizdə, bölmə qaydaları ona əsaslanır ki, hər bir təpə üçün ya onu, ya da onun qonşusunu cavab olaraq qəbul etmək lazımdır.
Ümumi sxem belədir: biz sadələşdirmə qaydalarını tətbiq edirik, sonra hansısa təpəni seçirik və iki rekursiv çağırış edirik: birincidə onu cavab olaraq qəbul edirik, digərində isə onun bütün qonşularını götürürük. Bu təpə boyunca parçalanma (budaqlanma) dediyimiz budur.
Növbəti paraqrafda bu sxemə dəqiq bir əlavə ediləcək.
Bölmə (brunching) qaydaları üçün fikirlər
Parçalanmanın baş verəcəyi təpənin necə seçiləcəyini müzakirə edək.
Əsas fikir alqoritmik mənada çox acgözdür: maksimum dərəcədə bir təpə götürək və onun boyunca parçalayaq. Niyə daha yaxşı görünür? Çünki rekursiv çağırışın ikinci qolunda biz bu şəkildə çoxlu təpələri siləcəyik. Siz qalan kiçik bir qrafikə arxalana bilərsiniz və biz onun üzərində tez işləyə bilərik.
Artıq müzakirə olunmuş sadə kernelləşdirmə üsulları ilə bu yanaşma özünü yaxşı göstərir və ölçüdə bir neçə min təpənin bəzi testlərini həll edir. Lakin, məsələn, kub qrafikləri (yəni hər təpənin dərəcəsi üç olan qrafiklər) üçün yaxşı işləmir.
Kifayət qədər sadə fikrə əsaslanan başqa bir fikir də var: qrafikin əlaqəsi kəsilərsə, onun birləşdirilmiş komponentləri üzrə problem sonunda cavabları birləşdirərək müstəqil şəkildə həll edilə bilər. Yeri gəlmişkən, bu, həlli əhəmiyyətli dərəcədə sürətləndirəcək sxemdə kiçik vəd edilmiş bir dəyişiklikdir: əvvəllər, bu halda, biz komponentlərin cavablarını hesablamaq üçün zamanın məhsulu üçün işləyirdik, indi isə işləyirik. məbləğ. Və budaqlanmağı sürətləndirmək üçün birləşdirilmiş qrafiki ayrılmış qrafikə çevirmək lazımdır.
Bunu necə etmək olar? Qrafikdə artikulyasiya nöqtəsi varsa, onunla mübarizə aparmaq lazımdır. Artikulyasiya nöqtəsi elə bir təpədir ki, çıxarıldıqda qrafik öz əlaqəsini itirir. Qrafikdəki bütün birləşmə nöqtələrini xətti vaxtda klassik alqoritmdən istifadə etməklə tapmaq olar. Bu yanaşma budaqlanmağı əhəmiyyətli dərəcədə sürətləndirir.
Seçilmiş təpələrdən hər hansı biri çıxarıldıqda, qrafik əlaqəli komponentlərə bölünəcəkdir.
Biz bunu edəcəyik, amma daha çoxunu istəyirik. Məsələn, qrafikdə kiçik təpə kəsiklərini axtarın və ondan təpələr boyunca bölün. Minimum qlobal təpə kəsimini tapmaq üçün bildiyim ən təsirli yol kub zamanda qurulmuş Gomori-Hu ağacından istifadə etməkdir. PACE Challenge-də tipik qrafik ölçüsü bir neçə min təpədir. Bu vəziyyətdə rekursiya ağacının hər təpəsində milyardlarla əməliyyat yerinə yetirilməlidir. Belə çıxır ki, ayrılan vaxtda problemi həll etmək sadəcə olaraq mümkün deyil.
Həllini optimallaşdırmağa çalışaq. Bir cüt təpə arasında kəsilmiş minimum təpə maksimum axını quran hər hansı bir alqoritmlə tapıla bilər. Siz onu belə bir şəbəkəyə buraxa bilərsiniz , praktikada çox tez işləyir. Şübhə edirəm ki, əməliyyat vaxtı üçün təxminləri sübut etmək nəzəri cəhətdən mümkündür , bu artıq olduqca məqbuldur.
Mən bir neçə dəfə təsadüfi təpə cütləri arasında kəsiklər axtarmağa və ən balanslı olanı götürməyə çalışdım. Təəssüf ki, bu, açıq PACE Challenge testində zəif nəticələr verdi. Mən bunu maksimum dərəcədə təpələri ayıran alqoritmlə müqayisə etdim, onları enmə dərinliyi məhdudiyyəti ilə işlədirdim. Bu şəkildə kəsik tapmağa çalışan bir alqoritm daha böyük qrafikləri geridə qoydu. Bu, kəsiklərin çox balanssız olması ilə əlaqədardır: 5-10 təpəni çıxararaq, yalnız 15-20-ni ayırmaq mümkün oldu.
Qeyd etmək lazımdır ki, nəzəri cəhətdən ən sürətli alqoritmlər haqqında məqalələr parçalanma üçün təpələri seçmək üçün daha təkmil üsullardan istifadə edir. Bu cür texnikalar çox mürəkkəb icraya malikdir və çox vaxt vaxt və yaddaş baxımından zəif performansa malikdir. Təcrübə üçün olduqca məqbul olanları müəyyən edə bilmədim.
Sadələşdirmə qaydalarını necə tətbiq etmək olar
Artıq kernelizasiya üçün ideyalarımız var. Sizə xatırlatmağa icazə verin:
- İzolyasiya edilmiş təpə varsa, onu silin.
- 1 dərəcə zirvəsi varsa, onu çıxarın və cavab olaraq qonşusunu götürün.
- Ən azı bir dərəcə zirvəsi varsa k+1, geri almaq.
İlk iki ilə hər şey aydındır, üçüncü ilə bir hiylə var. Əgər bar haqqında komik problemdə bizə yuxarı hədd verilmişdir k, onda AŞPA Çağırışında siz sadəcə olaraq minimum ölçüdə təpə örtüyü tapmaq lazımdır. Bu, Axtarış Problemlərinin Qərar Problemlərinə tipik çevrilməsidir; çox vaxt iki növ problem arasında heç bir fərq yoxdur. Təcrübədə təpəni əhatə edən problem üçün həlledici yazırıqsa, fərq ola bilər. Məsələn, üçüncü bənddə olduğu kimi.
İcra nöqteyi-nəzərindən, davam etməyin iki yolu var. Birinci yanaşma iterativ dərinləşmə adlanır. Bu belədir: cavaba aşağıdan bəzi ağlabatan məhdudiyyətlə başlaya bilərik və sonra rekursiyada bu məhdudiyyətdən aşağı getmədən yuxarıdan cavabda məhdudiyyət kimi bu məhdudiyyətdən istifadə edərək alqoritmimizi işlədə bilərik. Əgər müəyyən bir cavab tapmışıqsa, bunun optimal olacağına zəmanət verilir, əks halda bu limiti bir artırıb yenidən başlaya bilərik.
Başqa bir yanaşma, bəzi cari optimal cavabı saxlamaq və tapıldıqda bu parametri dəyişdirərək daha kiçik cavab axtarmaqdır k axtarışda lazımsız budaqların daha çox kəsilməsi üçün.
Bir neçə gecə eksperimenti apardıqdan sonra bu iki metodun kombinasiyası üzərində qərar verdim: birincisi, mən alqoritmimi axtarış dərinliyinə müəyyən məhdudiyyət qoyaraq işlədirəm (onu əsas həlllə müqayisədə cüzi vaxt aparacaq şəkildə seçirəm) və ən yaxşısını istifadə edirəm. cavabın yuxarı həddi kimi tapılan həll - yəni eyni şeyə k.
2-ci dərəcə təpələri
0 və 1 dərəcə təpələri ilə məşğul olduq. Belə çıxır ki, bunu 2-ci dərəcəli təpələrlə etmək olar, lakin bunun üçün qrafikdən daha mürəkkəb əməliyyatlar tələb olunacaq.
Bunu izah etmək üçün bir şəkildə təpələri təyin etməliyik. 2-ci dərəcə təpəsini təpə adlandıraq v, və onun qonşuları - təpələr x и y. Növbəti iki halımız olacaq.
- Zaman x и y - qonşular. Sonra cavab verə bilərsiniz x и yVə v silin. Həqiqətən də, bu üçbucaqdan ən azı iki təpə götürmək lazımdır və götürsək, mütləq itirməyəcəyik. x и y: yəqin ki, onların başqa qonşuları var və v Onlar burada deyil.
- Zaman x и y - qonşu deyil. Sonra hər üç təpənin birinə yapışdırıla biləcəyi bildirilir. İdeya ondan ibarətdir ki, bu halda optimal cavab var, biz də onu qəbul edirik v, və ya hər iki təpə x и y. Üstəlik, birinci halda cavab olaraq bütün qonşuları götürməli olacağıq x и y, lakin ikincidə bu lazım deyil. Bu, cavab olaraq yapışdırılmış təpəni götürmədiyimiz və qəbul etdiyimiz hallara tam uyğun gəlir. Yalnız qeyd etmək qalır ki, hər iki halda belə bir əməliyyatdan cavab bir azalır.
Qeyd etmək lazımdır ki, bu yanaşma ədalətli xətti vaxtda dəqiq həyata keçirmək olduqca çətindir. Təpələri yapışdırmaq mürəkkəb bir əməliyyatdır, qonşuların siyahılarını kopyalamalısınız. Əgər bu diqqətsiz həyata keçirilirsə, siz asimptotik suboptimal işləmə vaxtı ilə nəticələnə bilərsiniz (məsələn, hər yapışdırmadan sonra çoxlu kənarları köçürürsünüz). Mən 2-ci dərəcəli təpələrdən bütün yolları tapmağa və bir dəstə xüsusi halları, məsələn, bu təpələrdən və ya birindən başqa bütün bu təpələrdən olan dövrləri təhlil etməyə qərar verdim.
Bundan əlavə, bu əməliyyatın geri qaytarılması lazımdır ki, rekursiyadan qayıdanda qrafiki ilkin formasına qaytaraq. Bunu təmin etmək üçün mən birləşdirilən təpələrin kənar siyahılarını təmizləmədim və sonra hansı kənarların hara getməli olduğunu bildim. Qrafiklərin bu şəkildə həyata keçirilməsi də dəqiqlik tələb edir, lakin ədalətli xətti vaxt təmin edir. Bir neçə on minlərlə kənarın qrafikləri üçün, sürətdə böyük üstünlüklər verən prosessorun önbelleğine uyğun gəlir.
Xətti nüvə
Nəhayət, nüvənin ən maraqlı hissəsi.
Başlamaq üçün xatırlayın ki, ikitərəfli qrafiklərdə minimum təpə örtüyü istifadə edərək tapıla bilər . Bunu etmək üçün alqoritmdən istifadə etməlisiniz orada maksimum uyğunluğu tapmaq və sonra teoremi istifadə etmək üçün .
Xətti nüvənin ideyası belədir: əvvəlcə qrafiki, yəni hər bir təpənin yerinə bifurkasiya edirik. v iki zirvə əlavə edək и , və hər kənarın yerinə u - v iki qabırğa əlavə edək и . Nəticədə alınan qrafik ikitərəfli olacaqdır. Onun içindəki minimum təpə örtüyünü tapaq. Orijinal qrafikin bəzi təpələri ora iki dəfə çatacaq, bəziləri yalnız bir dəfə, bəziləri isə heç vaxt. Nemhauzer-Trotter teoremində deyilir ki, bu halda bir dəfə də olsun vurmayan təpələri çıxarmaq və iki dəfə vuranları geri almaq olar. Üstəlik, o deyir ki, qalan təpələrin (bir dəfə vuranların) ən azı yarısını cavab olaraq qəbul etməlisiniz.
Biz daha çox tərk etməyi öyrəndik 2k zirvələri Həqiqətən, əgər qalan cavab bütün təpələrin ən azı yarısıdırsa, o zaman cəmi təpələrdən daha çox təpə yoxdur. 2k.
Burada irəliyə doğru kiçik bir addım ata bildim. Aydındır ki, bu şəkildə qurulan nüvə ikitərəfli qrafikdə hansı minimal təpə örtüyü götürməyimizdən asılıdır. Qalan təpələrin sayının minimal olması üçün birini götürmək istərdim. Əvvəllər bunu yalnız vaxtında edə bilirdilər . Vaxtında bu alqoritmin tətbiqi ilə gəldim , beləliklə, bu nüvəni hər budaqlanma mərhələsində yüz minlərlə təpənin qrafiklərində axtarmaq olar.
Nəticə
Təcrübə göstərir ki, mənim həllim bir neçə yüz təpənin və bir neçə min kənarın sınaqlarında yaxşı işləyir. Belə sınaqlarda yarım saat ərzində həll yolunun tapılacağını gözləmək tamamilə mümkündür. Cavabın məqbul bir zamanda tapılma ehtimalı, prinsipcə, qrafikdə kifayət qədər çox sayda yüksək dərəcəli təpələr, məsələn, 10 və daha yüksək dərəcə olduqda artır.
Müsabiqədə iştirak etmək üçün həllər göndərilməli idi . Orada təqdim olunan məlumatlara əsasən , açıq testlərdə mənim həllim ikincidən böyük bir boşluqla iyirmidən üçüncü yerdədir. Düzünü desəm, həllərin müsabiqənin özündə necə qiymətləndiriləcəyi tam aydın deyil: məsələn, mənim həllim dördüncü yerdəki həlldən daha az sınaqdan keçir, lakin keçənlərdə daha sürətli işləyir.
Qapalı testlərin nəticələri iyulun 1-də məlum olacaq.
Mənbə: www.habr.com