bidirectional search

Angol

Főnév

bidirectional search (tsz. bidirectional searches)

1. (informatika) A számítástechnikai keresési algoritmusok egyik hatékony típusa a kétirányú keresés (bidirectional search). Ezt az algoritmust elsősorban gráfokban való útkeresésre használják, amikor a cél az, hogy megtaláljuk a legrövidebb vagy legköltséghatékonyabb utat egy kezdőpont (start) és egy célpont (goal) között.

A kétirányú keresés különlegessége, hogy egyszerre két irányból indul el a keresés:

• Előre keresés a start pontból → cél felé
• Hátrafelé keresés a célpontból → start felé

Az algoritmus akkor fejeződik be, amikor a két irányból induló keresés találkozik, vagyis az egyik irányban megtalált csúcsot a másik irányban is elértük. Ekkor a teljes út rekonstruálható.

---

Miért hasznos?

A kétirányú keresés legnagyobb előnye a keresési tér drasztikus csökkentése.

Vegyünk egy példát: ha egy gráfban a csúcsok száma ${\textstyle N}$, és a keresés kiterjedése (search depth) ${\textstyle d}$, akkor egy sima BFS (Breadth-First Search) O(b^d) idő- és memóriaigényű, ahol ${\textstyle b}$ az ágak száma (branching factor).

Viszont kétirányú keresés esetén mindkét irányban csak ${\textstyle d/2}$ mélységig kell keresni:

• ${\textstyle O(b^{d/2}+b^{d/2})=O(2\cdot b^{d/2})}$, ami nagyságrendekkel kevesebb.

Ez különösen nagy méretű gráfokban látványos:

• Például ha ${\textstyle b=10}$, ${\textstyle d=6}$, akkor
  • egyirányú BFS: ${\textstyle 10^{6}=1,000,000}$ állapotot érint
  • kétirányú keresés: ${\textstyle 2\times 10^{3}=2000}$ állapotot érint → 500-szor kevesebb.

---

Hogyan működik?

A kétirányú keresés alapesetben BFS-t alkalmaz mindkét irányban:

1. Kezdjük a keresést startból előre (Forward BFS).
2. Kezdjük a keresést goalból hátra (Backward BFS).
3. A kettő felváltva lépked: minden lépésben bővítünk egy szintet mindkét irányban.
4. Ha a két részkeresés metszi egymást (azonos csúcsba érünk mindkét irányból), akkor az út rekonstruálható.

---

Általános algoritmus lépések

1. Hozzuk létre a két munkalistát (frontier):
   • forward_frontier = {start}
   • backward_frontier = {goal}
2. Hozzunk létre két visited halmazt:
   • visited_forward
   • visited_backward
3. Amíg a két frontier nem üres:
   • Végezzük el a következő lépést a forward search irányban:
     • Vegyük ki a következő csúcsot a forward_frontier-ből.
     • Bővítsük a szomszédokkal.
     • Ha valamelyik szomszéd benne van visited_backward-ben, akkor találtunk utat → STOP.
   • Végezzük el a következő lépést a backward search irányban:
     • Ugyanez, de visszafelé.
   • Ha nincs metszés, folytatjuk.
4. Ha sikerült találkozni → rekonstruáljuk az utat.

---

Egyszerű kódvázlat (Python-szerű pszeudokód)

def bidirectional_search(graph, start, goal):
    from collections import deque

    # frontier = queue of nodes to visit
    forward_frontier = deque([start])
    backward_frontier = deque([goal])

    # visited sets to record explored nodes
    visited_forward = {start: None}
    visited_backward = {goal: None}

    while forward_frontier and backward_frontier:
        # Expand forward
        current_forward = forward_frontier.popleft()
        for neighbor in graph[current_forward]:
            if neighbor not in visited_forward:
                visited_forward[neighbor] = current_forward
                forward_frontier.append(neighbor)
                if neighbor in visited_backward:
                    return reconstruct_path(visited_forward, visited_backward, neighbor)

        # Expand backward
        current_backward = backward_frontier.popleft()
        for neighbor in graph[current_backward]:
            if neighbor not in visited_backward:
                visited_backward[neighbor] = current_backward
                backward_frontier.append(neighbor)
                if neighbor in visited_forward:
                    return reconstruct_path(visited_forward, visited_backward, neighbor)

    return None  # No path found

def reconstruct_path(visited_forward, visited_backward, meeting_point):
    # Reconstruct path from start to goal
    path = []
    node = meeting_point
    while node is not None:
        path.append(node)
        node = visited_forward[node]
    path.reverse()

    node = visited_backward[meeting_point]
    while node is not None:
        path.append(node)
        node = visited_backward[node]

    return path

---

Használati esetek

A kétirányú keresés számos területen hasznos:

• Útkeresés térképeken (Google Maps, GPS navigáció)
• Robot navigáció (pl. robotok mozgása raktárban)
• Játékokban AI útkeresés (pl. sakk, puzzle játékok)
• Szociális gráfok elemzése (pl. Facebook kapcsolati hálóban “shortest path”)
• Hálózatok optimalizálása

---

Mikor nem hatékony?

• Ha a célállapot ismeretlen (pl. “keressünk bármilyen végállapotot”) → nem lehet célból visszafelé keresni.
• Ha nagy a keresési tér szabálytalansága → az egyik irány sokkal bonyolultabb lehet.
• Ha a gráf nem szimmetrikus vagy a fordított élek nem ismertek → nehézkes a backpropagation.

---

Heurisztikus változatok

A fenti algoritmus alap BFS volt.

Lehet heurisztikus verziókat is készíteni:

• Bidirectional A* → A* algoritmust futtatunk mindkét irányból.
• A heurisztika segít abban, hogy ne minden irányba bővítsük a keresést, csak a legígéretesebb felé.

→ Ez még hatékonyabbá teszi a keresést.

---

Összefoglalás

Előny	Hátrány
Sokkal kevesebb állapotot vizsgál	Nem minden probléma alkalmas rá
Nagy gráfokban gyors	Célállapotot is ismerni kell
Egyszerű implementáció BFS alapokon	Hátrafelé keresés nem mindig könnyű

---

TL;DR

A kétirányú keresés hatékony útkereső algoritmus, ami két irányból (start és goal) egyszerre keres, így a keresési tér méretét jelentősen csökkenti. Elsősorban gráfokban, útvonaltervezésre és AI feladatokban használják. Hátránya, hogy célállapot ismerete szükséges, és nem minden gráfnál alkalmazható egyszerűen.

További információk

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