Mam drzewo (w sensie teorii grafów), takie jak następujący przykład:
Jest to ukierunkowane drzewo z jednym węzłem początkowym (korzeń) i wieloma końcowymi węzłami (liście). Każda krawędź ma przypisaną długość.
Moje pytanie brzmi: jak znaleźć najdłuższą ścieżkę, zaczynając od korzenia i kończąc na którymś z liści? Podejście brutalnej siły polega na sprawdzeniu wszystkich ścieżek liści korzenia i wybraniu ścieżki o maksymalnej długości, ale wolałbym bardziej wydajny algorytm, jeśli taki istnieje.
algorithms
graphs
Grawiton
źródło
źródło
Odpowiedzi:
Ran G. dał wskazówki w kierunku wydajnego algorytmu, choć być może pominął pewne szczegóły. Obliczanie wszystkich ścieżek root-leaf jest rzeczywiście trochę nieefektywne, jeśli wykonujesz pracę w kółko, na przykład, jeśli obliczasz każdą ścieżkę, a następnie obliczasz długość.
Wykonaj następujący algorytm rekurencyjny, zaczynając od, a
LongestPath(root)
otrzymasz to, czego chcesz. Zasadniczo oblicza rekurencyjnie najdłuższą ścieżkę dla każdego poddrzewa. W każdym węźle wymaga to zbudowania nowych ścieżek i zwrócenia najdłuższej.Jest to kombinacja pseudokodu z pewną notacją Haskell, więc mam nadzieję, że jest zrozumiała.
źródło