headerphoto

Algorytmy z powrotami - Przykładowe zastosowania algorytmów z powrotami

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.