Невозможно отобразить презентацию
ПрограммированиеПохожие презентации:
Zaawansowane techniki programowania
Sld 9.1.
Zaawansowane techniki programowania 1.Algorytmy typu „dziel-i-rządź”(“conquer and divide”) 2.Algorytmy „zachłanne“ (“żarłoczne”, “greedy”) 3.Algorytmy dynamiczne Sld 9.2.
Algorytmy typu „dziel-i-rządź“ Programowanie typu „dziel-i-rządź" polega na wykorzystaniu podstawowej cechy rekurencji: 1.dekompozycji problemu na pewną skończoną ilość podproblemów tego samego typu, 2.rozwiązania podproblemów, 3.połączeniu częściowych rozwiązań w celu odnalezienia rozwiązania globalnego.
Jeśli oznaczymy problem do rozwiązania przezPb, a rozmiar danych przezN, to zabieg wyżej opisany da się przedstawić za pomocą zapisu: Pb(N)→ Pb(N1) + Pb(N2 ) + ...+ Pb(Nk) + KOMB(N).
Problem „rzędu"N został podzielony nak podproblemów.
Funkcja KOMB(N) nie jest rekurencyjna.
• Technika „dziel-i-rządź" pozwala w wielu przypadkach na zmianę klasy algorytmu (np.
z O(n)do O(log2N) ).•I stnieje grupa zadań, dla których zastosowanie metody „dziel-i-rządź" nie spowoduje przyspieszenia.
Sld 9.3.
Algorytmy typu „dziel-i-rządź“ - 2 Pb0 Pb1 Pbi Pbn Pb1,1 Pb1,k Pbi,1 Pb i,l, Pbn,1 Pbn,s Pb i,1,t Pb i,1,1.
°°° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Sld 9.4.
Quicksort Złożoność O(n log2n) Sld 9.5.
Przeszukiwanie binarne Złożoność O(n log2n) Binarne przeszukiwanie elementu27 w liście⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 2527 37 41 57 69 73 92 94 Sld 9.6.
Znajdowanie zera funkcji metodą połowienia przedziałuabx3x4x2x1yx1 = a+½(b - a);
y > 0;x2 = a+½(x1 - a);
y < 0;x3= x2 +½(x1 - x2 );
y > 0;x4= x2 +½(x3 - x2 );
y > 0;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.x Ilość iteracji i = log2 ((b – a)/Δ;Δ – dokładność obliczeń Sld 8.7.
Algorytmy „zachłanne“ (“żarłoczne“, ”greedy”)
• Cechą szczególną algorytmu „zachlannego" jest to, że w każdym etapie poszukiwania rozwiązania wybiera on opcję lokalnie optymalną.
W zależności od tego doboru, rozwiązanie globalne może być również optymalne, ale nie jest to gwarantowane.yxΔ = 1,2,3,4,5,6xoptyminy min,loc 8.8.
Algorytm zachłanny Algorytm zachłanny (ang.
greedy algorithm) – 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.
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.
8.9.
Przykład Dany jest problem znalezienia trasy podróży z Madrytu do Rzeszowa.
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–Paryż –Berlin – Warszawa - Rzeszow czy nawet tak nieoptymalnych jak Madryt–Rzym–Hongkong–Pekin – Moskwa – Kijów – Lwów - Rzeszow.
9 .10.
Poprawność rozwiązania zachłannego 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.
9 .11.
Własność zachłannego wyboru Za pomocą lokalnie optymalnych (zachłannych) wyborów można uzyskać optymalne rozwiązanie całego zadania.
Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów.
Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.
• Jeżeli problem wykazuje własność optymalnej podstruktury, to można znaleźć rozwiązujący go algorytm dynamiczny, a także zachłanny.9 .12.
Przeszukiwanie grafu
• Przeszukiwanie grafu lub inaczej przechodzenie grafu to czynność polegająca na odwiedzeniu w jakiś usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacji.
• Często podczas przejścia grafu rozwiązujemy już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu.
• Powszechnie stosuje się dwie podstawowe metody przeszukiwania grafów:– przeszukiwanie wszerz (BFS),– przeszukiwanie w głąb (DFS).9 .13.
Przeszukiwanie wszerz
• Przeszukiwanie wszerz (ang.
Breadth-first search, w skrócie BFS) – jeden z najprostszych algorytmów przeszukiwania grafu.
• Przechodzenie grafu rozpoczyna się od zadanego wierzchołkas i polega na odwiedzeniu wszystkich osiągalnych z niego wierzchołków.
• Wykorzystywany jest do odnajdywania najkrótszej drogi w grafie.
• Wynikiem działania algorytmu jest także drzewo przeszukiwania wszerz o korzeniu ws, zawierające wszystkie wierzchołki do których prowadzi droga zs.
Kolejność odwiedzania węzłów Złożoność czasowa:O(|V|+|E|)9 .14.
Przeszukiwanie wszerz9 .15.
Przeszukiwanie w głąb Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka.
Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzony.
Kolejność odwiedzania węzłów Złożoność czasowa:O(|V|+|E|) 9 .16.
Przechodzenie drzewa Istnieje 6 sposobów przejścia drzewa binarnego: VLR, LVR, LRV, VRL, RVL, RLV, gdzie: Visit - "odwiedź" węzeł, Left - idź w lewo, Right - idź w prawo.
Wyróżnia się 3 pierwsze:
• VLR - pre-order, przejście wzdłużne
• LVR - in-order, przejście poprzeczne
• LRV - post-order, przejście wsteczne
• W przypadku gdy dane drzewo jest binarnym drzewem AST przejścia określa się również:
• pre-order - prefiksowym, gdyż wynik odwiedzania poszczególnych węzłów jest trawestacją wyrażenia zawartego w strukturze AST do postaci przedrostkowej (notacji Łukasiewicza)
• in-order - infiksowym, gdyż trawestuje wyrażenie do postaci wrostkowej
• post-order - postfiksowym, gdyż trawestuje wyrażenie do postaci przyrostkowej (odwrotnej notacji polskiej)9 .17.
Podstawowe algorytmy odwiedzają węzły w następującej kolejności:
• pre-order: F, B, A, D, C, E, G, I, H
• post-order: A, C, E, D, B, H, I, G, F
• in-order: A, B, C, D, E, F, G, H, I
• Algorytm Prima – algorytm zachłanny wyznaczający tzw.
minimalne drzewo rozpinające (MDR).
• Mając do dyspozycji graf G = (V, E) nieskierowany i spójny, tzn.
taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E' zbioru krawędziE , dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E' jest najmniejsza możliwa.
• Algorytm został wynaleziony w 1930 przez czeskiego matematyka Vojtěcha Jarníka, a następnie odkryty na nowo przez informatyka Roberta C.
Prima w 1957 oraz niezależnie przez Edsgera Dijkstrę w 1959.
Z tego powodu algorytm nazywany jest również czasami algorytmem Dijkstry–Prima, algorytmem DJP, algorytmem Jarníka, albo algorytmem Prima–Jarníka.
9.18.
Algorytm Prima 9.19.
Przekroj grafu Przekrojem w grafie G, oznaczanym przez (S1, S2) nazywamy zbior krawędzi, ktorych jeden koniec nalezy do S1 a drugi do S2: {S1, S2} = {{i, j}: i∈ S1, j∈ S2}.S1S2 9.20.
Drzewo rozpinające (MDR).
Niech T bedzie drzewem rozpinajacym grafu.
Wtedy 1.
Dla kazdej krawędzi {k, l}∉ T istnieje w T jedyna droga od k do l.
Krawedz {k, l} łacznie z ta droga tworza cykl.
2.
Jesli z drzewa T usunie sie dowolna krawedz {i, j} to drzewo T rozpada sie na dwa rozłaczne podgrafy.
Krawędzie grafu G, ktorych konce znajduja sie w roznych podgrafach tworza przekroj.S1S2lkij9 .21.
Przekroj drzewaS1S2 9.22.
Twierdzenie Drzewo rozpinajace T* jest minimalne wtedy i tylkowtedy, gdy spełniony jest nastepujcy warunek:
• Dla kazdej krawedzi {i, j}∈ T* jest spełniona nierowność:cij ckl, gdzie {k, l} jest dowolna krawedzia nalezaca do przekroju otrzymanego z drzewa T* przez usuniecie z niego krawedzi {i, j}.
9.23.
Twierdzenie Drzewo rozpinajace T* jest minimalnym drzewem rozpinajacym wtedy i tylko wtedy, gdy jest spełniony nastepujacy warunek:
• Dla kazdej krawedzi {k, l} grafu G nie nalezacej do T* ({k, l}∉ T* ) prawdziwa jest nierownośćcij ckl, gdzie {i, j} jest dowolna krawedzia drogi łaczacej wezły k oraz l w T*.
9.24.
Schemat działania Algorytmu Prima 1.Utwórz drzewo zawierające jeden wierzchołek, dowolnie wybrany z grafu.
2.Powtarzaj, dopóki drzewo nie obejmuje wszystkich wierzchołków grafu: - wśród nieprzetworzonych wierzchołków (spoza obecnego MDR) wybierz ten, dla którego koszt dojścia z obecnego MDR jest najmniejszy, - dodaj do obecnego MDR wybrany wierzchołek i krawędź realizującą najmniejszy koszt.
Uwaga: dodawana krawędz nie tworze cyklu z już utworzoną częścą MDR.
9.25.
Minimalne drzewo rozpinające (MDR)32656314213421254865756481212123 ψ(T* ) = 1+2+2+3+1+1+2+1+2+1= 16 9.26.
Złożoność obliczeniowa Algorytmu Prima O(|E| log(|V|)) 9.27.
Dowód poprawności Poprawność algorytmu polega na tym, iż w każdym kroku algorytm konstruuje MDR (za każdym razem wybierane są krawędzie o najmniejszej wadze) dla coraz większego zbioru wierzchołków.
To indukuje stwierdzenie, iż w końcu uzyskiwane jest drzewo rozpinające dla całego grafu G.9 .28.
Algorytm Dijkstry.
Znajdowania najkrótszej ścieżki Algorytm Dijkstry, opracowany przez holenderskiego informatyka E.
Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.
Działanie
• Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków.
• Łatwo zmodyfikować go tak, aby szukał wyłącznie (najkrótszej) ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego, bądź transponując tablicę incydencji grafu.
• Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a wszystkimi pozostałymi, wyliczając również koszt przejścia każdej z tych ścieżek.
• Algorytm Dijkstry jest przykładem algorytmu zachłannego.9 .29.
Algorytm Dijkstry
• PrzezS oznaczamy wierzchołek źródłowy,∀ω (i,j) - to waga krawędzi (i,j) w grafie.
1.Stwórz tablicęd odległości od źródła dla wszystkich wierzchołków grafu.
2.Na początkud[S] = 0.
3.Dla wszystkich pozostałych wierzchołkówd[v] =∞ .
4.Utwórz kolejkę priorytetową wszystkich wierzchołków grafu.
Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego .
5.Dopóki kolejka nie jest pusta: - Usuń z kolejki wierzchołeku o najniższym priorytecie (wierzchołek najbliższy źródła, który nie został jeszcze rozważony), - Dla każdego sąsiadav wierzchołkau dokonaj relaksacji poprzezu : jeślid[u]+ω(u,v)< d(v), (poprzezu da się dojść dov szybciej niż dotychczasową ścieżką), tod(v): =d[u] +ω(u,v).
Na końcu tablicad zawiera najkrótsze odległości do wszystkich wierzchołków.
9.30.
Algorytm Dijkstry Ilustracja algorytmu Dijkstry dla znalezienia drogi od węzła początkowego do węzła celu.
Otwarte węzły stanowią "wstępny" zestaw.
Wypełnione są węzły odwiedzane.
Węzły w wszystkich kierunkach różnych są badane w sposób jednolity, pojawiający się jako wavefront .
9.31.
Algorytm Dijkstry 9 .32.
Problem komiwojażera
• Problem komiwojażera (TSP - ang.
travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
• Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jestn miast, które komiwojażer ma odwiedzić, oraz odległość/cena podróży/czas podróży pomiędzy każdą parą miast.
Celem jest znalezienie najkrótszej/najtańszej/najszybszej drogi łączącej wszystkie miasta zaczynającej się i kończącej się w określonym punkcie.
• Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A.
W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne.
• Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
9.33.
Przykład
• Miasta: Kutno,Warszawa,Poznań,Kraków
• Odległości:KutnoWars PoznańKraków
• Kutno 0130180300
• Warszawa 1300320350
• Poznań 1803200360
• Kraków 3003503600
• Należy znaleźć najkrótszą trasę zaczynającą się np.
z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.
Sld 9.34.
Ogólny problem plecakowy
• Polega on na zapakowaniu do plecaka o ograniczonej pojemności możliwie najbardziej wartościowych rzeczy.
W innych zastosowaniach, może to dotyczyć pakowania walizek, paczek, samochodu, samolotu itp.
• Dane: •n rzeczyR1 R2, ...,Rn, każda w nieograniczonej ilości;
• rzeczRi ważywi i ma wartośćpi.
• maksymalna pojemność plecaka, wynoszącaWmax.
• Wyniki: Ilościni, n2 ,..., nn, poszczególnych rzeczy (mogą być zerowe), których całkowita wagaW nie przekraczaWmax i których sumaryczna wartośćP jest największa.•W = ∑ niwi =n1 w1+ n2 w2 + ...
+nwn≤ Wmax•P = ∑ nipi =n1 p1+ n2 p2 + … + nn pi → max Sld 9.
35.
Algorytm zachłanny dla ogólnego problemu plecakowego W decyzjach ścierają się ze sobą trzy kryteria wyboru kolejnych rzeczy do zapakowania: 1.wybierać najcenniejsze rzeczy, czyli w kolejności nierosnących wartościpt;
2.wybierać rzeczy zajmujące najmniej miejsca, czyli w kolejności niemalejących wagwi 3.wybierać rzeczy najcenniejsze w stosunku do swojej wagi, czyli w kolejności nierosnących wartości ilorazupi/wi.
Sld 9.36.
Przyklad problemu plecakowegoRi123456pi6457102wi623231pi/wi6/64/25/37/2 10/32/1 Kryterian1p1n1w1n2p2n2w2n3p3n3w3n4p4n4w4n5p5n5w5n6p6n6w6?nipi?niwi10 1×7 1×2 7×10 7×30772320 23×2 23×1462330 11×7 11×20 1×2 1×17923Wmax = ∑ niwi ≤ 23 9.37.
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.
9.38.
Programowanie dynamiczne
• 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.
9.39.
Programowanie dynamiczne
• 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.
• 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.Sld9 .40.
Programowanie dynamiczne 1.koncepcja:
• dla danego problemuP stwórz rekurencyjny model jego rozwiązania (wraz z jednoznacznym określeniem przypadków elementarnych);
• stwórz tablicę, w której będzie można zapamiętywać rozwiązania przypadków elementarnych i rozwiązania podproblemów, które zostaną obliczone na ich podstawie;
2.inicjacja:
• wpisz do tablicy wartości numeryczne, odpowiadające przypadkom elementarnym;
3.progresja:
• na podstawie wartości numerycznych wpisanych do tablicy używając formuły rekurencyjnej, oblicz rozwiązanie problemu wyższego rzędu i wpisz je do tablicy;
• postępuj w ten sposób do osiągnięcia pożądanej wartości.Sld9 .41.
Ciąg Fibonacciego fib(4)=5 fib(1)=1 fib(2) = 2 fib(1)=1 fib(0)=1 fib(3)=3 fib(2)=2 fib(1)= 1 fib(5)=8 fib(1)=1 fib(0)=1 fib(3)=3 fib(2)=2 fib(1)= 1 fib(0) = 1, fib(1) = 1, fib(n) = f(n - I) + fib(n - 2) gdzie n ≥ 2;Nf = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Tablicadla zapamiętywania rozwiązania podproblemów:Sld9 .42.
Dwuwymiarowy wzór rekurencyjny.
Do obliczenia wartości P(i, j) potrzebna jest znajomość dwóch sąsiednich komórek: dolnej - P(ij-l) oraz tej znajdującej się z lewej strony - P(i-l,j).
N aturalnym sposobem obliczania wartości P(i,j) będzie posuwanie się „zygzakiem" zaznaczonym na rysunku.Sld9 .43.
Znajdowanie najkrótszej drogi do wyjścia z labiryntu 1.Rozpowszechnianie fali od polaS.
2.Zwinięcie fali od pola wyjściaC1.Sld9 .44.
Własności algorytmów — podsumowanie Najważniejsze własności algorytmów to: 1.Dobra określoność.
2.Ogólność (uniwersalność).
3.Poprawność.
4.Skończoność.
5.Efektywność.Sld9 .45.
Specyfikacja
• Algorytm poprawny rozwiązuje problem, dla którego został opracowany.
Poprawność algorytmu określamy względem specyfikacji problemu.
Każdy algorytm jest opisany w postaci listy kroków, którą poprzedza specyfikacja problemu i względem tej specyfikacji możemy określać wszystkie jego własności, w tym — czy algorytm jest rzeczywiście poprawny.
• Specyfikacja jest ścisłą definicją problemu i składa się z danych, wyników oraz opisu związków zachodzących między nimi.
Zatem specyfikacja to coś więcej niż tylko dane i wyniki, gdyż podane w niej są: dane i warunek, jaki muszą one spełniać, zwany warunkiem początkowym, oraz wyniki i warunek, zwany warunkiem końcowym, jaki muszą one spełniać.
Warunek końcowy określa również związek wyników z danymi.Sld9 .46.
Poprawność
• Algorytm jest poprawny, jeżeli działa zgodnie ze specyfikacją, to znaczy dla każdych poprawnych danych daje odpowiedni wynik.
Algorytm jest całkowicie poprawny względem warunku początkowego i warunku końcowego, gdy dla każdych danych spełniających warunek początkowy obliczenia algorytmu kończą się i wyniki spełniają warunek końcowy.
• Algorytm jest częściowo poprawny, jeśli dla każdych obliczeń, które się kończą, wynik jest poprawny względem warunku początkowego i końcowego.
Weryfikując częściową poprawność nie musimy wykazać, że obliczenia kończą się dla wszystkich poprawnych danych.Sld9 .47.
Dobra określoność
• Dobra określoność opisu algorytmu oznacza, że wszystkie występujące w opisie polecenia i operacje są zrozumiałe dla czytającego i mogą być przez niego wykonane, oraz kolejność działań w algorytmie nie pozostawia żadnej dowolności co do porządku ich wykonywania.
Konsekwencją i sprawdzianem dobrej określoności opisu algorytmu może być możliwość jednoznacznego reprezentowania go w postaci jeszcze bardziej sformalizowanej, np.
w w programie zapisanym w dowolnym języku programowania.Sld9 .48.
Ogólność( uniwersalność) algorytmu
• Ogólnośćczy uniwersalność algorytmu jest jego cechą ściśle związaną z rozwiązywanym problemem: algorytm ma służyć do rozwiązywania klasy zadań, które spełniają specyfikację problemu, a mogą różnić się wartościami danych.
Na przykład, jeśli algorytm jest przeznaczony do rozwiązywania równania kwadratowego, to można go zastosować do rozwiązywania równania o dowolnych współczynnikach, jedynie współczynnik przy kwadracie zmiennej powinien być różny od zera, by rzeczywiście było to równanie kwadratowe.
Podobnie, z każdego algorytmu porządkowanian liczb można korzystać, chcąc znaleźć porządek wśród dowolnychn liczb, nawet jeśli ( n – 1) lub, gdy te liczby są już uporządkowane .Sld9 .49.
Skończoność
• Algorytm można uznać za poprawny, gdy daje rozwiązanie w skończonej liczbie kroków, czyli - gdy jest skuteczny.
• Na skończoność algorytmu mają wpływ przede wszystkim iteracje, zwłaszcza warunkowe instrukcje iteracyjne, które powinny zawierać dobrze określony warunek zakończenia.
Za iteracje uznajemy również ciąg wywołań rekurencyjnych.
• Powodem nie zatrzymywania się algorytmu (programu) może być sprawdzanie spełnienia dokładnych równości wielkości, które w algorytmach mogą przyjmować niedokładne wartości.
Swojego działania może nie kończyć również algorytm, taki jak iteracyjne znajdowanie wartości pierwiastka kwadratowego lub znajdowanie zera funkcji metodą połowienia przedziału, gdy chcemy uzyskać zbyt dużą dokładność wyniku (np.
większą niż wynosi dokładność arytmetyki komputerowej, w której są wykonywane obliczenia).
• Badanie skończoności działania algorytmu może się odbywać w trakcie uruchamiania i testowania programu, gdy chcemy sprawdzić, czy dla danych testowych program zawsze się zatrzymuje.Sld9 .50.
Problem stopu
• Z badaniem skończoności obliczeń jest związany bardzo poważny problem informatyczny, tzw.
problem stopu, który polega na stwierdzeniu, czy istnieje jeden algorytm, który mógłby być użyty do sprawdzania skończoności działania każdego algorytmu, również siebie.
Dla konkretnego algorytmu i jego poprawnych danych, jeśli algorytm kończy działanie, to dobrze, ale jeśli się nie zatrzymuje, to na ogół nie wiemy, kiedy możemy przerwać oczekiwanie na jego zakończenie.
Niestety, problem stopu nie ma rozwiązania, a dokładniej — jest nierozstrzygalny.Sld9 .51.
Efektywność algorytmów
• Nawet jeśli algorytm charakteryzuje się skończonością działania, to może nie być praktyczną metodą rozwiązywania problemu dla dużej liczby danych.
I nie ma wówczas znaczenia, czy posługujemy się w tym celu komputerem i jak szybkim.
W ostatnich latach znacznie wzrosła moc komputerów, ale nastąpił jeszcze większy wzrost rozmiarów problemów, które człowiek chciałby rozwiązywać.
Dlatego nieodłączną cechą dobrego algorytmu stała się jego efektywność, czyli mała złożoność obliczeniowa, gwarantująca jego użyteczność w praktycznych sytuacjach.Sld9 .53.
Literatura 1.P.Wróblewski.
Algorytmy.
Struktury danych i techniki programowania.
Helion.
2001.
2.K.A.Lambert, D.W.Nance, T.L.Naps.
Introduction to Computer Science with C++.
Books/Cole, 2000.
3.M.M.
Syslo.
Algorytmy.
Warszawa, WSP, 1997.
4.Wikipedia.
Grupa, Rok, Kierunek studiów:.................Nazwisko i imię..............№..................
Algorytmy i struktury danych EFEKTY KSZTAŁCENIA - WIEDZA, UMIEJĘTNOŚCI I KOMPETENCJE Grupa, Rok, Kierunek studiów:....................Nazwisko i imię.........................................№..................
Algorytmy i struktury danych EFEKTY KSZTAŁCENIA - WIEDZA, UMIEJĘTNOŚCI I KOMPETENCJE EfektyNarzędziaOcena W01:Wyjaśnić pojęcia dotyczące złożoności obliczeniowej algorytmów._ W02: Podać matematyczny opis struktur grafowych.
OK ! W03: Scharakteryzować metody projektowania
Zaawansowane techniki programowania 1.Algorytmy typu „dziel-i-rządź”(“conquer and divide”) 2.Algorytmy „zachłanne“ (“żarłoczne”, “greedy”) 3.Algorytmy dynamiczne Sld 9.2.
Algorytmy typu „dziel-i-rządź“ Programowanie typu „dziel-i-rządź" polega na wykorzystaniu podstawowej cechy rekurencji: 1.dekompozycji problemu na pewną skończoną ilość podproblemów tego samego typu, 2.rozwiązania podproblemów, 3.połączeniu częściowych rozwiązań w celu odnalezienia rozwiązania globalnego.
Jeśli oznaczymy problem do rozwiązania przezPb, a rozmiar danych przezN, to zabieg wyżej opisany da się przedstawić za pomocą zapisu: Pb(N)→ Pb(N1) + Pb(N2 ) + ...+ Pb(Nk) + KOMB(N).
Problem „rzędu"N został podzielony nak podproblemów.
Funkcja KOMB(N) nie jest rekurencyjna.
• Technika „dziel-i-rządź" pozwala w wielu przypadkach na zmianę klasy algorytmu (np.
z O(n)do O(log2N) ).•I stnieje grupa zadań, dla których zastosowanie metody „dziel-i-rządź" nie spowoduje przyspieszenia.
Sld 9.3.
Algorytmy typu „dziel-i-rządź“ - 2 Pb0 Pb1 Pbi Pbn Pb1,1 Pb1,k Pbi,1 Pb i,l, Pbn,1 Pbn,s Pb i,1,t Pb i,1,1.
°°° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Sld 9.4.
Quicksort Złożoność O(n log2n) Sld 9.5.
Przeszukiwanie binarne Złożoność O(n log2n) Binarne przeszukiwanie elementu27 w liście⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94⇓ 2 4 7 8 8 9 10 11 14 15 17 20 21 2527 37 41 57 69 73 92 94 Sld 9.6.
Znajdowanie zera funkcji metodą połowienia przedziałuabx3x4x2x1yx1 = a+½(b - a);
y > 0;x2 = a+½(x1 - a);
y < 0;x3= x2 +½(x1 - x2 );
y > 0;x4= x2 +½(x3 - x2 );
y > 0;
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.x Ilość iteracji i = log2 ((b – a)/Δ;Δ – dokładność obliczeń Sld 8.7.
Algorytmy „zachłanne“ (“żarłoczne“, ”greedy”)
• Cechą szczególną algorytmu „zachlannego" jest to, że w każdym etapie poszukiwania rozwiązania wybiera on opcję lokalnie optymalną.
W zależności od tego doboru, rozwiązanie globalne może być również optymalne, ale nie jest to gwarantowane.yxΔ = 1,2,3,4,5,6xoptyminy min,loc 8.8.
Algorytm zachłanny Algorytm zachłanny (ang.
greedy algorithm) – 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.
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.
8.9.
Przykład Dany jest problem znalezienia trasy podróży z Madrytu do Rzeszowa.
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–Paryż –Berlin – Warszawa - Rzeszow czy nawet tak nieoptymalnych jak Madryt–Rzym–Hongkong–Pekin – Moskwa – Kijów – Lwów - Rzeszow.
9 .10.
Poprawność rozwiązania zachłannego 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.
9 .11.
Własność zachłannego wyboru Za pomocą lokalnie optymalnych (zachłannych) wyborów można uzyskać optymalne rozwiązanie całego zadania.
Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów.
Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.
• Jeżeli problem wykazuje własność optymalnej podstruktury, to można znaleźć rozwiązujący go algorytm dynamiczny, a także zachłanny.9 .12.
Przeszukiwanie grafu
• Przeszukiwanie grafu lub inaczej przechodzenie grafu to czynność polegająca na odwiedzeniu w jakiś usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacji.
• Często podczas przejścia grafu rozwiązujemy już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu.
• Powszechnie stosuje się dwie podstawowe metody przeszukiwania grafów:– przeszukiwanie wszerz (BFS),– przeszukiwanie w głąb (DFS).9 .13.
Przeszukiwanie wszerz
• Przeszukiwanie wszerz (ang.
Breadth-first search, w skrócie BFS) – jeden z najprostszych algorytmów przeszukiwania grafu.
• Przechodzenie grafu rozpoczyna się od zadanego wierzchołkas i polega na odwiedzeniu wszystkich osiągalnych z niego wierzchołków.
• Wykorzystywany jest do odnajdywania najkrótszej drogi w grafie.
• Wynikiem działania algorytmu jest także drzewo przeszukiwania wszerz o korzeniu ws, zawierające wszystkie wierzchołki do których prowadzi droga zs.
Kolejność odwiedzania węzłów Złożoność czasowa:O(|V|+|E|)9 .14.
Przeszukiwanie wszerz9 .15.
Przeszukiwanie w głąb Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka.
Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzony.
Kolejność odwiedzania węzłów Złożoność czasowa:O(|V|+|E|) 9 .16.
Przechodzenie drzewa Istnieje 6 sposobów przejścia drzewa binarnego: VLR, LVR, LRV, VRL, RVL, RLV, gdzie: Visit - "odwiedź" węzeł, Left - idź w lewo, Right - idź w prawo.
Wyróżnia się 3 pierwsze:
• VLR - pre-order, przejście wzdłużne
• LVR - in-order, przejście poprzeczne
• LRV - post-order, przejście wsteczne
• W przypadku gdy dane drzewo jest binarnym drzewem AST przejścia określa się również:
• pre-order - prefiksowym, gdyż wynik odwiedzania poszczególnych węzłów jest trawestacją wyrażenia zawartego w strukturze AST do postaci przedrostkowej (notacji Łukasiewicza)
• in-order - infiksowym, gdyż trawestuje wyrażenie do postaci wrostkowej
• post-order - postfiksowym, gdyż trawestuje wyrażenie do postaci przyrostkowej (odwrotnej notacji polskiej)9 .17.
Podstawowe algorytmy odwiedzają węzły w następującej kolejności:
• pre-order: F, B, A, D, C, E, G, I, H
• post-order: A, C, E, D, B, H, I, G, F
• in-order: A, B, C, D, E, F, G, H, I
• Algorytm Prima – algorytm zachłanny wyznaczający tzw.
minimalne drzewo rozpinające (MDR).
• Mając do dyspozycji graf G = (V, E) nieskierowany i spójny, tzn.
taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E' zbioru krawędziE , dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E' jest najmniejsza możliwa.
• Algorytm został wynaleziony w 1930 przez czeskiego matematyka Vojtěcha Jarníka, a następnie odkryty na nowo przez informatyka Roberta C.
Prima w 1957 oraz niezależnie przez Edsgera Dijkstrę w 1959.
Z tego powodu algorytm nazywany jest również czasami algorytmem Dijkstry–Prima, algorytmem DJP, algorytmem Jarníka, albo algorytmem Prima–Jarníka.
9.18.
Algorytm Prima 9.19.
Przekroj grafu Przekrojem w grafie G, oznaczanym przez (S1, S2) nazywamy zbior krawędzi, ktorych jeden koniec nalezy do S1 a drugi do S2: {S1, S2} = {{i, j}: i∈ S1, j∈ S2}.S1S2 9.20.
Drzewo rozpinające (MDR).
Niech T bedzie drzewem rozpinajacym grafu.
Wtedy 1.
Dla kazdej krawędzi {k, l}∉ T istnieje w T jedyna droga od k do l.
Krawedz {k, l} łacznie z ta droga tworza cykl.
2.
Jesli z drzewa T usunie sie dowolna krawedz {i, j} to drzewo T rozpada sie na dwa rozłaczne podgrafy.
Krawędzie grafu G, ktorych konce znajduja sie w roznych podgrafach tworza przekroj.S1S2lkij9 .21.
Przekroj drzewaS1S2 9.22.
Twierdzenie Drzewo rozpinajace T* jest minimalne wtedy i tylkowtedy, gdy spełniony jest nastepujcy warunek:
• Dla kazdej krawedzi {i, j}∈ T* jest spełniona nierowność:cij ckl, gdzie {k, l} jest dowolna krawedzia nalezaca do przekroju otrzymanego z drzewa T* przez usuniecie z niego krawedzi {i, j}.
9.23.
Twierdzenie Drzewo rozpinajace T* jest minimalnym drzewem rozpinajacym wtedy i tylko wtedy, gdy jest spełniony nastepujacy warunek:
• Dla kazdej krawedzi {k, l} grafu G nie nalezacej do T* ({k, l}∉ T* ) prawdziwa jest nierownośćcij ckl, gdzie {i, j} jest dowolna krawedzia drogi łaczacej wezły k oraz l w T*.
9.24.
Schemat działania Algorytmu Prima 1.Utwórz drzewo zawierające jeden wierzchołek, dowolnie wybrany z grafu.
2.Powtarzaj, dopóki drzewo nie obejmuje wszystkich wierzchołków grafu: - wśród nieprzetworzonych wierzchołków (spoza obecnego MDR) wybierz ten, dla którego koszt dojścia z obecnego MDR jest najmniejszy, - dodaj do obecnego MDR wybrany wierzchołek i krawędź realizującą najmniejszy koszt.
Uwaga: dodawana krawędz nie tworze cyklu z już utworzoną częścą MDR.
9.25.
Minimalne drzewo rozpinające (MDR)32656314213421254865756481212123 ψ(T* ) = 1+2+2+3+1+1+2+1+2+1= 16 9.26.
Złożoność obliczeniowa Algorytmu Prima O(|E| log(|V|)) 9.27.
Dowód poprawności Poprawność algorytmu polega na tym, iż w każdym kroku algorytm konstruuje MDR (za każdym razem wybierane są krawędzie o najmniejszej wadze) dla coraz większego zbioru wierzchołków.
To indukuje stwierdzenie, iż w końcu uzyskiwane jest drzewo rozpinające dla całego grafu G.9 .28.
Algorytm Dijkstry.
Znajdowania najkrótszej ścieżki Algorytm Dijkstry, opracowany przez holenderskiego informatyka E.
Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.
Działanie
• Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków.
• Łatwo zmodyfikować go tak, aby szukał wyłącznie (najkrótszej) ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego, bądź transponując tablicę incydencji grafu.
• Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a wszystkimi pozostałymi, wyliczając również koszt przejścia każdej z tych ścieżek.
• Algorytm Dijkstry jest przykładem algorytmu zachłannego.9 .29.
Algorytm Dijkstry
• PrzezS oznaczamy wierzchołek źródłowy,∀ω (i,j) - to waga krawędzi (i,j) w grafie.
1.Stwórz tablicęd odległości od źródła dla wszystkich wierzchołków grafu.
2.Na początkud[S] = 0.
3.Dla wszystkich pozostałych wierzchołkówd[v] =∞ .
4.Utwórz kolejkę priorytetową wszystkich wierzchołków grafu.
Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego .
5.Dopóki kolejka nie jest pusta: - Usuń z kolejki wierzchołeku o najniższym priorytecie (wierzchołek najbliższy źródła, który nie został jeszcze rozważony), - Dla każdego sąsiadav wierzchołkau dokonaj relaksacji poprzezu : jeślid[u]+ω(u,v)< d(v), (poprzezu da się dojść dov szybciej niż dotychczasową ścieżką), tod(v): =d[u] +ω(u,v).
Na końcu tablicad zawiera najkrótsze odległości do wszystkich wierzchołków.
9.30.
Algorytm Dijkstry Ilustracja algorytmu Dijkstry dla znalezienia drogi od węzła początkowego do węzła celu.
Otwarte węzły stanowią "wstępny" zestaw.
Wypełnione są węzły odwiedzane.
Węzły w wszystkich kierunkach różnych są badane w sposób jednolity, pojawiający się jako wavefront .
9.31.
Algorytm Dijkstry 9 .32.
Problem komiwojażera
• Problem komiwojażera (TSP - ang.
travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
• Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jestn miast, które komiwojażer ma odwiedzić, oraz odległość/cena podróży/czas podróży pomiędzy każdą parą miast.
Celem jest znalezienie najkrótszej/najtańszej/najszybszej drogi łączącej wszystkie miasta zaczynającej się i kończącej się w określonym punkcie.
• Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A.
W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne.
• Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
9.33.
Przykład
• Miasta: Kutno,Warszawa,Poznań,Kraków
• Odległości:KutnoWars PoznańKraków
• Kutno 0130180300
• Warszawa 1300320350
• Poznań 1803200360
• Kraków 3003503600
• Należy znaleźć najkrótszą trasę zaczynającą się np.
z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.
Sld 9.34.
Ogólny problem plecakowy
• Polega on na zapakowaniu do plecaka o ograniczonej pojemności możliwie najbardziej wartościowych rzeczy.
W innych zastosowaniach, może to dotyczyć pakowania walizek, paczek, samochodu, samolotu itp.
• Dane: •n rzeczyR1 R2, ...,Rn, każda w nieograniczonej ilości;
• rzeczRi ważywi i ma wartośćpi.
• maksymalna pojemność plecaka, wynoszącaWmax.
• Wyniki: Ilościni, n2 ,..., nn, poszczególnych rzeczy (mogą być zerowe), których całkowita wagaW nie przekraczaWmax i których sumaryczna wartośćP jest największa.•W = ∑ niwi =n1 w1+ n2 w2 + ...
+nwn≤ Wmax•P = ∑ nipi =n1 p1+ n2 p2 + … + nn pi → max Sld 9.
35.
Algorytm zachłanny dla ogólnego problemu plecakowego W decyzjach ścierają się ze sobą trzy kryteria wyboru kolejnych rzeczy do zapakowania: 1.wybierać najcenniejsze rzeczy, czyli w kolejności nierosnących wartościpt;
2.wybierać rzeczy zajmujące najmniej miejsca, czyli w kolejności niemalejących wagwi 3.wybierać rzeczy najcenniejsze w stosunku do swojej wagi, czyli w kolejności nierosnących wartości ilorazupi/wi.
Sld 9.36.
Przyklad problemu plecakowegoRi123456pi6457102wi623231pi/wi6/64/25/37/2 10/32/1 Kryterian1p1n1w1n2p2n2w2n3p3n3w3n4p4n4w4n5p5n5w5n6p6n6w6?nipi?niwi10 1×7 1×2 7×10 7×30772320 23×2 23×1462330 11×7 11×20 1×2 1×17923Wmax = ∑ niwi ≤ 23 9.37.
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.
9.38.
Programowanie dynamiczne
• 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.
9.39.
Programowanie dynamiczne
• 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.
• 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.Sld9 .40.
Programowanie dynamiczne 1.koncepcja:
• dla danego problemuP stwórz rekurencyjny model jego rozwiązania (wraz z jednoznacznym określeniem przypadków elementarnych);
• stwórz tablicę, w której będzie można zapamiętywać rozwiązania przypadków elementarnych i rozwiązania podproblemów, które zostaną obliczone na ich podstawie;
2.inicjacja:
• wpisz do tablicy wartości numeryczne, odpowiadające przypadkom elementarnym;
3.progresja:
• na podstawie wartości numerycznych wpisanych do tablicy używając formuły rekurencyjnej, oblicz rozwiązanie problemu wyższego rzędu i wpisz je do tablicy;
• postępuj w ten sposób do osiągnięcia pożądanej wartości.Sld9 .41.
Ciąg Fibonacciego fib(4)=5 fib(1)=1 fib(2) = 2 fib(1)=1 fib(0)=1 fib(3)=3 fib(2)=2 fib(1)= 1 fib(5)=8 fib(1)=1 fib(0)=1 fib(3)=3 fib(2)=2 fib(1)= 1 fib(0) = 1, fib(1) = 1, fib(n) = f(n - I) + fib(n - 2) gdzie n ≥ 2;Nf = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Tablicadla zapamiętywania rozwiązania podproblemów:Sld9 .42.
Dwuwymiarowy wzór rekurencyjny.
Do obliczenia wartości P(i, j) potrzebna jest znajomość dwóch sąsiednich komórek: dolnej - P(ij-l) oraz tej znajdującej się z lewej strony - P(i-l,j).
N aturalnym sposobem obliczania wartości P(i,j) będzie posuwanie się „zygzakiem" zaznaczonym na rysunku.Sld9 .43.
Znajdowanie najkrótszej drogi do wyjścia z labiryntu 1.Rozpowszechnianie fali od polaS.
2.Zwinięcie fali od pola wyjściaC1.Sld9 .44.
Własności algorytmów — podsumowanie Najważniejsze własności algorytmów to: 1.Dobra określoność.
2.Ogólność (uniwersalność).
3.Poprawność.
4.Skończoność.
5.Efektywność.Sld9 .45.
Specyfikacja
• Algorytm poprawny rozwiązuje problem, dla którego został opracowany.
Poprawność algorytmu określamy względem specyfikacji problemu.
Każdy algorytm jest opisany w postaci listy kroków, którą poprzedza specyfikacja problemu i względem tej specyfikacji możemy określać wszystkie jego własności, w tym — czy algorytm jest rzeczywiście poprawny.
• Specyfikacja jest ścisłą definicją problemu i składa się z danych, wyników oraz opisu związków zachodzących między nimi.
Zatem specyfikacja to coś więcej niż tylko dane i wyniki, gdyż podane w niej są: dane i warunek, jaki muszą one spełniać, zwany warunkiem początkowym, oraz wyniki i warunek, zwany warunkiem końcowym, jaki muszą one spełniać.
Warunek końcowy określa również związek wyników z danymi.Sld9 .46.
Poprawność
• Algorytm jest poprawny, jeżeli działa zgodnie ze specyfikacją, to znaczy dla każdych poprawnych danych daje odpowiedni wynik.
Algorytm jest całkowicie poprawny względem warunku początkowego i warunku końcowego, gdy dla każdych danych spełniających warunek początkowy obliczenia algorytmu kończą się i wyniki spełniają warunek końcowy.
• Algorytm jest częściowo poprawny, jeśli dla każdych obliczeń, które się kończą, wynik jest poprawny względem warunku początkowego i końcowego.
Weryfikując częściową poprawność nie musimy wykazać, że obliczenia kończą się dla wszystkich poprawnych danych.Sld9 .47.
Dobra określoność
• Dobra określoność opisu algorytmu oznacza, że wszystkie występujące w opisie polecenia i operacje są zrozumiałe dla czytającego i mogą być przez niego wykonane, oraz kolejność działań w algorytmie nie pozostawia żadnej dowolności co do porządku ich wykonywania.
Konsekwencją i sprawdzianem dobrej określoności opisu algorytmu może być możliwość jednoznacznego reprezentowania go w postaci jeszcze bardziej sformalizowanej, np.
w w programie zapisanym w dowolnym języku programowania.Sld9 .48.
Ogólność( uniwersalność) algorytmu
• Ogólnośćczy uniwersalność algorytmu jest jego cechą ściśle związaną z rozwiązywanym problemem: algorytm ma służyć do rozwiązywania klasy zadań, które spełniają specyfikację problemu, a mogą różnić się wartościami danych.
Na przykład, jeśli algorytm jest przeznaczony do rozwiązywania równania kwadratowego, to można go zastosować do rozwiązywania równania o dowolnych współczynnikach, jedynie współczynnik przy kwadracie zmiennej powinien być różny od zera, by rzeczywiście było to równanie kwadratowe.
Podobnie, z każdego algorytmu porządkowanian liczb można korzystać, chcąc znaleźć porządek wśród dowolnychn liczb, nawet jeśli ( n – 1) lub, gdy te liczby są już uporządkowane .Sld9 .49.
Skończoność
• Algorytm można uznać za poprawny, gdy daje rozwiązanie w skończonej liczbie kroków, czyli - gdy jest skuteczny.
• Na skończoność algorytmu mają wpływ przede wszystkim iteracje, zwłaszcza warunkowe instrukcje iteracyjne, które powinny zawierać dobrze określony warunek zakończenia.
Za iteracje uznajemy również ciąg wywołań rekurencyjnych.
• Powodem nie zatrzymywania się algorytmu (programu) może być sprawdzanie spełnienia dokładnych równości wielkości, które w algorytmach mogą przyjmować niedokładne wartości.
Swojego działania może nie kończyć również algorytm, taki jak iteracyjne znajdowanie wartości pierwiastka kwadratowego lub znajdowanie zera funkcji metodą połowienia przedziału, gdy chcemy uzyskać zbyt dużą dokładność wyniku (np.
większą niż wynosi dokładność arytmetyki komputerowej, w której są wykonywane obliczenia).
• Badanie skończoności działania algorytmu może się odbywać w trakcie uruchamiania i testowania programu, gdy chcemy sprawdzić, czy dla danych testowych program zawsze się zatrzymuje.Sld9 .50.
Problem stopu
• Z badaniem skończoności obliczeń jest związany bardzo poważny problem informatyczny, tzw.
problem stopu, który polega na stwierdzeniu, czy istnieje jeden algorytm, który mógłby być użyty do sprawdzania skończoności działania każdego algorytmu, również siebie.
Dla konkretnego algorytmu i jego poprawnych danych, jeśli algorytm kończy działanie, to dobrze, ale jeśli się nie zatrzymuje, to na ogół nie wiemy, kiedy możemy przerwać oczekiwanie na jego zakończenie.
Niestety, problem stopu nie ma rozwiązania, a dokładniej — jest nierozstrzygalny.Sld9 .51.
Efektywność algorytmów
• Nawet jeśli algorytm charakteryzuje się skończonością działania, to może nie być praktyczną metodą rozwiązywania problemu dla dużej liczby danych.
I nie ma wówczas znaczenia, czy posługujemy się w tym celu komputerem i jak szybkim.
W ostatnich latach znacznie wzrosła moc komputerów, ale nastąpił jeszcze większy wzrost rozmiarów problemów, które człowiek chciałby rozwiązywać.
Dlatego nieodłączną cechą dobrego algorytmu stała się jego efektywność, czyli mała złożoność obliczeniowa, gwarantująca jego użyteczność w praktycznych sytuacjach.Sld9 .53.
Literatura 1.P.Wróblewski.
Algorytmy.
Struktury danych i techniki programowania.
Helion.
2001.
2.K.A.Lambert, D.W.Nance, T.L.Naps.
Introduction to Computer Science with C++.
Books/Cole, 2000.
3.M.M.
Syslo.
Algorytmy.
Warszawa, WSP, 1997.
4.Wikipedia.
Grupa, Rok, Kierunek studiów:.................Nazwisko i imię..............№..................
Algorytmy i struktury danych EFEKTY KSZTAŁCENIA - WIEDZA, UMIEJĘTNOŚCI I KOMPETENCJE Grupa, Rok, Kierunek studiów:....................Nazwisko i imię.........................................№..................
Algorytmy i struktury danych EFEKTY KSZTAŁCENIA - WIEDZA, UMIEJĘTNOŚCI I KOMPETENCJE EfektyNarzędziaOcena W01:Wyjaśnić pojęcia dotyczące złożoności obliczeniowej algorytmów._ W02: Podać matematyczny opis struktur grafowych.
OK ! W03: Scharakteryzować metody projektowania