Kazi ya utafiti labda ndiyo sehemu inayovutia zaidi ya mafunzo yetu. Wazo ni kujaribu mwenyewe katika mwelekeo uliochagua ukiwa bado chuo kikuu. Kwa mfano, wanafunzi kutoka maeneo ya Uhandisi wa Programu na Mafunzo ya Mashine mara nyingi huenda kufanya utafiti katika makampuni (hasa JetBrains au Yandex, lakini si tu).
Katika chapisho hili nitazungumza juu ya mradi wangu katika Sayansi ya Kompyuta. Kama sehemu ya kazi yangu, nilisoma na kuweka katika vitendo mbinu za kutatua moja ya shida maarufu za NP-ngumu: tatizo la kufunika vertex.
Siku hizi, mbinu ya kuvutia ya matatizo ya NP-ngumu inakua haraka sana - algorithms ya parameterized. Nitajaribu kukufanya uongeze kasi, nikuambie baadhi ya algorithms rahisi za parameterized na kuelezea njia moja yenye nguvu ambayo imenisaidia sana. Niliwasilisha matokeo yangu kwenye shindano la PACE Challenge: kulingana na matokeo ya majaribio ya wazi, suluhisho langu linachukua nafasi ya tatu, na matokeo ya mwisho yatajulikana mnamo Julai 1.
Kuhusu mimi mwenyewe
Jina langu ni Vasily Alferov, sasa ninamaliza mwaka wangu wa tatu katika Chuo Kikuu cha Taifa cha Utafiti wa Shule ya Juu ya Uchumi - St. Nimekuwa na nia ya algorithms tangu siku zangu za shule, niliposoma shule ya Moscow No. 179 na kushiriki kwa mafanikio katika Olympiads ya sayansi ya kompyuta.
Idadi isiyo na kikomo ya wataalamu katika algoriti zilizoainishwa huingia kwenye upau...
Mfano uliochukuliwa kutoka kwa kitabu
Fikiria kuwa wewe ni mlinzi wa baa katika mji mdogo. Kila Ijumaa, nusu ya jiji huja kwenye baa yako ili kupumzika, ambayo inakupa shida nyingi: unahitaji kutupa wateja walio na safu nje ya baa ili kuzuia mapigano. Hatimaye, unapata kulishwa na kuamua kuchukua hatua za kuzuia.
Kwa kuwa jiji lako ni dogo, unajua ni jozi zipi za wateja wana uwezekano wa kupigana ikiwa wataishia kwenye baa pamoja. Je! unayo orodha ya n watu ambao watakuja kwenye bar usiku wa leo. Unaamua kuwaweka baadhi ya watu wa mjini nje ya baa bila mtu yeyote kupigana. Wakati huo huo, wakubwa wako hawataki kupoteza faida na hawatafurahi ikiwa hautaruhusu zaidi ya k Binadamu.
Kwa bahati mbaya, shida iliyo mbele yako ni shida ngumu ya NP. Unaweza kumjua kama , au kama shida ya kufunika vertex. Kwa matatizo hayo, katika hali ya jumla, hakuna algorithms ambayo inafanya kazi kwa wakati unaokubalika. Kwa usahihi, nadharia isiyothibitishwa na yenye nguvu kabisa ETH (Exponential Time Hypothesis) inasema kwamba tatizo hili haliwezi kutatuliwa kwa wakati. , yaani, huwezi kufikiria chochote bora zaidi kuliko utafutaji kamili. Kwa mfano, tuseme mtu atakuja kwenye baa yako n = 1000 Binadamu. Kisha utafutaji kamili utakuwa chaguzi ambazo kuna takriban - kiasi wazimu. Kwa bahati nzuri, usimamizi wako umekupa kikomo k = 10, kwa hivyo idadi ya michanganyiko unayohitaji kurudia ni ndogo zaidi: idadi ya vijisehemu vya vitu kumi ni . Hii ni bora, lakini bado haitahesabiwa kwa siku hata kwenye nguzo yenye nguvu.
Ili kuondoa uwezekano wa mapigano katika usanidi huu wa uhusiano mbaya kati ya wageni wa bar, unahitaji kuweka Bob, Daniel na Fedor nje. Hakuna suluhisho ambalo ni wawili tu wataachwa nyuma.
Je, hii inamaanisha kuwa ni wakati wa kujitoa na kuruhusu kila mtu aingie? Hebu fikiria chaguzi nyingine. Naam, kwa mfano, huwezi kuruhusu tu wale ambao wana uwezekano wa kupigana na idadi kubwa sana ya watu. Ikiwa mtu anaweza kupigana angalau na k+1 mtu mwingine, basi hakika huwezi kumruhusu aingie - vinginevyo itabidi uweke kila mtu nje k+1 watu wa jiji, ambaye anaweza kupigana nao, ambayo hakika itaudhi uongozi.
Wacha utupe kila mtu ambaye unaweza kulingana na kanuni hii. Kisha kila mtu mwingine anaweza kupigana na hakuna zaidi ya k watu. Kuwatupa nje k mtu, unaweza kuzuia chochote zaidi kuliko migogoro. Hii ina maana kwamba kama kuna zaidi ya Ikiwa mtu anahusika katika mzozo angalau mmoja, basi hakika huwezi kuwazuia wote. Kwa kuwa, bila shaka, hakika utaruhusu watu wasio na migogoro kabisa, unahitaji kupitia sehemu zote za ukubwa wa kumi kati ya watu mia mbili. Kuna takriban , na idadi hii ya shughuli inaweza tayari kupangwa kwenye nguzo.
Ikiwa unaweza kuchukua kwa usalama watu ambao hawana migogoro hata kidogo, basi vipi kuhusu wale wanaoshiriki katika mgogoro mmoja tu? Kwa kweli, wanaweza pia kuruhusiwa kwa kufunga mlango kwa mpinzani wao. Kwa kweli, ikiwa Alice anagombana na Bob tu, basi ikiwa tutamruhusu Alice kutoka kwa hao wawili, hatutapoteza: Bob anaweza kuwa na migogoro mingine, lakini Alice hakika hana. Isitoshe, haina maana kwetu kutoturuhusu sisi sote wawili kuingia. Baada ya shughuli kama hizo hakuna zaidi wageni walio na hatima ambayo haijatatuliwa: tunayo tu migogoro, kila mmoja na washiriki wawili na kila mmoja kushiriki katika angalau wawili. Kwa hivyo kilichobaki ni kutatua chaguzi, ambazo zinaweza kuzingatiwa kwa urahisi nusu ya siku kwenye kompyuta ndogo.
Kwa kweli, kwa sababu rahisi unaweza kufikia hali ya kuvutia zaidi. Kumbuka kwamba kwa hakika tunahitaji kusuluhisha mizozo yote, yaani, kutoka kwa kila wanandoa wanaogombana, chagua angalau mtu mmoja ambaye hatutamruhusu aingie. Hebu tuchunguze algorithm ifuatayo: kuchukua mgogoro wowote, ambao tunaondoa mshiriki mmoja na kuanza kwa kurudia kutoka kwa salio, kisha uondoe mwingine na pia uanze kwa kurudia. Kwa kuwa tunatupa mtu nje kwa kila hatua, mti wa kujirudia wa algorithm kama hiyo ni mti wa kina wa kina k, kwa hivyo kwa jumla algorithm inafanya kazi ndani Ambapo n ni idadi ya wima, na m - idadi ya mbavu. Katika mfano wetu, hii ni karibu milioni kumi, ambayo inaweza kuhesabiwa kwa sekunde ya mgawanyiko sio tu kwenye kompyuta ya mkononi, lakini hata kwenye simu ya mkononi.
Mfano hapo juu ni mfano algorithm ya parameterized. Algorithms zilizo na vigezo ni algoriti zinazoendeshwa kwa wakati f(k) aina nyingi(n)Ambapo p - polynomial, f ni kitendakazi kiholela cha kukokotwa, na k - baadhi ya parameter, ambayo, inawezekana kabisa, itakuwa ndogo sana kuliko ukubwa wa tatizo.
Hoja zote kabla ya algorithm hii inatoa mfano ugavi ni mojawapo ya mbinu za jumla za kuunda algoriti zenye vigezo. Kernelization ni kupunguza ukubwa wa tatizo hadi thamani iliyodhibitiwa na chaguo za kukokotoa za kigezo. Tatizo linalosababishwa mara nyingi huitwa kernel. Kwa hivyo, kwa hoja rahisi kuhusu digrii za vipeo, tulipata kerneli ya quadratic kwa tatizo la Jalada la Vertex, iliyoainishwa na saizi ya jibu. Kuna chaguzi zingine ambazo zinaweza kuchaguliwa kwa kazi hii (kwa mfano, Jalada la Vertex Juu ya LP), lakini hii ndio chaguo tutakayojadili.
Changamoto ya Kasi
Ushindani (The Parameterized Algorithms and Computational Experiments Challenge) ilizaliwa mwaka wa 2015 ili kuanzisha uhusiano kati ya algoriti zilizoainishwa na mbinu zinazotumiwa katika mazoezi kutatua matatizo ya hesabu. Mashindano matatu ya kwanza yalijitolea kutafuta upana wa mti wa grafu (), wakitafuta mti wa Steiner () na kutafuta seti ya wima ambayo hupunguza mizunguko () Mwaka huu, moja ya matatizo ambayo unaweza kujaribu mkono wako ilikuwa tatizo la kufunika vertex iliyoelezwa hapo juu.
Mashindano hayo yanazidi kupata umaarufu kila mwaka. Ikiwa unaamini data ya awali, mwaka huu timu 24 zilishiriki katika shindano la kutatua tatizo la kufunika vertex pekee. Inafaa kumbuka kuwa mashindano hayachukua masaa kadhaa au hata wiki, lakini miezi kadhaa. Timu zina fursa ya kusoma fasihi, kuja na wazo lao la asili na kujaribu kutekeleza. Kimsingi, shindano hili ni mradi wa utafiti. Mawazo kwa ajili ya ufumbuzi wa ufanisi zaidi na utoaji wa washindi utafanyika pamoja na mkutano huo. (Kongamano la Kimataifa la Uhesabuji Vigezo na Usahihi) kama sehemu ya mkutano mkubwa wa kila mwaka wa algoriti barani Ulaya. . Maelezo zaidi juu ya shindano yenyewe yanaweza kupatikana kwa , na matokeo ya miaka ya nyuma ni uongo .
Mchoro wa suluhisho
Ili kutatua shida ya kifuniko cha vertex, nilijaribu kutumia algorithms ya parameta. Kwa kawaida huwa na sehemu mbili: sheria za kurahisisha (ambazo kwa hakika husababisha kernelization) na sheria za mgawanyiko. Sheria za kurahisisha ni usindikaji wa awali wa ingizo katika wakati wa polynomia. Madhumuni ya kutumia sheria hizo ni kupunguza tatizo kwa tatizo sawa ndogo. Sheria za kurahisisha ni sehemu ya gharama kubwa zaidi ya algorithm, na kutumia sehemu hii husababisha jumla ya muda wa kukimbia badala ya wakati rahisi wa polynomial. Kwa upande wetu, sheria za kugawanyika zinatokana na ukweli kwamba kwa kila vertex unahitaji kuchukua ama au jirani yake kama jibu.
Mpango wa jumla ni huu: tunatumia sheria za kurahisisha, kisha tunachagua vertex fulani, na kupiga simu mbili za kujirudia: kwa kwanza tunachukua kwa kujibu, na kwa nyingine tunachukua majirani zake wote. Hii ndio tunaita kugawanyika (kuweka matawi) kando ya vertex hii.
Hasa nyongeza moja itafanywa kwa mpango huu katika aya inayofuata.
Mawazo ya sheria za kugawanyika (brunching).
Hebu tujadili jinsi ya kuchagua vertex ambayo mgawanyiko utatokea.
Wazo kuu ni uchoyo sana kwa maana ya algorithmic: wacha tuchukue vertex ya kiwango cha juu na tugawanye kando yake. Kwa nini inaonekana kuwa bora zaidi? Kwa sababu katika tawi la pili la simu ya kujirudia tutaondoa wima nyingi kwa njia hii. Unaweza kutegemea grafu ndogo iliyobaki na tunaweza kuifanyia kazi haraka.
Mbinu hii, iliyo na mbinu rahisi zilizojadiliwa za kernelization, inajionyesha vizuri na kutatua baadhi ya majaribio ya vipeo elfu kadhaa kwa ukubwa. Lakini, kwa mfano, haifanyi kazi vizuri kwa grafu za ujazo (yaani, grafu ambazo kiwango cha kila vertex ni tatu).
Kuna wazo lingine kulingana na wazo rahisi: ikiwa grafu imekatwa, tatizo kwenye vipengele vyake vilivyounganishwa linaweza kutatuliwa kwa kujitegemea, kuchanganya majibu mwishoni. Hii, kwa njia, ni muundo mdogo ulioahidiwa katika mpango huo, ambao utaharakisha suluhisho kwa kiasi kikubwa: hapo awali, katika kesi hii, tulifanya kazi kwa bidhaa ya nyakati kwa kuhesabu majibu ya vipengele, lakini sasa tunafanya kazi kwa jumla. Na ili kuharakisha matawi, unahitaji kugeuza grafu iliyounganishwa kuwa iliyokatwa.
Jinsi ya kufanya hivyo? Ikiwa kuna hatua ya kuelezea kwenye grafu, unahitaji kupigana nayo. Sehemu ya kutamka ni vertex ambayo inapoondolewa, grafu inapoteza muunganisho wake. Sehemu zote za makutano kwenye grafu zinaweza kupatikana kwa kutumia algoriti ya kawaida katika muda wa mstari. Njia hii inaharakisha sana matawi.
Wakati wima yoyote iliyochaguliwa imeondolewa, grafu itagawanyika katika vipengele vilivyounganishwa.
Tutafanya hivi, lakini tunataka zaidi. Kwa mfano, tafuta sehemu ndogo za vertex kwenye grafu na ugawanye kando ya wima kutoka kwake. Njia bora zaidi ninayojua kupata kiwango cha chini cha kukatwa kwa vertex duniani ni kutumia mti wa Gori-Hu, ambao umejengwa kwa muda wa ujazo. Katika Changamoto ya PACE, saizi ya kawaida ya grafu ni wima elfu kadhaa. Katika hali hii, mabilioni ya shughuli zinahitaji kufanywa katika kila kipeo cha mti wa kujirudia. Inageuka kuwa haiwezekani kutatua tatizo kwa wakati uliopangwa.
Wacha tujaribu kuongeza suluhisho. Kipeo cha chini kilichokatwa kati ya jozi ya wima kinaweza kupatikana kwa algoriti yoyote inayounda mtiririko wa juu zaidi. Unaweza kuiruhusu kwenye mtandao kama huo , katika mazoezi inafanya kazi haraka sana. Nina shaka kuwa inawezekana kinadharia kuthibitisha makadirio ya muda wa kufanya kazi , ambayo tayari inakubalika kabisa.
Nilijaribu mara kadhaa kutafuta kupunguzwa kati ya jozi za wima bila mpangilio na kuchukua ile iliyosawazishwa zaidi. Kwa bahati mbaya, hii ilitoa matokeo duni katika majaribio ya wazi ya PACE Challenge. Nililinganisha na algorithm ambayo iligawanya wima za kiwango cha juu, nikiziendesha na kizuizi juu ya kina cha asili. Algorithm inayojaribu kupata kata kwa njia hii iliacha nyuma ya grafu kubwa. Hii ni kutokana na ukweli kwamba kupunguzwa kuligeuka kuwa na usawa sana: baada ya kuondoa wima 5-10, iliwezekana kugawanyika 15-20 tu.
Ni vyema kutambua kwamba makala kuhusu algoriti za kasi zaidi kinadharia hutumia mbinu za juu zaidi za kuchagua vipeo vya kugawanyika. Mbinu hizo zina utekelezaji mgumu sana na mara nyingi utendaji duni katika suala la wakati na kumbukumbu. Sikuweza kutambua zile ambazo zinakubalika kwa mazoezi.
Jinsi ya Kutumia Kanuni za Kurahisisha
Tayari tunayo mawazo ya kutengeneza kernelization. Acha nikukumbushe:
- Ikiwa kuna vertex pekee, futa.
- Ikiwa kuna vertex ya shahada ya 1, iondoe na uchukue jirani yake kwa kujibu.
- Ikiwa kuna vertex ya digrii angalau k+1, irudishe.
Na mbili za kwanza kila kitu ni wazi, na ya tatu kuna hila moja. Ikiwa katika shida ya vichekesho kuhusu baa tulipewa kikomo cha juu cha k, basi katika Changamoto ya PACE unahitaji tu kupata kifuniko cha vertex cha ukubwa wa chini. Haya ni mabadiliko ya kawaida ya Shida za Utafutaji kuwa Shida za Uamuzi; mara nyingi hakuna tofauti kati ya aina hizi mbili za shida. Katika mazoezi, ikiwa tunaandika solver kwa tatizo la kifuniko cha vertex, kunaweza kuwa na tofauti. Kwa mfano, kama katika hatua ya tatu.
Kutoka kwa mtazamo wa utekelezaji, kuna njia mbili za kuendelea. Njia ya kwanza inaitwa Kukuza kwa Iterative. Ni kama ifuatavyo: tunaweza kuanza na kizuizi kinachofaa kutoka hapa chini kwenye jibu, na kisha kuendesha algorithm yetu kwa kutumia kizuizi hiki kama kikwazo cha jibu kutoka juu, bila kwenda chini kwa kujirudia kuliko kizuizi hiki. Ikiwa tumepata jibu fulani, imehakikishwa kuwa bora zaidi, vinginevyo tunaweza kuongeza kikomo hiki kwa moja na kuanza tena.
Njia nyingine ni kuhifadhi jibu bora la sasa na kutafuta jibu dogo, kubadilisha paramu hii inapopatikana k kwa kukata zaidi matawi yasiyo ya lazima katika utaftaji.
Baada ya kufanya majaribio kadhaa ya usiku, nilikaa kwenye mchanganyiko wa njia hizi mbili: kwanza, ninaendesha algorithm yangu na aina fulani ya kikomo kwenye kina cha utaftaji (kuichagua ili ichukue muda kidogo ikilinganishwa na suluhisho kuu) na kutumia bora zaidi. suluhisho linalopatikana kama kikomo cha juu cha jibu - ambayo ni, kwa kitu kimoja k.
Viwango vya digrii 2
Tumeshughulikia wima za digrii 0 na 1. Inabadilika kuwa hii inaweza kufanywa na wima ya digrii 2, lakini hii itahitaji shughuli ngumu zaidi kutoka kwa grafu.
Ili kuelezea hili, tunahitaji kwa namna fulani kuteua wima. Wacha tuite kipeo cha digrii 2 kipeo v, na majirani zake - wima x ΠΈ y. Ifuatayo tutakuwa na kesi mbili.
- Wakati x ΠΈ y - majirani. Kisha unaweza kujibu x ΠΈ yNa v kufuta. Hakika, kutoka kwa pembetatu hii angalau wima mbili zinahitaji kuchukuliwa kwa kurudi, na hakika hatutapoteza ikiwa tutachukua. x ΠΈ y: labda wana majirani wengine, na v hakuna hata mmoja wao.
- Wakati x ΠΈ y - sio majirani. Kisha inaelezwa kuwa wima zote tatu zinaweza kuunganishwa kwenye moja. Wazo ni kwamba katika kesi hii kuna jibu mojawapo, ambalo tunachukua ama v, au wima zote mbili x ΠΈ y. Aidha, katika kesi ya kwanza tutalazimika kuchukua majirani wote kwa kujibu x ΠΈ y, lakini kwa pili sio lazima. Hii inalingana kabisa na kesi wakati hatuchukui vertex ya glued kwa kujibu na tunapofanya. Inabakia tu kutambua kwamba katika hali zote mbili majibu kutoka kwa operesheni hiyo hupungua kwa moja.
Inafaa kumbuka kuwa njia hii ni ngumu sana kutekeleza kwa wakati unaofaa. Vipeo vya kuunganisha ni kazi ngumu; unahitaji kunakili orodha za majirani. Ikiwa hii itafanywa bila uangalifu, unaweza kuishia na wakati usiofaa wa kukimbia (kwa mfano, ikiwa unakili kingo nyingi baada ya kila gluing). Nilitulia kutafuta njia nzima kutoka kwa vipeo vya shahada ya 2 na kuchambua rundo la kesi maalum, kama vile mizunguko kutoka kwa vipeo kama hivyo au kutoka kwa wima zote isipokuwa moja.
Kwa kuongeza, ni muhimu kwamba operesheni hii ibadilishwe, ili wakati wa kurudi kutoka kwa kujirudia tunarejesha grafu kwa fomu yake ya awali. Ili kuhakikisha hili, sikufuta orodha za makali za wima zilizounganishwa, kisha nilijua ni kingo zipi zinahitajika kwenda wapi. Utekelezaji huu wa grafu pia unahitaji usahihi, lakini hutoa muda wa mstari wa haki. Na kwa grafu ya makumi kadhaa ya maelfu ya kingo, inafaa kwenye cache ya processor, ambayo inatoa faida kubwa kwa kasi.
Kokwa ya mstari
Hatimaye, sehemu ya kuvutia zaidi ya kernel.
Kuanza, kumbuka kuwa katika grafu mbili, kifuniko cha chini cha vertex kinaweza kupatikana kwa kutumia . Ili kufanya hivyo unahitaji kutumia algorithm ili kupata kiwango cha juu kinacholingana hapo, na kisha utumie nadharia .
Wazo la kerneli ya mstari ni hii: kwanza tunabadilisha grafu, ambayo ni, badala ya kila vertex. v tuongeze vilele viwili ΠΈ , na badala ya kila makali u - v tuongeze mbavu mbili ΠΈ . Grafu inayotokana itakuwa sehemu mbili. Wacha tupate kifuniko cha chini cha vertex ndani yake. Baadhi ya vipeo vya grafu asili vitafika hapo mara mbili, vingine mara moja tu, na vingine kamwe. Nadharia ya Nemhauser-Trotter inasema kwamba katika kesi hii mtu anaweza kuondoa wima ambazo hazikupiga hata mara moja na kurudisha zile zilizogonga mara mbili. Kwa kuongezea, anasema kwamba kati ya wima zilizobaki (zile ambazo ziligonga mara moja) unahitaji kuchukua angalau nusu kama jibu.
Tumejifunza tu kuondoka zaidi ya 2k vilele Hakika, ikiwa jibu lililosalia ni angalau nusu ya wima zote, basi hakuna wima kwa jumla kuliko 2k.
Hapa niliweza kupiga hatua ndogo mbele. Ni wazi kwamba kerneli iliyojengwa kwa njia hii inategemea ni aina gani ya kifuniko kidogo cha vertex tulichochukua kwenye grafu ya pande mbili. Ningependa kuchukua moja ili idadi ya wima iliyobaki iwe ndogo. Hapo awali, waliweza kufanya hivyo kwa wakati tu . Nilikuja na utekelezaji wa algorithm hii kwa wakati , kwa hivyo, msingi huu unaweza kutafutwa katika grafu za mamia ya maelfu ya wima katika kila hatua ya matawi.
Matokeo
Mazoezi yanaonyesha kuwa suluhisho langu linafanya kazi vizuri kwenye majaribio ya wima mia kadhaa na kingo elfu kadhaa. Katika vipimo hivyo inawezekana kabisa kutarajia kwamba suluhisho litapatikana kwa nusu saa. Uwezekano wa kupata jibu kwa wakati unaokubalika, kwa kanuni, huongezeka ikiwa grafu ina idadi kubwa ya kutosha ya viwango vya juu, kwa mfano, shahada ya 10 na ya juu.
Ili kushiriki katika shindano, suluhu zilipaswa kutumwa kwa . Kwa kuangalia taarifa iliyotolewa hapo , suluhisho langu katika vipimo vya wazi huchukua nafasi ya tatu kati ya ishirini, na pengo kubwa kutoka kwa pili. Kuwa waaminifu kabisa, haijulikani kabisa jinsi ufumbuzi utakavyotathminiwa kwenye ushindani yenyewe: kwa mfano, suluhisho langu hupita vipimo vichache kuliko suluhisho katika nafasi ya nne, lakini kwa wale wanaopita, hufanya kazi kwa kasi zaidi.
Matokeo ya majaribio yaliyofungwa yatajulikana tarehe XNUMX Julai.
Chanzo: mapenzi.com