Modelowanie systemów i procesów transportowyc Nowak Wojciech IPaweł-skonwertowany PDF

Preview

Summary

Download Modelowanie systemów i procesów transportowyc Nowak Wojciech IPaweł-skonwertowany PDF

Description

Politechnika Krakowska im. Tadeusza Kościuszki Wydział Mechaniczny PK Modelowanie systemów i procesów transportowych

Projekt pierwszy Poszukiwanie optymalnej drogi w grafie

WOJCIECH NOWAK PAWEŁ NOWAK GRUPA 41T1

1. Dane początkowe Ilość wierzchołków:10 Ilość krawędzi: 20 Punkt początkowy: X0 Punkt końcowy: X9

2. Metoda Forda Algorytm forda pozwala w sposób bardzo dogodny odnaleźć optymalną drogę w grafie. Można go podzielić na etapy. Etap 1. Określenie optymalnej wartości drogi w grafie. Krok 1. Każdemu z wierzchołków grafu x, przyporządkowujemy wielkość λi ograniczającą od góry lub od dołu wartość drogi maksymalnej lub minimalnej. W przypadku minimalizacji zakładamy: λ0 = 0 i λi = ∞ ∀i ≠ 0 W przypadku maksymalizacji: λ0 = 0 i λi = 0 ∀i ≠ 0 Krok 1. Modyfikujemy wartości początkowe λi. Modyfikacja ta polega na poszukiwaniu krawędzi grafu (xi, xj), jeżeli istnieje, przy czym dla drogi minimalnej: λj − λi > c (xi, xj ) dla drogi maksymalnej: λj − λi < c (xi, xj ) Zastępujemy następnie λj przez nową wartość: λj = λi + c (xi, xj ) Jeżeli po pewnej ilości prób zmiany λi nie jest możliwa dalsza ich modyfikacja, wartości przyporządkowane wierzchołkom xi określają drogi ekstremalne pomiędzy wierzchołkiem x0 i wierzchołkiem xi. Etap 2. Identyfikacja drogi optymalnej. Niech λh jest to długość drogi optymalnej łączącej wierzchołek x0 i xh c (x0, xh) = coh Aby zidentyfikować drogę optymalną, analizujemy graf idąc wstecz, tzn. od wierzchołka xh do wierzchołka x0 i zatrzymujemy wierzchołek xij taki, że: λh − λi1 = c (xi1, xh) Następnie zatrzymujemy jako element drogi optymalnej wierzchołek xi2 taki, że: λi1 − λi2 = c (xi1, xi2) Stosując krok po kroku powyższa procedurę otrzymamy w końcu wierzchołek x0 = xik-1 oraz drogę optymalną: μ = (x0, xik, xik−1, ... , xi1, xh)

Obliczanie najkrótszej drogi za pomocą metody Forda X0 X1 X2 X3 X4 X5 X6 X7 X8 X9

0 6 9 7 15 17 15 22 22 24

12 17 33 23 19 21 26 23 26

λ9 = cmin(μ) = 24 24 – 22 = 2 X7 nie należy do drogi minimalnej 24 – 17 = 7 X5 należy do drogi minimalnej 24 – 16 = 2 X8 nie należy do drogi minimalnej 24 – 15 = 7 X6 nie należy do drogi minimalnej 17 – 7 = 10 X3 należy do drogi minimalnej 17 – 6 = 11 X1 nie należy do drogi minimalnej 13 – 22 = -9 X7 nie należy do drogi minimalnej 7–6=1 X1 nie należy do drogi minimalnej 7–0=7 X0 należy do drogi minimalnej

Droga najkrótsza obliczona metodą Forda: μ1 = (x0, x3, x5, x9) c(μ1) = 7 + 10 + 7 = 24

30 30 23 31

36

