[Algorytmy] DFS (Depth First Search)

lastsigma
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 6 lis 2011, o 23:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 4 razy

[Algorytmy] DFS (Depth First Search)

Post autor: lastsigma »

Czy jest znany algorytm, który w czasie wielomianowym (ze względu na rozmiar grafu) sprawdzałby, jaka może być maksymalna głębokość rekursji przy odpaleniu algorytmu DFS na jakimś wierzchołku grafu ?
Inaczej: Czy jest algorytm wielomianowy, który dla danego grafu spójnego G i jakiegoś jego wierzchołka A, oblicza maksymalną możliwą wysokość drzewa rozpinającego tego grafu G 'ukorzenionego' w A ?
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] DFS (Depth First Search)

Post autor: Afish »

A czy czasem sam DFS nie działa w czasie wielomianowym, jeżeli zwiedzamy bez powtórzeń?
lastsigma
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 6 lis 2011, o 23:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 4 razy

[Algorytmy] DFS (Depth First Search)

Post autor: lastsigma »

Sam DFS oczywiście działa, ale wyobraźmy sobie, że zapuszczamy DFSa i w każdym wywołaniu funkcji odpalamy się na jakimś z sąsiadów obecnie przetwarzanego wierzchołka. Sęk w tym, że odpalając się na sąsiedzie A możemy otrzymać na koniec inną głębokość rekursji, a odpalając się na sąsiedzie B inną. Teraz cały problem polega na tym, czy możemy jakoś (bez wykładniczego brute force'a) sprawdzić na jakim sąsiedzie powinniśmy się odpalić, żeby otrzymać jak najgłębszą rekursję przy zwiedzaniu całego grafu.
royas
Użytkownik
Użytkownik
Posty: 363
Rejestracja: 24 sie 2012, o 09:27
Płeć: Mężczyzna
Lokalizacja: Cieszyn
Pomógł: 80 razy

[Algorytmy] DFS (Depth First Search)

Post autor: royas »

Twój problem chyba sprowadza się do znalezienia najdłuższej ścieżki o ustalonym początku. Znajdywanie najdłuższej ścieżki w grafie jest NP-zupełne. Ustalenie jednego wierzchołka raczej nie przyśpieszy tego znacząco.
lastsigma
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 6 lis 2011, o 23:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 4 razy

[Algorytmy] DFS (Depth First Search)

Post autor: lastsigma »

Zgoda. Co nie oznacza, że nie da się tego zrobić w czasie wielomianowym. Zapuściłem problem na forum, bo fajnie rozwiązywał mi słynny 3 - SAT, więc myślałem, że ktoś na forum znajdzie coś ciekawego i wspólnie zrobimy jakiś przełom w teorii NP zupełności
royas
Użytkownik
Użytkownik
Posty: 363
Rejestracja: 24 sie 2012, o 09:27
Płeć: Mężczyzna
Lokalizacja: Cieszyn
Pomógł: 80 razy

[Algorytmy] DFS (Depth First Search)

Post autor: royas »

Aha, że przyjdzie ktoś, kto nie wie, że się nie da i zrobi.
ODPOWIEDZ