Zadanie z rozmowy rekrutacyjnej

0

Hej!

Mam problem, chciałbym napisać program który będzię zwracał z podanej listy 10 par miast z połączeniem kolejowym możliwe kombinacje dla przejazdu z 5 miastami pod warunkiem, że one się nie powtarzają. W jaki sposób mogę to ugryźć.

5

No to musisz znaleźć ścieżkę Hamiltona o długości 5 w grafie skierowanym. Co ciekawe już samo stwierdzenie czy taka ścieżka istnieje w grafie jest problemem NP-zupełnym. No ale tutaj masz E=10 czyli V<10 to każdy głupi brut nawet zadziała bo przecież nawet n! nie jest tu takie straszne.

A jak to zrobić? Możesz np. brać kolejne wariacje bez powtórzeń ze zbioru wierzchołków i sprawdzać czy taka ścieżka w grafie istnieje (wariacje a nie kombinacje, bo zakładam że podane na wejściu krawędzie są skierowane)

0

Możesz użyć algorytmu z nawrotami opartego na DFS. Różnica w stosunku do DFS jest taka, że po odwiedzeniu wierzchołka docelowego możesz powtórnie go odwiedzić, ale z innego wierzchołka źródłowego. (Czytaj: po odwiedzeniu wierzchołka i wszystkich jego krawędzi wychodzących usuwasz wierzchołek z aktualnego zbioru visited). Jest to oczywiście podejście brute force.

1 użytkowników online, w tym zalogowanych: 0, gości: 1