65. Grafy i metody ich przeszukiwania. Zastosowania.
Definicja
Graf jest zbiorem połączonych ze sobą wierzchołków. Są one podstawowym obiektem
rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda
Eulera.
Grafy dzielimy na:
-
prosty, nieskierowany: jest to uporządkowana para (V, E), gdzie V jest niepustym
zbiorem, zaś E rodziną dwuelementowych podzbiorów zbioru wierzchołków V,
zwanych krawędziami.
-
skierowany, digraf: jest to uporządkowana para (V, A), gdzie V jest zbiorem
wierzchołków, zaś A jest zbiorem uporządkowanych par różnych wierzchołków ze
zbioru V, zwanych krawędziami skierowanymi.
-
mieszany: jest to uporządkowana trójka (V, E, A) zdefiniowana jak wyżej, czyli może
zawierać zarówno krawędzie jak i krawędzie skierowane.
Metody przeszukiwania
Bardzo istotne przy badaniu grafów są algorytmy przeszukiwania, które polegają na
odwiedzaniu wierzchołków w wyznaczonym celu. Może nim być sprawdzenie czy istnieje
połączenie pomiędzy wierzchołkami lub znalezienie najkrótszej drogi pomiędzy nimi.
Podstawowe algorytmy to:
1. BFS (Breadth First Search) - algorytm przeszukiwania wszerz
Algorytm zaczyna od korzenia i odwiedza wszystkie połączone z nim węzły. Następnie
odwiedza węzły połączone z tymi węzłami i tak dalej, aż do odnalezienia celu.
Algorytm BFS:
1. Utwórz kolejkę.
2. Zapisz do kolejki wierzchołek początkowy.
3. Oznacz wierzchołek S jako odwiedzony.
4. Dopóki kolejka jest niepusta wykonuj:
4.1.Pobierz z kolejki wierzchołek i nazwij go S.
4.2.Jeśli S jest poszukiwanym wierzchołkiem końcowym, to
zwróć SUKCES i zakończ algorytm.
4.3.Jeśli S nie jest poszukiwanym wierzchołkiem końcowym, to
zapisz do kolejki wszystkie nieodwiedzone wierzchołki sąsiadujące z S.
5. Zwróć BRAK ROZWIĄZANIA i zakończ algorytm.
Ponieważ trzeba utrzymywać listę węzłów które się już odwiedziło, złożoność pamięciowa
przeszukiwania wszerz wynosi O(V + E), gdzie V to liczba węzłów, a E to liczba krawędzi w
grafie. Z powodu tak dużego zapotrzebowania na pamięć przeszukiwanie wszerz jest
niepraktyczne dla dużych danych.
W najgorszym przypadku przeszukiwanie wszerz musi przebyć wszystkie krawędzie
prowadzące do wszystkich węzłów, więc złożoność czasowa przeszukiwania wszerz wynosi
O(V + E), gdzie V to liczba węzłów, a E to liczba krawędzi w grafie.
Gdy istnieje rozwiązanie, przeszukiwanie wszerz odnajdzie je niezależnie od grafu.
2. DFS (Depth First Search) - algorytm przeszukiwania wgłąb
Przeszukiwanie zaczyna się od korzenia i porusza się w dół do samego końca gałęzi, po
czym wraca się o jeden poziom i próbuje kolejne gałęzie itd.
Algorytm DFS:
1. Utwórz stos.
2. Zapisz do stosu wierzchołek początkowy.
3. Oznacz wierzchołek S jako odwiedzony.
4. Dopóki stos jest niepuste wykonuj:
4.1.Pobierz ze stosu wierzchołek i nazwij go S.
4.2.Jeśli S jest poszukiwanym wierzchołkiem końcowym, to
zwróć SUKCES i zakończ algorytm.
4.3.Jeśli S nie jest poszukiwanym wierzchołkiem końcowym, to
dodaj do stosu wszystkie nieodwiedzone wierzchołki sąsiadujące z S.
5. Zwróć BRAK ROZWIĄZANIA i zakończ algorytm.
Złożoność pamięciowa przeszukiwania wgłąb w przypadku drzewa jest o wiele mniejsza niż
przeszukiwania wszerz, gdyż algorytm w każdym momencie wymaga zapamiętania tylko
ścieżki od korzenia do bieżącego węzła, podczas gdy przeszukiwanie wszerz wymaga
zapamiętywania wszystkich węzłów w danej odległości od korzenia, co zwykle rośnie
wykładniczo w funkcji długości ścieżki.
Złożoność czasowa jest taka sama jest w przypadku BFS, czyli O(V+E).
Algorytm jest zupełny (czyli znajduje rozwiązanie lub informuje, że ono nie istnieje) dla
drzew skończonych. Grafy skończone wymagają oznaczania już odwiedzonych
wierzchołków. Dla grafów nieskończonych nie jest zupełny.
Zastosowania
Kiedy rozwój informatyki pozwolił na reprezentowanie grafów za pomocą komputera,
okazało się, że algorytmy na nich oparte znajdują wiele praktycznych zastosowań. Szczególny
rodzaj grafów zwanych drzewami okazał się przydatny do reprezentacji hierarchii.
Przedstawione na rysunku obok drzewo binarne może opisywać np. mistrzostwa sportowe czy
drzewo genealogiczne, a po dodaniu etykiet może służyć np. do tworzenia kodów Huffmana,
do opisu rozwoju populacji bakterii w laboratorium albo niedeterministycznego automatu
skończonego.
Kiedy komputery stały się powszechne okazało się, że grafy można zastosować w
wielu problemach. Jako graf przedstawiono sieć dróg. Skrzyżowania stały się wierzchołkami
grafu, a ulice jego krawędziami. Potem w podobny sposób przedstawiono sieci pomieszczeń i
korytarzy w budynkach. Taka reprezentacja pozwoliła komputerom na poszukiwanie
najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Oprogramowanie oparte
na algorytmach analizujących grafy znalazło zastosowanie w przenośnych urządzeniach PDA
wyposażonych w GPS, które potrafią wskazać kierowcy trasę w nieznanym mieście.
Innym przykładem wykorzystania grafów stały się gry komputerowe, gdzie system
sztucznej inteligencji musiał odszukać najlepszą drogę dla postaci sterowanych przez
program, która pozwoli zaatakować ludzkiego przeciwnika. Sztuczna inteligencja mogła
rozwiązać to zagadnienie tylko dzięki odpowiedniej reprezentacji mapy wirtualnego otoczenia
jako grafu.
Projektanci robotów mobilnych również skorzystali z podobnych algorytmów, aby ich
maszyny mogły bez udziału człowieka odnaleźć trasę w trudnym terenie. Przedstawienie sieci
komputerowych w postaci grafów pozwoliło na stworzenie oprogramowania usprawniającego
trasowanie w Internecie.
Aby zwiększyć wydajność pracy w dużych organizacjach, realizację zlecanych przez
klientów zadań przedstawiono w postaci grafów. Pracownikom odpowiadać mogą
wierzchołki, a przepływ zadań między nimi opisać można za pomocą krawędzi.
Zaprojektowano oprogramowanie pozwalające automatycznie śledzić pracę tak opisanej
organizacji, co miało służyć wzrostowi wydajności. Rozwiązania tego typu znalazły
zastosowanie w działach wsparcia technicznego klientów dużych korporacji.
66. Metody projektowania algorytmów
1. Dziel i rządź
Najważniejszą jej cechą jest to, że algorytm ją wykorzystujący dzieli problem na
niezależne części i wywołuje siebie rekurencyjnie dla tych części. Wyniki uzyskane w
podwywołaniach są wykorzystywane w wyższych wywołaniach, by na końcu otrzymać
wynik.
Metoda pozwala tworzyć algorytmy szybsze niż proste algorytmy iteracyjne – oczywiście
zależy to od zagadnienia.
Podstawowe zasady w metodzie „dziel i rządź” przy dzieleniu problemu to:
● żadna część nie może być większa od całości,
● żadna część nie może być pusta.
Przy zachowaniu powyższych zasad mamy następujące możliwości dzielenia problemu:
● na części, których suma jest równa całemu problemowi,
● na części, których suma jest mniejsza od całego problemu,
● na części, które na siebie zachodzą i suma ich jest większa od problemu (zachowane są
zasady mówiące, że każda część jest niepusta i mniejsza od całości)
Części te nie muszą być sobie równe.
Mamy też dwa przypadki działania takiego algorytmu pod względem czasu działania:
● gdy każde wywołanie funkcji wykonuje stałą ilość pracy; wówczas całkowity czas
działania takiego algorytmu jest liniowy;
● gdy każde wywołanie funkcji wykonuje więcej pracy; wówczas analiza całkowitego
czasu działania jest bardziej złożona.
Bardzo często korzysta się z tej metody przy projektowaniu rozwiązania dla algorytmu
rekurencyjnego min-max. Będzie polegało ono na podzieleniu danych na dwie, możliwie
równe części, znalezienie elementów największego i najmniejszego w każdej z nich, a
następnie ustalenie elementu najmniejszego całego ciągu, przez porównanie wybranych
elementów najmniejszych i ustalenie elementu największego przez porównanie
elementów największych każdej z dwóch części.
2. Programowanie dynamiczne
Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów,
stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą
dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych.
Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to
odkrycie medalem IEEE (ang. medal of honour) w 1979 roku.
Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na
podproblemy względem kilku parametrów. W odróżnieniu od techniki dziel i zwyciężaj
podproblemy w programowaniu dynamicznym nie są na ogół rozłączne, ale musi je
cechować własność optymalnej podstruktury. Zagadnienia odpowiednie dla
programowania dynamicznego cechuje również to, że zastosowanie do nich metody
siłowej (ang. brute force) prowadzi do ponadwielomianowej liczby rozwiązań
podproblemów, podczas gdy sama liczba różnych podproblemów jest wielomianowa.
Zazwyczaj jednym z parametrów definiujących podproblemy jest liczba elementów
znajdujących się w rozpatrywanym problemie, drugim jest pewna wartość liczbowa,
zmieniająca się w zakresie od 0 do największej stałej występującej w problemie. Możliwe
są jednak bardziej skomplikowane dobory parametrów, a także większa ich liczba.
Ponieważ jednak uzyskiwany algorytm zazwyczaj wymaga pamięci (i czasu)
proporcjonalnego do iloczynu maksymalnych wartości wszystkich parametrów,
stosowanie większej ilości parametrów niż 3-4 rzadko bywa praktyczne.
Klucz do zaprojektowania algorytmu tą techniką leży w znalezieniu równania
rekurencyjnego opisującego optymalną wartość funkcji celu dla danego problemu jako
funkcji optymalnych wartości funkcji celu dla podproblemów o mniejszych rozmiarach.
Programowanie dynamiczne znajduje optymalną wartość funkcji celu dla całego
zagadnienia rozwiązując podproblemy od najmniejszego do największego i zapisując
optymalne wartości w tablicy. Pozwala to zastąpić wywołania rekurencyjne odwołaniami
do odpowiednich komórek wspomnianej tablicy i gwarantuje, że każdy podproblem jest
rozwiązywany tylko raz. Rozwiązanie ostatniego z rozpatrywanych podproblemów jest na
ogół wartością rozwiązania zadanego zagadnienia.
Niejednokrotnie stosowanie techniki programowania dynamicznego daje w rezultacie
algorytm pseudowielomianowy. Programowanie dynamiczne jest jedną z bardziej
skutecznych technik rozwiązywania problemów NP-trudnych. Niejednokrotnie może być
z sukcesem stosowana do względnie dużych przypadków problemów wejściowych, o ile
stałe występujące w problemie są stosunkowo nieduże. Na przykład, w przypadku
dyskretnego zagadnienia plecakowego jako parametry dynamiczne w metodzie
programowania dynamicznego należy przyjąć rozmiar kolejno rozpatrywanych
podzbiorów elementów oraz rozmiar plecaka, zmieniający się od 0 do wartości B danej w
problemie.
Programowanie dynamiczne może być również wykorzystywane jako alternatywna
metoda rozwiązywania problemów zaliczanych do klasy P, o ile złożoność algorytmu
wielomianowego nie jest satysfakcjonująca, a w praktyce, nawet dla dużych instancji
problemu, wartości liczbowe występujące w problemie są niewielkie.
3. Algorytm zachłanny
Jest to algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje
zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania
częściowego. Innymi słowy algorytm zachłanny nie patrzy czy w kolejnych krokach jest
sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on
wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie
podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą
zachłanną ma charakter optymalizacyjny. W dziedzinie sztucznej inteligencji zachłanna
odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".
Nie istnieje ogólna metoda dowodzenia, czy dla danego problemu rozwiązanie zachłanne
(zawsze) odnajduje poprawny (i optymalny) wynik. Istnieją jednak stosujące się do
samego problemu kryteria, pozwalające sądzić, iż dla owego problemu istnieje
rozwiązanie zachłanne.
Dany jest problem znalezienia trasy podróży z Madrytu do Moskwy. Można na niego
spojrzeć jako problem z dziedziny teorii grafów – jeżeli z wierzchołkami grafu utożsami
się punkty podróży (miasta, lotniska, stacje kolejowe, skrzyżowania dróg itp.) a z
krawędziami możliwe trasy przebiegu (autostrady, trasy przelotu samolotów, przejazdu
pociągów itp.), z wagami odpowiadającymi kosztom podróży (odległości, ceny biletów
itp.) to zadanie sprowadza się do odnalezienia minimalnej ścieżki łączącej wierzchołki
opowiadające Madrytowi i Moskwie, a zbiór wszystkich rozwiązań C składa się z
rozwiązań zarówno optymalnych jak i propozycji tras typu Madryt–Rzym–Moskwa czy
nawet tak nieoptymalnych jak Madryt–Rzym–Tel Awiw–Hongkong–Moskwa.
67. Kryteria oceny efektywności algorytmów
Algorytm powinien osiągać efekt końcowy możliwie niskim kosztem. Koszty eksploatacji są
związane z czasem pracy wykonawcy: im bardziej efektywny algorytm, tym mniej czasu
zajmie jego wykonanie temu samemu wykonawcy. Efektywność algorytmów wyraża się za
pomocą pojęcia złożoności obliczeniowej; w najprostszym ujęciu charakteryzuje ona
pracochłonność wykonania jako funkcję ilości danych wejściowych. Niestety — często
algorytmy bardziej efektywne są trudniejsze w realizacji, tym samym więcej czasu musi im
poświęcić projektant i programista.
Analizy algorytmów używa się po to, by:
● porównywać różne algorytmy wykonujące te same zadania,
● przewidywać wydajność algorytmów w nowym środowisku,
● ustalać wartości parametrów algorytmów.
Analiza algorytmów poszukuje policzalnych i tym samym porównywalnych zależności
między danymi wejściowymi i czasem wykonania algorytmów na nich.
Dwa najważniejsze kryteria oceny efektywności algorytmów to:
-
czas działania,
-
pamięć.
Zależą one od:
● konstrukcji algorytmu,
● rodzaju danych wejściowych,
● wielkości danych wejściowych.
To co można z pewnością zmierzyć to wielkość danych wejściowych. Stąd czas działania i
zużycie pamięci określa się względem tej wielkości. Przyjęło się określać wielkość danych
wejściowych przez n. Czasami jednak może ona zależeć nie tylko od n, ale jeszcze od drugiej
liczby: m. W takim przypadku często wyraża się jedną z nich jako funkcję drugiej, żeby
ograniczyć analizę do jednej zmiennej.
Oczywiste jest, że algorytm wykonuje operacje na danych wejściowych. Jednak w analizie
algorytmu bada się dane i operacje abstrakcyjne. To oznacza, że analizuje się takie operacje i
takie dane, jakie występują w teorii matematycznej. Innymi słowy bada się algorytm w
postaci niezależnej od implementacji. Taka analiza teoretyczna, w przeciwieństwie do
empirycznej, może dawać więcej informacji i jest mniej zasobożerna. Podejście to daje
jeszcze możliwość uniwersalnego porównywania algorytmów między sobą. Nie oznacza ono
abstrahowanie od rzeczywistości. Złożoność i rozmiar danych określa się tak jak jest w
rzeczywistości, ale względem teoretycznego modelu danych.
W przypadku złożoności czasowej, z reguły wyróżnimy pewną operację dominującą, a czas
będziemy traktować jako liczbę wykonanych operacji dominujących. W ten sposób nasza
analiza będzie zależna jedynie od algorytmu, a nie od implementacji i sprzętu. W przypadku
sortowania, operacją dominującą jest przeważnie porównanie dwóch elementów, a w
przypadku przeglądania drzewa - jedno przejście w drzewie między wierzchołkami. W
przypadku algorytmów tekstowych operacją dominującą jest porównanie dwóch symboli.
Zazwyczaj określamy pewien parametr n, będący rozmiarem problemu wejściowego i
określamy złożoność jako funkcję T(n), której argumentem jest rozmiar problemu.
Złożoność algorytmu może być rozumiana w sensie złożoności najgorszego przypadku lub
złożoności średniej. Złożoność najgorszego przypadku nazywamy złożonością pesymistyczną
- jest to maksymalna złożoność dla danych tego samego rozmiaru n. W praktyce ważniejsza
może się okazać złożoność średnia lub oczekiwana. W tym przypadku T(n) jest średnią
(oczekiwaną) wartością złożoności dla wszystkich problemów rozmiaru n. Tego typu
złożoność zależy istotnie od tego, jaka się pod tym kryje przestrzeń probabilistyczna danych
wejściowych. Z reguły zakładamy, że wszystkie dane wejściowe tego samego rozmiaru mogą
się pojawić z tym samym prawdopodobieństwem. Jednakże jest to często mało realistyczne
założenie. Przestrzeń probabilistyczna danych wejściowych może być bardzo
skomplikowana. Prowadzić to może do bardzo trudnych analiz.
Algorytmy możemy badać na 2 sposoby:
1. Złożoność praktyczna
Złożoność praktyczna jest funkcją, która dla podanego rozmiaru danych wyznacza dokładną
liczbę elementarnych kroków potrzebnych do wykonania danego algorytmu. Oznaczmy ją
przez T(n).
W praktycznych zastosowaniach każdy algorytm jest wywoływany wielokrotnie, najczęściej
dla różnych danych. W najlepszym przypadku złożoność jest funkcją liniową względem n,
czyli jest proporcjonalna do rozmiaru danych. Taki skrajny przypadek jest bardzo rzadki. Na
drugim końcu leży wariant wybitnie pesymistyczny, zakładający maksymalny koszt
wykonania algorytmu (np. gdy sortując dane otrzymujemy na wejściu dane posortowane
odwrotnie).
2. Złożoność teoretyczna
Złożoność teoretyczna (zwana też klasą algorytmu) określa, jak silnie zależą od siebie:
rozmiar danych i czas wykonania algorytmu - przy założeniu, że ten pierwszy wzrasta
nieograniczenie.
Złożoność teoretyczna jest uniwersalną miarą efektywności.
Podstawowymi funkcjami do mierzenia złożoności algorytmów są notacje: