search algorithm
(search algorithms szócikkből átirányítva)
Főnév
search algorithm (tsz. search algorithms)
A search algorithm (keresési algoritmus) olyan eljárás, amely célja valamilyen információ vagy megoldás megtalálása egy adott térben – például egy gráfban, fastruktúrában, adatbázisban vagy állapottérben.
🔍 Típusai keresési céltól függően
1. Adatkeresés
- Lineáris keresés: egymás után vizsgálja az elemeket.
- Bináris keresés: rendezett tömbben logaritmikus időben keres (osztás alapú).
- Hash-alapú keresés: kulcs alapján azonnal megkeresi az elemet.
2. Állapottér-keresés (AI-ben, gráfban, játékban stb.)
- A cél: megtalálni az induló állapottól a célig vezető utat.
🌳 Állapottér-keresési algoritmusok
🧠 Nem informált (uninformed) – nem használ a célhoz vezető útra vonatkozó extra információt:
| Algoritmus | Jellemzők |
|---|---|
| Breadth-First Search (BFS) | Szélességi bejárás, megtalálja a legrövidebb utat, lassú memória |
| Depth-First Search (DFS) | Mélységi bejárás, kis memóriaigény, lehet, hogy nem talál célt |
| Uniform-Cost Search (UCS) | Legolcsóbb út szerint halad, garantált optimális út |
| Depth-Limited Search | DFS korlátozott mélységgel, elkerüli végtelen ágakat |
| Iterative Deepening DFS | Kombinálja a DFS és BFS előnyeit |
💡 Informált (informed / heuristic) – használ heurisztikát a célhoz vezető út becslésére:
| Algoritmus | Jellemzők |
|---|---|
| Greedy Best-First Search | Heurisztikát követ, gyors, de nem garantáltan optimális |
| A* | f(n) = g(n) + h(n), garantáltan optimális (ha h helyes) |
| IDA* | Iteratív mélyítéses A*, alacsony memóriaigény |
| RBFS (Recursive Best-First Search) | A* memóriahatékony változata |
| D* (Dynamic A*) | Dinamikus környezetekhez (pl. robotok navigációja) |
🕹️ Különleges keresési területek
🎲 Játékok és ellenfelek
- Minimax algoritmus: kétjátékos játékokhoz, feltételezve, hogy az ellenfél is optimálisan játszik.
- Alpha-Beta metszés: Minimax gyorsítása, irreleváns ágak elhagyása.
🧩 Korlátos vagy részlegesen megfigyelt környezet
- Online search: az ügynök csak a saját környezetét látja (pl. labirintus bejárás)
- Partially Observable Search: nem minden állapot ismert, gyakran Bayes-hálókkal kombinálva
📈 Teljesítménymutatók
| Mutató | Leírás |
|---|---|
| Completeness | Megtalálja-e a megoldást, ha van |
| Optimality | A legjobb (legolcsóbb, legrövidebb) megoldást találja-e |
| Time Complexity | Futási idő (pl. O(b^d)) |
| Space Complexity | Memóriaigény |
📌 Példa: A* algoritmus
f(n) = g(n) + h(n) g(n): költség a kezdőtől n-ig h(n): becsült költség n-től a célig
Ha h(n) admisszibilis (sosem becsül túl), az A* optimális és komplett.
🔧 Felhasználási területek
- Mesterséges intelligencia
- Útvonaltervezés (pl. GPS)
- Játékfejlesztés
- Logisztika (útvonal-optimalizálás)
- Problémamegoldás (pl. 8 királynő, rubik-kocka)
- search algorithm - Szótár.net (en-hu)
- search algorithm - Sztaki (en-hu)
- search algorithm - Merriam–Webster
- search algorithm - Cambridge
- search algorithm - WordNet
- search algorithm - Яндекс (en-ru)
- search algorithm - Google (en-hu)
- search algorithm - Wikidata
- search algorithm - Wikipédia (angol)