3. Opis metody Dijkstry Etap 1. Tworzymy dwa zbiory wierzchołków Q i S. Początkowo zbiór Q zawiera wszystkie wierzchołki grafu, a zbiór S jest pusty. Dla wszystkich wierzchołków u grafu za wyjątkiem startowego v ustawiamy koszt dojścia d(u) na nieskończoność. Koszt dojścia d(v) zerujemy. Dodatkowo ustawiamy poprzednik p(u) każdego wierzchołka u grafu na niezdefiniowany. Poprzedniki będą wyznaczały w kierunku odwrotnym najkrótsze ścieżki od wierzchołków u do wierzchołka startowego v. Teraz w pętli dopóki zbiór Q zawiera wierzchołki, wykonujemy następujące czynności: Wybieramy ze zbioru Q wierzchołek u o najmniejszym koszcie dojścia d(u). Etap 2. Wybrany wierzchołek u usuwamy ze zbioru Q i dodajemy do zbioru S. Etap 3. Dla każdego sąsiada w wierzchołka u, który jest wciąż w zbiorze Q, sprawdzamy, czy d(w)>d(u) + waga krawędzi u–w. Jeśli tak, to wyznaczamy nowy koszt dojścia do wierzchołka w jako: d(w)←d(u) + waga krawędzi u–w. Następnie wierzchołek u czynimy poprzednikiem w: p(w)←u.

Obliczanie najkrótszej drogi za pomocą metody Dijkstry Krok 1

u d(u) p(u)

0 0 -1

1 ∞ -1

2 ∞ -1

3 ∞ -1

4 ∞ -1

5 ∞ -1

6 ∞ -1

7 ∞ -1

8 ∞ -1

9 ∞ -1

Krok 2

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 ∞ -1

5 ∞ -1

6 ∞ -1

7 ∞ -1

8 ∞ -1

9 ∞ -1

d [ 1 ] > d [ 0 ] + 6 ? – TAK, zatem d [ 1 ] ← d [ 0 ] + 6 = 6. Do p [ 1 ] wpisujemy 0, poprzednik na ścieżce. d [ 2 ] > d [ 0 ] + 9 ? – TAK, zatem d [ 2 ] ← d [ 0 ] + 9 = 9. Do p [ 2] wpisujemy 0, poprzednik na ścieżce. d [ 3 ] > d [ 0 ] + 7 ? – TAK, zatem d [ 3 ] ← d [ 0 ] + 7 = 7. Do p [ 3] wpisujemy 0, poprzednik na ścieżce.

Krok 3

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 ∞ -1

5 17 1

6 15 1

7 ∞ -1

8 23 1

9 ∞ -1

d [ 5 ] > d [ 1 ] + 15 ? – TAK, zatem d [ 5 ] ← d [ 1 ] + 15 = 21. Do p [ 5] wpisujemy 1, czyli poprzednik na ścieżce. d [ 8 ] > d [ 1 ] + 17 ? – TAK, zatem d [ 8 ] ← d [ 1 ] + 17 = 23. Do p [ 8] wpisujemy 1, czyli poprzednik na ścieżce. d [ 6] > d [ 1 ] + 9 ? – TAK, zatem d [ 6 ] ← d [ 1 ] + 9 = 15. Do p [ 6] wpisujemy 1, czyli poprzednik na ścieżce.

Krok 4

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 ∞ -1

5 17 5

6 15 1

7 ∞ -1

8 ∞ 1

d [ 2 ] > d [ 3 ] + 10 ? – NIE, zostawiamy wierzchołek d [ 5 ] > d [ 3 ] + 10 ? – TAK, zatem d [ 6 ] ← d [ 3 ] + 10= 17. Do p [ 6] wpisujemy 1, czyli poprzednik na ścieżce.

9 ∞ -1

Krok 5

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 5

6 15 1

7 ∞ -1

8 ∞ 1

9 ∞ -1

d [ 4 ] > d [ 2] + 6? – TAK, zatem d [ 4 ] ← d [2] + 6 = 15. Do p [ 4] wpisujemy 2, czyli poprzednik na ścieżce.

Krok 6

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 3

6 15 1

7 22 4

8 ∞ 1

9 ∞ -1

d [ 7 ] > d [ 4 ] + 7? – TAK, zatem d [ 7] ← d [ 4] + 7 = 22. Do p [ 7] wpisujemy 4, czyli poprzednik na ścieżce.

Krok 7

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 5

6 15 1

7 22 4

8 23 6

9 24 6

