Ko nga mahi rangahau pea te waahanga tino pai o a maatau whakangungu. Ko te whakaaro ko te whakamatau i a koe ano i te huarahi i whiriwhiria e koe i a koe i te whare wananga. Hei tauira, he maha nga wa ka haere nga akonga mai i nga waahi o te Hangarau Pūmanawa me te Ako Miihini ki te rangahau i nga kamupene (te nuinga o JetBrains, Yandex ranei, engari ehara i te mea anake).
I tenei pou ka korero ahau mo taku kaupapa i roto i te Rorohiko Pūtaiao. Hei waahanga o aku mahi, i ako ahau me te whakamahi i nga huarahi ki te whakaoti i tetahi o nga raruraru NP-pakeke tino rongonui: raruraru hipoki pito.
I enei wa, he huarahi whakamere ki nga raru NP-pakeke kei te whanake tere - nga tohu algorithm. Ka ngana ahau ki te whakaara i a koe ki te tere, ki te korero atu ki a koe i etahi o nga huringa tawhā ngawari me te whakaahua i tetahi tikanga kaha i tino awhina i ahau. I whakaatu ahau i aku hua ki te whakataetae PACE Wero: e ai ki nga hua o nga whakamatautau tuwhera, ka eke taku otinga ki te turanga tuatoru, ka mohio nga hua whakamutunga hei te 1 o Hurae.
Mōku anō
Ko Vasily Alferov toku ingoa, kei te whakaoti ahau i taku tau tuatoru i te Whare Wananga Rangahau National Higher School of Economics - St. Kua aro ahau ki nga algorithms mai i nga ra o taku kura, i taku ako i te kura o Moscow Nama 179 me te whai waahi angitu ki nga Olympiads pūtaiao rorohiko.
He maha o nga tohunga mo nga taarua algorithm ka uru ki te pae...
He tauira i tangohia mai i te pukapuka
Whakaarohia ko koe he kaitiaki parepare i tetahi taone iti. Ia Paraire, ka tae mai te haurua o te taone ki to paera ki te whakangawari, he nui te raru ki a koe: me peia e koe nga kaihoko ngangau ki waho o te pa kia kore ai e whawhai. I te mutunga, ka makona koe ka whakatau koe ki te mahi aukati.
I te mea he iti to taone, e mohio ana koe ko wai nga takirua o nga kaiwhaiwhai ka kaha ki te whawhai mena ka noho tahi raua ki roto i te paera. Kei a koe he rarangi o n nga tangata ka haere mai ki te paera i tenei po. Ka whakatau koe ki te pupuri i etahi tangata o te taone ki waho o te paera me te kore tetahi e uru ki te whawhai. I te wa ano, kaore o rangatira e hiahia ki te ngaro nga hua me te kore e koa ki te kore koe e tuku atu k iwi.
Kia aroha mai, ko te raruraru kei mua i a koe he raruraru NP-pakeke. Ka mohio pea koe ki a ia , hei rapanga hipoki pokapu ranei. Mo enei raruraru, i roto i te keehi whanui, kaore he algorithms e mahi ana i te waa e manakohia ana. Ki te tika, ko te whakapae koretake me te tino kaha ETH (Exponential Time Hypothesis) e kii ana kaore e taea te whakaoti i tenei raru i te waa. , ara, kaore e taea e koe te whakaaro ki tetahi mea tino pai ake i te rapu katoa. Hei tauira, me kii ka haere mai tetahi ki to paera n = 1000 Tangata. Na ko te rapu katoa kōwhiringa e tata ana - nui haurangi. Waimarie, kua hoatu e to whakahaere he rohe ki a koe k = 10, no reira he iti ake te maha o nga huinga e hiahia ana koe ki te huri: ko te maha o nga huinga o nga huānga tekau he . He pai ake tenei, engari kaore ano kia tatauhia i roto i te ra ahakoa i runga i te roopu kaha.
Hei whakakore i te tupono o te whawhai i roto i tenei whirihoranga o nga whanaungatanga uaua i waenga i nga manuhiri o te paera, me waiho e koe a Bob, Daniel me Fedor. Karekau he otinga e rua anake ka mahue.
Ko te tikanga tenei kua tae ki te wa ki te tuku me te tuku i nga tangata katoa ki roto? Kia whai whakaaro tatou ki etahi atu whiringa. Ae, hei tauira, kaore e taea e koe te tuku i te hunga anake ka whawhai ki te tini o nga tangata. Mena ka taea e tetahi te whawhai i te iti rawa k+1 tetahi atu tangata, kare rawa e taea e koe te tuku i a ia ki roto - ki te kore ka peia e koe nga tangata katoa ki waho k+1 nga tangata o te taone, ka taea e ia te whawhai, ka tino raruraru te kaiarahi.
Kia peia e koe nga tangata katoa ka taea e koe i runga i tenei kaupapa. Na ka taea e te katoa te whawhai me te kore e nui ake k tangata. Ka maka atu ki waho k e te tangata, kare e taea e koe te aukati noa atu pakanga. Ko te tikanga mena he nui ake i te Mena ka uru tetahi tangata ki tetahi pakanga, katahi ka kore e taea e koe te aukati katoa. I te mea, o te akoranga, ka tino tukuna e koe nga tangata kore-patupatu, me haere koe ki nga waahanga iti katoa o te rahi tekau mai i te rua rau tangata. He tata , a ko tenei maha o nga mahi ka taea te whakariterite i runga i te tautau.
Mena ka taea e koe te kawe humarie i nga tangata kaore he pakanga, ka pehea te hunga ka uru ki te pakanga kotahi? Inaa, ka taea hoki te tuku ki roto ma te kati i te kuaha ki to hoa riri. Inaa, mena kei te whawhai a Alice ki a Bob anake, mena ka tukuna e tatou a Alice ki waho o raua tokorua, kare tatou e ngaro: He raruraru ano pea a Bob, engari karekau i a Alice. I tua atu, kare he tikanga kia kaua maua e tuku i a maua ki roto. I muri i enei mahi karekau he toenga Ko nga manuhiri kaore i whakatauhia: kei a matou anake nga taupatupatu, e rua nga kaiuru o ia tangata, e rua neke atu ranei. Na ko nga mea e toe ana ko te whakariterite kōwhiringa, e taea te whakaaro ngāwari te hawhe ra i runga i te pona.
Inaa, ma te whakaaro ngawari ka taea e koe te whakatutuki i nga ahuatanga tino ataahua. Kia mahara me tino whakatau tatou i nga tautohetohe katoa, ara, mai i ia tokorua e taupatupatu ana, whiriwhiri kia kotahi te tangata e kore e tukuna e tatou. Kia whai whakaaro tatou ki te algorithm e whai ake nei: tango i tetahi pakanga, ka tangohia e tatou tetahi kaiuru ka timata mai i te toenga, ka tango i tetahi atu ka timata ano hoki. I te mea ka makahia e matou tetahi ki waho i ia taahiraa, ko te rakau recursion o taua algorithm he rakau rua o te hohonu k, na i te katoa ka mahi te algorithm i roto te wahi n ko te maha o nga poutoko, me m - te maha o nga rara. I roto i to maatau tauira, tata ki te tekau miriona tenei, ka taea te tatau i roto i te waahanga tuarua kaore i runga i te pona anake, engari i runga i te waea waea.
Ko te tauira i runga ake nei he tauira algorithmized tawhā. Ko nga algorithms kua whakatapua he algorithms e rere ana i te waa f(k) poly(n)te wahi p - polynomial, f he taumahi rorohiko noa, a k - etahi tawhā, tera pea, ka iti ake i te rahi o te raru.
Ko nga whakaaro katoa i mua i tenei algorithm he tauira te whakawhanaunga Ko tetahi o nga tikanga whaanui mo te hanga i nga algorithms tawhā. Ko te Kernelization te whakaiti i te rahi o te rapanga ki te uara e whakawhāitihia ana e te mahi o te tawhā. Ko te raruraru ka puta mai i te nuinga o te wa ka kiia ko te kernel. No reira, na roto i te whakaaro ngawari mo nga nekehanga o nga poupou, i whiwhi matou i te kakano tapawha mo te raru o te Uwhi Pouaka, kua tohua e te rahi o te whakautu. Ko etahi atu tautuhinga ka taea e koe te whiriwhiri mo tenei mahi (penei i te Vertex Cover Above LP), engari koinei te waahi ka korerohia e matou.
Te Wero Pace
Whakataetae (The Parameterized Algorithms and Computational Experiments Challenge) i whanau i te tau 2015 ki te whakatuu hononga i waenga i nga algorithms tawhā me nga huarahi e whakamahia ana hei whakaoti rapanga rorohiko. Ko nga whakataetae tuatahi e toru i whakatapua ki te rapu i te whanui rakau o te kauwhata (), e rapu ana i tetahi rakau Steiner () me te rapu i te huinga poupou ka tapahia nga huringa (). I tenei tau, ko tetahi o nga raru ka taea e koe te whakamatau i to ringa ko te raru o te uhi i runga ake nei.
Kei te rongonui te whakataetae ia tau. Ki te whakapono koe ki nga raraunga tuatahi, i tenei tau e 24 nga kapa i uru ki te whakataetae ki te whakaoti i te raru o te uhi o runga anake. He mea tika kia mahara ko te whakataetae e kore e maha nga haora, ahakoa he wiki, engari he maha nga marama. Ka whai waahi nga roopu ki te ako i nga tuhinga, ki te whakaputa i o raatau ake whakaaro taketake me te ngana ki te whakatinana. Ko te tikanga, he kaupapa rangahau tenei whakataetae. Ko nga whakaaro mo nga otinga tino whai hua me te whakawhiwhinga i nga toa ka tu tahi me te hui (Ko te Huihuinga Ao mo te Whakatairanga Whakatairanga me te Tika) hei waahanga o te hui a-tau nui rawa atu i Uropi. . Ka kitea etahi atu korero mo te whakataetae ake i , ka takoto nga hua o nga tau o mua .
Hoahoa otinga
Hei whakaoti i te raru o te uhi o te pito, i whakamatau ahau ki te whakamahi i nga algorithm kua whakaritea. E rua nga wahanga: ko nga ture whakangawari (e arai ana ki te kernelization) me nga ture wehewehe. Ko nga ture whakangawari ko te tukatuka o mua o te whakaurunga i te wa polynomial. Ko te kaupapa o te whakamahi i aua ture he whakaiti i te raruraru ki te raruraru iti ake. Ko nga ture whakangawari te waahanga utu nui o te algorithm, a ko te whakamahi i tenei waahanga ka arahi ki te katoa o te waa whakahaere hei utu mo te wa polynomial ngawari. I roto i a maatau, ko nga ture wehewehe i runga i te meka mo ia pito me tango e koe, ko tona hoa tata ranei hei whakautu.
Ko te kaupapa whaanui ko tenei: ka whakamahia e matou nga ture whakangawari, katahi ka kowhiria etahi tohu, ka rua nga waea recursive: i te tuatahi ka tangohia hei whakautu, i tetahi atu ka tango i ona hoa tata katoa. Koia tenei e kiia nei ko te wehenga (manga) i te taha o tenei pito.
Kotahi tonu te taapiri atu ki tenei kaupapa i te wharangi e whai ake nei.
Nga whakaaro mo te wehewehe (brunching) ture
Kia matapakihia me pehea te kowhiri i tetahi pito ka puta te wehenga.
Ko te whakaaro matua ko te tino apo i roto i te tikanga algorithmic: me tango tetahi pito o te tohu teitei ka wehea ki runga. He aha te ahua pai ake? Na te mea i roto i te peka tuarua o te karanga recursive ka tangohia e matou te maha o nga poutoko penei. Ka taea e koe te tatau ki te kauwhata iti e toe ana ka taea e matou te mahi tere.
Ko tenei huarahi, me nga tikanga whakamaarama ngawari kua korerohia, he pai te whakaatu i a ia ano me te whakaoti i etahi whakamatautau mo nga mano tini o te rahi. Engari, hei tauira, kaore i te pai te mahi mo nga kauwhata putorino (ara, nga kauwhata e toru nga tohu o ia pito).
He whakaaro ano kei runga i te whakaaro tino ngawari: ki te momotuhia te kauwhata, ka taea te whakatau takitahi te raruraru i runga i ona waahanga hono, me te whakakotahi i nga whakautu ki te mutunga. Ko tenei, i te ara, he whakarereketanga iti i oatihia i roto i te kaupapa, ka tino tere ake te otinga: i mua, i tenei keehi, i mahi matou mo te hua o nga wa mo te tatau i nga whakautu o nga waahanga, engari inaianei ka mahi matou mo te tapeke. A, kia tere ake te peka, me huri te kauwhata hono ki te momo momotu.
Me pehea te mahi? Mena he tohu korero kei te kauwhata, me whawhai koe. Ko te tohu toi he tohu ka tangohia, ka ngaro te hononga o te kauwhata. Ka kitea nga tohu honohono katoa i roto i te kauwhata ma te whakamahi i te algorithm puāwaitanga i roto i te wa raina. Ko tenei huarahi ka tino tere ake te manga.
Ina tangohia tetahi o nga poupou kua tohua, ka wehea te kauwhata ki nga waahanga hono.
Ka mahia e matou tenei, engari e hiahia ana matou kia nui ake. Hei tauira, titiro mo nga tapahanga pito iti o te kauwhata, ka wehea ma te taha o nga poupou mai i reira. Ko te huarahi tino pai e mohio ana ahau ki te kimi i te tapahanga iti rawa o te ao ko te whakamahi i te rakau Gomori-Hu, he mea hanga i roto i te waa putoru. I roto i te Wero PACE, ko te rahi o te kauwhata e hia mano nga poupou. I tenei ahuatanga, he maha nga piriona o nga mahi me mahi ki ia pito o te rakau recursion. Ka puta mai kaore e taea te whakaoti i te raru i roto i te waa kua whakaritea.
Kia ngana ki te arotau i te otinga. Ko te tapahi pito iti rawa i waenga i nga poutoko takirua ka kitea e tetahi algorithm e hanga ana i te rerenga teitei. Ka taea e koe te tuku ki runga i taua whatunga , i roto i nga mahi ka tino tere te mahi. Kei te whakapae ahau ka taea te whakaatu i te whakatau tata mo te wa whakahaere , kua tino whakaaetia.
He maha nga wa i whakamatau ahau ki te rapu mo nga tapahi i waenga i nga takirua o nga poupou matapōkere me te tango i te mea tino taurite. Heoi, he kino nga hua i puta i nga whakamatautau PACE Wero tuwhera. I whakatauritea e au ki te algorithm e wehewehe ana i nga poupou o te taumata teitei, e whakahaere ana me te iti o te hohonutanga o te hekenga. Whai muri i tetahi algorithm e ngana ana ki te rapu tapahi penei, ka waiho nga kauwhata nui ake. Ko tenei na te mea ko nga tapahi i puta he tino koretake: kua tangohia e 5-10 nga pito, ka taea te wehe i te 15-20 anake.
Kia mahara ko nga tuhinga mo nga algorithms tere tere e whakamahi ana i nga tikanga matatau ake mo te kowhiri i nga poupou mo te wehenga. Ko enei tikanga he tino uaua te whakatinanatanga me te maha o nga mahi ngoikore i runga i te waa me te mahara. Kaore i taea e au te tautuhi i nga mea e tino manakohia ana mo te mahi.
Me pehea te Hoatu i nga Ture Whakamaamaa
Kei a matou ano nga whakaaro mo te whakangao. Kia whakamahara ahau ki a koe:
- Mēnā he kōtaha taratahi, mukua.
- Mēnā he tohu tohu 1, tangohia, ka mau ki te hoa tata hei whakautu.
- Mena he tohu tohu kei te iti rawa k+1, whakahokia mai.
Ma nga mea tuatahi e rua ka marama nga mea katoa, me te tuatoru he mahi kotahi. Mena i roto i te raruraru kōmeke e pā ana ki te pae i hoatu ki a matou te rohe o runga o k, katahi i roto i te Wero PACE me rapu noa koe i te uhi o te pito o te iti rawa. He panoni angamaheni tenei o nga Raruraru Rapu hei Raruraru Whakataunga; he maha tonu karekau he rereketanga i waenga i nga momo raru e rua. I roto i te mahi, mena kei te tuhi tatou i te whakaotinga mo te rapanga kapi i te tihi, tera pea he rereke. Hei tauira, pera i te wahanga tuatoru.
Mai i te tirohanga whakatinanatanga, e rua nga huarahi hei haere tonu. Ko te huarahi tuatahi ka kiia ko Iterative Deepening. Ko te mea e whai ake nei: ka taea e tatou te timata me etahi herenga whaitake mai i raro i runga i te whakautu, katahi ka whakahaere i ta tatou algorithm ma te whakamahi i tenei herenga hei herenga mo te whakautu mai i runga ake nei, me te kore e heke ki raro i te recurring i tenei herenga. Mena kua kitea e matou etahi whakautu, he mea tino pai, ki te kore ka taea e taatau te whakanui ake i tenei tepe ma te kotahi ka timata ano.
Ko tetahi atu huarahi ko te penapena i etahi whakautu tino pai o naianei me te rapu whakautu iti ake, ka huri i tenei tawhā ina kitea k kia nui ake te tapahi i nga manga koretake i te rapu.
I muri i te whakahaere i etahi whakamatautau i ia po, ka whakatauhia e au he huinga o enei tikanga e rua: tuatahi, ka whakahaerehia e ahau taku algorithm me etahi momo rohe mo te hohonu o te rapu (te kowhiri kia kore e iti te waa ki te whakataurite ki te otinga matua) me te whakamahi i te pai rawa atu. ka kitea te otinga hei tepe o runga ki te whakautu - ara, ki te mea ano k.
Ko nga tohu tohu 2
Kua mahia e matou nga poupou o te tohu 0 me te 1. Ko te ahua ka taea tenei ki nga poupou o te tohu 2, engari ka nui ake nga mahi uaua mai i te kauwhata.
Hei whakamaarama i tenei, me tohu e tatou nga tohu. Karangatia te tohu tohu tohu 2 he tohu v, me ona hoa tata - vertices x и y. I muri mai ka rua nga keehi.
- Ahea x и y - hoa tata. Na ka taea e koe te whakautu x и ya v whakakore. Ae ra, mai i tenei tapatoru me tango kia rua nga kokonga hei utu, a ka kore tatou e ngaro ki te tango tatou x и y: tera pea etahi atu hoa tata, a v Kaore ratou i konei.
- Ahea x и y - ehara i nga hoa tata. Kātahi ka kīia ka taea te whakapiri i ngā poutū e toru ki te kotahi. Ko te whakaaro kei roto i tenei keehi he whakautu tino pai, kei roto i a maatau te tango v, nga pito e rua ranei x и y. Ano, i roto i te take tuatahi ka whai tatou ki te tango i nga hoa tata katoa i roto i te whakautu x и y, engari i te tuarua kaore e tika. He rite tonu tenei ki nga keehi ka kore tatou e tango i te tihi kapia hei whakautu me te wa e mahi ana tatou. Ka noho tonu ki te kite i nga keehi e rua ka heke iho te whakautu mai i taua mahi ma te kotahi.
He mea tika kia mohio he tino uaua tenei huarahi ki te whakatinana tika i roto i te waa raina tika. Ko te whakapiri i nga poupou he mahi uaua; me tuhi koe i nga rarangi o nga hoa tata. Mena ka mahia marietia tenei, ka taea e koe te mutunga ki te waa whakahaere asymptotically suboptimal (hei tauira, mena ka kape koe i te maha o nga tapa i muri i ia whakapiri). I whakatau ahau ki te rapu i nga huarahi katoa mai i nga poupou o te tohu 2 me te tātari i te tini o nga keehi motuhake, penei i nga huringa mai i aua poupou, mai i aua poupou katoa haunga te kotahi.
I tua atu, he mea tika kia hokia tenei mahi, na ka hoki mai i te recursion ka whakahokia te kauwhata ki tona ahua taketake. Hei whakarite i tenei, kaore au i whakawātea i nga rarangi tapa o nga poutoko hanumi, katahi au ka mohio ko nga tapa me haere ki hea. Ko tenei whakatinanatanga o nga kauwhata me tika ano, engari he wa tika. A, mo nga kauwhata o nga mano tini o nga taha, ka uru ki roto i te keteroki tukatuka, e whai hua nui ana mo te tere.
kākano rārangi
Ka mutu, ko te waahanga tino whakamere o te kernel.
Hei timata, maharatia kei roto i nga kauwhata takirua ka kitea te uhi pito iti rawa ma te whakamahi . Ki te mahi i tenei me whakamahi koe i te algorithm kia kitea ai te tino tauritenga ki reira, katahi ka whakamahi i te kaupapa .
Ko te whakaaro o te kakano raina ko tenei: tuatahi ka wehea e tatou te kauwhata, ara, hei utu mo ia pou v me tapiri e rua nga tihi и , a hei utu mo ia tapa koe - v kia rua nga rara и . Ko te kauwhata ka puta ko te wahanga rua. Kia kimihia te uhi pito iti rawa o roto. Ko etahi pooti o te kauwhata taketake ka tae atu ki reira e rua, ko etahi kotahi anake, ko etahi kaore. E kii ana te kaupapa Nemhauser-Trotter i tenei keehi ka taea e te tangata te tango i nga poutokonga karekau i pa ki te kotahi, ka whakahoki ano i nga mea i pa ki te rua. I tua atu, e kii ana ia mo nga toenga poutoko (ko nga mea i pa kotahi) me tango e koe te haurua hei whakautu.
Katahi ano matou ka ako ki te wehe atu 2k nga tihi Inaa, mena ko te toenga o te whakautu he haurua o nga poutoko katoa, karekau he nui ake nga poutokonga katoa 2k.
I konei ka taea e au te hikoi ki mua. E marama ana ko te kakano i hangaia penei e whakawhirinaki ana ki te ahua o te uhi hiku iti i tangohia e matou i te kauwhata takirua. E hiahia ana ahau ki te tango i tetahi kia iti te maha o nga poutoko e toe ana. I mua, i taea e ratou te mahi i tenei wa anake . I puta mai he whakatinanatanga o tenei algorithm i te waa , no reira, ka taea te rapu i tenei matua i roto i nga kauwhata o nga rau mano o nga poupou i ia wahanga manga.
hua
E whakaatu ana te parakatihi he pai te mahi o taku otinga i runga i nga whakamatautau o te maha rau poupou me te maha mano nga taha. I roto i enei whakamatautau ka taea te tumanako ka kitea he otinga i roto i te hawhe haora. Ko te tupono ka kitea he whakautu i roto i te waa e whakaaetia ana, inaa ka piki ake mena he nui te maha o nga poutoko teitei o te kauwhata, hei tauira, tohu 10 me te teitei ake.
Hei whakauru atu ki te whakataetae, me tuku nga otinga ki . Ma te whakatau i nga korero kua whakaatuhia ki reira , ko taku otinga i roto i nga whakamatautau tuwhera kei te tuatoru o nga rua tekau, me te waahi nui mai i te tuarua. Ki te tino pono, kaore i te tino marama me pehea te arotake i nga otinga i te whakataetae ano: hei tauira, he iti ake nga whakamatautau i taku otinga i te otinga i te waahi tuawha, engari ki nga mea ka paahitia, ka tere ake te mahi.
Ko nga hua o nga whakamatautau kati ka mohiotia hei te 1 o Hurae.
Source: will.com