Keresőalgoritmus
A keresőalgoritmusok olyan, az informatikában használt algoritmust jelöl, aminek a segítségével egy bizonyos tulajdonsággal felruházott elemet keresünk elemek egy gyűjteményében. Ez a gyűjtemény lehet akár rekordok sorozata, tömb(ök), mátrixok, vagy akár adatbázisok, az internet vagy akár egy matematikailag leírható tér is.
Általános jellemzők
Az algoritmusok, így a keresőalgoritmusok hatékonyságát is jellemezhetjük az idő-, és tárbonyolultságukkal, azzal a két metrikával, ami leírja, hogy az adott algoritmus mennyi időt, és helyet igényel a lefuttatáshoz, és ezáltal valamilyen osztályba sorolhatók. Ezeket a számítástudomány eszközeinek segítségével számolhatjuk ki. Sok esetben a keresőalgoritmusokat valamilyen korlátozás-kielégítő probléma (angolul CSP) megoldására használjuk, ekkor a célunk olyan eredmény/eredmények előállítása, mely eleget tesz valamilyen matematikailag leírható feltételrendszernek. Természetesen az is előfordulhat, hogy nem a legjobb megoldással, vagy nem az összes megoldással tér vissza egy ilyen algoritmus.
Fajták
Az egyik legegyszerűbb keresőalgoritmus-típus, a brute-force, ami lineárisan végignézi az értelmezési tartomány elemeit, és a feltételnek legjobban megfelelőt visszaadja. Azonban ennek az algoritmusnak az időigénye nagyon nagy, sőt, sok esetben a tér végtelensége miatt nem is alkalmazható sikerrel. Ha van valamilyen ismeretünk az értelmezési tartományról (pl. tudjuk, hogy egy növekvően rendezett tömbben keresünk egy adott értéket), akkor azt kihasználhatjuk, így jelentősen gyorsabb keresőt kapunk (pl. bináris kereső[1]). Azonban a legtöbb (akár való életbeli) probléma nem oldható meg ilyen kereséssel. Ezért több különböző megközelítés is létezik a problémák megoldására:
- Lokális keresők: ezeknél a probléma értelmezési terét úgy fogjuk fel, mint egy függvényt, melynek tipikusan valamely tulajdonságnak megfelelő pontját (szélsőértékeit, inflexiós pontjait, stb.) keressük, mindig az éppen vizsgált pontunk környezetéből kiindulva. Ilyenkor mindig ezen pont(ok) környezetében keresünk egy, vagy több olyan pontot (adott vizsgált tulajdonságnak jobban megfelelőket, vagy akár sztochasztikus módszereket alkalmazva), majd következő lépésként onnan vizsgálódunk tovább. Mindezt addig folytatjuk, amíg nem találunk egy kellően jó megoldást, vagy amíg el nem érünk egy iterációs korlátot, vagy időhatárt. Tipikusan ilyen keresőalgoritmusok pl. a hegymászó algoritmus, szimulált hűtés, vagy ide sorolható akár a Bees-algoritmus is.
- Fa struktúrában kereső algoritmusok: amikor a keresési teret egy fa struktúraként ábrázolhatjuk, és a feladat, hogy olyan utat/bejárást találjunk, ami megfelel a feltételeinknek. A bejárásnak irányítás szempontjából két fajtája lehet: a mélységi bejárás és a szélességi bejárás, de léteznek megosztó, és véletlen alapján keresők is. Tipikusan ilyen elven működik pl. a visszalépéses keresés, ahol addig haladunk előre, amíg jó/jobb értékeket találunk, majd ha találunk egy rosszabbat, akkor visszalépünk az első elágazáshoz, és a másik irányban folytatjuk a keresést. Ezen algoritmusokat felhasználják a játékelméletben (kétszemélyes játékok, pl. sakk lépéseinek kiszámítására), katonai, és gazdasági folyamatok modellezésére, és optimalizálására. Ide tartozó algoritmusok, pl. a Minimax algoritmus, A* algoritmus.
- Gráfokban kereső algoritmusok: Sok esetben hasonlóak a fában kereső algoritmusokra, az adott fa-kereső minimális változtatással alkalmazható gráfokra is. Ezek az algoritmusok rendszerint valamilyen részgráfot, utat keresnek, tipikusan valamilyen bejárást (mélységi, szélességi) megvalósítva. Optimalizációra használjuk őket, egyik legismertebb feladata ezeknek az utazó ügynök probléma megoldása.[2] Ilyen algoritmusok pl. a Dijkstra-algoritmus, Kruskal-algoritmus, Prim-algoritmus.
- Sztringben kereső algoritmusok: Mintaillesztéssel foglalkoznak tipikusan, vagyis egy adott részsztringet (mintát) keresnek a kiinduló szövegben, eredményként pedig általában két dolgot vizsgálnak:[3]
- előfordult-e a keresett minta a szövegben, vagy
- hányszor fordult elő
Két közismert példa: Boyer–Moore-algoritmus, Knuth–Morris–Pratt-algoritmus.
Jegyzetek
- ↑ Archivált másolat. [2010. augusztus 15-i dátummal az eredetiből archiválva]. (Hozzáférés: 2011. április 14.)
- ↑ Archivált másolat. [2011. április 24-i dátummal az eredetiből archiválva]. (Hozzáférés: 2011. április 14.)
- ↑ http://www-igm.univ-mlv.fr/~lecroq/string/node2.html#SECTION0020
Források
- Jon Kleinberg - Éva Tardos: Algorithm Design, ISBN 0-321-29535-8