d [ 8 ] > d [ 6 ] + 8? – TAK, zatem d [ 8] ← d [ 6] + 8 = 23. Do p [ 8] wpisujemy 8, czyli poprzednik na ścieżce d [ 9 ] > d [ 9 ] + 21? – TAK, zatem d [ 9] ← d [ 6] + 21 = 36. Do p [ 9] wpisujemy 8, czyli poprzednik na ścieżce

Krok 8

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 3

6 15 1

7 22 4

8 23 5

9 24 5

d [ 8] > d [ 5] + 5? – TAK, zatem d [ 8 ] ← d [ 5] + 5 = 22. Do p [87] wpisujemy 7, czyli poprzednik na ścieżce d [ 9] > d [ 5] + 7? – TAK, zatem d [ 9 ] ← d [ 5] + 7 = 24. Do p [ 9] wpisujemy 7, czyli poprzednik na ścieżce d [ 7] > d [ 5] + 9? – NIE, zostawiamy wierzchołek

Krok 9

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 3

6 15 1

d [ 9] > d [ 7] + 12? – NIE, nic dalej nie robimy z tym wierzchołkiem

7 22 4

8 23 5

9 24 5

Krok 10

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 3

6 15 1

d [ 9 ] > d [ 8 ] + 8? – NIE, nic dalej nie robimy z tym wierzchołkiem

7 22 4

8 23 5

9 24 5

Krok 11

u d(u) p(u)

0 0 -1

1 6 0

2 9 0

3 7 0

4 15 2

5 17 3

6 15 1

7 22 4

8 23 5

Najkrótsza droga algorytmem Dijkstry. Za pomocą tabeli z kroku nr. 11 wyznaczamy minimalne drogi do każdego wierzchołka. ➢ ➢ ➢ ➢ ➢ ➢ ➢ ➢ ➢ ➢

Droga do wierzchołka 0: droga pusta, odległość 0, Droga do wierzchołka 1: 0-1, odległość 6, Droga do wierzchołka 2: 0-2, odległość 9, Droga do wierzchołka 3: 0-3, odległość 7, Droga do wierzchołka 4: 0-2-4, odległość 15, Droga do wierzchołka 5: 0-3-5, odległość 17, Droga do wierzchołka 6: 0-1-6, odległość 15, Droga do wierzchołka 7: 0-2-4-7, odległość 22, Droga do wierzchołka 8: 0-1-5-8, odległość 24, Droga do wierzchołka 9: 0-3-5-9, odległość 24,

Przebieg minimalnej drogi końcowego wierzchołka 9 jest następujący: 0-3-5-9 Droga składa się z 3 krawędzi i ma długość 24 km.

9 24 5

4. Metoda Bellmana-Kalaby Algorytm Bellmana-Kalaby, jest z grupy algorytmów macierzowych. Wykorzystuje on macierzową reprezentację grafu. Wymaga obliczeń potrzebnych do realizacji tej metody. W wyniku działania tego algorytmu otrzymuje się optymalne trasy pomiędzy dowolnymi wierzchołkami grafu, tzn. jednocześnie uzyskuje się dla danego grafu rozwiązania wszystkich zagadnień optymalizacyjnych. Metoda możemy podzielić na dwa etapy: Etap 1. Poszukiwanie optymalnej wartości dróg Procedura pozwalaa na wyliczanie macierzy 𝐷𝑛𝑥𝑛𝑘 dla dowolnego k>1 na podstawie macierzy początkowej 𝐷𝑛𝑥𝑛1. Procedura ta polega na wielokrotnym wykorzystaniu 1 nxn zależności: 𝑑𝑖𝑗 𝑘+1= 𝑚𝑖𝑛ℎ (𝑑𝑖ℎ 𝑘+𝑑 ℎ𝑗 1 ); h=1,2…..,n 𝑑𝑖𝑗 𝑘+1= 𝑚𝑖𝑛ℎ (𝑑ℎ 𝑖 1+𝑑 ℎ𝑗𝑘 ); h=1,2…..,n Stosując jedną z tych procedur otrzymujemy sukcesywne macierze 𝐷𝑘, k > 1 aż do momentu, gdy 𝐷𝑘+1=DK lub używając wskaźników, gdy k+1 = n-1 Element 𝑑𝑖𝑗𝑘 macierzy Dk reprezentuje wartość optymalnej drogi pomiędzy wierzchołkiem xi i xj o długości maksymalnej k, tzn. posiadającej co najwyżej k krawędzi. Aby uzyskać szybciej rozwiązanie, można zastosować procedurę przyspieszoną polegającą na podwajaniu indeksu k, tzn. na podstawie macierzy Dk zamiast wyliczać macierz Dk+1 znajdujemy macierz D2k itd. Uwzględnia się wówczas relację: 𝐷2 𝑘=[𝑖𝑗𝑑 2𝑘]=𝑚𝑖𝑛ℎ (𝑑𝑖ℎ 𝑘+ 𝑑ℎ𝑗 𝑘);ℎ =1,2…,𝑛 Obliczenia są przerwane, gdy stwierdzimy że spełniony jest warunek: 𝐷2𝑘=𝐷𝑘 lub wykorzystując indeksy, gdy 2k ≥ (n-1). Elementy macierzy DK , przy której zadziałało kryterium stopu, zawierają optymalne wartości dróg pomiędzy dowolnymi wierzchołkami grafu, przy czym liczba krawędzi łączących dowolne wierzchołki grafu nie może przekroczyć liczby k. Etap 2. Identyfikacja drogi optymalnej

