best-first search

Angol

Főnév

best-first search (tsz. best-first searches)

1. (informatika) legjobbat először keresés

---

A Best-First Search (BFS) egy heurisztikus gráfkereső algoritmus, amely minden lépésben az éppen legígéretesebb csomópontot vizsgálja tovább. A döntés alapja egy heurisztikus érték – az algoritmus mindig azt a csomópontot bővíti, amelyről a leginkább valószínű, hogy elvezet a célhoz.

Ez a stratégia egy általános keretrendszer, amely olyan ismert algoritmusokat is magába foglal, mint:

• Greedy Best-First Search – csak a célhoz való távolságot nézi
• A* – figyelembe veszi az eddigi költséget is

---

🧠 Alapötlet

A keresés során a csomópontokhoz hozzárendelünk egy értéket (f(n)), amely megmondja, hogy mennyire „jó” az adott állapot a célhoz vezető úton.

$$f(n)={\text{heurisztika}}(n)$$

Az algoritmus mindig azt a csomópontot választja ki, amelynek a legalacsonyabb f(n) értéke van.

---

📦 Fő jellemzők

Tulajdonság	Best-First Search
Stratégia	Heurisztikus
Adatszerkezet	Prioritási sor (pl. min-heap)
Visszalépés	Nem garantált (nem mindig teljes)
Optimalitás	Nem garantált, hacsak nem A*-ként használjuk
Heurisztika	A célhoz való távolság becslése

---

🔧 Algoritmus lépései

1. Inicializálás: a kiinduló állapot bekerül a prioritási sorba
2. Iteráció:
   • Vegyük ki a legjobb (legalacsonyabb f(n)) állapotot a sorból
   • Ha ez a cél → kész
   • Különben: bővítsük (generate successors), és adjuk hozzá az új állapotokat a sorhoz
3. Ismételjük, amíg megtaláljuk a célt vagy a sor ki nem ürül

---

💡 Példa: Greedy Best-First Search

Itt:

$$f(n)=h(n)$$

A h(n) érték a célhoz való becsült távolság. Ez gyors, de nem optimális (mert nem veszi figyelembe az eddigi út költségét).

---

🧠 Példa: A* mint best-first search

Az A* algoritmus is a Best-First Search egyik esete:

$$f(n)=g(n)+h(n)$$

• ${\textstyle g(n)}$: az eddig megtett út költsége
• ${\textstyle h(n)}$: a célhoz vezető út heurisztikus becslése

Az A* garantáltan optimális és teljes, ha a ${\textstyle h(n)}$ optimista (admissible).

---

📘 Példa (táblázatos keresés)

Képzeljük el, hogy az alábbi gráfból akarunk eljutni A-ból G-be.

   A
  / \
 B   C
 |   |
 D   E
  \ /
   F
   |
   G

Heurisztikus értékek (h):

Csúcs	h(n)
A	6
B	5
C	4
D	3
E	2
F	1
G	0

Greedy BFS útvonala: A → C → E → F → G

---

✅ Előnyök

• ✅ Gyors a célhoz közeli irányban
• ✅ Egyszerű implementáció
• ✅ Hatékony nagy gráfoknál jó heurisztikával

---

❌ Hátrányok

• ❌ Nem garantált az optimális megoldás
• ❌ Nem mindig teljes (ha körök vagy végtelen utak vannak)
• ❌ Erősen függ a heurisztikától

---

💻 Pszeudokód

open_list = PriorityQueue()
open_list.put(start_node, f(start_node))
closed_list = set()

while not open_list.empty():
    current = open_list.get()

    if current == goal:
        return reconstruct_path(current)

    closed_list.add(current)

    for neighbor in successors(current):
        if neighbor in closed_list:
            continue
        open_list.put(neighbor, f(neighbor))

---

🧩 TL;DR

A Best-First Search egy heurisztika-alapú kereső algoritmus, amely mindig azt a csomópontot vizsgálja, amelyről a legígéretesebbnek tűnik, hogy elvezet a célhoz. Egyszerű, gyors, de nem mindig ad optimális megoldást – kivéve, ha A*-ként használjuk.

További információk

• best-first search - Szótár.net (en-hu)
• best-first search - Sztaki (en-hu)
• best-first search - Merriam–Webster
• best-first search - Cambridge
• best-first search - WordNet
• best-first search - Яндекс (en-ru)
• best-first search - Google (en-hu)
• best-first search - Wikidata
• best-first search - Wikipédia (angol)