Algorytmy, które omówiliśmy do tej pory, zaczynają się od stanu początkowego i mogą osiągnąć dowolny z wielu możliwych stanów docelowych. Alternatywne podejście zwane przeszukiwaniem dwukierunkowym jednocześnie przeszukuje w przód od stanu początkowego i wstecz od stanu(ów) docelowego(ych), mając nadzieję, że oba wyszukiwania się spotkają. Motywacja jest taka, że bd/2 + bd/2 to znacznie mniej niż bd (np. 50 000 razy mniej, gdy b = d = 10).
Aby to zadziałało, musimy śledzić dwie granice i dwie tabele osiągniętych stanów, a także musimy być w stanie rozumować wstecz: jeśli stan s’ jest następcą w kierunku do przodu, to musimy wiedzieć, że jest następca s’ w kierunku wstecznym. Mamy rozwiązanie, gdy zderzają się dwie granice.
Istnieje wiele różnych wersji wyszukiwania dwukierunkowego, podobnie jak istnieje wiele różnych algorytmów wyszukiwania jednokierunkowego. W tej sekcji opisujemy dwukierunkowe wyszukiwanie od najlepszej do pierwszej. Chociaż istnieją dwie oddzielne granice, węzeł, który ma zostać rozwinięty jako następny, jest zawsze takim, który ma minimalną wartość funkcji oceny, po obu stronach granicy. Gdy funkcją oceny jest koszt ścieżki, otrzymujemy dwukierunkowe przeszukiwanie o jednolitym koszcie, a jeśli kosztem optymalnej ścieżki jest C*, to żaden węzeł z kosztem > C*/2 nie zostanie rozszerzony. Może to spowodować znaczne przyspieszenie. Ogólny algorytm dwukierunkowego wyszukiwania „najlepszy-pierwszy” pokazano na rysunku 3.14. Przekazujemy dwie wersje zadania i funkcji oceny, jedną w kierunku do przodu (subscript ) i jedną w kierunku wstecznym (subscript ). Gdy funkcją oceny jest koszt ścieżki, wiemy, że pierwsze znalezione rozwiązanie będzie rozwiązaniem optymalnym, ale z różnymi funkcjami oceny, co niekoniecznie jest prawdą. Dlatego śledzimy najlepsze znalezione do tej pory rozwiązanie i być może będziemy musieli aktualizować je kilka razy, zanim test ZAKOŃCZONY wykaże, że nie ma lepszego rozwiązania.
Dwukierunkowe wyszukiwanie „najlepszy-pierwszy” zachowuje dwie granice i dwie tabele osiągniętych stanów. Gdy ścieżka w jednej granicy osiąga stan, który został osiągnięty również w drugiej połowie poszukiwań, obie ścieżki są łączone (funkcją JOIN-NODES) w celu utworzenia rozwiązania. Pierwsze rozwiązanie, które otrzymamy, nie gwarantuje, że będzie najlepsze; funkcja ZAKOŃCZONA określa, kiedy przestać szukać nowych rozwiązań.