Egy matematikai m´odszer tutajos feladatok a´ltal´anos megold´as´ara ´ Scipiades Armin 2010. szeptember 12.
1. Tutajos feladatok L´etezik a logikai feladv´anyoknak egy j´ol felismerhet˝o t´ıpusa, melyben azt kell kital´alni, hogy l´enyek bizonyos csoportja hogyan tud, adott korl´atoz´o szab´alyokat betartva, egy kicsi tutajon ´ atkelni egy foly´on. Intuit´ıvan nem k¨ ul¨on¨ osebben neh´ez megoldani ezeket a feladatokat; n´emi gyakorlattal, ha ,,r´aa´ll az agyunk”az eff´ele feladv´anyokra, gyorsan r´aj¨ohet¨ unk az adott feladat nyitj´ ara. Az intuit´ıv megk¨ozel´ıt´es gyorsan eredm´enyre vezethet, m´egis vannak h´atr´ anyai: – az intuit´ıv megold´ as nem felt´etlen minim´alis, vagy ha az is, minim´ aliss´ ag´ at nem bizony´ıtottuk matematikailag. – csak egy megold´ asunk lesz, nem tudjuk, van-e t¨obb, ´es ha van, mik? – nem tudjuk bizony´ıtani, ha a feladv´anynak nincs megold´asa. – megold´asunk nem algoritmiz´alhat´o: csak az adott feladatra ´erv´enyes, nem ´altal´ anos megold´as; m´odszer¨ unket nem tudjuk m´ asoknak megtan´ıtani, ´es sz´ am´ıt´ og´epeket sem tudunk megtan´ıtani r´a. A k´erd´es teh´at az, hogyan tudn´ank matematikai alapokra helyezni ennek a t´ıpusfeladatnak a megold´ as´at?
2. Egy nem-intuit´ıv m´ odszer A feladat intuit´ıv megold´asa sor´an gondolatban fordul´okra koncentr´alunk: a´tvisz¨ unk n´eh´ any l´enyt a m´asik oldalra, megvizsg´ aljuk, szab´ alyos-e a helyzet, majd visszavisz¨ uk a tutajt egy vagy t¨obb l´ennyel – ez egy fordul´ o. A megold´as teh´at ´ all helyzetekb˝ ol, ´es az ezeket egym´ ashoz kapcsol´o utakb´ ol – ha ezt v´egiggondoljuk, k¨onnyen ad´odik a felismer´es, hogy a feladat o¨sszes megold´ as´at fel´ırhatjuk egy gr´affal, amelyben a csom´opontok a helyzetek, az ´elek pedig az utak. 1
A gr´ afot a k¨ ovetkez˝ o l´ep´esekkel ´ırhatjuk fel: – ´Irjuk fel az o¨sszes lehets´eges helyzetet, vagyis a l´enyek elhelyezked´es´enek o¨sszes permut´aci´oj´ at. A helyzetek sz´ ama fel¨ ulr˝ol becs¨ ulhet˝o Vn2ism = 2n nel (n a l´enyek sz´am´at jel¨oli), hiszen egy l´eny vagy az egyik oldalra ker¨ ul, vagy a m´ asikra. – H´ uzzuk ki a szab´alytalan helyzeteket, vagyis azokat, amelyek nem felelnek meg a kik¨ ot´eseknek. – ´Irjuk f¨ ol az ´eleket! Hasonl´ıtsunk ¨ ossze minden helyzetet minden m´ as helyzettel, ´es ´ırjuk f¨ol, hogyan hozhat´o l´etre az egyik helyzetb˝ol a m´asik. ¨ Ugyelj¨ unk r´a, hogy a gr´afunk lehet ir´any´ıtott, ´es kaphatunk multigr´afot is. A kapott gr´af m´ar matematikailag kezelhet˝o: a feladat minim´ alis megold´as´at p´eld´aul k¨onnyen megkapjuk a Dijkstra-f´ele algoritmus haszn´alat´aval (keress¨ uk a legr¨ovidebb utat a kezd˝opont ´es a k´ıv´ant v´egpont k¨oz¨ott). Az ´ıgy kapott megold´ as bizony´ıtottan minim´alis megold´as lesz. A m´odszert, b´ ar komplexit´asa magas, naiv megval´ os´ıt´as eset´en faktori´ alis nagys´ agrend˝ u, k¨ ul¨ on¨ osebb gond n´elk¨ ul le lehet programozni.
3. Kidolgozott p´ elda H´arom ember, egy nagy majom ´es k´et kis majom szeretne a´tkelni a foly´ on. Hogyan csin´ alj´ak? – Evezni csak az emberek ´es a nagy majom tud. – Egy helyen egyid˝oben nem lehet t¨obb majom, mint ember, mert akkor a majmok megeszik az embereket. – A cs´ onakba kett˝ on´el t¨obben nem f´ernek el.
3.1. ´Irjuk fel az ¨ osszes lehets´ eges helyzetet ´ es h´ uzzuk ki a szab´ alytalan helyzeteket! A k¨ovetkez˝o t´abl´azatban E jel¨oli az embereket, M a nagy majmot ´es m a kismajmokat. Az ´erv´enytelen sorokat pirossal, a szab´alyosakat z¨olddel sz´ınezt¨ uk. 1. 2. 3. 4.
E E E E E E
E E E E M E
E M E E m m
M m M m m m
m m m m m
2
E m M E E E M
5. 6. 7. 8.
9. 10. 11. 12. 13. 14. 15. 16.
E E E M E E E E E E E E M m E m M
E E E m M m E E E E M m m m
M m E m E M m m m M m E
E M m E E E E E M E E E E E E E E E
m m m E E E m M M M E E E E E E E E
E m M m m m m m M E E M E E E
m m m m M m M m M
m m m m m
A huszonn´egy permut´ aci´ob´ol teh´at tizenhat bizonyult szab´alyosnak. A csom´opontokhoz ´ert´eket rendelhet¨ unk aszerint, mennyire ´allnak k¨ ozel a k´ıv´ant helyzethez; egy helyzet ´ert´eke legyen egyenl˝o a c´elparton l´ev˝o l´enyek sz´am´ aval.
3.2. ´Irjuk f¨ ol az ´ eleket Fentebb azt mondtuk, hogy az ´elek fel´ır´ as´ahoz minden helyzetet ¨ ossze kell hasonl´ıtani minden m´asik helyzettel: val´ oj´aban egy helyzetet el´eg azokkal a helyzetekkel ¨osszehasonl´ıtani, amelyek a cs´ onak kapacit´as´at´ ol f¨ ugg˝oen l´etrej¨ohetnek (a k´et helyzet elt´er´ese kisebb a cs´ onak kapacit´as´an´al – ne feledj¨ uk, hogy a cs´ onakot vissza is kell vinni a kiindul´asi partra, kiv´eve az c´elba vezet˝ o ´elek eset´eben). Az al´abbi t´abl´azatban z¨olddel sz´ınezt¨ uk az alacsonyabb ´ert´ek˝ u csom´opontb´ol a magasabbik ´ert´ek˝ ube viv˝o ´eleket, s´arg´ aval a visszafele viv˝o ´eleket, k´ekkel az egyenrang´ u csom´opontok k¨oz¨ ottieket, ´es feh´errel a c´elba vezet˝ o ´eleket.
1→2 1→2 1→3
oda E m M m M E
K¨ oztes helyzet E E M m E m E E E m M m E E m m M E
3
vissza E M E
2→1 2→1 2→7 3→1 4→5 4→6 4→8 5→4 5→6 5→7 6→4 6→5 7→5 8→4 8 → 11 8 → 12 10 → 11 10 → 12 10 → 15 10 → 16 11 → 10 11 → 12 11 → 15 11 → 16 12 → 8 12 → 10 12 → 11 12 → 15 12 → 16 15 → 10 15 → 11 15 → 12 15 → 16
M E M E E E E E E E E E E M M M E E E E E E E E M M M M M M M M M
m m m E M M m E E E m m M M M M m m m m
E E E E E E m E E E E E E m m m
E E E E m m m m m M m m M m
E m M m E m m
m m m m m
M E M M E E E E E E E E E E E E E E E E E E E E E E E E E E E E E
m m m E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E
m M M E M M m M M m E E E E E E E E E E E E E E E E E E E E
m m M m m m m m m M M M M M M M M M M M M M M M M M M M M
m m m m m m m m m m m m m m m m m m m
m m m m m m m m m m m m m m m m
M E M M E E M E E E E E E E E M E M M
m m E M E m E E m M m E
m m
E M M m M M m E M E m M E M E m M m
Ekkor m´ar fel tudjuk rajzolni a gr´afot, amelyr˝ol r¨ ogt¨on kit˝ unik, hogy van u ´t a kezd˝o- ´es v´egpont k¨oz¨ott, teh´at a feladatnak van megold´asa. Megfigyelhet˝ o az is, hogy bizonyos helyzetek, b´ar a kik¨ot´eseknek megfelelnek, soha nem j¨ohetnek l´etre, ezeket a rajzon s´arg´aval sz´ınezt¨ uk.
4
4
10
3
9
14
5
11
1
16 6
12
2
8
15
7
13
3.3. A megold´ as Rendelj¨ unk minden ´elhez ugyanakkora ´ert´eket, ´es alkalmazzuk a gr´ afra a Dijkstra-f´ele algoritmust! N´egy minim´alis megold´as ad´odik (mert az 1. csom´opontb´ol a 2-ba k´et ´el vezet; illetve mert a 8. helyzetb˝ol a 11. ´es 12. csom´oponton kereszt¨ ul is c´elba´erhet¨ unk). A megold´asokat a rajzon a piros ´elek jelzik. A n´egy minim´ alis megold´asb´ol egy ¨onk´enyesen v´alasztottat k¨ozl¨ unk:
→ ← → ← → ← → ← → ← → ← →
M M M M E E E E E M M E E
m m E m M m E m
E E E E E E E E E m M m E
E E E E E M E m E m m
E E E E E
M m m m M m M
M m m m m
m
m
5
M m M m E E E E E E E E E
m m m E m E M E E E E E
m m m M m E E E M E
M M m m M m m
¨ 4. Osszegz´ es A mechanikus m´odszerek sosem helyettes´ıtik a gondolkod´ast. A most t´argyalt m´odszer eset´eben is elmondhat´o, hogy intuit´ıv megk¨ozel´ıt´essel – ha u ´ gy tetszik heurisztikusan – gyorsabban ´es eleg´ansabban megoldhat´oak a tutajos feladatok. M´ odszer¨ unk akkor haszn´ aland´ o, ha a feladat megold´ as´ aval v´egleg k´aty´ uba jutottunk, vagy ha szeretn´enk megbizonyosodni megold´asunk helyess´eg´er˝ol illetve minim´aliss´ag´ar´ol, vagy ha szeretn´enk m´elyebben elemezni a feladatot.
6
