Mosebetsi oa ho etsa lipatlisiso mohlomong ke karolo e thahasellisang ka ho fetisisa ea koetliso ea rona. Sepheo ke hore u itekoe ka tsela eo u e khethileng u ntse u le univesithing. Ka mohlala, liithuti tse tsoang libakeng tsa Software Engineering le Machine Learning hangata li ea ho etsa lipatlisiso lik'hamphaning (haholo-holo JetBrains kapa Yandex, empa eseng feela).
Ka poso ena ke tla bua ka morero oa ka ho Computer Science. E le karolo ea mosebetsi oa ka, ke ithutile le ho sebelisa mekhoa ea ho rarolla bothata bo tummeng ka ho fetisisa ba NP: bothata ba ho koahela vertex.
Matsatsing ana, mokhoa o khahlisang oa mathata a thata a NP o ntse o tsoela pele ka potlako haholo - li-algorithms tsa parameterized. Ke tla leka ho u potlakisa, ke u joetse li-algorithms tse bonolo tsa parameter mme ke hlalose mokhoa o le mong o matla o nthusitseng haholo. Ke hlahisitse liphetho tsa ka tlholisanong ea PACE Challenge: ho latela liphetho tsa liteko tse bulehileng, tharollo ea ka e nka sebaka sa boraro, 'me liphetho tsa ho qetela li tla tsejoa ka la 1 Phupu.
Ka 'na
Lebitso la ka ke Vasily Alferov, hona joale ke qeta selemo sa ka sa boraro Sekolong se Phahameng sa Moruo sa Sechaba sa Patlisiso ea Sechaba - St. Petersburg. Ke 'nile ka thahasella li-algorithms ho tloha matsatsing a sekolo, ha ke ne ke ithuta sekolong sa Moscow No. 179 'me ka atleha ho kenya letsoho ho Olympiads ea saense ea k'homphieutha.
Palo e lekanyelitsoeng ea litsebi tsa li-algorithms tsa parameterized li kena bareng...
Mohlala o nkiloeng bukeng
Ak'u nahane u le molebeli oa bareng motseng o monyenyane. Labohlano le leng le le leng, halofo ea toropo e tla bareng ea hau ho tla phomola, e leng se u fang mathata a mangata: o hloka ho lahlela bareki ba lerata ka ntle ho bareng ho thibela lintoa. Qetellong, oa khathala ebe u etsa qeto ea ho nka mehato ea thibelo.
Kaha toropo ea heno e nyane, u tseba hantle hore na ke lipara life tsa bareki bao ho ka etsahalang hore ba loane haeba ba ka qetella ba le bareng hammoho. Na u na le lethathamo la n batho ba tla tla bareng bosiung bona. U etsa qeto ea ho thibela batho ba bang hore ba tsoe ka har'a bar ntle le ho loana. Ka nako e ts'oanang, baokameli ba hau ha ba batle ho lahleheloa ke phaello mme ba ke ke ba thaba haeba u sa lumelle ho feta. k batho.
Ka bomalimabe, bothata bo ka pele ho uena ke bothata ba khale ba NP-hard. O ka nna wa mo tseba jwalo ka
Ho felisa monyetla oa ho loana tlhophisong ena ea likamano tse senyehileng lipakeng tsa baeti ba bar, o hloka ho boloka Bob, Daniel le Fedor ba le kantle. Ha ho na tharollo eo ho eona ho tla sala ba babeli feela.
Na see se bolela hore ke nako ea ho inehela le ho lumella bohle ho kena? A re hlahlobeng mekhoa e meng. Hantle, ho etsa mohlala, u ke ke ua lumella ho kena feela ba ka 'nang ba loana le palo e kholo haholo ea batho. Haeba motho a ka loana bonyane ka k+1 motho e mong, joale u ke ke ua mo lumella ho kena - ho seng joalo u tla tlameha ho thibela bohle ho tsoa k+1 batho ba toropo, bao a ka loanang le bona, e leng se tla khopisa boetapele.
E re u lahle bohle bao u ka ba khonang ho latela molao-motheo ona. Joale e mong le e mong a ka loana ka letho ho feta k batho. Ho ba lahla k monna, u ka thibela letho ho feta likhohlano. Sena se bolela hore haeba ho na le ho feta Haeba motho a ameha bonyane khohlanong e le ’ngoe, joale ka sebele u ke ke ua li thibela kaofela. Kaha, ha e le hantle, u tla lumella batho ba se nang likhohlano ka ho feletseng, u lokela ho feta likarolong tsohle tsa boholo ba leshome ho batho ba makholo a mabeli. Ho na le hoo e ka bang , 'me palo ena ea ts'ebetso e se e ka hlophisoa sehlopheng.
Haeba u ka khona ho nka ka mokhoa o sireletsehileng batho ba se nang khohlano ho hang, joale ho thoe’ng ka ba keneng ntoeng e le ’ngoe feela? Ha e le hantle, ba ka boela ba lumelloa ka ho koala lemati ho mohanyetsi oa bona. Ka 'nete, haeba Alice a loantšana le Bob feela, joale haeba re tlohela Alice ho tsoa ka bobeli ba bona, re ke ke ra lahleheloa: Bob a ka 'na a ba le likhohlano tse ling, empa Alice ka sebele ha a na tsona. Ho feta moo, ha ho utloahale hore re se ke ra kena ka bobeli ba rōna. Ka mor'a ts'ebetso e joalo ha ho sa na letho baeti ba nang le qetello e sa rarolloang: re na le feela likhohlano, e 'ngoe le e 'ngoe e na le barupeluoa ba babeli 'me e mong le e mong a ameha bonyane ho tse peli. Kahoo se setseng ke ho hlophisa dikgetho, tse ka nkoang habonolo halofo ea letsatsi ka laptop.
Ha e le hantle, ka ho beha mabaka ka tsela e bonolo u ka finyella maemo a khahlehang le ho feta. Hlokomela hore ka sebele re hloka ho rarolla liqabang tsohle, ke hore, ho tsoa ho sehlopha se seng le se seng se loantšanang, khetha bonyane motho a le mong eo re ke keng ra mo lumella ho kena. A re nahaneng ka algorithm e latelang: nka khohlano leha e le efe, eo ho eona re tlosang morupeluoa e mong ebe re qala ka ho pheta-pheta ho tloha ho setseng, ebe re tlosa e 'ngoe' me re qale ka ho pheta-pheta. Kaha re lahlela motho mohatong o mong le o mong, sefate sa recursion sa algorithm e joalo ke sefate sa binary sa botebo k, kahoo ka kakaretso algorithm e sebetsa ho kae n ke palo ea li-vertices, le m - palo ea likhopo. Mohlala oa rona, sena se ka ba limilione tse leshome, tse ka baloang ka metsotsoana e arohaneng eseng feela ka laptop, empa esita le ka selefouno.
Mohlala o ka holimo ke mohlala parameterized algorithm. Li-algorithms tsa parameterized ke li-algorithms tse tsamaeang ka nako f(k) poly(n)kae p - polynomial, f ke ts'ebetso e ikemetseng ea computable, le k - parameter e 'ngoe, eo, mohlomong, e tla ba nyane haholo ho feta boholo ba bothata.
Mabaka ohle pele a algorithm ena a fana ka mohlala kernelization ke e 'ngoe ea mekhoa e akaretsang ea ho theha li-algorithms tsa parameterized. Kernelization ke phokotso ea boholo ba bothata ho boleng bo lekantsoeng ke ts'ebetso ea paramente. Bothata bo hlahang hangata bo bitsoa kernel. Kahoo, ka ho beha mabaka a bonolo mabapi le likhato tsa vertices, re ile ra fumana quadratic kernel bakeng sa bothata ba Vertex Cover, e lekantsoeng ka boholo ba karabo. Ho na le litlhophiso tse ling tseo u ka li khethang bakeng sa mosebetsi ona (joalo ka Vertex Cover Above LP), empa ena ke tlhophiso eo re tla buisana ka eona.
Lebelo Phephetso
Tlholisano
Tlholisano e ntse e tuma selemo le selemo. Haeba u lumela lintlha tsa selelekela, selemong sena lihlopha tse 24 li nkile karolo tlholisanong ea ho rarolla bothata ba ho koahela vertex feela. Ke habohlokoa ho hlokomela hore tlhōlisano ha e nke lihora tse 'maloa kapa esita le beke, empa likhoeli tse' maloa. Lihlopha li na le monyetla oa ho ithuta lingoliloeng, ho tla le maikutlo a tsona a mantlha le ho leka ho li sebelisa. Ha e le hantle, tlhōlisano ena ke morero oa lipatlisiso. Mehopolo bakeng sa tharollo e sebetsang ka ho fetisisa le ho fana ka likhau tsa bahloli li tla tšoaroa hammoho le seboka.
Setšoantšo sa tharollo
Ho rarolla bothata ba ho koahela vertex, ke lekile ho sebelisa li-algorithms tsa parameterized. Hangata li na le likarolo tse peli: melao ea ho nolofatsa (e lebisang ho kernelization) le melao ea ho arola. Melao ea ho nolofatsa e ntse e tsoela pele ho kenya letsoho ka nako ea polynomial. Sepheo sa ho sebelisa melao e joalo ke ho fokotsa bothata ho bothata bo lekanang le bona bo bonyenyane. Melao ea ho nolofatsa ke karolo e theko e boima ka ho fetisisa ea algorithm, 'me ho sebelisa karolo ena ho lebisa ho nako eohle ea ho sebetsa sebakeng sa nako e bonolo ea polynomial. Tabeng ea rona, melao ea ho arohana e thehiloe tabeng ea hore bakeng sa vertex e 'ngoe le e' ngoe u lokela ho e nka kapa moahelani oa eona e le karabo.
Morero o akaretsang ke ona: re sebelisa melao ea ho nolofatsa, ebe re khetha vertex e 'ngoe, ebe re etsa li-call tse peli tse pheta-phetoang: ka lekhetlo la pele re e nka ka ho arabela,' me ho e 'ngoe re nka baahelani bohle ba eona. Sena ke seo re se bitsang ho petsoha (branching) haufi le vertex ena.
Hantle-ntle tlatsetso e le 'ngoe e tla etsoa morerong ona serapeng se latelang.
Mehopolo ea melao ea ho arola (brunching).
A re tšohleng mokhoa oa ho khetha vertex eo ho arohana ho tla etsahala.
Mohopolo o ka sehloohong o meharo haholo ka kutloisiso ea algorithmic: ha re nke vertex ea tekanyo e phahameng 'me re arohane ho eona. Ke hobane'ng ha e bonahala e le betere? Hobane lekaleng la bobeli la pitso e pheta-phetoang re tla tlosa li-vertices tse ngata ka tsela ena. U ka itšetleha ka kerafo e nyane e setseng mme re ka e sebetsa kapele.
Mokhoa ona, ka mekhoa e bonolo ea kernelization e seng e tšohliloe, e iponahatsa hantle mme e rarolla liteko tse ling tsa li-vertices tse likete tse 'maloa ka boholo. Empa, ka mohlala, ha e sebetse hantle bakeng sa li-graph tsa cubic (ke hore, li-graph tseo tekanyo ea vertex ka 'ngoe e leng tse tharo).
Ho na le mohopolo o mong o thehiloeng mohopolong o bonolo: haeba kerafo e khaotsoe, bothata ba likarolo tsa eona tse hokahaneng bo ka rarolloa ka boikemelo, ho kopanya likarabo qetellong. Sena, ka tsela, ke phetoho e nyane e tšepisitsoeng morerong, e tla potlakisa tharollo haholo: pele, tabeng ena, re ne re sebeletsa sehlahisoa sa linako bakeng sa ho bala likarabo tsa likarolo, empa hona joale re sebeletsa kakaretso. Le ho potlakisa branching, o hloka ho fetola graph e hokahaneng hore e be e khaotsoeng.
Joang ho e etsa? Haeba ho na le ntlha ea ho bua ka graph, u lokela ho loana ho eona. Ntlha ea ho hlalosa ke vertex eo ha e tlosoa, kerafo e lahleheloang ke khokahanyo ea eona. Lintlha tsohle tsa mateano a kerafo li ka fumanoa ho sebelisoa algorithm ea khale ka nako ea mola. Mokhoa ona o potlakisa lekala haholo.
Ha leha e le efe ea li-vertices tse khethiloeng e tlosoa, kerafo e tla arohana ka likarolo tse hokahaneng.
Re tla etsa sena, empa re batla ho feta. Ka mohlala, sheba likheo tse nyenyane tsa vertex ka har'a kerafo 'me u arole li-vertices tse tsoang ho eona. Tsela e sebetsang ka ho fetisisa eo ke e tsebang ea ho fumana bonyane ba lefats'e ba sehiloeng ke ho sebelisa sefate sa Gomori-Hu, se hahiloeng ka nako ea cubic. Ho PACE Challenge, boholo bo tloaelehileng ba kerafo ke li-vertices tse likete tse 'maloa. Boemong bona, libilione tsa liopereishene li hloka ho etsoa sebakeng se seng le se seng sa sefate sa recursion. Hoa fumaneha hore ho ke ke ha khoneha ho rarolla bothata ka nako e behiloeng.
Ha re leke ho ntlafatsa tharollo. Bonyane vertex sehiloeng pakeng tsa para ea vertices e ka fumanoa ke algorithm efe kapa efe e hahang phallo e phahameng. U ka e lumella ho netweke e joalo
Ke lekile ka makhetlo a 'maloa ho batla likheo lipakeng tsa li-vertices tse sa reroang ebe ke nka e leka-lekaneng ka ho fetisisa. Ka bomalimabe, sena se hlahisitse liphetho tse mpe litekong tse bulehileng tsa PACE Challenge. Ke ile ka e bapisa le algorithm e arolang li-vertices tsa tekanyo e phahameng ka ho fetisisa, ke li tsamaisa ka moeli oa botebo ba ho theoha. Algorithm e lekang ho fumana sehiloeng ka tsela ena e siile li-graph tse kholoanyane. Sena se bakoa ke taba ea hore likhahla li ile tsa fetoha tse sa leka-lekaneng haholo: ka mor'a ho tlosa li-vertices tse 5-10, ho ne ho ka khoneha ho arola 15-20 feela.
Ke habohlokoa ho hlokomela hore lingoloa tse mabapi le li-algorithms tse potlakileng ka ho fetesisa li sebelisa mekhoa e tsoetseng pele haholo ea ho khetha li-vertices bakeng sa ho petsoha. Mekhoa e joalo e na le ts'ebetsong e rarahaneng haholo 'me hangata e sa sebetse hantle ho latela nako le mohopolo. Ke ne ke sa khone ho khetholla tse loketseng ho sebelisoa.
Kamoo U ka Sebelisang Melao ea ho Nolofatsa
Re se re ntse re e-na le mehopolo ea kernelization. E re ke u hopotse:
- Haeba ho na le vertex e ka thoko, e tlose.
- Haeba ho na le vertex ea degree 1, e tlose 'me u nke moahelani oa eona ho arabela.
- Haeba ho na le vertex ea degree bonyane k+1, e khutlise.
Ka tse peli tsa pele ntho e 'ngoe le e' ngoe e hlakile, ka ea boraro ho na le leqheka le le leng. Haeba bothateng ba li-comic mabapi le bar re ne re fuoa moeli o ka holimo oa k, ebe ho PACE Challenge o hloka feela ho fumana sekoaelo sa vertex sa boholo bo fokolang. Ena ke phetoho e tloaelehileng ea Mathata a Patlo ho Mathata a Qeto; hangata ha ho na phapang lipakeng tsa mefuta e 'meli ea mathata. Ha e le hantle, haeba re ngola tharollo bakeng sa bothata ba ho koahela vertex, ho ka 'na ha e-ba le phapang. Mohlala, joalo ka ntlheng ea boraro.
Ho latela pono ea ts'ebetsong, ho na le mekhoa e 'meli ea ho tsoela pele. Mokhoa oa pele o bitsoa Iterative Deepening. E ka tsela e latelang: re ka qala ka tšitiso e itseng e utloahalang ho tloha ka tlase ho karabo, ebe re tsamaisa algorithm ea rona re sebelisa thibelo ena e le tšitiso ea karabo e tsoang holimo, ntle le ho theoha ka morao ho feta thibelo ena. Haeba re fumane karabo e itseng, ho netefalitsoe hore e nepahetse, ho seng joalo re ka eketsa moeli ona ka e le 'ngoe ebe re qala hape.
Mokhoa o mong ke ho boloka karabo e nepahetseng ea hajoale le ho batla karabo e nyane, ho fetola paramethara ena ha e fumanoa k bakeng sa ho khaola ho hoholo ha makala a sa hlokahaleng ha ho batloa.
Ka mor'a ho etsa liteko tse 'maloa tsa bosiu, ke ile ka rarolla motsoako oa mekhoa ena e' meli: pele, ke tsamaisa algorithm ea ka ka mofuta o itseng oa moeli holim'a botebo ba ho batla (ho e khetha e le hore ho nka nako e fokolang ho bapisoa le tharollo e kholo) le ho sebelisa se molemo ka ho fetisisa. tharollo e fumanoang e le moeli o ka holimo oa karabo - ke hore, ho ntho e le 'ngoe k.
Litefiso tsa degree ea 2
Re sebetsana le li-vertices tsa degree 0 le 1. Hoa fumaneha hore sena se ka etsoa ka li-vertices tsa degree 2, empa sena se tla hloka ts'ebetso e rarahaneng ho tsoa ho kerafo.
Ho hlalosa sena, re hloka ho khetha li-vertices ka tsela e itseng. Ha re bitse vertex ea degree 2 vertex v, le baahelani ba eona - vertices x и y. E latelang re tla ba le linyeoe tse peli.
- Ha x и y - baahelani. Joale u ka araba x и yle v hlakola. Ha e le hantle, ho tloha ho khutlotharo ena bonyane li-vertices tse peli li lokela ho nkoa e le ho khutlisa, 'me ka sebele re ke ke ra lahleheloa ke haeba re nka. x и y: mohlomong ba na le baahelani ba bang, le v Ha ba eo mona.
- Ha x и y - eseng baahisane. Ebe ho boleloa hore li-vertices tse tharo kaofela li ka kopanngoa ho e le 'ngoe. Khopolo ke hore tabeng ena ho na le karabo e nepahetseng, eo re e nkang ho eona v, kapa mahlakore ka bobeli x и y. Ho feta moo, tabeng ea pele re tla tlameha ho nka baahelani bohle ho arabela x и y, empa ka lekhetlo la bobeli ha ho hlokahale. Sena se lumellana hantle le linyeoe ha re sa nke vertex e khomaretsoeng ha re arabela le ha re etsa joalo. E sala feela ho hlokomela hore maemong ana ka bobeli karabelo e tsoang ts'ebetsong e joalo e fokotseha ka e le 'ngoe.
Ke habohlokoa ho hlokomela hore mokhoa ona o thata haholo ho o sebelisa ka mokhoa o nepahetseng ka nako e nepahetseng. Li-vertices tsa Gluing ke ts'ebetso e rarahaneng; o hloka ho kopitsa manane a baahisani. Haeba sena se etsoa ka mokhoa o sa tsotelleng, u ka qetella u e-na le nako ea ho sebetsa e sa sebetseng hantle (mohlala, haeba u kopitsa likarolo tse ngata ka mor'a ho khoasolla ka 'ngoe). Ke ile ka ikemisetsa ho fumana litsela tse felletseng ho tsoa ho li-vertices tsa degree 2 le ho sekaseka letoto la linyeoe tse ikhethang, joalo ka lipotoloho tse tsoang ho li-vertices tse joalo kapa ho tsoa litsing tsohle tse joalo ntle le e le 'ngoe.
Ho phaella moo, hoa hlokahala hore ts'ebetso ena e khutlisetsoe morao, e le hore ha re khutla ho tloha recursion re khutlisetsa graph ka mokhoa oa eona oa pele. Ho etsa bonnete ba sena, ha kea hlakisa manane a holimo a li-vertices tse kopantsoeng, ebe ke tseba feela hore na ke lithako life tse lokelang ho ea kae. Ts'ebetso ena ea li-graph e boetse e hloka ho nepahala, empa e fana ka nako e nepahetseng ea mola. 'Me bakeng sa li-graph tsa mashome a likete a mathōko, e lumellana le cache ea processor, e fanang ka melemo e meholo ka lebelo.
Mohala oa kernel
Qetellong, karolo e thahasellisang ka ho fetisisa ea kernel.
Ho qala, hopola hore ho li-graph tsa bipartite bonyane sekoaelo sa vertex se ka fumanoa se sebelisoa . Ho etsa sena, o hloka ho sebelisa algorithm
Mohopolo oa kernel e otlolohileng ke ona: pele re kopanya graph, ke hore, sebakeng sa vertex ka 'ngoe. v ha re kenye litlhōrō tse peli и , mme sebakeng sa ntlha ka nngwe u-v a re kenye likhopo tse peli и . Kerafo e hlahisoang e tla ba bipartite. A re fumaneng bonyane sekoahelo sa vertex ho eona. Li-vertices tse ling tsa graph ea mantlha li tla fihla moo habeli, tse ling hanngoe feela, tse ling ha ho mohla. Khopolo-taba ea Nemhauser-Trotter e bolela hore tabeng ena motho a ka ntša lithapo tse sa otlang le hanngoe feela ebe o khutlisa tse otlang habeli. Ho feta moo, o re ho li-vertices tse setseng (tse otlang hang) o hloka ho nka bonyane halofo e le karabo.
Re sa tsoa ithuta ho tlohela ho feta 2k tlhoro Ehlile, haeba karabo e setseng e le bonyane halofo ea li-vertices tsohle, ha ho na li-vertices ka kakaretso ho feta. 2k.
Mona ke ile ka khona ho nka mohato o monyenyane oa ho ea pele. Ho hlakile hore kernel e hahiloeng ka tsela ena e itšetlehile ka hore na re nkile sekoaelo sa vertex sa mofuta ofe ka graph ea bipartite. Ke kopa ho nka e le 'ngoe e le hore palo ea li-vertices tse setseng e fokotsehe. Pele, ba ne ba khona ho etsa sena feela ka nako . Ke ile ka tla ka ts'ebetsong ea algorithm ena ka nako , ka hona, motheo ona o ka batlisisoa ho li-graph tsa li-vertices tse makholo a likete sethaleng ka seng sa makala.
sephetho
Boikoetliso bo bonts'a hore tharollo ea ka e sebetsa hantle litekong tsa li-vertices tse makholo a 'maloa le likhohlo tse likete tse' maloa. Litekong tse joalo ho ka khoneha ho lebella hore tharollo e tla fumanoa ka halofo ea hora. Monyetla oa ho fumana karabo ka nako e amohelehang, ha e le hantle, e eketseha haeba kerafo e na le palo e lekaneng ea li-vertices tsa tekanyo e phahameng, mohlala, tekanyo ea 10 le ho feta.
Ho kenya letsoho tlholisanong, ho ne ho tlameha ho romelloa litharollo ho
Liphetho tsa liteko tse koetsoeng li tla tsejoa ka la XNUMX Phupu.
Source: www.habr.com