Dokonując identyfikacji drogi optymalnej ustalamy wierzchołki lub krawędzie, przez które będzie przebiegać Wykorzystuje się do tego celu macierz D1 oraz macierz Dk , przy której zadziałało kryterium stopu. Aby znaleźć najkrótszą trasę, np. pomiędzy wierzchołkami xi oraz xj grafu, należy: - na podstawie macierzy Dk ustalić odległość idąc wstecz od wierzchołka xj do xi. - w oparciu o macierz D1 znaleźć odległość między wierzchołkami xj oraz pewną liczbą h wierzchołków, które są związane z wierzchołkiem xi za pośrednictwem jednej krawędzi, - wykorzystując macierz D1 znajduje się odległości pomiędzy wierzchołkami xh oraz wierzchołkiem xj tzn. wartość drogi (xh, xj). Wśród wierzchołków xh znajduje się te, dla których różnica pomiędzy wartościami (xh, xj) oraz (xi, xj) jest równa dokładnie wartości (xh, xj). 2 2 ℎ 𝑖𝑗 drogi optymalnej 𝑑𝑖 𝑘+𝑑ℎ𝑗1=𝑑 𝑘 - Wierzchołki takie stanowią zbiór wierzchołków przedostatniej –powyższą procedurę należy kontynuować do momentu, gdy dojdzie się do wierzchołka początkowego xo.

d1 0

0 0

1 6

1∞

2 9

0∞

2∞

∞

3∞

3 7∞ ∞

∞

0∞ 5

10

4 ∞

5

13 6∞

0∞

∞

10 ∞

∞

∞

∞

7∞

∞

∞

∞

∞

15 ∞

6∞

∞

∞

∞

∞

∞

7∞

∞

∞

∞

∞

∞

∞

8∞

∞

∞

∞

∞

∞

∞

∞

9∞

∞

∞

∞

∞

∞

∞

∞

0∞

9 0∞

1

2

3

4

5

0

6

9

7

15

17

15 ∞

13

9

2∞

∞

3∞

5

0

24

6

10

0

16

6

14

12 8 0

8

9

23 ∞ 17

20 ∞

19

22

17

28 ∞

7

20

19

0∞

9

5

7

8

21

∞

∞

5∞

∞

∞

∞

∞

6∞

∞

∞

∞

∞

∞

7∞

∞

∞

∞

∞

∞

∞

8∞

∞

∞

∞

∞

∞

∞

∞

9∞

∞

∞

∞

∞

∞

∞

∞

0∞ 0∞

12 0

∞

8 0

0

1

2

3

4

5

6

7

8

9

0

6

9

7

15

17

15

22

22

24

13

9

22

17

20

1∞ 2∞

21

13 ∞

∞

0

8

∞

22

4∞

d4

0

7

0

7

21 ∞ 10

5

0∞

0

∞

17 ∞ ∞

∞

∞

9 ∞

∞

5∞

0∞

8

∞

∞

1∞

7 ∞

