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.