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 ?
[Algorytmy] DFS (Depth First Search)
-
- 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)
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.
-
- 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)
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.
-
- 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)
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