Fejlett keresőalgoritmusok működésének és hatékonyságának vizualizációja

Dátum
2012-06-11T10:31:29Z
Szerzők
Szatmári, László
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt
A mesterséges intelligencia a számítástudomány talán legjelentősebb és legkiterjedtebb ága, ami ma már a tudomány szinte minden területén jelen van valamilyen formában. Segítségével nagyon sok olyan problémára választ adhatunk, amelyek megoldása egyébként komoly munkát igényelne. A mesterséges intelligencia keresőalgoritmusaira jellemző, hogy a megoldást igen nagy halmazból kell kiválasztaniuk, és az egyes megoldásjelöltekről nem mindig lehet megállapítani, hogy milyen távol vannak a globális optimális megoldástól. Az a feladatuk, hogy minél gyorsabban, vagyis minél kevesebb elem megvizsgálásával megtalálják a megoldást. Az olyan algoritmusokat, amelyek nem vizsgálnak meg minden elemet, hanem valamilyen gondolkodásmód szerint az állapottér bizonyos részeit vizsgálják, fejlett keresőalgoritmusoknak nevezzük. A fejlett keresőalgoritmusoknak számos fajtájuk létezik, csoportosításuk nehéz. Ezek az algoritmusok legtöbbször a természetből vagy a tudomány egy más területéről vett ötleten alapszanak. Például az evolúciós algoritmusokat Darwin evolúciós elmélete ihlette. Ezek az algoritmusok a természetes kiválasztódást működését alkalmazzák. A neurális hálók az emberi agy neuronjait modellezik. A raj intelligenciai algoritmusok állatrajok mozgását szimulálják. Vannak olyan algoritmusok is, amiket a fizika ihletett. Például a szimulált hűtés (Simulated Annealing) algoritmus egy lassan hűlő fizikai rendszert modellez, amiben a hőmérséklet csökkenésével lassul a részecskék mozgása. Számos algoritmus létezik, azonban a hatékonyságuk a problémák jellegétől függően változik. Egyes algoritmusok lehet, hogy általánosságban lassabbak a többinél, viszont előfordulhatnak olyan problémák, amiken sokkal jobb teljesítenek, vagy csak ezek képesek megoldást találni. Gyakran sorsdöntő lehet az algoritmus megfelelő megvalósítása, valamint a jó paraméterezése. Komplexebb problémáknál általában több algoritmus keresztezése nyújtja a legjobb eredményt. Ehhez azonban jól kell ismerni az algoritmusokat, és magát a problémát is. Dolgozatom célja néhány algoritmus működésének bemutatása, valamint hatékonyságuk vizsgálata. Az algoritmusok összehasonlításához azonban szükség van egy problémára, amely megoldható a kiválasztott algoritmusokkal. Ehhez a japán nonogram rejtvény megoldását választottam. Ez egy olyan probléma, amely az összes lehetséges eset végigpróbálgatásával csak nagyon hosszú idő alatt oldható meg. Bizonyítottan NP-teljes probléma. Célom egy olyan vizualizációs program elkészítése, amely szemlélteti az algoritmusokat működés közben. Mindemellett szeretném a problémát különböző algoritmusokkal megoldani, és ezeket részletesen összehasonlítani, teljesítményüket kiértékelni.
Leírás
Kulcsszavak
mesterséges intelligencia, fejlett keresőalgoritmus, logigrafika, nongram, genetikus algoritmus, hegymászó algoritmus
Forrás