Jak decydujemy, który węzeł z granicy będzie dalej rozszerzany? Bardzo ogólne podejście nazywa się przeszukiwaniem „najlepszy-pierwszy”, w którym wybieramy węzeł n , z minimalną wartością pewnej funkcji oceny f(n). Rysunek przedstawia algorytm. W każdej iteracji wybieramy węzeł na granicy z minimalną wartością f(n), zwracamy go, jeśli jego stan jest stanem docelowym, a w przeciwnym razie stosujemy EXPAND do generowania węzłów podrzędnych. Każdy węzeł podrzędny jest dodawany do granicy, jeśli nie został wcześniej osiągnięty, lub jest dodawany ponownie, jeśli jest teraz osiągany ścieżką, która ma niższy koszt ścieżki niż jakakolwiek poprzednia ścieżka. Algorytm zwraca albo wskazanie niepowodzenia, albo węzeł reprezentujący ścieżkę do celu. Stosując różne funkcje f(n), otrzymujemy różne specyficzne algorytmy, które omówimy.
