Iṣẹ iwadi jẹ boya apakan ti o nifẹ julọ ti ikẹkọ wa. Ero naa ni lati gbiyanju ararẹ ni itọsọna ti o yan lakoko ti o wa ni ile-ẹkọ giga. Fun apẹẹrẹ, awọn ọmọ ile-iwe lati awọn agbegbe ti Imọ-ẹrọ sọfitiwia ati Ẹkọ ẹrọ nigbagbogbo lọ lati ṣe iwadii ni awọn ile-iṣẹ (nipataki JetBrains tabi Yandex, ṣugbọn kii ṣe nikan).
Ninu ifiweranṣẹ yii Emi yoo sọrọ nipa iṣẹ akanṣe mi ni Imọ-ẹrọ Kọmputa. Gẹgẹbi apakan ti iṣẹ mi, Mo kọ ẹkọ ati fi sinu awọn isunmọ iṣe lati yanju ọkan ninu awọn iṣoro NP-lile olokiki julọ: fatesi ibora isoro.
Ni ode oni, ọna ti o nifẹ si awọn iṣoro NP-lile n dagbasoke ni iyara pupọ - parameterized algorithms . Emi yoo gbiyanju lati gba ọ ni iyara, sọ fun ọ diẹ ninu awọn algoridimu parameterized ti o rọrun ati ṣapejuwe ọna ti o lagbara ti o ṣe iranlọwọ fun mi pupọ. Mo ṣe afihan awọn abajade mi ni idije Ipenija PACE: ni ibamu si awọn abajade ti awọn idanwo ṣiṣi, ojutu mi gba ipo kẹta, ati pe awọn abajade ikẹhin yoo jẹ mimọ ni Oṣu Keje Ọjọ 1.
Nipa ara mi
Orukọ mi ni Vasily Alferov, Mo n pari ọdun kẹta mi ni Ile-ẹkọ giga ti Ile-ẹkọ giga ti Orilẹ-ede Iwadi ti Orilẹ-ede - St. Mo ti nifẹ si awọn algoridimu lati awọn ọjọ ile-iwe mi, nigbati Mo kọ ẹkọ ni ile-iwe Moscow No.. 179 ati ni aṣeyọri kopa ninu imọ-ẹrọ kọnputa Olympiads.
Nọmba ipari ti awọn alamọja ni awọn algoridimu parameterized tẹ igi naa…
Apeere ti o ya lati iwe
Fojuinu pe o jẹ oluso aabo igi ni ilu kekere kan. Ni gbogbo ọjọ Jimọ, idaji ilu wa si ọpa rẹ lati sinmi, eyiti o fun ọ ni wahala pupọ: o nilo lati jabọ awọn alabara alarinrin kuro ninu igi lati yago fun awọn ija. Ni ipari, o jẹ jẹ ki o pinnu lati ṣe awọn igbese idena.
Niwọn bi ilu rẹ ti jẹ kekere, o mọ pato iru awọn orisii ti awọn onibajẹ le ja ti wọn ba pari ni igi kan papọ. Ṣe o ni akojọ kan ti n eniyan ti o yoo wa si awọn igi lalẹ. O pinnu lati pa diẹ ninu awọn ara ilu kuro ni igi laisi ẹnikẹni ti o ni ija. Ni akoko kanna, awọn ọga rẹ ko fẹ lati padanu awọn ere ati pe yoo ko ni idunnu ti o ko ba jẹ ki o ju. k eniyan.
Laanu, iṣoro ṣaaju ki o jẹ iṣoro NP-lile Ayebaye kan. O le mọ rẹ bi , tabi bi a fatesi ibora isoro. Fun iru awọn iṣoro bẹ, ni ọran gbogbogbo, ko si awọn algoridimu ti o ṣiṣẹ ni akoko itẹwọgba. Lati jẹ kongẹ, aiṣedeede ti ko ni idaniloju ati agbara to lagbara ETH (Itumọ Aago Exponential) sọ pe iṣoro yii ko le yanju ni akoko. , iyẹn ni, o ko le ronu ohunkohun ti o ṣe akiyesi dara ju wiwa pipe lọ. Fun apẹẹrẹ, jẹ ki a sọ pe ẹnikan yoo wa si ọpa rẹ n = 1000 Eniyan. Lẹhinna wiwa pipe yoo jẹ awọn aṣayan ti o wa ni isunmọ - irikuri iye. O da, iṣakoso rẹ ti fun ọ ni opin kan k = 10, ki awọn nọmba ti awọn akojọpọ ti o nilo lati iterate lori jẹ Elo kere: awọn nọmba ti subsets ti mẹwa eroja jẹ. . Eyi dara julọ, ṣugbọn kii yoo ka ni ọjọ kan paapaa lori iṣupọ ti o lagbara.
Lati se imukuro awọn seese ti a ija ni yi iṣeto ni ti strained ajosepo laarin awọn igi ká alejo, o nilo lati tọju Bob, Daniel ati Fedor jade. Ko si ojutu ninu eyiti meji nikan ni yoo fi silẹ.
Ṣe eyi tumọ si pe o to akoko lati fun ni ki gbogbo eniyan wọle? Jẹ ki a ro awọn aṣayan miiran. O dara, fun apẹẹrẹ, o ko le jẹ ki o wọle nikan awọn ti o ṣee ṣe lati ja pẹlu nọmba nla ti eniyan. Ti o ba ti ẹnikan le ja ni o kere pẹlu k+1 eniyan miiran, lẹhinna dajudaju o ko le jẹ ki o wọle - bibẹẹkọ iwọ yoo ni lati pa gbogbo eniyan mọ k+1 awon ara ilu, ti o le ba ja, eyi ti yoo da olori ru.
Jẹ ki o jabọ gbogbo eniyan ti o le ni ibamu si ilana yii. Lẹhinna gbogbo eniyan miiran le ja pẹlu ko si ju k eniyan. Jiju wọn jade k ọkunrin, o ko ba le se ohunkohun siwaju sii ju ija. Eleyi tumo si wipe ti o ba ti wa ni siwaju sii ju Ti eniyan ba ni ipa ninu o kere ju ija kan, lẹhinna o daju pe o ko le ṣe idiwọ gbogbo wọn. Niwọn igba ti, nitorinaa, dajudaju iwọ yoo jẹ ki awọn eniyan ti kii ṣe rogbodiyan patapata, o nilo lati lọ nipasẹ gbogbo awọn ipin ti iwọn mẹwa ninu ọgọrun eniyan meji. Nibẹ ni o wa to , ati awọn nọmba ti mosi le tẹlẹ ti wa ni lẹsẹsẹ jade lori iṣupọ.
Ti o ba le mu awọn ẹni kọọkan ti ko ni ija rara, lẹhinna kini nipa awọn ti o kopa ninu ija kanṣoṣo? Ni otitọ, wọn tun le jẹ ki wọn wọle nipa tiipa ilẹkun alatako wọn. Nitootọ, ti Alice ba ni ija pẹlu Bob nikan, lẹhinna ti a ba jẹ ki Alice jade ninu awọn mejeeji, a kii yoo padanu: Bob le ni awọn ija miiran, ṣugbọn Alice ko ni wọn. Pẹlupẹlu, ko ṣe oye fun wa lati ma jẹ ki awọn mejeeji wọle. Lẹhin iru awọn iṣẹ ṣiṣe ko si mọ alejo pẹlu ohun unresolved ayanmọ: a ni nikan ija, kọọkan pẹlu meji olukopa ati kọọkan lowo ninu o kere ju meji. Nitorinaa gbogbo ohun ti o ku ni lati to lẹsẹsẹ awọn aṣayan, eyi ti o le awọn iṣọrọ wa ni kà idaji ọjọ kan lori laptop.
Ni otitọ, pẹlu ero ti o rọrun o le ṣaṣeyọri paapaa awọn ipo ti o wuyi diẹ sii. Ṣakiyesi pe dajudaju a nilo lati yanju gbogbo awọn ariyanjiyan, iyẹn, lati ọdọ tọkọtaya kọọkan, yan o kere ju eniyan kan ti a kii yoo jẹ ki wọn wọle. Jẹ ki a ṣe akiyesi algorithm atẹle: mu eyikeyi rogbodiyan, lati eyiti a yọ alabaṣe kan kuro ki o bẹrẹ recursively lati iyokù, lẹhinna yọ ekeji kuro ki o tun bẹrẹ ni igbagbogbo. Niwọn igba ti a ti sọ ẹnikan jade ni gbogbo igbesẹ, igi atunṣe ti iru algoridimu jẹ igi alakomeji ti ijinle k, nitorina ni apapọ algorithm ṣiṣẹ ni nibo n ni awọn nọmba ti vertices, ati m - nọmba ti wonu. Ninu apẹẹrẹ wa, eyi jẹ nipa miliọnu mẹwa, eyiti o le ṣe iṣiro ni pipin iṣẹju-aaya kii ṣe lori kọǹpútà alágbèéká nikan, ṣugbọn paapaa lori foonu alagbeka kan.
Apeere ti o wa loke jẹ apẹẹrẹ parameterized alugoridimu. Awọn algoridimu paramita jẹ awọn algoridimu ti o ṣiṣẹ ni akoko f (k) poly(n)nibo p - ilopọ, f jẹ ẹya lainidii isiro iṣẹ, ati k - diẹ ninu awọn paramita, eyiti, o ṣee ṣe, yoo kere pupọ ju iwọn iṣoro naa lọ.
Gbogbo ero ṣaaju ki algorithm yii funni ni apẹẹrẹ kernelization jẹ ọkan ninu awọn ilana gbogbogbo fun ṣiṣẹda awọn algoridimu parameterized. Kernelization jẹ idinku iwọn iṣoro naa si iye ti o ni opin nipasẹ iṣẹ kan ti paramita kan. Iṣoro ti o waye nigbagbogbo ni a pe ni ekuro. Nitorinaa, nipasẹ ero ti o rọrun nipa awọn iwọn ti awọn inaro, a gba ekuro kuadiratiki kan fun iṣoro Ideri Vertex, parameterized nipasẹ iwọn idahun. Awọn aṣayan miiran wa ti o le yan fun iṣẹ yii (fun apẹẹrẹ, Ideri Vertex Loke LP), ṣugbọn eyi ni aṣayan ti a yoo jiroro.
Pace Ipenija
Idije (Awọn Algorithms Parameterized ati Ipenija Awọn Idanwo Iṣiro) ni a bi ni 2015 lati fi idi asopọ kan mulẹ laarin awọn algoridimu parameterized ati awọn isunmọ ti a lo ninu adaṣe lati yanju awọn iṣoro iṣiro. Awọn idije mẹta akọkọ jẹ iyasọtọ si wiwa iwọn igi ti aworan kan (), wiwa igi Steiner () ati wiwa fun akojọpọ awọn inaro ti o ge awọn iyipo (). Ni ọdun yii, ọkan ninu awọn iṣoro ninu eyiti o le gbiyanju ọwọ rẹ ni iṣoro ibora fatesi ti a ṣalaye loke.
Idije naa n gba olokiki ni gbogbo ọdun. Ti o ba gbagbọ data alakoko, ni ọdun yii awọn ẹgbẹ 24 ṣe alabapin ninu idije lati yanju iṣoro ibora ti fatesi nikan. O tọ lati ṣe akiyesi pe idije naa kii ṣe awọn wakati pupọ tabi paapaa ọsẹ kan, ṣugbọn awọn oṣu pupọ. Awọn ẹgbẹ ni aye lati ṣe iwadi awọn iwe-iwe, wa pẹlu imọran atilẹba tiwọn ati gbiyanju lati ṣe imuse rẹ. Ni pataki, idije yii jẹ iṣẹ akanṣe iwadi. Awọn imọran fun awọn ojutu ti o munadoko julọ ati fifunni ti awọn aṣeyọri yoo waye ni apapo pẹlu apejọ naa (Symposium International lori Parameterized ati Computation Gangan) gẹgẹbi apakan ti ipade algorithmic lododun ti o tobi julọ ni Yuroopu . Alaye alaye diẹ sii nipa idije funrararẹ ni a le rii ni , ati awọn esi ti išaaju years purọ .
Aworan ojutu
Lati yanju iṣoro ibora fatesi, Mo gbiyanju lilo awọn algoridimu parameterized. Nigbagbogbo wọn ni awọn ẹya meji: awọn ofin simplification (eyiti o dara julọ ja si kernelization) ati awọn ofin pipin. Awọn ofin irọrun jẹ iṣaju iṣaju ti titẹ sii ni akoko pupọ. Idi ti lilo iru awọn ofin ni lati dinku iṣoro naa si iṣoro kekere deede. Awọn ofin simplification jẹ apakan ti o gbowolori julọ ti algorithm, ati lilo apakan yii yori si akoko ṣiṣe lapapọ dipo akoko iloyepo ti o rọrun. Ninu ọran wa, awọn ofin pipin da lori otitọ pe fun aaye kọọkan o nilo lati mu boya o tabi aladugbo rẹ bi idahun.
Ilana gbogbogbo ni eyi: a lo awọn ofin simplification, lẹhinna a yan diẹ ninu awọn ifaworanhan, ki o si ṣe awọn ipe loorekoore meji: ni akọkọ a mu ni idahun, ati ninu ekeji a mu gbogbo awọn aladugbo rẹ. Eyi ni ohun ti a pe ni pipin (ẹka) lẹgbẹẹ fatesi yii.
Gangan afikun kan ni a yoo ṣe si ero yii ni paragi ti nbọ.
Awọn imọran fun pipin (brunching) awọn ofin
Jẹ ki a jiroro bi o ṣe le yan fatesi kan pẹlu eyiti iyapa yoo waye.
Ero akọkọ jẹ ojukokoro pupọ ni ori algorithmic: jẹ ki a mu fatesi ti alefa ti o pọju ati pin pẹlu rẹ. Kini idi ti o dara julọ? Nitoripe ni ẹka keji ti ipe recursive a yoo yọ ọpọlọpọ awọn vertices kuro ni ọna yii. O le gbekele lori iwọn kekere ti o ku ati pe a le ṣiṣẹ lori rẹ ni kiakia.
Ọna yii, pẹlu awọn imọ-ẹrọ kernelization ti o rọrun ti jiroro tẹlẹ, fihan ararẹ daradara ati yanju diẹ ninu awọn idanwo ti ọpọlọpọ ẹgbẹrun awọn inaro ni iwọn. Ṣugbọn, fun apẹẹrẹ, ko ṣiṣẹ daradara fun awọn aworan onigun (iyẹn, awọn aworan ti iwọn ti fatesi kọọkan jẹ mẹta).
Imọran miiran wa ti o da lori imọran ti o rọrun ti o rọrun: ti o ba ti ge-yaya, iṣoro naa lori awọn paati ti o sopọ ni a le yanju ni ominira, apapọ awọn idahun ni ipari. Eyi, nipasẹ ọna, jẹ iyipada kekere ti a ṣe ileri ninu ero naa, eyiti yoo ṣe iyara ojutu ni pataki: ni iṣaaju, ninu ọran yii, a ṣiṣẹ fun ọja ti awọn akoko fun iṣiro awọn idahun ti awọn paati, ṣugbọn ni bayi a ṣiṣẹ fun apao. Ati lati yara sisẹ ẹka, o nilo lati yi aworan ti a ti sopọ si ọkan ti a ge.
Bawo ni lati ṣe? Ti aaye asọye ba wa ninu iyaya, o nilo lati ja ni rẹ. Ojuami asọye jẹ fatesi kan ti o jẹ pe nigbati o ba yọkuro, aworan naa padanu asopọ rẹ. Gbogbo awọn aaye isọpọ ni iwọn ni a le rii ni lilo algorithm kilasika ni akoko laini. Yi ona significantly awọn ọna soke branching.
Nigbati eyikeyi ti a ti yan vertices ti wa ni kuro, awonya yoo pin si ti sopọ irinše.
A yoo ṣe eyi, ṣugbọn a fẹ diẹ sii. Fun apẹẹrẹ, wa awọn gige fatesi kekere ninu awọn aworan ati pipin lẹgbẹẹ awọn inaro lati ọdọ rẹ. Ọna ti o munadoko julọ ti Mo mọ lati wa gige ti o kere ju agbaye ni lati lo igi Gomori-Hu, eyiti a ṣe ni akoko onigun. Ninu Ipenija PACE, iwọn awọn aworan aṣoju jẹ ọpọlọpọ ẹgbẹrun awọn inaro. Ni ipo yii, awọn ọkẹ àìmọye ti awọn iṣẹ ṣiṣe nilo lati ṣe ni aaye kọọkan ti igi atunkọ. O han pe ko ṣee ṣe lati yanju iṣoro naa ni akoko ti a pin.
Jẹ ká gbiyanju lati je ki awọn ojutu. Gige fatesi ti o kere ju laarin bata meji le ṣee rii nipasẹ eyikeyi alugoridimu ti o ṣe ṣiṣan ti o pọju. O le jẹ ki o lori iru nẹtiwọki kan , ni iṣe o ṣiṣẹ ni iyara pupọ. Mo ni ifura pe o ṣee ṣe ni imọ-jinlẹ lati ṣe afihan iṣiro kan fun akoko iṣẹ , eyi ti o jẹ itẹwọgba tẹlẹ.
Mo gbiyanju ni ọpọlọpọ igba lati wa awọn gige laarin awọn orisii ti awọn ila laileto ati mu ọkan ti o ni iwọntunwọnsi julọ. Laanu, eyi ṣe awọn abajade ti ko dara ni idanwo Ipenija PACE ṣiṣi. Mo ṣe afiwe pẹlu algorithm kan ti o pin awọn inaro ti alefa ti o pọju, ṣiṣe wọn pẹlu aropin lori ijinle iran. Algoridimu ti n gbiyanju lati wa gige kan ni ọna yii ti o fi sile awọn aworan nla. Eyi jẹ nitori otitọ pe awọn gige naa ti jade lati jẹ aiṣedeede pupọ: ti yọkuro 5-10 vertices, o ṣee ṣe lati pin kuro ni 15-20 nikan.
O tọ lati ṣe akiyesi pe awọn nkan nipa awọn algoridimu ti imọ-jinlẹ ti o yara julọ lo awọn ilana ilọsiwaju pupọ diẹ sii fun yiyan awọn inaro fun pipin. Iru awọn imuposi ni imuse eka pupọ ati nigbagbogbo iṣẹ ṣiṣe ti ko dara ni awọn ofin ti akoko ati iranti. Emi ko le ṣe idanimọ awọn ti o jẹ itẹwọgba fun adaṣe.
Bawo ni lati Waye Awọn Ofin Irọrun
A ti ni awọn imọran tẹlẹ fun kernelization. Jẹ ki n ran ọ leti:
- Ti fatesi ti o ya sọtọ ba wa, paarẹ rẹ.
- Ti o ba wa fatesi ti ìyí 1, yọ kuro ki o mu aladugbo rẹ ni esi.
- Ti o ba wa ni fatesi ti alefa o kere ju k+1, gba pada.
Pẹlu awọn meji akọkọ ohun gbogbo jẹ kedere, pẹlu ẹkẹta o wa ẹtan kan. Ti o ba ti ni a apanilerin isoro nipa a igi ti a fi fun ohun oke ni iye to ti k, lẹhinna ninu Ipenija PACE o kan nilo lati wa ideri fatesi ti iwọn to kere julọ. Eyi jẹ iyipada aṣoju ti Awọn iṣoro Wiwa sinu Awọn iṣoro Ipinnu; nigbagbogbo ko si iyatọ laarin awọn iru awọn iṣoro meji. Ni iṣe, ti a ba n kọ olutọpa kan fun iṣoro ibora fatesi, iyatọ le wa. Fun apẹẹrẹ, bi ninu aaye kẹta.
Lati oju wiwo imuse, awọn ọna meji wa lati tẹsiwaju. Ọna akọkọ ni a npe ni Iterative Deepening. O jẹ bi atẹle: a le bẹrẹ pẹlu diẹ ninu awọn idiwọ ti o ni imọran lati isalẹ lori idahun, ati lẹhinna ṣiṣe algorithm wa nipa lilo idiwọ yii bi idinamọ lori idahun lati oke, lai lọ si isalẹ ni atunṣe ju idiwọ yii lọ. Ti a ba ti ri diẹ ninu awọn idahun, o ti wa ni ẹri lati wa ni ti aipe, bibẹkọ ti a le mu yi iye to nipa ọkan ki o si bẹrẹ lẹẹkansi.
Ona miiran ni lati tọju diẹ ninu idahun aipe lọwọlọwọ ati wa idahun ti o kere ju, yi paramita yii pada nigbati o ba rii k fun gige nla ti awọn ẹka ti ko wulo ni wiwa.
Lẹhin ṣiṣe ọpọlọpọ awọn adanwo alẹ, Mo yanju lori apapọ awọn ọna meji wọnyi: akọkọ, Mo ṣiṣẹ algorithm mi pẹlu iru opin lori ijinle wiwa (yiyan rẹ ki o gba akoko aifiyesi ni akawe si ojutu akọkọ) ati lo dara julọ. ojutu ti a rii bi opin oke si idahun - iyẹn ni, si ohun kanna k.
Awọn ila ti iwọn 2
A ti ṣe pẹlu awọn inaro ti iwọn 0 ati 1. O wa ni jade wipe eyi le ṣee ṣe pẹlu vertices ti ìyí 2, ṣugbọn yi yoo nilo eka sii awọn iṣẹ-ṣiṣe lati awonya.
Lati ṣe alaye eyi, a nilo lati ṣe afihan awọn ibi-ipin. Jẹ ki ká pe fatesi ti ìyí 2 a fatesi v, ati awọn oniwe-aladugbo - vertices x и y. Nigbamii ti a yoo ni awọn ọran meji.
- Nigbawo x и y - awọn aladugbo. Lẹhinna o le dahun x и y, ati v parẹ. Lootọ, lati igun onigun mẹta yii o kere ju awọn inaro meji nilo lati mu ni ipadabọ, ati pe dajudaju a kii yoo padanu ti a ba mu. x и y: nwọn jasi ni miiran awọn aladugbo, ati v Wọn ko wa nibi.
- Nigbawo x и y - kii ṣe awọn aladugbo. Lẹhinna o ti sọ pe gbogbo awọn inaro mẹta ni a le lẹ pọ si ọkan. Awọn agutan ni wipe ninu apere yi nibẹ jẹ ẹya ti aipe idahun, ninu eyi ti a ya boya v, tabi mejeji vertices x и y. Pẹlupẹlu, ninu ọran akọkọ a yoo ni lati mu gbogbo awọn aladugbo ni idahun x и y, sugbon ni awọn keji o jẹ ko wulo. Eyi ni deede ni ibamu si awọn ọran nigba ti a ko gba fatesi ti o lẹ pọ ni idahun ati nigba ti a ṣe. O wa nikan lati ṣe akiyesi pe ni awọn ọran mejeeji idahun lati iru iṣẹ ṣiṣe kan dinku nipasẹ ọkan.
O tọ lati ṣe akiyesi pe ọna yii jẹ ohun ti o nira pupọ lati ṣe imuse ni deede ni akoko laini ododo. Awọn ibi isunmọ jẹ iṣẹ eka kan; o nilo lati daakọ awọn atokọ ti awọn aladugbo. Ti eyi ba ṣe ni aibikita, o le pari pẹlu asymptotically suboptimal yen akoko (fun apẹẹrẹ, ti o ba da ọpọlọpọ awọn egbegbe lẹhin gluing kọọkan). Mo yanju lori wiwa gbogbo awọn ọna lati awọn inaro ti alefa 2 ati itupalẹ opo kan ti awọn ọran pataki, gẹgẹbi awọn iyipo lati iru awọn inaro tabi lati gbogbo iru awọn inaro ayafi ọkan.
Ni afikun, o jẹ dandan pe iṣiṣẹ yii jẹ iyipada, nitorinaa nigba ti o ba pada lati iṣipopada a mu aworan naa pada si fọọmu atilẹba rẹ. Lati rii daju eyi, Emi ko ko awọn atokọ eti ti awọn ila ti o dapọ mọ, lẹhinna Mo kan mọ iru awọn egbegbe ti o nilo lati lọ si ibiti. Imuse ti awọn aworan tun nilo deede, ṣugbọn o pese akoko laini deede. Ati fun awọn aworan ti ọpọlọpọ awọn ẹgbẹẹgbẹrun egbegbe, o baamu si kaṣe ero isise, eyiti o fun awọn anfani nla ni iyara.
Ekuro laini
Nikẹhin, apakan ti o nifẹ julọ ti ekuro.
Lati bẹrẹ pẹlu, ranti pe ninu awọn aworan bipartite o le rii ideri fatesi to kere julọ ni lilo . Lati ṣe eyi o nilo lati lo algorithm ni ibere lati wa awọn ti o pọju ibaamu nibẹ, ati ki o si lo theorem .
Ero ti ekuro laini ni eyi: ni akọkọ a pin iwọn aworan naa, iyẹn ni, dipo fatesi kọọkan v jẹ ki a fi awọn oke meji kun и , ati dipo ti kọọkan eti u - v e je ki a fi egbe meji kun и . Abajade awonya yoo jẹ bipartite. Jẹ ki a wa ideri fatesi ti o kere julọ ninu rẹ. Diẹ ninu awọn inaro aworan atilẹba yoo wa nibẹ lẹẹmeji, diẹ ninu lẹẹkan, ati diẹ ninu rara. Theorem Nemhauser-Trotter sọ pe ninu ọran yii ọkan le yọ awọn inaro ti ko lu paapaa ni ẹẹkan ki o gba awọn ti o lu lẹẹmeji pada. Pẹlupẹlu, o sọ pe ti awọn opin ti o ku (awọn ti o lu ni ẹẹkan) o nilo lati mu o kere ju idaji bi idahun.
A ti kọ ẹkọ lati lọ ko ju 2k awọn oke giga Lootọ, ti idahun ti o ku ba jẹ o kere ju idaji gbogbo awọn inaro, lẹhinna ko si awọn inaro diẹ sii lapapọ ju 2k.
Nibi Mo ni anfani lati gbe igbesẹ kekere kan siwaju. O han gbangba pe ekuro ti a ṣe ni ọna yii da lori iru iru ideri fatesi ti o kere julọ ti a mu ninu iyaya bipartite. Emi yoo fẹ lati mu ọkan ki awọn nọmba ti o ku vertices jẹ iwonba. Ni iṣaaju, wọn ni anfani lati ṣe eyi nikan ni akoko . Mo wa pẹlu imuse ti algorithm yii ni akoko naa , nitorinaa, mojuto yii ni a le wa ni awọn aworan ti awọn ọgọọgọrun egbegberun awọn inaro ni ipele ẹka kọọkan.
Esi
Iṣeṣe fihan pe ojutu mi ṣiṣẹ daradara lori awọn idanwo ti ọpọlọpọ awọn igun ọgọọgọrun ati ọpọlọpọ awọn egbegbe. Ninu iru awọn idanwo bẹẹ o ṣee ṣe pupọ lati nireti pe ojutu yoo wa ni idaji wakati kan. Awọn iṣeeṣe ti wiwa idahun ni akoko itẹwọgba, ni ipilẹ, pọ si ti aworan naa ba ni nọmba ti o tobi pupọ ti awọn ipele giga, fun apẹẹrẹ, iwọn 10 ati giga julọ.
Lati kopa ninu idije, awọn ojutu ni lati firanṣẹ si . Idajọ nipasẹ alaye ti a gbekalẹ nibẹ , Ojutu mi ni awọn idanwo ṣiṣi ni ipo kẹta ninu ogun, pẹlu aafo nla lati keji. Lati jẹ ooto patapata, ko ṣe kedere bi a ṣe le ṣe ayẹwo awọn solusan ni idije funrararẹ: fun apẹẹrẹ, ojutu mi kọja awọn idanwo diẹ ju ojutu lọ ni aaye kẹrin, ṣugbọn lori awọn ti o kọja, o ṣiṣẹ ni iyara.
Awọn abajade ti awọn idanwo pipade yoo jẹ mimọ ni Oṣu Keje ọjọ XNUMXst.
orisun: www.habr.com