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źć.
Zadanie z rozmowy rekrutacyjnej
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
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)
- Rejestracja: dni
- Ostatnio: dni
- Postów: 1039
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.