Ayyukan bincike watakila shine mafi ban sha'awa na horon mu. Manufar ita ce gwada kanku ta hanyar da kuka zaɓa yayin da kuke jami'a. Misali, ɗalibai daga fannonin Injiniyan Software da Koyan Injiniya sukan je yin bincike a kamfanoni (yafi JetBrains ko Yandex, amma ba kawai ba).
A cikin wannan rubutu zan yi magana game da aikina a Kimiyyar Kwamfuta. A matsayin wani ɓangare na aikina, na yi karatu kuma na aiwatar da hanyoyin magance ɗaya daga cikin shahararrun matsalolin NP-hard: matsala ta rufe vertex.
A zamanin yau, hanya mai ban sha'awa ga matsalolin NP-hard suna haɓaka da sauri - algorithms parameterized. Zan yi ƙoƙari in haɓaka ku da sauri, in gaya muku wasu ƙayyadaddun algorithms masu sauƙi kuma in bayyana hanya ɗaya mai ƙarfi wacce ta taimaka mini da yawa. Na gabatar da sakamakona a gasar kalubalen PACE: bisa ga sakamakon budaddiyar gwaje-gwaje, mafitata ta dauki matsayi na uku, kuma za a san sakamakon karshe a ranar 1 ga Yuli.
Game da ni
Sunana Vasily Alferov, yanzu na kammala shekara ta uku a Makarantar Harkokin Tattalin Arziki ta Jami'ar Bincike ta Kasa - St. Petersburg. Ina sha'awar algorithms tun lokacin da nake makaranta, lokacin da na yi karatu a makarantar Moscow No. 179 kuma na samu nasarar shiga Olympiads kimiyyar kwamfuta.
Ƙayyadaddun ƙwararrun ƙwararrun ƙwararrun ƙwararrun ma'auni sun shiga mashaya...
Misali da aka dauko daga littafin
Ka yi tunanin kai mai tsaron mashaya ne a wani ƙaramin gari. Kowace Juma'a, rabin gari yana zuwa mashaya don shakatawa, wanda ke ba ku matsala mai yawa: kuna buƙatar jefa kwastomomin da ba su da hankali daga mashaya don hana faɗa. Daga ƙarshe, kun koshi kuma ku yanke shawarar ɗaukar matakan rigakafi.
Tun da yake garin ku ƙanƙane ne, kun san ainihin ma'auratan da za su iya yin faɗa idan sun ƙare a mashaya tare. Kuna da jerin sunayen n mutanen da za su zo mashaya yau da dare. Ka yanke shawarar hana wasu mutanen gari fita daga mashaya ba tare da wani ya yi fada ba. A lokaci guda kuma, shugabannin ku ba sa son rasa riba kuma ba za su ji daɗi ba idan ba ku ƙyale fiye da haka ba. k Mutum.
Abin takaici, matsalar da ke gaban ku ita ce matsala ta NP-hard na gargajiya. Kuna iya saninta kamar , ko a matsayin matsala mai rufewa. Don irin waɗannan matsalolin, a cikin yanayin gabaɗaya, babu algorithms waɗanda ke aiki a cikin lokacin yarda. Don zama madaidaici, rashin tabbas kuma tabbataccen hasashe mai ƙarfi ETH (Tsarin Tsawon Lokaci) ya ce ba za a iya magance wannan matsalar cikin lokaci ba. , wato, ba za ku iya tunanin wani abu mai kyau ba fiye da cikakken bincike. Misali, bari mu ce wani zai zo mashaya n = 1000 Mutum. Sannan cikakken bincike zai kasance zaɓuɓɓukan da akwai kusan - mahaukaci adadin. Abin farin ciki, gudanarwarku ta ba ku iyaka k = 10, don haka adadin haɗin da kuke buƙatar sake maimaitawa ya fi ƙanƙanta: adadin ƙananan abubuwa goma shine. . Wannan ya fi kyau, amma har yanzu ba za a ƙidaya shi a cikin yini ɗaya ba ko da a kan gungu mai ƙarfi.
Don kawar da yuwuwar faɗa a cikin wannan daidaitawar dangantakar da ke tsakanin baƙi na mashaya, kuna buƙatar kiyaye Bob, Daniel da Fedor. Babu wata mafita da za a bar biyu kawai a baya.
Wannan yana nufin lokaci ya yi da za a ba da kyauta kuma a bar kowa ya shigo? Bari mu yi la'akari da wasu zaɓuɓɓuka. To, alal misali, ba za ku iya shigar da waɗanda ke da yuwuwar yin yaƙi da mutane da yawa ba. Idan wani zai iya fada akalla da ku+1 wani mutum, to tabbas ba za ku iya bari shi shiga ba - in ba haka ba dole ne ku kiyaye kowa ku+1 mutanen gari, wadanda zai iya fada da su, wanda ko shakka babu zai tayar da hankalin shugabanci.
Bari ku jefar da duk wanda za ku iya bisa ga wannan ka'ida. Sa'an nan kowa da kowa zai iya yin yãƙi da ba fiye da k mutane. Jifar su waje k mutum, ba za ka iya hana kome fiye da rikice-rikice. Wannan yana nufin cewa idan akwai fiye da Idan mutum yana da hannu a cikin aƙalla rikici ɗaya, to lallai ba za ku iya hana su duka ba. Tunda, ba shakka, ba shakka za ku ƙyale mutanen da ba su da rikici gaba ɗaya, kuna buƙatar shiga cikin kowane yanki na girman goma cikin mutane ɗari biyu. Akwai kusan , kuma wannan adadin ayyukan ana iya riga an daidaita shi akan gungu.
Idan za ku iya ɗaukar mutanen da ba su da wani rikici a cikin aminci, to, waɗanda suka shiga cikin rikici ɗaya fa? A gaskiya ma, ana iya shigar da su ta hanyar rufe kofa ga abokin hamayyarsu. Tabbas, idan Alice tana cikin rikici da Bob kawai, to, idan muka bar Alice daga cikin su biyun, ba za mu rasa ba: Bob na iya samun wasu rikice-rikice, amma Alice ba ta da su. Bugu da ƙari, ba ma'ana ba ne a gare mu kada mu bar mu biyu a ciki. Bayan irin waɗannan ayyuka babu sauran sauran baƙi tare da ƙaddarar da ba a warware ba: muna da kawai rikice-rikice, kowanne tare da mahalarta biyu kuma kowanne ya shiga cikin akalla biyu. Don haka abin da ya rage shi ne a warware ta zažužžukan, wanda za a iya sauƙi la'akari da rabin yini a kan kwamfutar tafi-da-gidanka.
A gaskiya ma, tare da sauƙi mai sauƙi za ku iya cimma ma mafi kyawun yanayi. Ka lura cewa babu shakka muna bukatar mu warware duk wata rigima, wato, daga kowane ma’aurata da suka yi karo da juna, zaɓi aƙalla mutum ɗaya wanda ba za mu bari ya shiga ba. Bari mu yi la'akari da algorithm mai zuwa: ɗauki kowane rikici, daga abin da muka cire ɗaya daga cikin mahalarta kuma mu fara maimaitawa daga saura, sa'an nan kuma cire ɗayan kuma fara maimaitawa. Tun da mun jefa wani a kowane mataki, bishiyar maimaita irin wannan algorithm shine bishiyar binaryar zurfi k, don haka a cikin duka algorithm yana aiki a ciki inda n shine adadin madaidaitan, kuma m - adadin hakarkarinsa. A misalinmu, wannan kusan miliyan goma ne, wanda za a iya ƙididdige su a cikin daƙiƙa guda ba kawai a kan kwamfutar tafi-da-gidanka ba, har ma da wayar hannu.
Misalin da ke sama misali ne parameterized algorithm. Algorithms masu daidaitawa sune algorithms waɗanda ke gudana cikin lokaci f (k) poly(n)inda p - polynomial, f aiki ne na sabani na lissafi, kuma k - wasu siga, wanda, mai yuwuwa, zai kasance mafi ƙanƙanta fiye da girman matsalar.
Duk dalilai kafin wannan algorithm ya ba da misali kernelization yana ɗaya daga cikin gabaɗayan fasaha don ƙirƙirar algorithms masu daidaitawa. Kernelization shine rage girman matsalar zuwa ƙima da aka iyakance ta aikin siga. Matsalar da ke haifarwa galibi ana kiranta kwaya. Don haka, ta hanyar sauƙaƙan dalili game da matakan madaidaitan, mun sami kernel quadrate don matsalar Cover Vertex, wanda aka daidaita da girman amsar. Akwai wasu saitunan da za ku iya zaɓar don wannan aikin (kamar Vertex Cover Sama LP), amma wannan shine saitin da za mu tattauna.
Kalubalen Taki
Gasa (The Parameterized Algorithms and Computational Experiments Challenge) an haife shi a cikin 2015 don kafa haɗin kai tsakanin algorithms masu daidaitawa da hanyoyin da ake amfani da su a aikace don magance matsalolin lissafi. Gasa uku na farko an sadaukar da su don gano fadin bishiyar jadawali (), neman bishiyar Steiner () da kuma neman saitin ƙofofin da ke yanke zagayawa ( .). A wannan shekara, ɗayan matsalolin da zaku iya gwada hannunku a ciki shine matsalar rufe bangon da aka bayyana a sama.
Gasar tana samun karbuwa a duk shekara. Idan kun yi imani da bayanan farko, a wannan shekara ƙungiyoyi 24 ne suka shiga gasar don magance matsalar da ke tattare da matsalar ita kaɗai. Yana da kyau a lura cewa gasar ba ta sa'o'i da yawa ko ma mako guda ba, amma watanni da yawa. Ƙungiyoyi suna da damar da za su yi nazarin wallafe-wallafen, su fito da nasu ra'ayin na asali da kuma kokarin aiwatar da shi. A zahiri, wannan gasa aikin bincike ne. Za a gudanar da ra'ayoyin don mafi kyawun mafita da bayar da kyautar ga masu nasara tare da taron (Taron Kasa da Kasa akan Ƙididdigar Ƙididdigar Ƙididdigar Ƙididdigar Ƙididdigar Ƙididdigar Ƙididdiga) a matsayin wani ɓangare na babban taron algorithmic na shekara-shekara a Turai. . Ana iya samun ƙarin cikakkun bayanai game da gasar kanta a , kuma sakamakon shekarun baya karya .
Tsarin bayani
Don magance matsalar rufe bakin, Na yi ƙoƙarin yin amfani da algorithms parameterized. Yawanci sun ƙunshi sassa biyu: ƙa'idodin sauƙaƙawa (wanda ke haifar da kernelization) da ka'idoji masu rarraba. Dokokin sauƙaƙawa suna ƙaddamar da shigarwar a cikin lokaci mai yawa. Manufar amfani da irin waɗannan ƙa'idodin shine a rage matsalar zuwa ƙaramar matsala daidai. Dokokin sauƙaƙawa sune mafi tsadar ɓangaren algorithm, kuma yin amfani da wannan ɓangaren yana kaiwa ga jimlar lokacin gudu maimakon sauƙaƙan lokaci mai yawa. A cikin yanayinmu, ƙa'idodin rarrabuwa sun dogara ne akan gaskiyar cewa kowane juzu'i kuna buƙatar ɗaukar ko dai shi ko maƙwabcinsa a matsayin amsa.
Tsarin gabaɗaya shi ne: muna amfani da ƙa'idodin sauƙaƙawa, sannan mu zaɓi wasu juzu'i, mu yi kira guda biyu masu maimaitawa: a farkon muna ɗaukar shi don amsawa, ɗayan kuma muna ɗaukar duk makwabta. Wannan shi ne abin da muke kira rarrabuwa (reshe) tare da wannan sigar.
Za a yi ƙari ɗaya daidai ga wannan makirci a sakin layi na gaba.
Ra'ayoyin don raba (brunching) dokokin
Bari mu tattauna yadda za a zabi wani juzu'in tare da tsagawa zai faru.
Babban ra'ayi yana da tsananin ƙishi a ma'anar algorithmic: bari mu ɗauki juzu'in matsakaicin matsakaicin digiri kuma mu raba tare da shi. Me yasa ya fi kyau? Domin a cikin reshe na biyu na maimaita kiran waya za mu cire ɗimbin yawa ta wannan hanya. Kuna iya ƙidaya ƙaramin jadawali da ya rage kuma za mu iya yin aiki da shi cikin sauri.
Wannan hanyar, tare da dabarun kernelization masu sauƙi waɗanda aka riga aka tattauna, suna nuna kanta da kyau kuma suna warware wasu gwaje-gwaje na tsayin tsayin dubun da yawa. Amma, alal misali, ba ya aiki da kyau ga zane-zane masu siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar siffar.
Akwai kuma wani ra'ayi bisa ra'ayi mai sauƙi: idan jadawali ya katse, za'a iya warware matsalar akan abubuwan haɗin da aka haɗa da kanta, haɗa amsoshi a ƙarshe. Wannan, ta hanyar, ƙaramin gyare-gyaren da aka yi alkawarinsa a cikin makircin, wanda zai iya hanzarta warwarewa: a baya, a cikin wannan yanayin, mun yi aiki don samfurin lokutan don ƙididdige martani na abubuwan da aka gyara, amma yanzu muna aiki don. jimlar. Kuma don haɓaka reshe, kuna buƙatar kunna jadawali mai alaƙa zuwa wanda aka yanke.
Yadda za a yi? Idan akwai wurin magana a cikin jadawali, kuna buƙatar yin yaƙi da shi. Ma'anar magana ita ce tawul wanda idan an cire shi, jadawali ya rasa haɗin kai. Ana iya samun duk wuraren haɗin gwiwa a cikin jadawali ta amfani da algorithm na al'ada a cikin lokacin layi. Wannan hanya tana ba da gudummawa sosai ga haɓaka reshe.
Lokacin da aka cire kowane ɗayan da aka zaɓa, jadawali zai rabu zuwa abubuwan da aka haɗa.
Za mu yi wannan, amma muna son ƙarin. Misali, nemo ƴan ƴan ƴan ƙwanƙwasa a cikin jadawali kuma a raba tare da ƙarshensa. Hanya mafi inganci da na sani don nemo mafi ƙarancin yanke ƙarshen duniya ita ce amfani da bishiyar Gomori-Hu, wacce aka gina ta cikin lokaci mai siffar sukari. A cikin Kalubalen PACE, matsakaicin girman jadawali yana da tsayi dubu da yawa. A wannan yanayin, ana buƙatar yin biliyoyin ayyuka a kowane gefen bishiyar maimaituwa. Sai ya zama cewa ba shi yiwuwa a magance matsalar a cikin lokacin da aka ware.
Bari muyi kokarin inganta mafita. Za'a iya samun mafi ƙarancin yanke tsakanin maɗaukaki biyu ta kowane algorithm wanda ke gina matsakaicin kwarara. Kuna iya barin shi zuwa irin wannan hanyar sadarwar , a aikace yana aiki da sauri. Ina da tuhuma cewa yana yiwuwa a ka'ida yana yiwuwa a tabbatar da kimantawa na lokacin aiki , wanda ya riga ya zama karbuwa.
Na yi ƙoƙari sau da yawa don neman yanke tsakanin nau'i-nau'i na tsaka-tsakin bazuwar kuma in ɗauki mafi daidaito. Abin takaici, wannan ya haifar da mummunan sakamako a buɗe gwajin Kalubalen PACE. Na kwatanta shi da algorithm wanda ke raba madaidaicin madaidaicin digiri, yana tafiyar da su tare da iyakancewa akan zurfin zuriya. Algorithm na ƙoƙarin nemo yanke ta wannan hanyar ya bar baya da manyan hotuna. Wannan shi ne saboda gaskiyar cewa yanke ya zama rashin daidaituwa: bayan cire 5-10 vertices, yana yiwuwa a raba kawai 15-20.
Yana da kyau a lura cewa labarai game da mafi saurin algorithms suna amfani da dabarun ci gaba da yawa don zaɓar madaidaitan don rarrabuwa. Irin waɗannan fasahohin suna da aiwatarwa mai sarƙaƙƙiya kuma galibi rashin aiki mara kyau dangane da lokaci da ƙwaƙwalwa. Na kasa gano wadanda aka yarda da su a aikace.
Yadda Ake Aiwatar da Dokokin Sauƙaƙe
Mun riga muna da ra'ayoyi don kernelization. Bari in tunatar da ku:
- Idan akwai keɓantaccen gefe, share shi.
- Idan akwai juzu'in digiri 1, cire shi kuma ɗauki maƙwabcinsa don amsawa.
- Idan akwai juzu'in digiri aƙalla ku+1, mayar da shi.
Tare da biyu na farko komai a bayyane yake, tare da na uku akwai dabara ɗaya. Idan a cikin matsala mai ban dariya game da mashaya an ba mu iyakar iyaka k, to a cikin Ƙalubalen PACE kawai kuna buƙatar nemo murfin bangon mafi ƙarancin girman. Wannan shine sauyin Matsalolin Bincike na yau da kullun zuwa Matsalolin Yankewa; galibi babu bambanci tsakanin nau'ikan matsalolin biyu. A aikace, idan muna rubuta mai warware matsala don rufe matsala, za a iya samun bambanci. Misali, kamar a aya ta uku.
Daga mahangar aiwatarwa, akwai hanyoyi guda biyu don ci gaba. Hanya ta farko ita ake kira Iterative Deepening. Yana da kamar haka: za mu iya farawa da wasu ƙuntatawa masu ma'ana daga ƙasa akan amsar, sannan mu gudanar da algorithm ta amfani da wannan ƙuntatawa a matsayin ƙuntatawa akan amsar daga sama, ba tare da raguwa a cikin maimaitawa fiye da wannan ƙuntatawa ba. Idan mun sami wasu amsa, yana da tabbacin zai zama mafi kyau, in ba haka ba za mu iya ƙara wannan iyaka da ɗaya kuma mu sake farawa.
Wata hanya kuma ita ce adana wasu mafi kyawun amsa na yanzu da neman ƙaramar amsa, canza wannan siga idan an samo k don mafi girma yanke rassan da ba dole ba a cikin bincike.
Bayan gudanar da gwaje-gwaje na dare da yawa, na daidaita kan haɗuwa da waɗannan hanyoyi guda biyu: na farko, Ina gudanar da algorithm na tare da wani nau'i na iyaka akan zurfin bincike (zabar shi don ɗaukar lokaci mara kyau idan aka kwatanta da babban bayani) da kuma amfani da mafi kyau. mafita da aka samo azaman babban iyaka ga amsar - wato, zuwa abu ɗaya k.
Matsayin digiri 2
Mun yi ma'amala da ƙarshen digiri 0 da 1. Ya bayyana cewa ana iya yin wannan tare da matakan digiri na 2, amma wannan zai buƙaci ƙarin hadaddun ayyuka daga jadawali.
Don bayyana wannan, muna buƙatar ko ta yaya za mu zayyana madaidaitan. Bari mu kira kintinkiri na digiri 2 a tsaye v, da maƙwabtansa - maƙwabta x и y. Na gaba za mu sami lokuta biyu.
- Lokacin x и y - makwabta. Sannan zaku iya amsawa x и yda kuma v share. Lallai, daga wannan triangle aƙalla ana buƙatar ɗauka biyu a mayar da martani, kuma ba shakka ba za mu yi asara ba idan muka ɗauka. x и y: tabbas suna da wasu makwabta, kuma v Ba su nan.
- Lokacin x и y - ba makwabta ba. Sa'an nan kuma an bayyana cewa za'a iya manna dukkan kusoshi guda uku. Ma'anar ita ce, a cikin wannan yanayin akwai amsa mafi kyau, wanda zamu dauki ko dai v, ko duka biyun x и y. Bugu da ƙari, a cikin shari'ar farko dole ne mu dauki duk makwabta don amsawa x и y, amma a cikin na biyu ba lallai ba ne. Wannan daidai yayi daidai da shari'o'in lokacin da ba mu ɗauki ɗigon manne a cikin martani da lokacin da muka yi ba. Ya rage kawai a lura cewa a cikin lokuta biyu martani daga irin wannan aikin yana raguwa da ɗaya.
Yana da kyau a lura cewa wannan hanyar tana da wahala sosai don aiwatarwa daidai a cikin madaidaiciyar lokaci. Manne madaidaicin aiki ne mai rikitarwa; kuna buƙatar kwafin lissafin maƙwabta. Idan an yi wannan ba tare da sakaci ba, zaku iya ƙarewa tare da lokacin gudu na asymptotically (misali, idan kun kwafi gefuna da yawa bayan kowane gluing). Na yanke shawarar nemo gabaɗayan hanyoyi daga madaidaitan digiri na 2 da yin nazarin ɗimbin lamurra na musamman, kamar hawan keke daga irin waɗannan madaidaitan ko kuma daga duk irin waɗannan ɓangarorin sai ɗaya.
Bugu da ƙari, yana da mahimmanci cewa wannan aikin ya zama mai jujjuyawa, ta yadda lokacin dawowa daga maimaitawa za mu mayar da jadawali zuwa ainihin siffarsa. Don tabbatar da wannan, ban share lissafin gefen madaidaitan madaidaicin ba, sannan na san kawai gefuna da ake buƙatar zuwa inda. Wannan aiwatar da jadawali kuma yana buƙatar daidaito, amma yana ba da lokacin madaidaiciyar lokaci. Kuma ga zane-zane na dubun dubatar gefuna, ya dace da cache mai sarrafawa, wanda ke ba da fa'idodi masu yawa cikin sauri.
Madaidaicin kwaya
A ƙarshe, ɓangaren mafi ban sha'awa na kwaya.
Don farawa da, tuna cewa a cikin jadawali bipartite ana iya samun ƙaramin murfin bango ta amfani da shi . Don yin wannan, kuna buƙatar amfani da algorithm don nemo iyakar daidaitawa a can, sannan a yi amfani da theorem .
Tunanin kwaya mai linzami shine wannan: da farko mun rarraba jadawali, wato, maimakon kowane juyi. v mu kara kololuwa biyu и , kuma maimakon kowane gefe ku - v mu kara hakarkari biyu и . Jadawalin da aka samu zai zama bipartite. Bari mu nemo mafi ƙarancin murfin bango a ciki. Wasu madaidaitan jadawali na ainihi zasu isa can sau biyu, wasu sau ɗaya kawai, wasu kuma ba za su taɓa zuwa ba. Ka'idar Nemhauser-Trotter ta bayyana cewa a wannan yanayin ana iya cire madaidaitan da ba su buga ko sau daya ba sannan a mayar da wadanda suka buga sau biyu. Haka kuma, ta ce daga cikin sauran vertices (waɗanda suka buga sau ɗaya) kuna buƙatar ɗaukar akalla rabin a matsayin amsa.
Mun dai koyi barin ba fiye da haka 2k kololuwa Lallai, idan ragowar amsar ta kasance aƙalla rabin duka, to, babu sauran filaye a cikin duka. 2k.
Anan na sami damar ɗaukar ɗan ƙaramin mataki gaba. A bayyane yake cewa kwaya da aka gina ta wannan hanyar ya dogara da irin ƙaramin murfin bangon da muka ɗauka a cikin jadawali bipartite. Ina so in ɗauki ɗaya domin adadin ragowar ya zama kaɗan. A baya can, sun sami damar yin hakan a cikin lokaci kawai . Na zo da aiwatar da wannan algorithm a lokacin , don haka, ana iya nemo wannan cibiya a cikin jadawali na dubban ɗaruruwan madaidaitan a kowane matakin reshe.
sakamakon
Aiki yana nuna cewa maganina yana aiki da kyau akan gwaje-gwajen ɗari da yawa da gefuna dubu da yawa. A irin waɗannan gwaje-gwajen yana yiwuwa a yi tsammanin za a sami mafita cikin rabin sa'a. Yiwuwar samun amsa a cikin lokacin karɓuwa, bisa ƙa'ida, yana ƙaruwa idan jadawali yana da isassun adadi mai yawa na madaidaicin matsayi, misali, digiri 10 da sama.
Don shiga gasar, dole ne a aika da mafita . Yin la'akari da bayanin da aka gabatar a can , Magani na a cikin buɗaɗɗen gwaje-gwaje yana matsayi na uku cikin ashirin, tare da babban rata daga na biyu. A gaskiya, ba a bayyana gaba ɗaya yadda za a tantance mafita a gasar da kanta ba: alal misali, maganina ya wuce gwaje-gwaje kaɗan fiye da mafita a matsayi na hudu, amma a kan waɗanda suka wuce, yana aiki da sauri.
Za a san sakamakon gwajin da aka rufe a ranar XNUMX ga Yuli.
source: www.habr.com