Nie są znane wielomianowe algorytmy rozwiązujące ten problem. Używając programowania dynamicznego jest algorytm O(2^n * n^2).
Zasada działania dynamika
Jak sama nazwa wskazuje bedzięmy tą drogę konstruować z czasem działania algorytmu. Musimy mieć jakąś strukturkę, która będzie przechowywała informacje gdzie jesteśmy, długość trasy oraz co już odwiedziliśmy (najlepiej jakaś maska bitowa, lub zwykła tablica dla małych danych).
Wrzucamy do kolejki wszystkie miasta po kolei.
W kolejce odczytujemy tą strukturkę, czyli gdzie jesteśmy, etc. Bierzemy wszystkich sąsiadów (nieodwiedzonych) tego miasta i wrzucamy znowu do kolejki modyfikując oczywiście odwiedzonych, dł trasy, oraz ostatnie miasto.
Pozdrawiam
)
