Muszę napisać program wyszukujący w podanym grafie skierowanym najdłuższą możliwą ścieżkę (względem ilości krawędzi). Przez jakiś czas kombinowałem trochę z algorytmem bfs i tablicą rodziców, ale nic ciekawego mi nie wyszło :( . Ma ktoś pomysł jak to zrobić ?
0
0
Jeżeli graf zawiera cykle to najdłuższej ścieżki nie znajdziesz ponieważ jest ona nieskończona.
Zaś jeżeli nie ma cykli, to użyj Dijkstrę z ujemnymi wagami krawędzi.
0
Wiki ma rozwiązanie:
For instance, for each vertex v in a given DAG, the length of the longest path ending at v may be obtained by the following steps:
- Find a topological ordering of the given DAG.
- For each vertex v of the DAG, in the topological ordering, compute the length of the longest path ending at v by looking at its incoming neighbors and adding one to the maximum length recorded for those neighbors. If v has no incoming neighbors, set the length of the longest path ending at v to zero. In either case, record this number so that later steps of the algorithm can access it.
Once this has been done, the longest path in the whole DAG may be obtained by starting at the vertex v with the largest recorded value, then repeatedly stepping backwards to its incoming neighbor with the largest recorded value, and reversing the sequence of vertices found in this way.
Dokładnie to samo co sam przed chwilą wymyśliłem, więc może nie będę pisał własnymi słowami. Złożoność liniowa.
0
No właśnie problem jest taki (zapomniałem dodać), że graf może posiadać cykle ale przez każdy wierzchołek można przejść tylko raz. Próbowałem przerobić algorytm Dijkstry, tak żeby po prostu zamiast najkrótszych ścieżek promował najdłuższe ale przez cykliczność grafu, to nie działa zawsze :/
0
W takim razie możliwe, że taki problem jest NP-trudny.
http://en.wikipedia.org/wiki/Longest_path_problem
Chociaż w sumie może i nie. Wiki mówi o przypadku ogólnym.
0
Hmm... w sumie nie jestem pewien jeszcze, ale chyba działa sposób z algorytmem Dijkstry, kiedy założę, że wszystkie krawędzie mają taką samą wagę większą od 0. Niestety muszę jeszcze znaleźć najdłuższą ścieżkę względem wag krawędzi i tutaj już Dijkstra nie pomaga (przez cykle).
Ok, jednak nie działał sposób z Dijkstrą i w zasadzie żaden z wymyślonych przeze mnie wariacji algorytmów bfs i dfs :(
Wydaje mi się, że chyba jedyne sensowne rozwiązanie to po prostu metoda losowego błądzenia po grafie (a przynajmniej na nic lepszego nie wpadłem).
W związku z powyższym stwierdziłem, że spróbuję rozwiązać to w ten sposób, że w zadanym wierzchołku będą tworzone obiekty - turyści, którzy losowo będą błądzić po danym grafie z zastrzeżeniem, że każdy wierzchołek mogą odwiedzić tylko raz. Problemem jest to, że nie bardzo wiem kiedy taki algorytm zatrzymać? Domyślam się, że minimum jakie należałoby osiągnąć to punkt, w którym wszystkie osiągalne wierzchołki zostaną odwiedzone przez przynajmniej jednego turystę. Niemniej jednak znacznie lepiej by było, żeby algorytm trwał trochę dłużej, zwiększając prawdopodobieństwo znalezienia tej najdłuższej. Nie wiem jednak jak wybrać ten punkt końcowy algorytmu? help !
0
Ale przecież dostałeś juz informację o tym że to problem NP-zupełny ;] Więc nie ma algorytmu wielomianowego tylko wykładniczy algorytm. Żeby mieć pewność że masz rozwiązanie optymalne musisz sprawdzić wszystkie możliwe ścieżki.