Obousměrné hledání

O(b^(d/2))

Obousměrné hledání zrychluje hledání nejkratší cesty tím, že hledá z obou konců současně: jedna vlna do šířky roste ze startu (amber/teal), druhá z cíle (fialová) a hledání skončí ve chvíli, kdy se dotknou. Protože každá vlna musí urazit jen zhruba polovinu vzdálenosti, dohromady prozkoumají řádově b^(d/2) buněk místo b^d — dramatická úspora u dlouhých cest. Nejkratší cesta se získá sešitím poloviny od startu s polovinou od cíle v místě setkání. Háček je vědět, kdy přestat: pokračuje, dokud žádná dosud neprozkoumaná dvojice frontových buněk nemůže utvořit kratší trasu. Na neohodnocené mřížce vrátí přesně stejnou délku jako prosté BFS.

Klikni na buňku pro přepnutí zdi
Mřížka
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Nech růst jednu frontu BFS ze startu a druhou z cíle.
  2. Vždy rozviň tu frontu, která je momentálně mělčí.
  3. Když je buňka dosažena oběma vlnami, zapamatuj si to setkání jako kandidátskou cestu.
  4. Zastav se, jakmile není možné kratší setkání, a spoj obě poloviny.

Pseudokód

1bidirectional(grid, start, goal):    # O(b^(d/2))2  BFS forward from start AND backward from goal3  expand whichever frontier is shallower4  when a cell is reached by both sides:5    record start→…→cell→…→goal as a candidate6  stop once no shorter meeting can exist7  stitch the two halves at the meeting cell