1 Techniki konstrukcji algorytmówMateusz Pisarek Październik 2009

2 Co to jest algorytm? Algorytm – w matematyce oraz informatyce to skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Algorytm to jednoznaczny przepis przetworzenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.

3 Techniki którymi się zajmiemyProgramowanie dynamiczne Programowanie zachłanne Dziel i zwyciężaj Programowanie z nawrotami

4 Programowanie dynamiczneProgramowanie dynamiczne jest to metoda rozwiązywania problemów (najczęściej optymalizacyjnych to znaczy takich, gdzie trzeba znaleźć najnajlepszą/najmniejszą/największą/itp wartość (czyli optymalną))), w której to problem dzieli się na mniejsze podproblemy, a następnie korzystając z rozwiązanych podproblemów rozwiązujemy problem główny. Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. 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.

5 Programowanie dynamiczneProces projektowania algorytmu opartego na programowaniu dynamicznym można podzielić na cztery etapy. Scharakteryzowanie struktury optymalnego rozwiązania. Rekurencyjne zdefiniowanie kosztu optymalnego rozwiązania. Obliczenie optymalnego kosztu metodą wstępującą. Konstruowanie optymalnego rozwiązania na podstawie wyników wcześniejszych obliczeń.

6 Problem

7 Etap 1: Struktura najszybszego sposobu montażu samochoduWłasność optymalnej podstruktury wykorzystuje się, żeby pokazać, że optymalne rozwiązanie dla problemu można uzyskać z optymalnych rozwiązań dla jego podproblemów.

8 Etap 2: Rozwiązanie rekurencyjnef1[1] := e1 + a1,1 f2[1] := e2 + a2,1 f1[j] := min(f1[j-1] + a1,j; f2[j-1] + t2,j-1 + a1,j) f2[j] := min(f2[j-1] + a2,j; f1[j-1] + t1,j-1 + a2,j) f* := min(f1[n] + x1 ; f2[n] + x2)

9 Etap 3: Obliczanie najkrótszych czasów montażuFASTES-WAY(a, t, e, x, n) f1[1] := e1 + a1,1 f2[1] := e2 + a2,1 for j := 2 to n do if f1[j-1] + a1,j <= f2[j-1] + t2,j-1 + a1,j then f1[j] := f1[j-1] + a1,j l1[j] := 1 else f1[j] := f2[j-1] + t2,j-1 + a1,j l1[j] := 2 if f2[j-1] + a2,j <= f1[j-1] + t1,j-1 + a2,j then f2[j] := f2[j-1] + a2,j l2[j] := 2 f2[j] := f1[j-1] + t1,j-1 + a2,j l2[j] := 1 if f1[n] + x1 <= f2[n] + x2 then f* := f1[n] + x1 l* := 1 f* := f2[n] + x2 l* := 2

10 Etap 4: Konstruowanie najszybszego sposobu montażuPRINT-STATIONS(l,n) i := l* print „linia” i „stanowisko” n for j := n downto 2 do i := li[j] print „linia” i „stanowisko” j-1

11 Programowanie zachłanneAlgorytm zachłanny – 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.

12 Ogólne własności metody zachłannejProblemy, dla których może być zastosowana strategia zachłanna mają dwie cechy charakterystyczne: własność wyboru zachłannego, własność optymalnej podstruktury.

13 Własność wyboru zachłannegoJeżeli wybory "lokalne" są optymalne, to wybór "globalny" (ostateczny) jest optymalny. Różnica między strategią zachłanną a programowaniem dynamicznym polega na tym, że w programowaniu dynamicznym w każdym kroku podejmowane są decyzje, których wybór zależy od rozwiązań podproblemów. W algorytmie zachłannym wybory są podejmowane jako najlepsze (z punktu widzenia zadania) w danej chwili. Wybory podejmowane w algorytmie zachłannym nie są zależne od wyborów przeszłych, w przeciwieństwie do wyborów podejmowanych przy strategii programowania dynamicznego.

14 Własność optymalnej podstrukturyProblem ma własność optymalnej podstruktury, jeżeli optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. Ta własność jest również spełniona dla problemów rozwiązywalnych metodą programowania dynamicznego

15 „Ciągły problem plecakowy”Złodziej rabujący sklep znalazł n przedmiotów; i-ty przedmiot ma wartość ci złotych i waży wi kilogramów, gdzie ci i wi są nieujemnymi liczbami całkowitymi. Dąży on do zabrania jak najwartościowszego łupu, ale do swojego plecaka nie może wziąć więcej niż W kilogramów. Złodziej może dzielić przedmioty (zabrać do plecaka tylko część wybranego przedmiotu). Interesuje nas odpowiedź na pytanie: Jakie przedmioty z puli n wybranych przedmiotów powinien zabrać złodziej, aby łup był największy?

16 „Ciągły problem plecakowy” – przykładPrzedmiot 1 (Substancja 1) o wadze 10 kg i wartości 60 zł (6 zł/kg) Przedmiot 2 (Substancja 2) o wadze 20 kg i wartości 100 zł (5 zł/kg) Przedmiot 3 (Substancja 3) o wadze 30 kg i wartości 120 zł (4 zł/kg) Plecak ma maksymalną pojemność 50 kg. Rozwiązanie: Złodziej wkłada do plecaka : 10 kg Substancji 1 (wartość 60 zł), 20 kg Substancji 2 (wartość 100 zł), 20 kg Substancji 3 (wartość 80 zł) Łączna wartość wynosi: 60 zł zł + 80 zł = 240 zł

