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: