Gratis flashcards

Antall noder Dijkstra utforsker vokser omtrent som søkeradius opphøyd i dimensjonen. Heuristisk: hvis ettrettet søk utforsker et område som vokser som $b^d$ (forgreningsfaktor b, avstand d kanter), utforsker hvert av de to bidireksjonelle søkene bare ut til halvparten av avstanden, altså cirka $2\cdot b^(d/2)$ noder til sammen. For store d er $2\cdot b^(d/2)$ ≪ $b^d,$ så man besøker langt færre noder. Gevinsten er størst når start og mål er langt fra hverandre i en graf med jevn forgrening; den forsvinner hvis grafen er smal eller målet ligger nær start.