17 Czy ciągły problem plecakowy ma własność wyboru zachłannego?Policzyć cenę jednostkową każdego przedmiotu. Zabrać największą możliwą ilość najbardziej wartościowej substancji. Jeżeli zapas tej substancji się wyczerpał, a w plecaku wciąż jest jeszcze wolne miejsce, złodziej wybiera następną pod względem ceny jednostkowej substancję i wypełnia nią plecak. Kroki 2 i 3 są powtarzane do momentu, gdy plecak będzie już pełen. Powyższy algorytm wymaga, aby substancje były posortowane według malejącej ceny jednostkowej. Przy tym założeniu wybór określony w algorytmie ma własność wyboru zachłannego.

18 Czy ciągły problem plecakowy ma własność optymalnej podstruktury?Jeżeli usuniemy z optymalnego ładunku w kilogramów pewnej substancji j, to pozostający ładunek powinien być najwartościowszym ładunkiem o wadze co najwyżej W-w, który złodziej może skompletować z n - 1 oryginalnych substancji, plus wj - w kilogramów substancji j.

19 Problem kasjera ProblemKasjer ma wydać resztę, będącą dowolną kwot między 0,01$ a 0,99$, przy użyciu minimalnej liczby monet. Rozwiązanie oparte na algorytmie zachłannym Najpierw używamy monety o największej dopuszczalnej wartości, redukując w ten sposób problem do wypłacenia mniejszej kwoty. Przykład Aby wydać 0,94 $, kasjer wypłaci: - półdolarówkę (zostawiając do zapłacenia 0,44 $), następnie - ćwierćdolarówkę (zostaje 0,19 $), - dziesięciocentówkę ( zostaje 0,09 $), - pięciocentówkę (zostaje 0,04 $) i w końcu - cztery jednocentówki

20 Dziel i zwyciężaj Metoda "dziel i zwyciężaj" może jedynie zostać zastosowana do problemów o strukturze rekurencyjnej, czyli takich, których podproblemy "wyglądają" tak samo i dadzą się rozwiązać tą samą metodą. Jak sama nazwa wskazuje metoda polega na podzieleniu problemu na kilka mniejszych podproblemów (najczęściej na dwa, pół na pół), osobnym rozwiązaniu tych podproblemów i połączeniu wyników w jedno rozwiązanie całego problemu. Oczywiście podproblemy rozwiązujemy w taki sam sposób (wszystko rekurencyjnie), chyba że są na tyle małe (niepodzielne na mniejsze), że trzeba je "ręcznie" rozwiązać.

21 Sortowanie przez scalanie (ang. merge sort)

22 Sortowanie szybkie (ang.quicksort)

23 Wyszukiwanie binarne

24 Programowanie z nawrotamiAlgorytm polegający na poszukiwaniu rozwiązania wśród wszystkich możliwych rozwiązań w sposób, który gwarantuje, że nie zostanie ono przeoczone, jeśli tylko istnieje. Algorytm wyszukiwania polegający na znajdowaniu wyniku metodą “prób i błędów”, z oznaczaniem niepowodzeń, dzięki czemu te same błędy nie są popełniane dwukrotnie.

25 Problem skoczka szachowego

26 Problem skoczka szachowego1. Ustawiamy skoczka na polu startowym. 2. Wyznaczamy współrzędne dostępnych w danym kroku pól pozostających w obrębie szachownicy (ustalając ich uporządkowaną listę). Odwiedzamy kolejne nieodwiedzone dotąd pole. 3. Powtarzamy to postępowanie budując częściową trasę skoczka. Jeżeli kolejnego ruchu nie da się wykonać, to cofamy się o jeden krok i wiersz i przesuwamy figurę na kolejne dostępne pole. Jeśli takie pole nie istnieje, cofamy się dalej (rekurencja z powrotami). Zbudowanie trasy złożonej z (n^2)-1 ruchów skoczka oznacza znalezienie rozwiązania. 4. Postępowanie można powtarzać do momentu znalezienia pierwszego rozwiązania, albo kontynuować aż skoczek znajdzie wszystkie możliwe rozwiązania z pola startowego.

27 Problem ośmiu hetmanów

28 Problem ośmiu hetmanów

29 Problem ośmiu hetmanów1. Pierwszego hetmana stawiamy na polu a1 (w wierszu 1, kolumnie a). 2. Dla drugiego hetmana szukamy wolnego, t.j. nieatakowanego pola w wierszu 2, będzie to pole c3. 3. Podobnie postępujemy z kolejnymi hetmanami. Jeżeli któregoś hetmana nie da się postawić w kolejnym wierszu, to cofamy się o jeden wiersz i przesuwamy figurę na kolejne wolne pole. Jeśli takie pole nie istnieje, cofamy się dalej (rekurencja z powrotami). Ustawienie na wolnym polu ósmego hetmana oznacza znalezienie rozwiązania. 4. Postępowanie można powtarzać do momentu znalezienia pierwszego rozwiązania, albo kontynuować aż hetman w wierszu 1 przejdzie przez wszystkie pola i wyznaczone zostaną wszystkie możliwe rozwiązania (92, w tym 12 istotnie różnych).

30 Źródła przykładów i rysunkówT. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: „Wprowadzenie do algorytmów” Wikipedia + strony tematyczne

31 Koniec  Dziękuję za uwagę