[Algorytmy] Znajdowanie najdłuższej drogi w grafie.
-
- Użytkownik
- Posty: 3
- Rejestracja: 8 sie 2012, o 12:23
- Płeć: Mężczyzna
- Lokalizacja: Opole
[Algorytmy] Znajdowanie najdłuższej drogi w grafie.
Czy może ktoś zna takie algorytmy (znajdowania najdłuższej ścieżki w grafie). Jest to jeden z problemów w informatyce, ale są aproksymacyjne algorytmy, które rozwiązują ten problem. Proszę o wymienianie nazw algorytmów, bądź opisanie znanej metody.
Ostatnio zmieniony 8 sie 2012, o 13:12 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
[Algorytmy] Znajdowanie najdłuższej drogi w grafie.
A Dijkstra (tyle że w trochę odwrotny sposób) nie zadziała? Trzebaby dopisać tylko wykrywanie cykli jakby miał się algorytm zapętlić.
-
- Użytkownik
- Posty: 3
- Rejestracja: 8 sie 2012, o 12:23
- Płeć: Mężczyzna
- Lokalizacja: Opole
[Algorytmy] Znajdowanie najdłuższej drogi w grafie.
A. Bjӧrklund i T. Husfeldt, wymyślili też pewien, algorytm tylko nie mogę prawie nic znaleźć na ten temat. Może ktoś coś wie, ma.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Znajdowanie najdłuższej drogi w grafie.
nie zadziała z wielu powodów, problem najdłuższej ścieżki w grafie ma status obliczeniowo trudnego. Można go za to efektywnie rozwiązywać w szczególnych przypadkach, np. dla drzewa, lub grafu skierowanego acyklicznego.bartek118 pisze:A Dijkstra (tyle że w trochę odwrotny sposób) nie zadziała? Trzebaby dopisać tylko wykrywanie cykli jakby miał się algorytm zapętlić.
-
- Użytkownik
- Posty: 3
- Rejestracja: 8 sie 2012, o 12:23
- Płeć: Mężczyzna
- Lokalizacja: Opole
[Algorytmy] Znajdowanie najdłuższej drogi w grafie.
Algorytm ma zadziałać dla grafów hamiltonowskich, posiadających taką ścieżkę.