Hujter Mih´ aly: Szerintem ez a j´ o magyar m´ odszer A jelen ´ır´as sz´and´eka, hogy a lehet˝ o legkevesebb k´eplet felhaszn´ al´ as´ aval, a lehet˝ o legh´etk¨ oznapibb m´ odon ismertesse az optimumsz´am´ıt´ as egy fontos ´es ´erdekes fejezet´et. Itt most mindig olyan n × n-es m´atrixokr´ ol lesz sz´o, melyek minden eleme nemnegat´ıv eg´esz sz´am. Sorcs¨okkent´esen azt ´ertj¨ uk, hogy a m´atrix egy eg´esz sor´at, annak minden elem´et egyazon eg´esz sz´ammal (ami negat´ıv is lehet) egyszerre cs¨okkentj¨ uk. Oszlopcs¨okkent´esek is lesznek, de ott egy-egy eg´esz oszlopot (csak nemnegat´ıv sz´ammal) cs¨okkent¨ unk. A cs¨okkent´esek csak olyan m´ert´ek˝ uek lehetnek, hogy a m´atrix elemei nemnegat´ıvok maradjanak. Alkalmaz´asok szempontj´ ab´ ol nagyon fontos tudni, hogy mi az olyan n! darab n-tag´ u o¨sszeg minimuma (azaz legkisebbike), mely o¨sszegek a m´atrix minden sor´ab´ ol, minden oszlop´ ab´ ol egy-egy m´atrixelemet tartalmaznak tagk´ent. Jel¨ olje ezt a minimumot σ (olv.: szigma). Mivel m´ar 100 k¨ or¨ uli n ´ert´ekekre is az n! sz´am elviselhetetlen¨ ul magas, ez´ert σ kisz´ am´ıt´ asa a defin´ıc´ o alapj´ an a´ltal´ aban rem´enytelen feladat korunk legjobb sz´am´ıt´ og´epei sz´ am´ara is. Ha az inputk´ent kapott m´atrixon sor- ´es oszlopcs¨okkent´eseket v´egz¨ unk, akkor σ ´ert´eke nyilv´ an annyival cs¨okken, amennyi a sor- ´es oszlopcs¨okkent´esek m´ert´ek´enek o¨sszege. K˝ onig D´enes ´es Egerv´ ary Jen˝ o t´etele szerint (melyet Harold W. Kuhn publik´ alt angolul negyed ´evsz´ azaddal k´es˝obb) lehet u ´ gy v´egezni a sor´es oszlopcs¨okkent´eseket, hogy a v´egs˝o m´atrixra σ ´ert´eke nulla legyen. Teh´ at az eredeti m´atrixon σ ´ert´eke megegyezik a sor- ´es oszlopcs¨okkent´esek m´ert´ek´enek el˝ ojeles o¨sszeg´evel. Ezzel egyen´ert´ek˝ u az az a´ll´ıt´ as, hogy a v´egs˝o m´atrix minden sor´ab´ ol, minden oszlop´ ab´ ol kiv´ alaszthat´ o egy-egy nulla elem. Tov´ abbi egyen´ert´ek˝ u a´tfogalmaz´ asa a K˝ onig–Egerv´ ary-t´etelnek a k¨ ovetkez˝o: Minden eg´esz sz´ amokat tartalmaz´ o n´egyzetes m´ atrix sorai ´es oszlopai (el˝ ojeles) cs¨ okkent´es´evel ´es az oszlopai sorrendj´enek m´ odos´ıt´ as´ aval olyan alakra hozhat´ o, melynek minden eleme nemnegat´ıv eg´esz sz´ am ´es a f˝ oa ´tl´ oban csak nulla van. A σ sz´am meghat´aroz´as´ ara szolg´ al´ o sor- ´es oszlopcs¨okkent´eses elj´ ar´ ast Kuhn 1955-ben ,,Hungarian Method” n´even ismertette. Az az´ ota eltelt f´el ´evsz´ azad alatt a m´odszer rengeteg alkalmaz´ast nyert. Lehet vele robotokat vez´erelni, titkos´ır´ast fejteni, t¨ omegdemonstr´aci´ os vide´ ofelv´etelekr˝ ol arcokat azonos´ıtani, iskolai o´rarendet jav´ıtani, h´ azass´agot k¨ ozvet´ıteni, vagyont igazs´ agosan sz´etosztani, ´es m´eg sz´amtalan egy´eb hasznos ´es haszontalan dolgot csin´alni. Hangs´ ulyozand´ o, hogy a magyar m´odszer nemcsak a K˝ onig–Egerv´ ary-t´etelt foglalja mag´aban, hanem annak algoritmikus bizony´ıt´ as´ at is. A l´enyeg teh´ at az, hogy a sz¨ uks´eges sor- ´es oszlopcs¨okkent´esek megfelel˝o m´odon legyenek v´egrehajtva. Az oszlopcs¨okkent´esekre vonatkoz´ o el˝ o´ır´asunk mindig nagyon egyszer˝ u: Mindegyik oszlop k¨ ul¨ on-k¨ ul¨ on a lehet˝ o legnagyobb m´ert´ekben cs¨okkenthet˝ o lesz, csak arra kell vigy´ azni, hogy ne ker¨ ulj¨ on negat´ıv sz´am a m´atrixba. Teh´ at az oszlopokat az azokban tal´ alhat´ o legkisebb elemmel cs¨okkentj¨ uk. Hasonl´ oan ´ertelmezhetj¨ uk a maxim´alis m´ert´ek˝ u sorcs¨okkent´est is, de ´erdekes m´odon erre a maxim´alis m´ert´ek˝ u sorcs¨okkent´esre csak a magyar m´odszer v´egrehajt´ as´ anak legelej´en lesz sz¨ uks´eg¨ unk. A tov´ abbi sorcs¨okkent´esek mind negat´ıv m´ert´ek˝ uek lesznek, azaz nem cs¨okkentj¨ uk, hanem n¨ ovelj¨ uk a sorokat. S˝ otmit¨obb, ha ezek a n¨ ovel´esek egy-egy alkalommal t¨ obb sorra vonatkoznak, akkor az ´erintett sorok mindegyik´et ugyanazzal a sz´ ammal n¨ ovelj¨ uk minden ilyen alkalommal. (M´as al1
kalomm´al m´ar lehet, hogy m´as sz´amma.) A m´odszer l´enyege az, hogy tiszt´azzuk, ilyen negat´ıv sorcs¨okkent´esekre — azaz sorn¨ovel´esekre — mikor, hogyan ker¨ ulj¨ on sor. A kulcs az lesz, hogy valahogyan kijel¨ olj¨ uk a pillanatnyilag utols´ o m´atrix n´eh´ any sor´at — legal´ abb 1 ´es legfeljebb n − 2 darabot —, a´th´ uzzuk ezeket, ´es a´th´ uzzuk azokat az oszlopkat is, melyekben m´eg maradt a´t nem h´ uzott nulla elem. A m´atrixban mindig maradnak majd m´eg a´th´ uzatlan elemek. Ezek legkisebbik´et megfigyelj¨ uk, ´es annak a (−1)-szeres´evel fogjuk az a´th´ uzott sorokat cs¨okkenteni, azaz a megfigyelt legkisebb-´ at-nem-h´ uzott sz´ammal n¨ ovelni. A magyar m´ odszer menete teh´ at a k¨ ovetkez˝o: 1. l´ep´es: Maxim´alis m´ert´ek˝ u sorcs¨okkent´es minden sorra k¨ ul¨ on-k¨ ul¨ on. 2. l´ep´es: Maxim´alis m´ert´ek˝ u oszlopcs¨okkent´es minden oszlopra k¨ ul¨ on-k¨ ul¨ on. Az els˝o k´et l´ep´es eredm´enyek´eppen minden sorban, minden oszlopban lesz legal´ abb egy-egy nulla m´atrixelem, ´es a t¨ obbi m´atrixelem mind pozit´ıv eg´esz sz´am lesz. 3. l´ep´es: El˝ obb megn´ezz¨ uk, hogy ki tudunk-e jel¨ olni n´eh´ any — 1, 2, ... vagy n − 2 darab — sort a fenteml´ıtett c´elra. (Ennek a ,,hogyanj´ at” k´es˝obb ismertetem.) Ha nem jel¨ ol¨ unk ki sorokat, itt nem lesz t¨ obb dolgunk, j¨ ohet a 4. l´ep´es. Ha kijel¨ ol¨ unk sorokat, elv´egezz¨ uk a kijel¨ olt sorok n¨ ovel´es´et a fentiekben r´eszletett m´odon, azt´ an visszat´er¨ unk az 2. l´ep´eshez. 4. l´ep´es: Az el˝ oz˝ o l´ep´esben teh´ at legutolj´ ara m´ar nem jel¨ olt¨ unk kis sorokat n¨ ovel´esre. Ilyenkor ki fogunk tudni v´ alasztani minden sorb´ol, minden oszlopb´ ol egy-egy null´ at. (Annak ok´ at, hogy mi´ert fogunk tudni, k´es˝obb ismertetem. Most csak annyit, hogy a 3. l´ep´es v´egrehajt´ as´ anak mell´ekterm´ekek´ent keletkez˝o adatok alapj´ an tudjuk majd kiv´ alasztani az n darab null´ at.) Az eredeti m´atrixb´ ol a most tal´ alt n darab nulla hely´er˝ol kiv´ alasztjuk a keresett optim´alis o¨sszeg tagjait ´es o¨sszeadva megkapjuk a σ o¨sszeget. Ez teh´ at a magyar m´odszer v´ azlata. A k´et z´ar´ ojeles mondatnak megfelel˝o r´eszletez´es k¨ ovetkezik az al´ abbiakban. Kezdj¨ uk a 3. l´ep´esn´el l´ev˝ o z´ar´ ojellel! Mely sorokat v´ alasszuk ki teh´ at n¨ ovel´esre ´es melyeket nem? A pillanatnyilag utols´ o m´atrixban lehetnek ,,egyed¨ ul´ all´ o” null´ ak, ahol egyed¨ ul´ all´ o alatt olyan elemet ´ert¨ unk, amely a saj´ at sor´aban vagy a saj´ at oszlop´ aban nem ism´etl˝ odik meg. Ha vannak az oszlopukban egyed¨ ul´ all´ o null´ ak (ak´ arcsak egy is), akkor azon null´ aknak a sor´at egy´ertelm˝ uen kiv´ alasztjuk n¨ ovel´esre, ´es az eg´esz sort a´t is h´ uzzuk, mert azzal pillanatnyilag v´egezt¨ unk. Ez tiszta u ¨ gy lesz. Ha m´eg egyed¨ ul´ all´ o null´ ara bukkanunk az a´t-nem-h´ uzott null´ ak k¨ oz¨ ott, azok a null´ ak m´ar csak a sorukban lehetnek egyed¨ ul´ all´ ok, ´es azoknak a null´ aknak a sor´at biztosan nem fogjuk kijel¨ olni, azaz a´th´ uzni. De az ilyen sorukban egyed¨ ul´ all´ o null´ ak oszop´ at igenis a´th´ uzzuk. Ez is tiszta u ¨ gy. Itt egyed¨ ul´ all´ onak sz´am´ıtanak mindazok a null´ ak is, melyek ugyan eredetileg nem voltak egyed¨ ul´ all´ ok, de az o¨sszes azonos sorban l´ev˝ o t¨ obbi null´ at m´ar mind a´th´ uztuk. Teh´ at amikor egy egyed¨ ul´ all´ o null´ at tal´ alunk, akkor egy sort vagy egy oszlopot a´th´ uzunk. Levad´ asszuk teh´ at az o¨sszes egyed¨ ul´ all´ o null´ at, a vad´ aszat sor´an sz¨ uletetteket is; m´eg az ´ırmagjukat is ki´ırtjuk. Ha az egyed¨ ul´ all´ o nulla az oszlop´ aban volt egyed¨ ul´ all´ o, akkor az egyed¨ ul´ all´ o nulla sor´at h´ uzzuk a´t, ha pedig az egyed¨ ul´ all´ o nulla csak a sor´aban egyed¨ ul´ all´ o, akkor az egyed¨ ul´ all´ o null´ anak az oszlop´ at 2
h´ uzzuk a´t. Menet k¨ ozben az a´th´ uz´ asok miatt u ´ jabb egyed¨ ul´ all´ o null´ ak jelenhetnek meg, k´es˝obb azokat is levad´ asszuk. A sorok ´es oszlopok a´th´ uz´ as´ at mindaddig folytatjuk, am´ıg tal´ alunk u ´ jabb ´es u ´ jabb egyed¨ ul´ all´ o null´ akat. Ha egy sor´aban ´es oszlop´ aban is egyar´ ant egyed¨ ul´ all´ o null´ ara bukkanunk, akkor tulajdonk´eppen mindegy, hogy a sor´at vagy az oszlop´ at h´ uzzuk-e ki, csak az sz´am´ıt, hogy a kett˝o k¨ oz¨ ul az egyiket, ´es csak az egyiket. Ha t¨ obb egyed¨ ul´ all´ o nulla is mutatja mag´at, akkor az is mindegy, hogy milyen sorrendben b´ anunk el vel¨ uk. Azt´ an amikor m´ar nem tal´ alunk t¨ obb egyed¨ ul´ all´ o null´ at, akkor az lesz, hogy vagy minden nulla a´t lesz h´ uzva — v´ızszintesen vagy f¨ ugg˝ olegesen —, vagy pedig minden marad´ek a´t-nem-h´ uzott nulla legal´ abb m´asodmag´aval van a saj´ at sor´aban is ´es a saj´ at oszlop´ aban is a´th´ uz´ as n´elk¨ ul. El˝ obbi esetben nem kell t¨ obb a´th´ uzand´ o sort megjel¨ oln¨ unk. Ut´ obbi esetben pedig m´eg legal´ abb k´et olyan sor marad, melynek m´eg nem d˝ olt el a sorsa, azaz m´eg nem d˝ olt el, v´eg¨ ul a´th´ uzzuk-e azokat a sorokat, vagy sem. A tov´ abbiakban is — itt a 3. l´ep´esen bel¨ ul — mindig csak olyan sorokat jel¨ olhet¨ unk ki a´th´ uz´ assal, melyekben m´eg legal´ abb 2 a´t-nem-h´ uzott nulla van. Ha eddig o¨sszesen — v´ızszintesen ´es f¨ ugg˝ olegesen egy¨ uttv´eve — k darab egyed¨ ul´ all´ o null´ at tal´ altunk, azaz k darab vonallal h´ uztuk a´t az egyed¨ ul´ all´ o null´ akat, akkor a mostanra visszamaradt legal´ abb n´egy a´t-nem-h´ uzott null´ at legfeljebb n− k − 1 darab — k¨ ul¨ on-k¨ ul¨ on ak´ ar v´ızszintes, ak´ ar f¨ ugg˝ oleges — vonallal kell (vagy kel´ lene) a´th´ uzni. Ez vagy siker¨ ul, vagy nem. Hogyan lehet ezt eld¨ onteni? Es ha lehet, hogyan kell ezt csin´alni? M´ar majdnem 100 ´eves K˝ onig D´enesnek az a t´etele ´es m´odszere, amivel megadhat´o a v´ alasz. K˝ onig elj´ ar´ as´ ara majd a k´es˝obbiekben visszat´er¨ unk. Itt most legyen el´eg annyi, hogy ha siker¨ ul legfeljebb n − k − 1 darab h´ uz´ assal megoldanunk a dolgot, megoldjuk, ´es ´ıgy kapjuk meg az a´th´ uzand´ o sorokat (meg az oszlopokat is). Ha nem siker¨ ul, akkor az eddigi a´th´ uzott sorok ´es oszlopok a´th´ uz´ as´ at is elfelejtj¨ uk, ´es a´tter¨ unk a 4. l´ep´esre. Akkor is elfelejt¨ unk minden a´th´ uz´ ast, ha ugyan csak egyed¨ ul´ all´ o null´ ak r´ev´en h´ uztunk vonalakat, de n − 1 vonal nem volt el´eg! Teh´ at a sikertelens´eg eset´eben a vonalakat elfelejthetj¨ uk, de nem felejtj¨ uk el az egyed¨ ul´ all´ onak tal´ alt null´ akat, azokat ugyanis a 4. l´ep´eshez majd felhaszn´ alhatjuk. P´eld´ aul z´ar´ ojelek k¨ oz´e ´ır´assal jegyezhetj¨ uk meg a megtal´alt ´es r¨ot¨ on levad´ aszott egyed¨ ul´ all´ o null´ akat. (Teh´ at nem minden nulla lesz lesz hulla, de ami hulla lesz, azt z´ar´ ojel-tariszny´ ankba gy˝ ujtj¨ uk.) 1. p´elda. Tekints¨ uk ak¨ ovetkez˝o 3 × 3-as m´atrixot:
3
1
5
5
4
3
5
1
8
Az 1. l´ep´es eredm´enye:
3
2
0
4
2
1
0
4
0
7
A 2. l´ep´es eredm´enye:
0
0
4
0
1
0
2
0
7
Indul a 3. l´ep´es. Oszlop´ aban egyed¨ ul´ all´ o nulla a 2. sor 3. eleme, aminek r´ev´en a´th´ uzzuk a 2. sort ´es megz´ar´ ojelezz¨ uk a tekintett nulla m´atrixelemet. −
0
0
0 −
1 −
2
0
4
(0) − 7
Sor´ aban egyed¨ ul´ all´ o a 3. sor 2. eleme is, aminek r´ev´en a´th´ uzzuk a 2. oszlopot: | 0 0 4 | − 0 − 1 − (0) − | 2 (0) 7 | Most sor´aban egyed¨ ul´ all´ o lett az 1. sor 1. eleme is, aminek r´ev´en a´th´ uzzuk az 1. oszlopot: | | (0) 0 4 | | − 0 − 1 − (0) − | | 2 (0) 7 | | De ezzel a vonalak sz´ama felszaladt n-re! Elfelejt¨ unk teh´ at minden vonalat, de nem felejtj¨ uk el az egyed¨ ul´ all´ o null´ ak hely´et, ´es a´tugrunk a 4. l´ep´esre.
4
4. l´ep´es: Mivel minden sorba, minden oszlopba jutott z´ar´ ojelezett nulla, a v´egeredm´ e ny el˝ o a ´ llt:
(3)
1
5
5
4
(3)
5
(1)
8
Itt teh´ at σ = 3 + 3 + 1 = 7. ´ Altal´ anos esetben a 3. l´ep´esn´el az n darab sor k¨ oz¨ ott maradhatnak m´eg olyan sorok, melyekr˝ ol nem der¨ ult ki, hogy kiv´ alasszuk-e azokat, vagy biztosan kihagyjuk-e azokat a kiv´ alaszt´ asb´ ol. Most ezekr˝ol a sorokr´ ol kell d¨ onteni! Mindegyikr˝ ol k¨ ul¨ on-k¨ ul¨ on kell d¨ onten¨ unk, hogy kiv´ alasszuk-e azokat, vagy sem. Minden ilyen eld¨ ontetlen sors´ u sorban van teh´ at legal´ abb soronl´ent k´et-k´et nemegyed¨ ul´ all´ o nulla. J´ ol v´ alasztani a nem eld¨ ontentlen sors´ u sorok k¨ oz¨ ul a´ltal´ aban nem k¨ onny˝ u. Egy o¨tletszer˝ u — Archim´ed´eszre eml´ekezve heurisztikus m´ odszer n´even nevezett — elj´ ar´ as k´ın´ alkozik: Ha az egyed¨ ul´ all´ o null´ ak nem teszik nyilv´ anval´ ov´ a, hogy mely sorokat, oszlopokat kell a´th´ uzni, akkor — v´ allalva annak a kock´ azat´ at, hogy nem lesz¨ unk sikeresek — h´ uzzuk a´t azt a sort, melyben a lehet˝ o legt¨ obb m´eg a´th´ uzatlan nulla van. Holtverseny eset´en a legfels˝o ilyent. Egy ilyen sok-null´ as sor a´th´ uz´ asa r´ev´en u ´ jabb egyed¨ ul´ all´ os´ agok keletkezhetnek. Ha az egyed¨ ull´ o null´ akat a fentiekhez hasonl´ oan levad´ asszuk, ´es m´eg mindig marad nem eld¨ ont¨ ott sors´ u, azaz legal´ abb-k´et-´at-nem-h´ uzott-null´ as sor, megint a legt¨ obb null´ at tartalmaz´o sor a´th´ uz´ as´ at kock´ aztatjuk meg. Mi lesz mindennek a v´ege? Vagy v´egs˝o o¨sszegz´esben legfeljebb n − 1 sor ´es oszlop lesz a´th´ uzva, visszat´er¨ unk a 2. l´ep´eshez annak rendje ´es m´odja szerint. Ha viszont az n-edik vonalat is be kellene h´ uznuk, a´llap´ıtsuk meg, hogy vesztett¨ unk! Kor´ abban kock´ aztattunk (legal´ abb egyszer), ez´ert nem lehet¨ unk biztosak abban, hogy j´ o sort v´ alasztottunk a´th´ uz´ asra. Felejts¨ uk el teh´ at azon a sorok ´es oszlopok a´th´ uz´ as´ at, melyek a kock´ azatv´ allal´ as ut´ an t¨ ort´entek. Kock´ azatmentes elj´ ar´ asra van sz¨ uks´eg! Minden megmaradt nem-´ath´ uzott sorban ´es oszlopban van teh´ at legal´ abb k´et-k´et nem-´ath´ uzott nulla. Ezen null´ ak k¨ oz¨ ul keress¨ unk egy legink´ abb egyed¨ ula´ll´ ot, azaz olyant, amely a saj´ at sor´aban vagy oszlop´ aban a lehet˝ o legkevesebbszer ism´etl˝ odik meg. Holtverseny eset´en a feljebb l´ev˝o sor, a baloldalibb oszlop legyen a nyer˝o. Az ´ıgy kiszemelt legink´ abb-egyed¨ ul´ all´ o null´ at jel¨ olj¨ uk meg sz¨ogletes z´ar´ ojellel. Majd u ´ jabb legink´ abb-egyed¨ ul´ all´ o null´ at keress¨ unk! De mindig vigy´ azzunk arra, hogy az o¨sszes — kerek vagy sz¨ogletes — z´ar´ ojelezett nulla egyed¨ ul maradjon a sor´aban is ´es az oszlop´ aban is. Ha u ´ gy adja a sors, hogy o¨sszesen n darab z´ar´ ojelezett null´ ank lesz, akkor sikertelen a´th´ uz´ asokkal v´eget´er a 3. l´ep´es, hiszen nyilv´ an m´ar a z´ar´ ojelezett ´ erhet¨ null´ ak a´th´ uz´ as´ ahoz is n darab vonalra van sz¨ uks´eg. Att´ unk teh´ at a 4. l´ep´esre, ´es a z´ar´ ojelez´esek mutatj´ ak a megold´ast! De mi van akkor, ha kerek ´es sz¨ogletes z´ar´ ojelekkel egy¨ uttv´eve is legfeljebb 5
n − 1 darab nulla ker¨ ul megz´ar´ ojelez´esre? Ilyenkor meg fogjuk n´ezni, hogy n¨ ovelhet˝ o-e a z´ar´ ojelezettek darabsz´ ama. A kerek z´ar´ ojeleket nem b´ antjuk, de a sz¨ogletesek k¨ oz¨ ul n´eh´ anyat m´ashova helyezhet¨ unk. K´epzel¨ uk el a m´atrixot u ´ gy, mint egy n-emeletes ´ep¨ uletet, melynek az emeletei a m´atrix sorai. Minden m´atrixoszlop tekinthet˝ o egy liftnek, mely lifteknek csak ott van ajtaja, ahol a m´atrixban nulla van. Pillanatnyilag sok liftajt´ o le van lakatolva, csak z´ar´ ojeles ajt´ ok nyithat´ ok. (Teh´ at egy-egy lift val´ oj´ aban csak egyegy emeletet k¨ ot o¨ssze a f¨ oldszinttel, de legal´ abb egy lift teljesen haszn´ alhatatlan) Mivel nem minden emeletre jut z´ar´ ojelezett nulla, vannak emeletek, ahol egyik lift sem m˝ uk¨ odik. Hogyan lehetne a lifttel ell´ atott emeletek darabsz´ am´at n¨ ovelni? A lifttel-nem-ell´atott emeletek bejelentik ig´eny¨ uket egy-egy, az emeletr˝ol esetleg haszn´ alhat´ o liftre, azaz valamelyik lelekatolt liftajt´ on´ al a lakat leemel´es´et k´erik. De ezzel vesz´elyeztetik egy-egy m´asik emelet lifttel val´ o ell´ atotts´ ag´ at, mert ha valahol le akarj´ ak szedni a lakatot, az ´erintett lift pillanatnyilag nemlelakatolt ajtaj´ at le kell lakatolni. De akkor a lelakatoland´ o ajtaj´ u emelet is bejelenti az ig´eny´et az o¨sszes, az emelethez tartoz´o, m´eg lelakatolt liftajt´ on´ al. De csak olyan liftet van ´ertelme ig´enyelni, amit m´as m´eg nem k´ert. Az liftig´eny fut´ ot˝ uzszer˝ uen terjed az ´ep¨ uletben. K´etf´ele v´eget ´erhet a fut´ ot˝ uz. Vagy siker¨ ul, vagy nem valakinak valahol olyan liftajt´ ot tal´ alni, ami egy ´eppen haszn´ alatlan lift ajtaja. El˝ obbi esetben azon u ´ tvonal ment´en, ahogyan a fut´ ot˝ uz ezt a ajt´ ot el´erte, lehets´eges a sz¨ogletes z´ar´ ojelek darabsz´ am´at eggyel n¨ ovelni. Ut´ obbi esetben meggondolhat´ o — ez a gondolatmenet l´enyeg´eben K˝ onig D´enes t´etele bizony´ıt´ as´ anak a r´esze — hogy a z´ar´ ojelezett null´ ak darabsz´ ama m´ar el´erte a fizikai lehet˝ os´egek hat´ ar´ at! (S˝ ot a matematikaiak´et is!) V´egk¨ ovetkeztet´es: A fenti m´odszerrel megkereshetj¨ uk a lehet˝ o legt¨ obb z´ar´ojelezett nulla hely´et. Ha a z´ar´ ojelezett null´ ak darabsz´ ama legfeljebb n − 1, akkor a fut´ ot˝ uzzel el´ert emeletek adj´ ak az a´th´ uzand´ o sorokat. Ezt´ an k¨ ovetkezik a visszat´er´es az 2. l´ep´eshez. Ha pedig a z´ar´ ojelezett null´ ak darabsz´ ama el´eri az n-et, a 4. l´ep´esn´el ´er v´eget a magyar m´odszer. Szerencs´ere konkr´et p´eld´ akon minden sokkal egyszer˝ ubb! (Legal´ abbis legt¨ obbsz¨ or.) 2. p´elda. Tekints¨ uk a k¨ ovetkez˝ o 4 × 4-es m´atrixot:
8
3
5
4
7
1
6
2
9
3
4
1
4
2
7
5
Az 1. l´ep´es ut´ an:
6
5
0
2
1
6
0
5
1
8
2
3
0
4
0
5
3
A 2. l´ep´es ut´ an:
1
0
0
1
2
0
3
1
4
2
1
0
0
0
3
3
A uz´ asa: 3. l´ep´esben a sorok ´es oszlopok a´th´ | | − 1 − 0 − (0) − 1 − | | 2 (0) 3 1 | | 4 2 1 (0) | | − (0) − 0 − 3 − 3 − | | Megvan a 4 darab z´ a r´ o jelezett nulla, at megvan a 3. l´ep´es is: ezzel teh´
1
0
(0)
1
2
(0)
3
1
4
2
1
(0)
(0)
0
3
3
A v´egeredm´eny:
7
8
3
(5)
4
7
(1)
6
2
9
3
4
(1)
(4)
2
7
5
σ = 5 + 1 + 1 + 4 = 11. (folyt. k¨ ov.)
8