9∞

∞

0

0

∞

4∞

d2

18

6 ∞

0∞ ∞

3∞

5

∞

∞

0

24

6

21

38

13

26

25

10

0

16

10

14

19

15

17

28 ∞

7

20

19

0∞

9

5

7

8

16

4∞

∞

∞

∞

0

5∞

∞

∞

∞

∞

6∞

∞

∞

∞

∞

∞

7∞

∞

∞

∞

∞

∞

∞

8∞

∞

∞

∞

∞

∞

∞

∞

9∞

∞

∞

∞

∞

∞

∞

∞

0∞ 0∞

12 0

∞

8 0

d8 0

0

1

2

3

4

5

6

7

8

9

0

6

9

7

15

17

15

22

22

24

13

9

22

17

20

1∞ 2∞

0∞ ∞

3∞

5

∞

∞

0

24

6

21

38

13

26

25

10

0

16

10

14

19

15

17

28 ∞

7

20

19

0∞

9

5

7

8

16

4∞

∞

∞

∞

0

5∞

∞

∞

∞

∞

6∞

∞

∞

∞

∞

∞

7∞

∞

∞

∞

∞

∞

∞

8∞

∞

∞

∞

∞

∞

∞

∞

9∞

∞

∞

∞

∞

∞

∞

∞

0∞ 0∞

12 0

∞

8 0

X5 26-7=19 X6=26-16=10 X7 26-12=14 X8 26-8=18 X1 15-9 =6 X0= 6-6=0 X3 6-5=1 X0 do X3 =7 X3 do X5=10 X5 do X9=10

Droga minimalna pomiędzy X0 a X9 Wynosi 24 Prowadzi przez punkty X0, X3, X5 do X9

Podsumowanie. Algorytm Forda służy do znalezienia optymalnej drogi w grafie, wyróżniamy dwie podstawowe fazy. Określenie optymalnej drogi w grafie oraz identyfikacja drogi optymalnej. W przypadku grafu w którym występują nieujemne wagi oraz krawędzie, właściwą metoda będzie zastosowanie algorytmu Dijkstry. Algorytm Belmana w odróżnieniu od algorytmu Dijkistry, działa poprawnie w w grafie, gdy niektóre krawędzie posiadają ujemne wagi. Dodatkowo algorytm ten rozwiązuje zadania optymalizacyjne. Teorie grafów są związane z informatyką. To w tej dziedzinie mają największe zastosowanie. W informatyce teoria grafów jest używana do projektowania np. struktury stron internetowych. Strona może być przedstawiana jako wierzchołek a hiperłącza do innych stron za pomocą krawędzi grafu. Grafu znalazły zastosowanie również przy badaniach budowy materii. W fizyce mogą posłużyć do symulacji zachowania skomplikowanych struktur atomów. Symulacje takie idealnie odwzorowują zachowanie materii w realnym świecie a to przekłada się na zwiększenie dokładności badań. Graf może również przedstawiać funkcjonowanie układu nerwowego. Za wierzchołki przyjmujemy

niektóre obszary mózgu a połączenia między nimi oznaczymy krawędziami to obraz będzie odpowiadał strukturze nerwów. W naszych rozważaniach, grafy mają szczególne zastosowanie w transporcie i w optymalnym sposobie przemieszczania się. Dzięki algorytmowi o wiele łatwiej znaleźć właściwe, najmniej kosztowne, najbezpieczniejsze połączenia drogowe dla miasta, województwa, kraju lub połączenia międzynarodowe. Wyszukiwanie np.. najszybszej trasy w systemach takich jak np. GPS również nie będzie stanowić problemu jeżeli zastosujemy odpowiedni algorytm. Porównując metody poszukiwania optymalnej drogi w grafie opisanych i wyliczonych w naszym projekcie zauważamy, że najprostszą i najszybszą metodą uzyskania wyniku będzie rozwiązanie za pomocą algorytmu Forda. Metoda Dijkstry wymaga więcej uwagi i czasu jednak w sposób obrazowy krok po kroku pokazuje schemat poszukiwania drogi. Metoda Belmana wymaga użycia aparatu matematycznego i jest metodą skomplikowaną w porównaniu do algorytmu Forda....