Problem cyklu Hamiltona
Cykl hamiltonowski to znane pojęcie w teorii grafów, jest to ścieżka rozpoczynająca się w danym wierzchołku, przechodząca przez każdy kolejny wierzchołek dokładnie jeden raz i kończąca się w "punkcie wyjścia".
Jeśli wierzchołki grafu potraktujemy jako miasta a krawędzie jako drogi między nimi, to problem cyklu Hamiltona sprowadza się do odnalezienia dowolnego połączenia umożliwiającego przejazd przez wszystkie miasta i powrót do domu (do miasta, w którym rozpoczęliśmy podróż). Nie ma tutaj znaczenia długość drogi.
Algorytm z powrotami analizuje zależności między węzłami na każdym poziomie drzewa przestrzeni stanów i odrzuca te ścieżki, które prowadzą do pominięcia któregoś
z wierzchołków w grafie (ominięcia któregoś z miast w czasie podróży).
Zadaniem algorytmu z powrotami jest określenie wszystkich cykli Hamiltona
w danym grafie.