Shaqada cilmi-baarista ayaa laga yaabaa inay tahay qaybta ugu xiisaha badan ee tababarkeena. Fikradda ayaa ah inaad isku daydo naftaada jihada aad dooratay adigoo weli jaamacad ku jira. Tusaale ahaan, ardayda ka socota qaybaha Software Engineering iyo Machine Learning inta badan waxay aadaan inay cilmi-baaris ka sameeyaan shirkadaha (badanaa JetBrains ama Yandex, laakiin maaha oo kaliya).
Maqaalkan waxaan kaga hadli doonaa mashruucayga cilmiga kumbuyuutarka. Iyada oo qayb ka ah shaqadayda, waxaan bartay oo aan hirgeliyay habab lagu xallinayo mid ka mid ah dhibaatooyinka NP-adag ee ugu caansan: dhibaatada daboolida vertex.
Maalmahan, habka xiisaha leh ee dhibaatooyinka NP-adag ayaa si dhakhso leh u kobcaya - algorithms-ka-soo-saarka. Waxaan isku dayi doonaa inaan ku gaadhsiiyo xawaare, kuu sheego qaar ka mid ah algorithms-ka-soo-jeedinta fudud oo aan qeexo hal hab oo awood leh oo wax badan iga caawiyay. Waxaan natiijadaydii ku soo bandhigay tartanka PACE Challenge: marka loo eego natiijooyinka imtixaannada furan, xalkeygu wuxuu galayaa kaalinta saddexaad, natiijada kama dambaysta ahna waxaa la ogaan doonaa Luulyo 1.
Naftayda ku saabsan
Magacaygu waa Vasily Alferov, hadda waxaan ku dhammaynayaa sannad-dugsiyeedkaygii saddexaad ee Jaamacadda Cilmi-baarista Qaranka ee Dugsiga Sare ee Dhaqaalaha - St. Petersburg. Waxaan xiisaynayay algorithms ilaa maalmahayga dugsiga, markii aan wax ku bartay dugsiga Moscow No. 179 oo aan si guul leh uga qaybqaatay sayniska kombiyuutarka Olympiads.
Tiro kooban oo khabiiro ah oo ku jira algorithms-ka la jaan-qaadaya waxay galaan barta...
Tusaale laga soo qaatay buugga
Ka soo qaad inaad tahay waardiye baar jooga magaalo yar. Jimce kasta, kala badh magaaladu waxay u timaadaa baarkaaga si ay u nasato, taas oo ku siinaysa dhib badan: waxaad u baahan tahay inaad ka tuurto macaamiisha qallafsan ee baarka si aad uga hortagto dagaal. Ugu dambeyntii, waad ka dheregsan tahay oo waxaad go'aansataa inaad qaado tallaabooyin ka hortag ah.
Maadaama magaaladaadu yar tahay, waxaad si sax ah u garanaysaa lamaanaha macaamiisha ah ee ay u badan tahay inay dagaalamaan haddii ay ku wada dhamaadaan baar. Ma haysaa liis n dadka baarka iman doona caawa. Waxaad go'aansatey inaad dadka magaalada qaarkood ka ilaaliso baarka iyada oo aan cidina dagaal gelin. Isla mar ahaantaana, madaxdaadu ma rabaan inay lumiyaan faa'iidada wayna ku faraxsanaan doonaan haddii aadan u ogolaan wax ka badan k Aadane.
Nasiib darro, dhibka kaa horreeya waa dhibaato NP-adag oo caadi ah. Waxaa laga yaabaa inaad u garanayso iyada , ama sida vertex daboolaya dhibaatada. Dhibaatooyinkan oo kale, xaaladda guud, ma jiraan algorithms ka shaqeeya waqti la aqbali karo. Si sax ah, mala-awaal aan la xaqiijin oo aad u xooggan ETH (Malo-awaal Wakhtiga Dheeraadka ah) ayaa sheegaya in dhibaatadan aan lagu xallin karin waqtiga. , taas oo ah, uma maleyn kartid wax si muuqata uga fiican raadinta dhamaystiran. Tusaale ahaan, aynu nidhaahno qof baa u imanaya baarkaaga n = 1000 Aadane. Kadib raadinta dhamaystiran waxay noqon doontaa fursadaha in ay jiraan ku dhawaad - qadar waalan. Nasiib wanaag, maamulkaagu wuxuu ku siiyay xad k = 10, markaa tirada isku-dhafka ah ee aad u baahan tahay inaad dib u soo celiso aad bay u yar tahay: tirada qaybaha tobanka qaybood waa . Tani way ka fiican tahay, laakiin weli lama tirin doono maalin gudaheed xitaa koox awood leh.
Si loo baabi'iyo suurtagalnimada dagaal qaabeyntan xiriirka xun ee ka dhexeeya booqdayaasha baar, waxaad u baahan tahay inaad ka ilaaliso Bob, Daniel iyo Fedor. Xal ma jiro oo laba kaliya ayaa ka haraya.
Tani miyay la macno tahay in la gaaray waqtigii la is dhiibi lahaa oo qof walba loo ogolaan lahaa? Aynu tixgelinno doorashooyin kale. Hagaag, tusaale ahaan, ma ogolaan kartid kaliya kuwa ay u badan tahay inay la dagaallamaan tiro aad u badan oo dad ah. Haddii qof uu la dagaallami karo ugu yaraan k+1 qof kale, markaa hubaal uma ogolaan kartid inuu soo galo - haddii kale waa inaad dadka oo dhan ka ilaalisaa k+1 reer magaalka, kuwaas oo uu la dagaalami karo, taas oo hubaal ah in ay ka xumaan doonto hoggaanka.
U ogolow inaad tuurto qof kasta oo aad awooddo si waafaqsan mabda'an. Markaa qof kasta oo kale ma dagaalami karo wax ka badan k dadka. Iyaga oo soo tuuraya k ninyahow, wax kale ma hor istaagi kartid colaadaha. Taas macnaheedu waa haddii ay jiraan wax ka badan Haddii qofku uu ku lug yeesho ugu yaraan hal isku dhac, markaa hubaal kama hortagi kartid dhammaantood. Maaddaama, dabcan, waxaad hubaal ahaan u ogolaan doontaa dadka aan isku dhacsanayn, waxaad u baahan tahay inaad dhex marto dhammaan qaybaha cabbirka ee toban ka mid ah laba boqol oo qof. Waxaa jira qiyaastii , iyo tiradan hawlgallada mar hore ayaa lagu kala saari karaa kutlada.
Haddii aad si badbaado leh u qaadan karto shakhsiyaad aan wax khilaaf ah qabin haba yaraatee, haddaba ka waran kuwa ka qayb qaadanaya hal khilaaf? Dhab ahaantii, sidoo kale waa lagu ogolaan karaa in albaabka laga xiro kuwa ka soo horjeeda. Runtii, haddii Alice ay isku dhacsan yihiin oo keliya Bob, markaa haddii aan u oggolaanno Alice labadooda, lumin mayno: Bob waxaa laga yaabaa inuu qabo isku dhacyo kale, laakiin hubaal Alice ma haysato. Waxaa intaa dheer, macno ma samaynayso in aynaan labadayada u ogolaan. Hawlgallada noocaas ah ka dib ma jiraan wax kale martida leh qaddar aan la xallin: waxaan leenahay oo keliya isku dhacyada, mid kastaa wuxuu leeyahay laba ka qaybgalayaal iyo mid kasta oo ku lug leh ugu yaraan laba. Markaa waxa hadhay oo dhan waa in la kala saaro fursadaha, kuwaas oo si fudud loo tixgalin karaa nus maalin on laptop ah.
Dhab ahaantii, sababo fudud waxaad ku gaari kartaa xitaa xaalado soo jiidasho leh. Ogow in aan xaqiiqdii u baahanahay in aan xallino dhammaan khilaafaadka, taas oo ah, labada qof ee is khilaafaya, ka dooro ugu yaraan hal qof oo aynaan u ogolaan doonin. Aynu tixgelinno algorithm-ka soo socda: qaado khilaaf kasta, kaas oo aan ka saarno mid ka mid ah ka qaybgalayaasha oo aan si isdaba-joog ah uga bilowno inta soo hartay, ka dibna ka saar kan kale oo sidoo kale u bilow si isdaba-joog ah. Maadaama aan qof ku tuurno tallaabo kasta, geedka soo noqnoqda ee algorithm-ka noocan oo kale ah waa geed qotodheer oo qoto dheer k, marka guud ahaan algorithm ayaa ku shaqeeya halkaas oo n waa tirada geesaha, iyo m - tirada feeraha. Tusaalahayaga, tani waa qiyaastii toban milyan, taas oo lagu xisaabin karo ilbiriqsiyo ma aha oo kaliya laptop-ka, laakiin xitaa taleefanka gacanta.
Tusaalaha kore waa tusaale algorithmized parameterized. Algorithm-yada la soo koobay waa algorithms kuwaas oo ku shaqeeya waqtiga f (k) poly(n)halkaas oo p - badan, f waa hawl xisaabin aan sabab lahayn, iyo k -beegyada qaarkood, kuwaas oo, si macquul ah, aad uga yaraan doona inta ay le'eg tahay dhibaatada.
Dhammaan sababaha ka hor algorithmamka waxay siinayaa tusaale kernelization waa mid ka mid ah farsamooyinka guud ee abuuritaanka algorithms-ka-soo-jeedinta. Kernelization waa hoos u dhigista cabbirka dhibka ilaa qiime xaddidan shaqada halbeegyada. Dhibaatada ka dhalata waxaa badanaa loo yaqaan kernel. Markaa, annagoo si fudud u sababeynayna darajooyinka barafka, waxaan helnay kernel quadratic ah dhibaatada Daboolka Vertex, oo lagu cabbiray cabbirka jawaabta. Waxa jira goobo kale oo aad u dooran karto hawshan (sida Vertex Cover Over LP), laakiin kani waa goobta aanu ka wada hadli doono.
Loolanka xawaaraha
Tartan (The Parameterized Algorithms and Computational Experiments Challenge) waxa uu dhashay 2015 si loo dhiso xidhiidh ka dhexeeya algorithms-ka la qiyaasi karo iyo hababka loo isticmaalo ficil ahaan si loo xalliyo dhibaatooyinka xisaabinta. Saddexda tartan ee ugu horreeya waxa loo qoondeeyey helidda ballaca geedka garaaf (), raadinta geedka Steiner (iyo raadinta dhawr geesood oo gooya wareegyada (). Sannadkan, mid ka mid ah dhibaatooyinka aad ku tijaabin karto gacantaada waxay ahayd dhibaatada daboolka ah ee kor lagu sharaxay.
Tartanku waxa uu noqonayaa mid caan ah sannad kasta. Haddii aad aaminsan tahay xogta hordhaca ah, sanadkan 24 kooxood ayaa ka qayb qaatay tartanka si ay u xalliyaan dhibaatada daboolaysa kaliya. Waxaa xusid mudan in tartanka uusan socon dhowr saacadood ama xitaa toddobaad, laakiin dhowr bilood. Kooxuhu waxay haystaan fursad ay ku bartaan suugaanta, la yimaadaan fikradooda asalka ah oo ay isku dayaan inay hirgeliyaan. Nuxur ahaan, tartankani waa mashruuc cilmi baaris ah. Fikradaha xalalka ugu waxtarka badan iyo abaal-marinnada guuleystayaasha ayaa la qaban doonaa iyadoo lala kaashanayo shirka (Symposium International on Parameterized and Exact Computation) oo qayb ka ah shirka sannadlaha ah ee algorithmic ee ugu weyn Yurub . Macluumaad faahfaahsan oo ku saabsan tartanka laftiisa ayaa laga heli karaa at , natiijooyinkii sannadihii horena waa been yihiin .
jaantuska xalka
Si loo xalliyo dhibaatada daboolaysa vertex, waxaan isku dayay isticmaalka algorithms-ka-soo-saarka. Caadi ahaan waxay ka kooban yihiin laba qaybood: qawaaniinta fududaynta (kuwaas oo si fiican u horseeda kernelization) iyo xeerar kala qaybsanaan. Xeerarka fududaynta ayaa horudhac u ah wax gelinta waqti badan. Ujeedada loo dabaqayo xeerarkan waa in la dhimo dhibaatada loona dhigo dhibaato yar oo u dhiganta. Xeerarka fududaynta ayaa ah qaybta ugu qaalisan algorithm-ka, adeegsiga qaybtan waxay keenaysaa wadarta wakhtiga orodka halkii ay ka ahaan lahayd waqti badan oo fudud. Xaaladeena, xeerarka kala qaybinta waxay ku saleysan yihiin xaqiiqda ah in rukun kasta oo aad u baahan tahay inaad u qaadato ama deriskeeda jawaab ahaan.
Nidaamka guud waa kan: waxaanu isticmaalnaa xeerarka fududaynta, ka dibna waxaanu dooranaa qaar ka mid ah vertex, oo waxaanu samaynaa laba wicitaan oo isdaba-joog ah: marka hore waxaan u qaadnaa jawaab celin, kan kalena waxaanu qaadnaa dhammaan deriskiisa. Tani waa waxa aan ugu yeerno kala-goynta (laanta) oo ku taal cirifkan.
Sida saxda ah hal dheeri ayaa lagu samayn doonaa qorshahan cutubka xiga.
Fikradaha lagu kala qaybin karo (burburin) xeerarka
Aynu ka wada hadalno sidii aan u dooran lahayn vertex ay weheliso kala qaybsanaantu.
Fikradda ugu weyni waa mid aad u hunguri weyn marka la eego macnaha algorithm: aan soo qaadanno dulucda heerka ugu sarreeya oo aan kala qaybsano. Waa maxay sababta ay ugu muuqato mid ka fiican? Sababtoo ah laanta labaad ee wicitaanka soo noqnoqda waxaynu ka saari doonaa meelo badan oo ka mid ah habkan. Waxaad ku xisaabtami kartaa garaaf yar oo haray waxaanan si dhaqso ah ugu shaqeyn karnaa.
Habkani, oo leh farsamooyinka kernelization ee fudud ee horeba looga hadlay, ayaa si fiican isu tusaya oo xalliya imtixaannada dhowr kun oo geesood oo cabbir ah. Laakiin, tusaale ahaan, si fiican uma shaqeeyo garaafyada cubic (taas oo ah, garaafyada kuwaas oo darajo kasta oo vertex ah waa saddex).
Waxaa jira fikrad kale oo ku salaysan fikrad fudud oo caddaalad ah: haddii garaafku go'o, dhibaatada qaybaha ku xiran waxaa loo xalin karaa si madax-bannaan, jawaabaha isku darka dhamaadka. Tani, habka, waa wax-ka-beddel yar oo ballan-qaad ah oo ku jira nidaamka, kaas oo si weyn u dedejin doona xalka: hore, kiiskan, waxaan u shaqeynay badeecada waqtiyada xisaabinta jawaabaha qaybaha, laakiin hadda waxaan u shaqeyneynaa wadarta Oo si loo dedejiyo laanta, waxaad u baahan tahay inaad garaaf ku xidhan u rogo mid go'an.
Sidee loo sameeyaa? Haddii ay jirto qodob qeexitaan garaafka, waxaad u baahan tahay inaad la dagaallanto. Barta articulation waa gees sida marka la saaro, garaafku lumiyo isku xirnaanta. Dhammaan dhibcaha isku xirka garaafyada waxaa laga heli karaa iyadoo la adeegsanayo algorithm-ka caadiga ah ee waqtiga tooska ah. Habkani wuxuu si weyn u dedejiyaa laanta.
Marka mid ka mid ah cidhifyada la doortay la saaro, garaafku wuxuu u kala qaybsanaan doonaa qaybo isku xidhan.
Waxaan sameyn doonaa tan, laakiin waxaan rabnaa wax badan. Tusaale ahaan, ka raadi jaranjaro yaryar oo vertex ah oo garaafyada ah oo u kala qaybsan darafyada ka soo baxa. Habka ugu waxtarka badan ee aan ogahay in lagu helo goynta ugu yar ee caalamiga ah waa in la isticmaalo geedka Gomori-Hu, kaas oo la dhisay wakhti cubic. Loolanka PACE, cabbirka garaafku waa dhowr kun oo geesood. Xaaladdan oo kale, balaayiin qalliin ayaa loo baahan yahay in lagu sameeyo gees kasta oo ka mid ah geedka soo noqnoqda. Waxaa soo baxday in ay tahay wax aan macquul aheyn in dhibaatada lagu xalliyo waqtiga loogu talagalay.
Aan isku dayno inaan hagaajino xalka. Goynta laf-dhabarta ugu yar ee u dhaxaysa labada geesood waxaa laga heli karaa algorithm kasta oo dhista socodka ugu badan. Waxaad u ogolaan kartaa inuu galo shabakad noocaas ah , ficil ahaan si dhakhso ah ayey u shaqeysaa. Waxaan qabaa shaki ah in aragti ahaan ay suurtogal tahay in la caddeeyo qiyaasta wakhtiga qalliinka , taas oo markii horeba ah mid la aqbali karo.
Waxaan isku dayay dhowr jeer in aan raadiyo gooyo u dhexeeya lammaanaha barafka aan tooska ahayn oo aan qaato midka ugu dheellitiran. Nasiib darro, tani waxay soo saartey natiijooyin liidata ee tijaabada PACE Challenge ee furan. Waxaan la barbardhigay algorithm-ka kala qaybiyay jaangooyooyinka heerka ugu sarreeya, iyaga oo ku socodsiinaya xaddidnaanta qoto-dheeraanta. Algorithm isku dayaya in uu sidaas u gooyo ayaa ka tagay garaafyo waaweyn. Tani waxay sabab u tahay xaqiiqda ah in gooyntu ay u soo baxday inay noqoto mid aad u dheellitiran: ka saarista 5-10 geesood, waxaa suurtagal ah in la kala gooyo kaliya 15-20.
Waxaa xusid mudan in maqaallada ku saabsan algorithms-yada aragti ahaan ugu dhaqsiyaha badan ay isticmaalaan farsamooyin aad u horumarsan oo lagu dooranayo geesaha kala goynta. Farsamooyinka noocan oo kale ah waxay leeyihiin hirgelin aad u adag oo inta badan waxtarkoodu liito marka la eego wakhtiga iyo xusuusta. Waxaan awoodi waayay inaan tilmaamo kuwa aad loo aqbali karo ku-dhaqanka.
Sida Loo Codsado Xeerarka Fududeynta
Waxaan horey u haysanay fikrado kernelization. Aan ku xasuusiyo:
- Haddii uu jiro duleel go'doonsan, tirtir.
- Haddi ay jirto darajo darajo 1 ah, ka saar oo qaado jaarkeeda si ay uga jawaabto.
- Haddii ay jirto duleel shahaado ah ugu yaraan k+1, soo celi.
Labada hore wax walba way cad yihiin, tan saddexaadna waxaa jira hal khiyaamo. Haddii dhibaato majaajillo ah oo ku saabsan baarka nala siiyay xad sare oo ah k, ka dib tartanka PACE waxaad u baahan tahay oo kaliya inaad hesho daboolka hoose ee cabbirka ugu yar. Tani waa u beddelka caadiga ah ee Dhibaatooyinka Raadinta oo loo beddelo Dhibaatooyin Go'aan ah; inta badan ma jiraan farqi u dhexeeya labada nooc ee dhibaatooyinka. Ficil ahaan, haddii aan u qorayno xaliye dhibaatada daboolaysa dulinka, waxaa jiri kara farqi. Tusaale ahaan, sida ku xusan qodobka saddexaad.
Marka laga eego dhinaca fulinta, waxaa jira laba siyaabood oo loo sii wadi karo. Habka ugu horreeya waxaa loo yaqaannaa qoto-dheeraynta. Waa sida soo socota: waxaan ku bilaabi karnaa xoogaa xaddidaad macquul ah xagga hoose ee jawaabta, ka dibna waxaan ku socodsiin karnaa algorithm-ka annaga oo adeegsanayna xannibaaddan sida xannibaadda jawaabta xagga sare, annaga oo aan hoos uga dhicin soo noqnoqoshada xannibaaddan. Haddii aan helnay xoogaa jawaab ah, waxaa la dammaanad qaadayaa inay fiicnaan doonto, haddii kale waxaan kordhin karnaa xadkan mid ka mid ah oo aan dib u bilowno.
Hab kale ayaa ah in la kaydiyo qaar ka mid ah jawaabaha hadda ugu fiican oo la raadiyo jawaab yar, beddelidda cabbirkan marka la helo k si weyn loo gooyo laamaha aan loo baahnayn ee raadinta.
Ka dib markii aan sameeyay dhowr tijaabo oo habeenkii ah, waxaan degay isku-darka labadan hab: marka hore, waxaan ku maamulaa algorithm-ka nooc ka mid ah xaddidaadda qoto dheer ee raadinta (doorashada si ay u qaadato waqti aan fiicneyn marka la barbardhigo xalka ugu weyn) oo aan isticmaalo sida ugu fiican. xal loo helay sida xadka sare ee jawaabta - taas oo ah, in wax la mid ah k.
Dusha sare ee darajada 2
Waxaan la macaamilnay geesaha darajada 0 iyo 1. Waxay soo baxday in tan lagu samayn karo geesaha darajada 2, laakiin tani waxay u baahan doontaa hawlo badan oo adag oo garaafka.
Si loo sharaxo tan, waxaan u baahanahay inaan si uun u qeexno geesaha. Aan u yeerno dulinka darajada 2 vertex v, iyo deriskeeda - geesaha x и y. Marka xigta waxaan yeelan doonaa laba xaaladood.
- Goorma x и y - deriska. Markaa waad ka jawaabi kartaa x и yiyo v tirtirto. Runtii, saddex-xagalkan ugu yaraan laba geesood ayaa loo baahan yahay in laga soo celiyo, hubaalna lumin mayno haddii aan qaadanno. x и y: malaha deris kale ayay leeyihiin, iyo v Halkan ma joogaan.
- Goorma x и y - maaha deris. Kadibna waxaa la sheegay in saddexda darafba mid lagu dhejin karo. Fikradda ayaa ah in kiiskan uu jiro jawaab wanaagsan, taas oo aan qaadanno midkood v, ama labada daraf x и y. Waxaa intaa dheer, kiiska ugu horreeya waa inaan qaadnaa dhammaan deriska si aan uga jawaabno x и y, laakiin in labaad looma baahna. Tani waxay si sax ah u dhigantaa kiisaska marka aynaan qaadan vertex-ka dhejiska ah ee jawaabta iyo marka aan samayno. Waxa kaliya oo ay tahay in la ogaado in labada xaaladoodba jawaabta hawlgalkan oo kale ay mid hoos u dhacdo.
Waxaa xusid mudan in habkani uu aad u adag yahay in si sax ah loo fuliyo waqti toos ah. Xabaggu waa hawl adag, waxaad u baahan tahay inaad nuqul ka sameysid liisaska deriska. Haddii tan si taxadar la'aan ah loo sameeyo, waxaad ku dhamaan kartaa asymptotically suboptimal orod (tusaale ahaan, haddii aad koobiyaysid geeso badan ka dib markii aad dhejisid). Waxaan degey inaan raadiyo dhammaan wadooyin laga soo bilaabo cidhifyada darajada 2 iyo falanqaynta kiisas badan oo gaar ah, sida wareegyo ka yimid cidhifyadan ama dhammaan cidhifyadan oo kale marka laga reebo hal.
Intaa waxaa dheer, waxaa lagama maarmaan ah in hawlgalkani uu noqdo mid dib loo rogo, si markaa marka laga soo laabto soo noqnoqoshada aan dib ugu soo celinno garaafka qaabkiisii hore. Si taas loo xaqiijiyo, ma aan nadiifin liisaska cidhifyada darafyada la isku daray, ka dibna waxaan kaliya gartay geesaha loo baahan yahay in la aado. Hirgelinta garaafyada sidoo kale waxay u baahan tahay saxsanaan, laakiin waxay bixisaa waqti toosan oo cadaalad ah. Iyo garaafyada dhowr tobanaan kun oo geesood ah, waxay ku habboon tahay kaydiyaha processor-ka, kaas oo ku siinaya faa'iidooyin waaweyn xawaaraha.
Kernel toosan
Ugu dambeyntii, qaybta ugu xiisaha badan ee kernel.
Si aad u bilawdo, xasuuso in garaafyada laba geesoodka ah laga heli karo daboolka vertex ugu yar iyadoo la isticmaalayo . Si tan loo sameeyo waxaad u baahan tahay inaad isticmaasho algorithm si aad halkaas u heshid isbarbardhigga ugu badan, ka dibna isticmaal aragtida .
Fikradda kernel toosan waa tan: marka hore waxaan kala saareynaa garaafka, taas oo ah, halkii laga heli lahaa mid kasta v aan ku darno laba sare и , iyo halkii gees kasta u - v aan ku darno laba feeraha и . Garaafka ka soo baxay wuxuu noqon doonaa laba geesood. Aynu ka helno daboolka vertex ugu yar ee ku jira. Qaar ka mid ah geesaha garaafka asalka ah ayaa halkaas gaari doona laba jeer, qaar hal mar kaliya, iyo qaar weligood. Aragtida Nemhauser-Trotter ayaa sheegaysa in kiiskan mid ka mid ah uu ka saari karo geesaha aan ku dhicin xitaa hal mar oo uu dib u soo celiyo kuwii ku dhuftay laba jeer. Waxaa intaa dheer, waxay sheegtay in cidhifyada soo haray (kuwa hal mar ku dhuftay) waxaad u baahan tahay inaad qaadato ugu yaraan kala badh jawaab ahaan.
Waxaan hadda barannay inaan ka tago wax ka badan 2k meelaha ugu sarreeya Runtii, haddii jawaabta soo hadhay ay tahay ugu yaraan kala badh dhammaan darafyada, markaa ma jiraan wax ka badan oo ka badan wadar ahaan 2k.
Halkan waxa aan awooday in aan tallaabo yar hore u qaado. Way caddahay in kernel-ka loo dhisay habkan uu ku xiran yahay nooca ugu yar ee daboolka vertex ee aan ku qaadnay garaafka laba-geesoodka ah. Waxaan jeclaan lahaa inaan qaato mid si tirada soo hartay ay u yaraato. Markii hore, waxay awoodaan inay tan sameeyaan oo keliya waqti . Waxaan la imid hirgelinta algorithm-ka wakhtiga , sidaas darteed, xuduntan waxaa lagu raadin karaa garaafyada boqollaal kun oo geesood heer kasta oo laamo ah.
natiijada
Tababarku wuxuu muujinayaa in xalkaygu si fiican u shaqeeyo imtixaanada dhowr boqol oo darood iyo dhowr kun oo geesood ah. Tijaabooyinka noocan oo kale ah waa suurtogal in la filan karo in xal lagu heli doono nus saac gudahood. Suurtagalnimada in jawaab loo helo wakhti la aqbali karo, mabda' ahaan, way korodhaa haddii garaafku leeyahay tiro ku filan oo tiro badan oo darajooyin sare ah, tusaale ahaan, shahaadada 10 iyo ka sare.
Si looga qayb galo tartanka, xalalka waa in loo diraa . Marka loo eego xogta halkaas lagu soo bandhigay , Xalkayga imtixaannada furan wuxuu galay kaalinta saddexaad ee labaatankii, oo leh farqi weyn oo ka yimid labaad. Si aad si daacad ah u noqoto, si buuxda uma cadda sida xalalka loo qiimeyn doono tartanka laftiisa: tusaale ahaan, xalkaygu wuxuu ku dhaafaa imtixaanno ka yar xalka booska afraad, laakiin kuwa ku guuleysta, si dhakhso ah ayuu u shaqeeyaa.
Natiijooyinka imtixaannada xiran waxaa la ogaan doonaa XNUMX-da Luulyo.
Source: www.habr.com