best-first search

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

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.

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

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

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

Itt:

$${\displaystyle 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).

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

$${\displaystyle 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).

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):

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

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

• ❌ 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

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))

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.

• 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)