Is dòcha gur e obair rannsachaidh am pàirt as inntinniche den trèanadh againn. Is e am beachd feuchainn ort fhèin anns an t-slighe a thagh thu fhad ‘s a tha thu fhathast san oilthigh. Mar eisimpleir, bidh oileanaich bho raointean Innleadaireachd Bathar-bog agus Ionnsachadh Inneal gu tric a’ dol a dhèanamh rannsachadh ann an companaidhean (gu sònraichte JetBrains no Yandex, ach chan ann a-mhàin).
Anns an dreuchd seo bruidhnidh mi mun phròiseact agam ann an Saidheans Coimpiutaireachd. Mar phàirt den obair agam, rinn mi sgrùdadh agus chuir mi an gnìomh dòighean-obrach airson fuasgladh fhaighinn air aon de na duilgheadasan NP-cruaidh as ainmeil: duilgheadas còmhdach vertex.
An-diugh, tha dòigh-obrach inntinneach a thaobh duilgheadasan NP-cruaidh a 'leasachadh gu math luath - algorithms parameterized. Feuchaidh mi ri do thoirt suas gu luath, innsidh mi dhut cuid de algorithms parameterichte sìmplidh agus bheir mi cunntas air aon dòigh chumhachdach a chuidich mi gu mòr. Thaisbean mi na toraidhean agam aig farpais PACE Challenge: a rèir toraidhean deuchainnean fosgailte, tha am fuasgladh agam a’ gabhail an treas àite, agus bidh fios air na toraidhean deireannach air 1 Iuchar.
Mu mo dheidhinn fhèin
Is e m ’ainm Vasily Alferov, tha mi a-nis a’ crìochnachadh an treas bliadhna agam aig Sgoil Eaconamas Àrd-ìre an Oilthigh Rannsachaidh Nàiseanta - St. Tha ùidh air a bhith agam ann an algorithms bho na làithean sgoile agam, nuair a bha mi ag ionnsachadh aig sgoil Moscow Àireamh 179 agus gu soirbheachail a’ gabhail pàirt ann an Olympiads saidheans coimpiutaireachd.
Bidh àireamh chrìochnaichte de eòlaichean ann an algorithms paramadair a’ dol a-steach don bhàr ...
Eisimpleir air a thoirt bhon leabhar
Smaoinich gu bheil thu nad gheàrd tèarainteachd bàr ann am baile beag. Gach Dihaoine, thig leth a’ bhaile chun bhàr agad gus fois a ghabhail, a bheir tòrr trioblaid dhut: feumaidh tu luchd-ceannach neònach a thilgeil a-mach às a’ bhàr gus sabaidean a sheachnadh. Aig a 'cheann thall, bidh thu sgìth agus bidh thu a' co-dhùnadh ceumannan casg a ghabhail.
Leis gu bheil am baile-mòr agad beag, tha fios agad gu cinnteach dè na paidhrichean de luchd-taic a bhios dualtach sabaid ma thig iad gu crìch ann am bàr còmhla. A bheil liosta agad de n daoine a thig dhan bhàr a-nochd. Bidh thu a’ co-dhùnadh cuid de mhuinntir a’ bhaile a chumail a-mach às a’ bhàr gun duine sam bith a dhol an sàs ann an sabaid. Aig an aon àm, chan eil na ceannardan agad airson prothaidean a chall agus bidh iad mì-thoilichte mura leig thu le barrachd na k daoine.
Gu mì-fhortanach, is e duilgheadas clasaigeach NP-cruaidh an duilgheadas a tha romhpa. Is dòcha gu bheil thu eòlach oirre mar , no mar dhuilgheadas còmhdach vertex. Airson duilgheadasan mar seo, anns a 'chùis choitcheann, chan eil algoirmean ann a bhios ag obair ann an ùine iomchaidh. Gus a bhith mionaideach, tha am beachd-bharail neo-dhearbhte agus gu math làidir ETH (Beachd-bharail Ùine Easbaigeach) ag ràdh nach urrainnear an duilgheadas seo fhuasgladh ann an ùine. , is e sin, chan urrainn dhut smaoineachadh air rud sam bith nas fheàrr na rannsachadh iomlan. Mar eisimpleir, canaidh sinn gu bheil cuideigin a’ dol a thighinn chun bhàr agad n = 1000 Duine. An uairsin bidh an rannsachadh iomlan roghainnean a tha timcheall air - suim crazy. Gu fortanach, tha do riaghladh air crìoch a thoirt dhut k = 10, mar sin tha an àireamh de choimeasgaidhean a dh’ fheumas tu ath-aithris mòran nas lugha: tha an àireamh de fo-bhuidhnean de dheich eileamaidean . Tha seo nas fheàrr, ach cha bhith e fhathast air a chunntadh ann an latha eadhon air cruinneachadh cumhachdach.
Gus cuir às do chomas sabaid anns an rèiteachadh seo de dhàimhean teann eadar luchd-tadhail a ’bhàr, feumaidh tu Bob, Daniel agus Fedor a chumail a-mach. Chan eil fuasgladh ann anns nach bi ach dithis air am fàgail.
A bheil seo a’ ciallachadh gu bheil an t-àm ann a dhol a-steach agus a h-uile duine a leigeil a-steach? Beachdaichidh sinn air roghainnean eile. Uill, mar eisimpleir, chan urrainn dhut a leigeil a-steach a-mhàin an fheadhainn a tha buailteach a bhith a 'sabaid le àireamh mhòr de dhaoine. Mas urrainn dha cuideigin sabaid co-dhiù k+1 neach eile, gu cinnteach chan urrainn dhut a leigeil a-steach - air neo feumaidh tu a h-uile duine a chumail a-mach k+1 muinntir a 'bhaile, leis am faod e sabaid, a bhios gu cinnteach a' cur dragh air an stiùireadh.
An tilg thu a-mach a h-uile duine a b 'urrainn dhut a rèir a' phrionnsapail seo. An uairsin faodaidh a h-uile duine eile sabaid le barrachd air k dhaoine. A 'tilgeil a-mach iad k A dhuine, chan urrainn dhut dad a bharrachd a sheachnadh còmhstri. Tha seo a’ ciallachadh ma tha barrachd air Ma tha neach an sàs ann an co-dhiù aon chòmhstri, gu cinnteach chan urrainn dhut casg a chuir orra uile. Leis, gu dearbh, leigidh tu a-steach daoine gu tur neo-chòmhstri, feumaidh tu a dhol tro gach fo-sheata de mheud deich a-mach à dà cheud neach. Tha timcheall air , agus faodar an àireamh seo de ghnìomhachd a rèiteachadh mu thràth air a’ bhuidheann.
Mas urrainn dhut daoine fa leth a thoirt gu sàbhailte aig nach eil còmhstri idir, dè mu dheidhinn an fheadhainn a tha a’ gabhail pàirt ann an aon chòmhstri a-mhàin? Gu dearbh, faodar an leigeil a-steach cuideachd le bhith a 'dùnadh an dorais air an neach-dùbhlain aca. Gu dearbha, ma tha Alice ann an còmhstri a-mhàin ri Bob, an uairsin ma leigeas sinn Alice a-mach às an dithis aca, cha chaill sinn: is dòcha gu bheil còmhstri eile aig Bob, ach gu cinnteach chan eil iad aig Alice. A bharrachd air an sin, chan eil e ciallach dhuinn gun a bhith a’ leigeil leinn an dithis againn a dhol a-steach. Às deidh a leithid de ghnìomhachd, chan eil dad air fhàgail aoighean le dànachd gun fhuasgladh: chan eil againn ach còmhstri, gach fear le dithis chom-pàirtichean agus gach fear an sàs ann an co-dhiù dithis. Mar sin chan eil air fhàgail ach a rèiteachadh roghainnean, a dh'fhaodar beachdachadh gu furasta air leth-latha air laptop.
Gu dearbh, le reusanachadh sìmplidh faodaidh tu suidheachaidhean eadhon nas tarraingiche a choileanadh. Thoir an aire gum feum sinn gu cinnteach a h-uile connspaid fhuasgladh, is e sin, bho gach paidhir connspaideach, tagh co-dhiù aon neach nach leig sinn a-steach. Beachdaichidh sinn air an algairim a leanas: gabh còmhstri sam bith, às am bi sinn a ’toirt air falbh aon chom-pàirtiche agus a’ tòiseachadh air ais bhon chòrr, an uairsin thoir air falbh am fear eile agus cuideachd a ’tòiseachadh gu ath-chuairteach. Leis gu bheil sinn a 'tilgeil cuideigin a-mach aig a h-uile ceum, tha craobh ath-chuairteachaidh algairim mar sin na chraobh domhainn domhainn k, mar sin gu h-iomlan tha an algairim ag obair a-steach càite n tha àireamh nan vertices, agus m - àireamh nan riban. Anns an eisimpleir againn, tha seo mu dheich millean, a dh'fhaodar a thomhas ann an diog sgoltadh chan ann a-mhàin air laptop, ach eadhon air fòn-làimhe.
Tha an eisimpleir gu h-àrd na eisimpleir algorithm parameterized. Is e algorithms parameterized algorithms a bhios a ’ruith ann an ùine f(k) poly(n)càite p - polynomial, f tha e na ghnìomh coimpiutaireachd neo-riaghailteach, agus k - cuid de paramadair, a tha, gu math is dòcha, bidh e mòran nas lugha na meud na trioblaid.
A h-uile reusanachadh mus algairim seo a 'toirt eisimpleir kernelization Is e seo aon de na dòighean coitcheann airson algorithms paramadair a chruthachadh. Is e kernelization an lughdachadh ann am meud duilgheadas gu luach cuibhrichte le gnìomh paramadair. Gu tric canar kernel ris an duilgheadas a thig às. Mar sin, le reusanachadh sìmplidh mu ìrean vertices, fhuair sinn kernel ceithir-cheàrnach airson duilgheadas Còmhdach Vertex, air a pharamadair le meud an fhreagairt. Tha roghainnean eile ann as urrainn dhut taghadh airson na h-obrach seo (leithid Vertex Cover Above LP), ach seo an suidheachadh air am bi sinn a’ bruidhinn.
Dùbhlan Luas
Farpais (An Algorithms Parameterized agus Dùbhlan Deuchainnean Coimpiutaireachd) a rugadh ann an 2015 gus ceangal a stèidheachadh eadar algorithms paramadair agus dòighean-obrach a thathar a’ cleachdadh ann an cleachdadh gus fuasgladh fhaighinn air duilgheadasan coimpiutaireachd. Chaidh a’ chiad trì farpaisean a thoirt seachad airson leud craoibhe grafa a lorg (), a’ lorg craobh Steiner () agus a’ lorg seata de vertices a bhios a’ gearradh chuairtean (). Am-bliadhna, b’ e an duilgheadas còmhdach vertex a tha air a mhìneachadh gu h-àrd aon de na duilgheadasan anns am b’ urrainn dhut do làmh fheuchainn.
Tha an fharpais a’ fàs mòr-chòrdte gach bliadhna. Ma tha thu a’ creidsinn an dàta tòiseachaidh, am-bliadhna ghabh sgiobaidhean 24 pàirt anns a’ cho-fharpais gus fuasgladh fhaighinn air an duilgheadas còmhdach vertex leotha fhèin. 'S fhiach toirt fa-near gu bheil an fharpais a' mairsinn chan eil grunn uairean a thìde no fiù 's san t-seachdain, ach grunn mhìosan. Tha cothrom aig sgiobaidhean an litreachas a sgrùdadh, am beachd tùsail fhèin a chruthachadh agus feuchainn ri a bhuileachadh. Gu dearbh, is e pròiseact rannsachaidh a th’ anns a’ cho-fharpais seo. Thèid beachdan airson na fuasglaidhean as èifeachdaiche agus buileachadh nan buannaichean a chumail an co-bhonn ris a’ cho-labhairt (Symposium Eadar-nàiseanta air Coimpiutaireachd Parameterized agus Dìreach) mar phàirt den choinneamh bhliadhnail as motha san Roinn Eòrpa . Gheibhear fiosrachadh nas mionaidiche mun fharpais fhèin aig , agus tha toraidhean nam bliadhnaichean roimhe sin nan laighe .
Diagram fuasglaidh
Gus fuasgladh fhaighinn air an duilgheadas còmhdach vertex, dh'fheuch mi ri algorithms parameterized a chleachdadh. Mar as trice tha dà phàirt annta: riaghailtean sìmpleachaidh (a bhiodh gu h-iomchaidh a’ leantainn gu kernelization) agus riaghailtean sgoltadh. Is e riaghailtean sìmpleachaidh ro-phròiseas an cuir a-steach ann an ùine polynomial. Is e adhbhar riaghailtean mar sin an duilgheadas a lughdachadh gu duilgheadas nas lugha co-ionann. Is e riaghailtean sìmpleachaidh am pàirt as daoire den algairim, agus le bhith a’ cur a’ phàirt seo an sàs bidh an ùine ruith iomlan an àite ùine shìmplidh polynomial. Anns a 'chùis againn, tha na riaghailtean sgoltadh stèidhichte air an fhìrinn gum feum thu e fhèin no a nàbaidh a ghabhail mar fhreagairt airson gach vertex.
Is e seo an sgeama coitcheann: bidh sinn a 'cur an gnìomh riaghailtean sìmplidh, an uairsin bidh sinn a' taghadh cuid de vertex, agus a 'dèanamh dà ghairm ath-chuairteach: anns a' chiad fhear bidh sinn ga ghabhail mar fhreagairt, agus anns an fhear eile bidh sinn a 'toirt a nàbaidhean gu lèir. Is e seo a chanas sinn ri sgoltadh (branching) air an vertex seo.
Thèid dìreach aon chur-ris a chur ris an sgeama seo anns an ath pharagraf.
Beachdan airson riaghailtean sgoltadh (brunching).
Bruidhnidh sinn mar a roghnaicheas tu vertex air am bi an sgaradh a 'tachairt.
Tha am prìomh bheachd gu math sanntach anns an t-seadh algorithmach: gabhamaid vertex den ìre as àirde agus roinneadh air. Carson a tha e coltach nas fheàrr? Oir anns an dàrna meur den ghairm ath-chuairteach bheir sinn air falbh mòran vertices san dòigh seo. Faodaidh tu cunntadh air graf beag air fhàgail agus is urrainn dhuinn obrachadh air gu sgiobalta.
Tha an dòigh-obrach seo, leis na dòighean kernelization sìmplidh a chaidh a dheasbad mar-thà, ga nochdadh fhèin gu math agus a ’fuasgladh cuid de dheuchainnean grunn mhìltean vertices ann am meud. Ach, mar eisimpleir, chan eil e ag obair gu math airson grafaichean ciùbach (is e sin, grafaichean aig a bheil ìre gach vertex trì).
Tha beachd eile ann stèidhichte air beachd gu math sìmplidh: ma tha an graf air a dhì-cheangal, faodar an duilgheadas air na co-phàirtean ceangailte aige fhuasgladh gu neo-eisimeileach, a 'ceangal nam freagairtean aig an deireadh. Tha seo, leis an t-slighe, na atharrachadh beag a chaidh a ghealltainn san sgeama, a luathaicheas am fuasgladh gu mòr: roimhe seo, anns a 'chùis seo, bha sinn ag obair airson toradh nan amannan airson freagairtean nan co-phàirtean obrachadh a-mach, ach a-nis tha sinn ag obair airson. an t-suim. Agus gus branching a luathachadh, feumaidh tu graf ceangailte a thionndadh gu graf neo-cheangailte.
Ciamar a dhèanamh? Ma tha puing ceangail anns a’ ghraf, feumaidh tu sabaid ris. Is e vertex a th’ ann am puing altachaidh gus an caill an graf a cheangal nuair a thèid a thoirt air falbh. Gheibhear a h-uile puing snaim ann an graf a’ cleachdadh algairim clasaigeach ann an ùine sreathach. Tha an dòigh-obrach seo gu mòr a 'luathachadh branching.
Nuair a thèid gin de na h-earrainnean taghte a thoirt air falbh, thèid an graf a roinn ann an co-phàirtean ceangailte.
Nì sinn seo, ach tha sinn ag iarraidh barrachd. Mar eisimpleir, coimhead airson gearraidhean beaga vertex anns a’ ghraf agus roinneadh air na vertices bhuaithe. Is e an dòigh as èifeachdaiche as aithne dhomh an gearradh vertex cruinne as ìsle a lorg craobh Gomori-Hu a chleachdadh, a tha air a thogail ann an ùine ciùbach. Ann an Dùbhlan PACE, tha meud àbhaisteach graf grunn mhìltean vertices. Anns an t-suidheachadh seo, feumar billeanan de ghnìomhachd a dhèanamh aig gach vertex den chraobh ath-chuairteachaidh. Tha e a 'tionndadh a-mach gu bheil e dìreach do-dhèanta gus fuasgladh fhaighinn air an duilgheadas ann an ùine ainmichte.
Feuchaidh sinn ris am fuasgladh as fheàrr fhaighinn. Faodar an gearradh vertex as ìsle eadar paidhir vertices a lorg le algairim sam bith a chruthaicheas sruth as àirde. Faodaidh tu a leigeil air lìonra mar sin , ann an cleachdadh bidh e ag obair gu math luath. Tha amharas agam gu bheil e comasach gu teòiridheach tuairmse a dhearbhadh airson an ùine obrachaidh , a tha mar-thà gu math iomchaidh.
Dh’ fheuch mi grunn thursan ri bhith a’ coimhead airson gearraidhean eadar paidhrichean de vertices air thuaiream agus a’ gabhail an tè as cothromaiche. Gu mì-fhortanach, thug seo droch thoraidhean ann an deuchainn fosgailte PACE Challenge. Rinn mi coimeas eadar e agus algairim a bha a’ sgoltadh vertices aig an ìre as àirde, gan ruith le cuingealachadh air doimhneachd an teàrnadh. Dh'fhàg algorithm a tha a 'feuchainn ri gearradh a lorg san dòigh seo air cùl grafaichean nas motha. Tha seo air sgàth gu robh na gearraidhean gu math mì-chothromach: às deidh dhaibh 5-10 vertices a thoirt air falbh, cha robh e comasach ach 15-20 a sgaradh.
Is fhiach a bhith mothachail gu bheil artaigilean mu na h-algorithms as luaithe ann an teòiridh a 'cleachdadh dhòighean fada nas adhartaiche airson a bhith a' taghadh vertices airson sgoltadh. Tha buileachadh gu math toinnte aig dòighean leithid seo agus gu tric droch choileanadh a thaobh ùine agus cuimhne. Cha b’ urrainn dhomh an fheadhainn a tha gu math iomchaidh airson cleachdadh aithneachadh.
Mar a chuireas tu riaghailtean sìmplidh an sàs
Tha beachdan againn mu thràth airson kernelization. Leig leam do chuimhneachadh:
- Ma tha vertex iomallach ann, cuir às dha.
- Ma tha vertex de cheum 1 ann, cuir air falbh e agus gabh a nàbaidh mar fhreagairt.
- Ma tha vertex de cheum co-dhiù k+1, thoir air ais e.
Leis a’ chiad dhà tha a h-uile dad soilleir, leis an treas fear tha aon chleas. Nam biodh sinn ann an duilgheadas èibhinn mu bhàr fhuair sinn crìoch as àirde de k, an uairsin anns an Dùbhlan PACE chan fheum thu ach còmhdach vertex den mheud as lugha a lorg. Is e cruth-atharrachadh àbhaisteach a tha seo air Duilgheadasan Rannsachaidh gu Duilgheadasan Co-dhùnaidh; gu tric chan eil diofar eadar an dà sheòrsa duilgheadas. Ann an cleachdadh, ma tha sinn a 'sgrìobhadh fuasgladh airson duilgheadas còmhdach vertex, dh'fhaodadh gum bi eadar-dhealachadh ann. Mar eisimpleir, mar anns an treas puing.
Bho shealladh buileachaidh, tha dà dhòigh air a dhol air adhart. Canar doimhneachadh ath-aithriseach ris a’ chiad dòigh-obrach. Tha e mar a leanas: is urrainn dhuinn tòiseachadh le beagan cuingealachadh reusanta bho shìos air an fhreagairt, agus an uairsin ruith ar n-algorithm a 'cleachdadh a' chuingealachadh seo mar bhacadh air an fhreagairt bho shuas, gun a bhith a 'dol nas ìsle ann an ath-chuairteachadh na an cuingealachadh seo. Ma tha sinn air beagan freagairt a lorg, tha e cinnteach gum bi e as fheàrr, air neo faodaidh sinn a’ chrìoch seo àrdachadh le aon agus tòiseachadh a-rithist.
Is e dòigh eile cuid de fhreagairt gnàthach as fheàrr a stòradh agus coimhead airson freagairt nas lugha, ag atharrachadh am paramadair seo nuair a lorgar e k airson gearradh nas motha de gheugan neo-riatanach san rannsachadh.
Às deidh dhomh grunn dheuchainnean oidhche a dhèanamh, shocraich mi air measgachadh den dà dhòigh seo: an toiseach, bidh mi a ’ruith an algairim agam le crìoch de sheòrsa air choreigin air doimhneachd an sgrùdaidh (ga thaghadh gus nach toir e glè bheag de ùine an taca ris a’ phrìomh fhuasgladh) agus cleachd an dòigh as fheàrr fuasgladh a chaidh a lorg mar chrìoch àrd air an fhreagairt - is e sin, chun an aon rud k.
Cruthan-clò airson ìre 2 a-nuas
Tha sinn air dèiligeadh ri vertices de cheumannan 0 agus 1. Tha e a 'tionndadh a-mach gum faodar seo a dhèanamh le vertices ìre 2, ach feumaidh seo obrachadh nas iom-fhillte bhon ghraf.
Gus seo a mhìneachadh, feumaidh sinn dòigh air choireigin ainmeachadh na vertices. Canaidh sinn vertex de cheum 2 mar vertex v, agus a nàbaidhean - vertices x и y. An ath rud bidh dà chùis againn.
- Cuin x и y - nàbaidhean. An uairsin faodaidh tu freagairt x и yagus v sguab às. Gu dearbh, bhon triantan seo feumar co-dhiù dà vertice a thoirt air ais, agus gu cinnteach cha chaill sinn ma ghabhas sinn x и y: theagamh gu bheil coimhearsnaich eile aca, agus v Chan eil iad an seo.
- Cuin x и y - chan e nàbaidhean. An uairsin thathar ag ràdh gum faodar na trì vertices a cheangal ann an aon. Is e am beachd gu bheil freagairt as fheàrr anns a 'chùis seo, anns a bheil sinn a' gabhail an dàrna cuid v, no an dà thaobh x и y. A bharrachd air an sin, anns a 'chiad chùis feumaidh sinn a h-uile nàbaidh a thoirt mar fhreagairt x и y, ach anns an dàrna fear chan eil e riatanach. Tha seo dìreach a’ freagairt ris na cùisean nuair nach gabh sinn an vertex glued mar fhreagairt agus nuair a nì sinn sin. Tha e fhathast ri thoirt fa-near gu bheil an fhreagairt bho leithid de dh'obair a 'lùghdachadh le aon anns gach cùis.
Is fhiach a bhith mothachail gu bheil an dòigh-obrach seo gu math duilich a chuir an gnìomh gu ceart ann an ùine sreathach cothromach. Is e obair iom-fhillte a th’ ann an gluing vertices; feumaidh tu liostaichean de nàbaidhean a chopaigeadh. Ma thèid seo a dhèanamh gu neo-chùramach, faodaidh tu crìoch a chuir air ùine ruith asymptotically suboptimal (mar eisimpleir, ma nì thu leth-bhreac de dh ’oirean às deidh gach gluing). Shuidhich mi air slighean slàn a lorg bho vertices ìre 2 agus a’ dèanamh anailis air dòrlach de chùisean sònraichte, leithid baidhsagalan bho na h-uinneagan sin no bho na vertices sin ach a-mhàin aon.
A bharrachd air an sin, feumar an obrachadh seo a thionndadh air ais, gus an cuir sinn air ais an graf chun chruth tùsail nuair a thilleas sinn air ais bho ath-chuairteachadh. Gus seo a dhèanamh cinnteach, cha do shoilleirich mi liostaichean iomaill nan vertices aonaichte, agus an uairsin bha fios agam dè na h-oirean a dh’ fheumadh a dhol càite. Feumaidh buileachadh ghrafaichean mar seo cuideachd cruinneas, ach tha e a’ toirt seachad ùine sreathach cothromach. Agus airson grafaichean grunn deichean de mhìltean de oirean, tha e a 'freagairt a-steach dhan tasgadan phròiseasar, a tha a' toirt buannachdan mòra ann an luaths.
Sreathach kernel
Mu dheireadh, am pàirt as inntinniche den kernel.
An toiseach, cuimhnich gur ann an grafaichean dà-thaobhach a gheibhear an còmhdach vertex as ìsle a’ cleachdadh . Gus seo a dhèanamh feumaidh tu an algairim a chleachdadh gus an maidseadh as àirde a lorg an sin, agus an uairsin cleachd an teòirim .
Is e seo am beachd air kernel sreathach: an toiseach bidh sinn a’ cuir a-mach an graf, is e sin, an àite gach vertex v cuireamaid dà stùc ris и , agus an àite gach oir u - v cuireamaid dà rib ris и . Bidh an graf mar thoradh air sin bipartite. Lorg sinn an còmhdach vertex as ìsle ann. Gheibh cuid de dh’innean a’ ghraf thùsail ann dà uair, cuid dìreach aon turas, agus cuid nach bi. Tha teòirim Nemhauser-Trotter ag ràdh gum faod neach anns a’ chùis seo vertices a thoirt air falbh nach do bhuail eadhon aon uair agus an fheadhainn a bhuail dà uair a thoirt air ais. A bharrachd air an sin, tha i ag ràdh, de na h-earrainnean a tha air fhàgail (an fheadhainn a bhuail aon uair) gum feum thu co-dhiù leth a ghabhail mar fhreagairt.
Tha sinn dìreach air ionnsachadh gun a bhith a’ fàgail barrachd na 2k stùcan Gu dearbha, ma tha an còrr den fhreagairt co-dhiù leth nan vertices uile, chan eil barrachd vertices ann uile gu lèir. 2k.
An seo bha e comasach dhomh ceum beag air adhart a ghabhail. Tha e soilleir gu bheil an kernel a chaidh a thogail san dòigh seo an urra ri dè an seòrsa còmhdach vertex as ìsle a ghabh sinn anns a’ ghraf dà-thaobhach. Bu mhath leam fear a ghabhail gus am bi an àireamh de vertices a tha air fhàgail cho beag. Roimhe sin, bha iad comasach air seo a dhèanamh a-mhàin ann an ùine . Thàinig mi suas le buileachadh an algairim seo san ùine , mar sin, faodar an cridhe seo a lorg ann an grafaichean de cheudan de mhìltean de vertices aig gach ìre meurachaidh.
thoradh air
Tha cleachdadh a’ sealltainn gu bheil am fuasgladh agam ag obair gu math air deuchainnean grunn cheudan vertices agus grunn mhìltean oir. Ann an leithid de dheuchainnean tha e gu math comasach a bhith an dùil gun lorgar fuasgladh ann an leth uair a thìde. Tha an coltachd gun lorgar freagairt ann an ùine iomchaidh, ann am prionnsapal, a’ dol am meud ma tha àireamh mhòr gu leòr de vertices aig ìre àrd aig a’ ghraf, mar eisimpleir, ceum 10 agus nas àirde.
Gus pàirt a ghabhail san fharpais, dh'fheumadh fuasglaidhean a chuir gu . A’ breithneachadh leis an fhiosrachadh a tha air a thaisbeanadh an sin , tha am fuasgladh agam ann an deuchainnean fosgailte san treas àite a-mach à fichead, le beàrn mòr bhon dàrna fear. Gus a bhith gu tur onarach, chan eil e gu tur soilleir ciamar a thèid fuasglaidhean a mheasadh aig a ’cho-fharpais fhèin: mar eisimpleir, bidh am fuasgladh agam a’ dol seachad nas lugha de dheuchainnean na am fuasgladh sa cheathramh àite, ach air an fheadhainn a thèid seachad, bidh e ag obair nas luaithe.
Bidh fios air toraidhean deuchainnean dùinte air 1 Iuchar.
Source: www.habr.com