Zadanie z rozmowy rekrutacyjnej

Odpowiedz Nowy wątek
2019-06-03 23:30
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źć.

Co już Zrobiłeś, pokaż kod. - lion137 2019-06-03 23:47

Pozostało 580 znaków

2019-06-04 00:20
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)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-06-04 00:22
Edit: tu była głupota, z której się wycofuje :) - nalik 2019-06-04 17:33

Pozostało 580 znaków

2019-06-04 17:46
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.

edytowany 2x, ostatnio: nalik, 2019-06-04 17:52

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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