Wykład #6
Sterowanie procesami dyskretnymi
Prowadzący:
Prowadzący:
Prowadzący:
Prowadzący:
Dr Paweł Lajmert
Dr Paweł Lajmert
Pokój: 327
Pokój: 327
Dyżur: Poniedz. 1015
Dyżur: Poniedz. 1015
Wykład #6 - 1
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Wykład #6 - 2
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Dany jest graf skierowany G = (V,E) oraz dla każdej krawędzi
pewna liczba rzeczywista a(u,v) zwana wagą krawędzi (inaczej:
odległość).
Definicja
Drogą (skierowaną) w grafie G = (V,E) nazywać będziemy ciąg
wierzchołków v0,v1,...vp takich, że:
wierzchołków v ,v ,...v takich, że:
Długością drogi nazywać będziemy liczbę:
Wykład #6 - 3
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Jeśli każdy cykl grafu ma dodatnią długość to najkrótsza droga jest zawsze
elementarna (bez powtórzeń wierzchołków)
Jeśli w grafie istnieje cykl o ujemnej długości, to odległość pomiędzy niektórymi
wierzchołkami jest nieokreślona (gdyz zależy od liczby przejść cyklu).
Lecture #6 - 4
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Wykład #6 - 5
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Wykład #6 - 6
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Wykład #6 - 7
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Wykład #6 - 9
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - definicje
Wykład #6 - 13
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Grafy - zastosowania
Grafy - zastosowania
Najkrótsze połączenie między miastami.
Najszybsze połączenie w sieci komputerowej
(przesyłanie meldunków).
Najardziej niezawodne połączenie między
węzłami w sieci (w tym przypadku a(u,v) = -
węzłami w sieci (w tym przypadku a(u,v) = -
logp(u,v), gdzie p(u,v) to prawdopodobieństwo
niezawodnej pracy kanału.
Znajdowanie ścieżki (drogi) krytycznej w
metodach PERT/CPM.
Szeregowanie zadań na linii produkcyjnej.
Wykład #6 - 15
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Metody przeszukiwania grafu
Metody przeszukiwania grafu
Metody globalne - etapy
Metody globalne - etapy
1. Utworzenie (pobranie) listy zadań/czynności do
1. Utworzenie (pobranie) listy zadań/czynności do
wykonania.
2. Utworzenie grafu połączeń.
3. Przeszukiwanie grafu w celu wyznaczenia
optymalnej kolejności wykonywania zadań.
Wykład #6 - 16
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Istotne parametry
Istotne parametry
1. Gęstość grafu
2. Sposób opisu grafu
3. Złożoność obliczeniowa metody
3. Złożoność obliczeniowa metody
(funkcja O)
Wykład #6 - 17
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Gęstość grafu
Gęstość grafu
" Każdy digraf (graf skierowany) prosty
spójny o N wierzchołkach posiada od
(N-1) krawędzi (drzewo rozpinające) do
(N-1) krawędzi (drzewo rozpinające) do
N(N-1) krawędzi (graf pełny)
" Jeżeli liczba krawędzi m << N(N-1) to
mówimy, że graf jest rzadki. W przeciw-
nym wypadku gęsty.
Wykład #6 - 18
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Reprezentacja grafu
Reprezentacja grafu
Wierzchołki  numery 1 do N.
Krawędzie  pary liczb + ewentualnie wagi.
Tablica jednowymiarowa
Element  opis krawędzi (a,b,waga)
Proste, ale bardzo utrudnia wyszukiwanie
Tablica dwuwymiarowa (macierz sąsiedztwa)
Tablica dwuwymiarowa (macierz sąsiedztwa)
Wymiar NxN
Na przecięciu waga połączenia dwóch węzłów lub
"nieskończoność", zera na przekątnej
Wyszukiwanie łatwiejsze ale wciąż złożoność liniowa
Listy sąsiadów
Każdy wierzchołek zawiera listę wierzchołków, z którymi się
łączy (listę łuków z niego wychodzących)
Wyszukiwanie zależy od liczby krawędzi  najbardziej
odpowiednie dla grafów rzadkich
Wykład #6 - 19
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Notacja O
Wykład #6 - 20
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przeszukiwanie grafu
Przeszukiwanie grafu
Problemy:
" jak szybko przejść przez wszystkie wierzchołki
zaczynając od podanego.
" Jaka jest najkrótsza droga od wierzchołka init do
goal
Algorytmy:
" Przeszukiwanie wszerz (Breadth First Search - BFS)
" Przeszukiwanie wgłąb (Depth First Search  DFS)
" Algorytm Dijikstry
Wykład #6 - 21
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przeszukiwanie wszerz
Przeszukiwanie wszerz
Używamy kolejki i zbiorów L i P
Przesuń s do zbioru L
Wstaw do kolejki wszystkie wierzchołki na które
wskazuje s
While(kolejka pełna)
While(kolejka pełna)
Pobierz wierzchołek u z kolejki P i przesuń do L
Wstaw do kolejki wszystkie wierzchołki na które
wskazuje u
Przydatne do wyszukania najkrótszych ścieżek
(przechodzących przez najmniej wierzchołków)
łączących z s
Wykład #6 - 22
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przeszukiwanie wszerz
Przeszukiwanie wszerz
kolejność odwiedzanych węzłów
Wykład #6 - 23
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przeszukiwanie wgłąb
Przeszukiwanie wgłąb
Używamy stosu i zbiorów L i P
Przesuń s do zbioru L
Wstaw na stos wszystkie wierzchołki na które
wskazuje s
While(stos pełny)
While(stos pełny)
Pobierz wierzchołek u ze stosu i przesuń do L
Wstaw na stos wszystkie wierzchołki na które
wskazuje u
Przydatne do liniowego wyszukiwania mostów w
grafie (krawędzi, po usunięciu których graf staje
się niespójny)
Wykład #6 - 24
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przeszukiwanie wgłąb
Przeszukiwanie wgłąb
kolejność odwiedzanych węzłów
Wykład #6 - 25
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Algorytm Dijkstry
Algorytm Dijkstry
" Wykorzystywane zmienne i funkcje:
" Sieć jest dana w postaci macierzy wag
W=[wi,j], gdzie wi,j jest wagą łuku z wierzchołka i do
j
" s, t  wierzchołki startu i celu
" s, t  wierzchołki startu i celu
" dist(v)  funkcja zawierająca odległość od s do v
" final(v) - funkcja informująca, że dist(v) jest drogą
najkrótszą
" prev(v)  funkcja wskazująca na poprzednik w
najkrótszym drzewie rozpinającym
Wykład #6 - 26
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Algorytm
Algorytm
Dijkstry
Dijkstry
Wykład #6 - 27
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przykład przeszukiwania
Przykład przeszukiwania
grafu
grafu
Algorytm Dijkstry
Algorytm Dijkstry
s a b c d t
s a b c d t
s a b c d t
s a b c d t
INICJALIZACJA " " " " "
0
15 " " 9 "
ITERACJA 1
1
15 " " "
9
13 " 11 "
ITERACJA 2
2
13 " "
11
13 " 18
ITERACJA 3
3
" 18
13
48 18
ITERACJA 4
4
48
18
Wykład #6 - 28