Kereső algoritmusok hatékonyságának összehasonlítása a Hanoi problémán keresztül
dc.contributor.advisor | Várterész, Magda | |
dc.contributor.author | Sotmari, Laslo | |
dc.contributor.department | DE--TEK--Informatikai Kar | hu_HU |
dc.date.accessioned | 2010-06-02T06:20:47Z | |
dc.date.available | 2010-06-02T06:20:47Z | |
dc.date.created | 2010 | |
dc.date.issued | 2010-06-02T06:20:47Z | |
dc.description.abstract | A hanoi tornyai matematikai játék, illetve feladvány egy legendából származó ötleten alapszik. A legenda szerint egykor az indiai Benaresben egy Shiva-templom jelölte a világ közepét. Fo Hi uralkodása idején a templomban élő szerzetesek feladatot kaptak Shiva istennőtől. A templom közepén volt egy márványtábla, melyből három gyémántrúd állt ki. Az első rúdon 64 különböző méretű arany korong volt. Legalul volt a legnagyobb, majd rajta méret szerint csökkenő sorrendben a többi. A szerzetesek feladata az volt, hogy áthelyezzék az összes korongot az első rúdról a másodikra, a következő szabályok betartása mellett. A korongok nagyon sérülékenyek, ezért egyszerre csak egy korong mozdítható, valamint egy korong nem helyezhető olyan rúdra, ahol van nála kisebb korong. A korongok megszenteltek, ezért csak ezt a három megszentelt rudat lehet használni, máshová nem rakhatják le a korongokat. Amint minden korong átkerült a második rúdra, a templom összeomlik, és a világ véget ér. Ha igaz ez a legenda, akkor jó lenne tudnunk, hogy ez mikor is következik be. A játék leírása először 1883-ban jelent meg egy párizsi újságban, amit a Li-Sou-Stian egyetem egyik hallgatója, N. Claus de Siam publikált. Kiderült, hogy a szerző csak egy álnév, az igazi szerző nevének anagrammája. A cikk valódi írója a Lyce Saint-Louis egyetem professzora, Edouard Lucas D’Ameins volt. A hanoi tornyai egy tipikus esete az úgynevezett „oszd meg és uralkodj” típusú problémáknak. A név onnan származik, hogy a megoldást legkönnyebben úgy találhatjuk meg, ha a problémát egyszerűbb, az eredetihez hasonló részproblémákra osztjuk, majd ha szükséges, a részproblémákat tovább osztjuk. Jelen esetben a problémának van egy kulcsmozzanata: a legnagyobb korong áthelyezése. Ha az első rúdról szeretnénk áthelyezni a korongokat a másodikra rúdra, akkor először a többi korongot kell átraknunk a harmadik rúdra, ezután át tudjuk rakni a legnagyobb korongot a második rúdra, majd a harmadik rúdra átrakott korongokat vissza kell rakni a második rúdra. A részproblémákat most a többi korong átrakása jelenti, először a harmadik rúdra, majd onnan vissza a másodikra. Ezeket a részproblémákat hasonló gondolkodásmód szerint oldhatjuk meg. Könnyen bizonyítható, hogy ezzel előállíthatjuk az optimális megoldást, ami n korong esetén 2^n-1 lépést jelent (a bizonyítást lásd később). Ezek szerint 64 korong esetén minimum 264 – 1 = 18 446 744 073 709 551 615 lépésre van szükség. Ha a szerzetesek képesek lennénk egy korongot egyik rúdról a másikra egy másodperc alatt átrakni, a probléma megoldása még akkor is megközelítőleg 590 000 000 000 évet venne igénybe, úgyhogy egy ideig még nem kell félnünk a világ végétől akkor sem, ha a legenda igaz. Meg kell jegyeznünk, hogy az Univerzum jelen ismereteink szerint 13 700 000 000 éves. Szakdolgozatom célja, hogy a hanoi problémát különböző módokon megoldjam, és ezeknek a megoldásoknak a hatékonyságát összehasonlítsam. Egy hagyományos mesterséges intelligenciai problémát általában legegyszerűbben állapottér-reprezentációval és az ismertebb kereső algoritmusokkal lehet megoldani. Természetesen ez közel sem a leghatékonyabb megoldás. Sokkal jobb eredményeket lehet elérni, ha elemezzük a problémát, és probléma specifikus algoritmust készítünk. Dolgozatom első felében két állapottér-reprezentációt fogok elemezni, majd a továbbiakban a problémát mélyebben megvizsgálva, ismertebb programozási technikákkal készítek többféle megoldást, és mindezeket összehasonlítom. Az algoritmusokat az egyszerűség kedvéért Java nyelven írtam, mivel célom nem a lehető legnagyobb hatékonyság elérése, hanem a különböző megoldások összehasonlítása. | hu_HU |
dc.description.course | programtervező informatikus | hu_HU |
dc.description.degree | Bsc | hu_HU |
dc.format.extent | 44 | hu_HU |
dc.identifier.uri | http://hdl.handle.net/2437/97042 | |
dc.language.iso | hu | hu_HU |
dc.subject | Hanoi | hu_HU |
dc.subject | hatékonyság | hu_HU |
dc.subject | mesterséges intelligencia | hu_HU |
dc.subject | kereső | hu_HU |
dc.subject.dspace | DEENK Témalista::Informatika::Számítógéptudomány | hu_HU |
dc.title | Kereső algoritmusok hatékonyságának összehasonlítása a Hanoi problémán keresztül | hu_HU |
Fájlok
Eredeti köteg (ORIGINAL bundle)
1 - 2 (Összesen 2)
Nem elérhető
- Név:
- Szakdolgozat[1].pdf
- Méret:
- 849.6 KB
- Formátum:
- Adobe Portable Document Format
- Leírás:
Engedélyek köteg
1 - 1 (Összesen 1)
Nem elérhető
- Név:
- license.txt
- Méret:
- 2.03 KB
- Formátum:
- Item-specific license agreed upon to submission
- Leírás: