Skierowany graf acykliczny
Z Wikipedii
Skierowany graf acykliczny (dag – z ang. directed acyclic graph) to graf skierowany, w którym nie ma cykli. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych.
Np. jeśli chcemy przedstawić pewne obliczenia za pomocą drzewa, może ono nam się wykładniczo rozrosnąć:
b = a + a c = b + b d = c + c e = d + d f = e + e g = f + f h = g + g
Drzewo dla h ma już 128 liści, operowanie na tej postaci nie jest więc wygodne. Z drugiej strony dla ogólnych grafów skierowanych trudno jest stworzyć algorytm wyliczania wartości wyrażeń, gdyż łatwo jest się zapętlić.
Jeśli skorzystamy ze skierowanych grafów acyklicznych i programowania dynamicznego, otrzymamy wyliczenia (załóżmy że a=10):
h = g + g (brak g, wyliczmy najpierw g)
g = f + f (brak f, wyliczmy najpierw f)
f = e + e (brak e, wyliczmy najpierw e)
e = d + d (brak d, wyliczmy najpierw d)
d = c + c (brak c, wyliczmy najpierw c)
c = b + b (brak b, wyliczmy najpierw b)
b = a + a = 10 + 10 = 20
c = b + b = 20 + 20 = 40
d = c + c = 40 + 40 = 80
e = d + d = 80 + 80 = 160
f = e + e = 160 + 160 = 320
g = f + f = 320 + 320 = 640
h = g + g = 640 + 640 = 1280
Na zasadzie skierowanych grafów acyklicznych działa m.in. algorytm unifikacji, działający w czasie liniowym (a którego wynik przedstawiony jako drzewo ma potencjalnie wykładniczy rozmiar).
