DAA - Multistage Graph
Wielostopniowy wykres G = (V, E) jest grafem skierowanym, na który podzielone są wierzchołki k (gdzie k > 1) liczba rozłącznych podzbiorów S = {s1,s2,…,sk}takie, że krawędź (u, v) jest w E, a następnie u Є s i i v Є s 1 + 1 dla niektórych podzbiorów w partycji i |s1| = |sk| = 1.
Wierzchołek s Є s1 nazywa się source i wierzchołek t Є sk jest nazywany sink.
Gzwykle przyjmuje się, że jest to wykres ważony. Na tym wykresie koszt krawędzi (i, j) jest reprezentowany przez c (i, j) . Stąd koszt ścieżki od źródłas tonąć t to suma kosztów każdej krawędzi na tej ścieżce.
Problem z wykresami wielostopniowymi polega na znalezieniu ścieżki przy minimalnych kosztach ze źródła s tonąć t.
Przykład
Rozważ poniższy przykład, aby zrozumieć koncepcję wykresu wielostopniowego.
Zgodnie ze wzorem musimy obliczyć koszt (i, j) wykonując następujące czynności
Krok 1: Koszt (K-2, j)
W tym kroku trzy węzły (węzły 4, 5, 6) są wybierane jako j. Dlatego na tym etapie mamy trzy opcje wyboru kosztu minimalnego.
Koszt (3, 4) = min {c (4, 7) + Koszt (7, 9), c (4, 8) + Koszt (8, 9)} = 7
Koszt (3, 5) = min {c (5, 7) + Koszt (7, 9), c (5, 8) + Koszt (8, 9)} = 5
Koszt (3, 6) = min {c (6, 7) + Koszt (7, 9), c (6, 8) + Koszt (8, 9)} = 5
Krok-2: Koszt (K-3, j)
Dwa węzły są wybrane jako j, ponieważ na etapie k - 3 = 2 są dwa węzły, 2 i 3. Zatem wartość i = 2 oraz j = 2 i 3.
Koszt (2, 2) = min {c (2, 4) + Koszt (4, 8) + Koszt (8, 9), c (2, 6) +
Koszt (6, 8) + Koszt (8, 9)} = 8
Koszt (2, 3) = {c (3, 4) + Koszt (4, 8) + Koszt (8, 9), c (3, 5) + Koszt (5, 8) + Koszt (8, 9), c (3, 6) + Koszt (6, 8) + Koszt (8, 9)} = 10
Krok 3: Koszt (K-4, j)
Koszt (1, 1) = {c (1, 2) + Koszt (2, 6) + Koszt (6, 8) + Koszt (8, 9), c (1, 3) + Koszt (3, 5) + Koszt (5, 8) + Koszt (8, 9))} = 12
c (1, 3) + Koszt (3, 6) + Koszt (6, 8 + Koszt (8, 9))} = 13
Stąd ścieżka o minimalnym koszcie to 1→ 3→ 5→ 8→ 9.