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.

Przykład:
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: