Hladové prohledávání

O(E log V)

Hladové best-first prohledávání je A* bez brzd: řadí otevřené buňky jen podle heuristiky — manhattanské vzdálenosti přímo k cíli — a ignoruje, jak daleko už jsou od startu. Díky tomu míří přímo na cíl a obvykle je rychlé, rozvine mnohem méně buněk než BFS. Háček je, že není optimální: tím, že vždy honí buňku, která jen vypadá nejblíž, se může upnout na trasu, která obejde překážku špatným směrem a skončí delší cestou než A*. Je to varovný protějšek A* — stejná mašinerie, ale vypuštění členu g vymění záruku optimality za rychlost.

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

Jak to funguje

  1. Ohodnoť každou buňku jen její heuristickou vzdáleností k cíli.
  2. Vždy rozviň otevřenou buňku, která vypadá nejblíž cíli.
  3. Přidej neviděné volné sousedy do otevřené množiny a zapamatuj, odkud přišli.
  4. Zastav se v cíli a vytrasuj zpět — cesta nemusí být nejkratší.

Pseudokód

1greedyBestFirst(grid, start, goal):  # O(E log V)2  open ← {start}3  while open not empty:4    cell ← node in open with least h    # h = manhattan(cell, goal)5    if cell = goal: stop6    for nbr in free neighbours(cell):7      if nbr not seen:8        prev[nbr] ← cell; add nbr to open9  walk prev from goal back to start     # NOT guaranteed shortest