Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00114 010375 11038340 na godz. na dobę w sumie
Podstawy algorytmów z przykładami w C++ - książka
Podstawy algorytmów z przykładami w C++ - książka
Autor: , Liczba stron: 648
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-429-X Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c++ - programowanie
Porównaj ceny (książka, ebook, audiobook).

Algorytmy są jednym z fundamentów programowania. Prawidłowo zaprojektowany algorytm jest podstawą efektywnego i niezawodnego programu. Opisanie problemu w postaci algorytmu nie jest prostym zadaniem -- wymaga wiedzy z zakresu matematyki, umiejętności oceny złożoności obliczeniowej i znajomości zasad optymalizacji obliczeń. Istnieje wiele metod projektowania algorytmów. Znajomość tych metod znacznie ułatwia analizę zagadnienia i przedstawienie go w postaci zalgorytmizowanej.

Książka 'Podstawy algorytmów z przykładami w C++' to kompletny podręcznik poświęcony tym właśnie zagadnieniom. Przedstawia sposoby podejścia do rozwiązywania zagadnień projektowych, udowadnia, że sporo z nich można zrealizować różnymi metodami, a także uczy, jak dobrać właściwą metodę do postawionego problemu. Materiał podzielony jest na wykłady, zilustrowane pseudokodem przypominającym język C++, co bardzo ułatwia zastosowanie poznanej wiedzy w praktyce.

Wykłady poświęcone algorytmom są uzupełnione dodatkami, zawierającymi kompendium niezbędnej wiedzy z dziedziny matematyki, technik rekurencyjnych i algebry zbiorów.

'Podstawy algorytmów z przykładami w C++' to doskonały podręcznik dla uczniów, studentów i wszystkich, którzy chcą poznać tę dziedzinę wiedzy.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Podstawy algorytmów z przyk³adami w C++ Autorzy: Richard Neapolitan, Kumarss Naimipour T³umaczenie: Bart³omiej Garbacz, Pawe³ Gonera, Artur Szczepaniak, Miko³aj Szczepaniak ISBN: 83-7361-429-X Tytu³ orygina³u: Foundations of Algorithms. Using C++ Pseudocode Format: B5, stron: 648 Algorytmy s¹ jednym z fundamentów programowania. Prawid³owo zaprojektowany algorytm jest podstaw¹ efektywnego i niezawodnego programu. Opisanie problemu w postaci algorytmu nie jest prostym zadaniem — wymaga wiedzy z zakresu matematyki, umiejêtnoġci oceny z³o¿onoġci obliczeniowej i znajomoġci zasad optymalizacji obliczeñ. Istnieje wiele metod projektowania algorytmów. Znajomoġæ tych metod znacznie u³atwia analizê zagadnienia i przedstawienie go w postaci zalgorytmizowanej. Ksi¹¿ka „Podstawy algorytmów z przyk³adami w C++” to kompletny podrêcznik poġwiêcony tym w³aġnie zagadnieniom. Przedstawia sposoby podejġcia do rozwi¹zywania zagadnieñ projektowych, udowadnia, ¿e sporo z nich mo¿na zrealizowaæ ró¿nymi metodami, a tak¿e uczy, jak dobraæ w³aġciw¹ metodê do postawionego problemu. Materia³ podzielony jest na wyk³ady, zilustrowane pseudokodem przypominaj¹cym jêzyk C++, co bardzo u³atwia zastosowanie poznanej wiedzy w praktyce. • Wprowadzenie do projektowania algorytmów • Zastosowanie techniki dziel i zwyciê¿aj • Algorytmy programowania dynamicznego • Analiza z³o¿onoġci obliczeniowej algorytmów na przyk³adzie lgorytmów sortowania i przeszukiwania • Algorytmy z zakresu teorii liczb • Algorytmy kompresji danych i kryptografii • Programowanie równoleg³e Wyk³ady poġwiêcone algorytmom s¹ uzupe³nione dodatkami, zawieraj¹cymi kompendium niezbêdnej wiedzy z dziedziny matematyki, technik rekurencyjnych i algebry zbiorów. „Podstawy algorytmów z przyk³adami w C++” to doskona³y podrêcznik dla uczniów, studentów i wszystkich, którzy chc¹ poznaæ tê dziedzinê wiedzy. Spis treści O Autorach ...................................................h...........................................9 Przedmowa ...................................................h.........................................11 Rozdział 1. Algorytmy — wydajność, analiza i rząd ...................................................h17 1.1. Algorytmy...................................................m...................................................m............ 1.2. Znaczenie opracowywania wydajnych algorytmów...................................................m...... 25 ....... 18 1.2.1. Wyszukiwanie sekwencyjne a wyszukiwanie binarne ........................................... 26 1.2.2. Ciąg Fibonacciego ...................................................m............................................... 28 1.3. Analiza algorytmów...................................................m...................................................m.. .. 33 1.3.1. Analiza złożoności...................................................m............................................... 33 1.3.2. Zastosowanie teorii...................................................m.............................................. 41 1.3.3. Analiza poprawności ...................................................m........................................... 42 1.4. Rząd ...................................................m...................................................m................ ............ 42 1.4.1. Intuicyjne wprowadzenie do problematyki rzędu...................................................m 43 1.4.2. Formalne wprowadzenie do problematyki rzędu ...................................................m 45 1.4.3. Wykorzystanie granic do określenia rzędu...................................................m.......... 56 1.5. Zarys dalszej treści książki ...................................................m............................................59 ........... 60 Ćwiczenia ...................................................m...................................................m................ Rozdział 2. Dziel i zwyciężaj...................................................h..................................65 2.1. Wyszukiwanie binarne ...................................................m...................................................m66 2.2. Sortowanie przez scalanie ...................................................m..............................................71 2.3. Podejście typu dziel i zwyciężaj...................................................m..................................... 77 2.4. Sortowanie szybkie (sortowanie przez podstawienie podziałów)..................................... 78 2.5. Algorytm Strassena mnożenia macierzy ...................................................m........................ 85 2.6. Arytmetyka wielkich liczb całkowitych...................................................m......................... 90 2.6.1. Reprezentacja wielkich liczb całkowitych: dodawmanie i inne operacje wykonywane w czasie liniowym ...................................................m...................... 91 2.6.2. Mnożenie wielkich liczb całkowitych ...................................................m................. 91 2.7. Określanie wartości progowych ...................................................m..................................... 97 2.8. Przeciwwskazania do używania podejścia dziel i zwyciężaj .......................................... 101 ......... 103 Ćwiczenia ...................................................m...................................................m................ Rozdział 3. Programowanie dynamiczne ...................................................h..............111 3.1. Współczynnik dwumianowy ...................................................m........................................ 112 3.2. Algorytm Floyda określania najkrótszej drogi w grafie.................................................. 117 3.3. Programowanie dynamiczne a problemy optymalizacyjne............................................. 125 3.4. Łańcuchowe mnożenie macierzy ...................................................m................................. 127 3.5. Optymalne drzewa wyszukiwania binarnego...................................................m............... 136 3.6. Problem komiwojażera...................................................m................................................. 145 Ćwiczenia ...................................................m...................................................m................ ......... 152 6 Podstawy algorytmów z przykładami w C++ Rozdział 4. Podejście zachłanne ...................................................h.........................157 4.1. Minimalne drzewo rozpinające...................................................m.................................... 161 4.1.1. Algorytm Prima ...................................................m................................................. 163 4.1.2. Algorytm Kruskala ...................................................m............................................ 169 4.1.3. Porównanie algorytmu Prima z algorytmem Kruskala......................................... 173 4.1.4. Dyskusja końcowa ...................................................m............................................. 173 4.2. Algorytm Dijkstry najkrótszych dróg z jednego źródła ................................................. 174 4.3. Szeregowanie...................................................m...................................................m......... ... 177 4.3.1. Minimalizacja całkowitego czasu w systemie...................................................m... 178 4.3.2. Szeregowanie z terminami granicznymi...................................................m............ 180 4.4. Kod Huffmana ...................................................m...................................................m......... . 188 4.4.1. Kody prefiksowe...................................................m................................................ 189 4.4.2. Algorytm Huffmana...................................................m........................................... 190 4.5. Podejście zachłanne a programowanie dynamiczne: problem plecakowy ..................... 194 4.5.1. Podejście zachłanne do problemu plecakowego 0-1 ............................................ 195 4.5.2. Podejście zachłanne do ułamkowego problemu plecakowego............................. 196 4.5.3. Podejście programowania dynamicznego do problemu plecakowego 0-1........... 197 4.5.4. Poprawiona wersja algorytmu programowania dynmamicznego dla problemu plecakowego 0-1 ...................................................m....................... 197 Ćwiczenia ...................................................m...................................................m................ ......... 201 Rozdział 5. Algorytmy z powrotami...................................................h......................207 5.1. Techniki algorytmów z powrotami...................................................m.............................. 208 5.2. Problem n-królowych ...................................................m.................................................. 215 5.3. Zastosowanie algorytmu Monte Carlo do oszacowania wydajności algorytmu z powrotami ...................................................m............................................. 219 5.4. Problem sumy podzbiorów ...................................................m.......................................... 223 5.5. Kolorowanie grafu ...................................................m...................................................m... . 228 5.6. Problem cyklu Hamiltona ...................................................m............................................ 232 5.7. Problem plecakowy 0-1 ...................................................m............................................... 235 5.7.1. Algorytm z powrotami dla problemu plecakowego 0-1 ....................................... 235 5.7.2. Porównanie algorytmu programowania dynamicznemgo Ćwiczenia ...................................................m...................................................m................ z algorytmem z powrotami do rozwiązywania problemu plecakowego 0-1......... 244 ......... 245 Rozdział 6. Metoda podziału i ograniczeń ...................................................h............251 6.1. Ilustracja metody podziału i ograniczeń dla problemu plecakowego 0-1 ...................... 253 6.1.1. Przeszukiwanie wszerz z przycinaniem metodą podziału i ograniczeń ............... 253 6.1.2. Przeszukiwanie typu najpierw najlepszy z przymcinaniem metodą podziału i ograniczeń...................................................m.......................... 258 6.2. Problem komiwojażera ...................................................m................................................ 264 6.3. Wnioskowanie abdukcyjne (diagnozowanie) ...................................................m.............. 272 Ćwiczenia ...................................................m...................................................m................ ......... 281 Rozdział 7. Wprowadzenie do złożoności obliczeniowej: problem sortowania ............285 7.1. Złożoność obliczeniowa ...................................................m.............................................. 286 7.2. Sortowanie przez wstawianie i sortowanie przez wybieranie ........................................ 288 7.3. Dolne ograniczenia dla algorytmów usuwających co najwyżej jedną inwersję dla jednej operacji porównania ...................................................m................................. 294 7.4. Przypomnienie algorytmu sortowania przez scalanie...................................................m.. 297 7.5. Przypomnienie algorytmu szybkiego sortowania...................................................m........ 303 7.6. Sortowanie stogowe...................................................m...................................................m..305 7.6.1. Stogi i podstawowe na nich operacje...................................................m................. 305 7.6.2. Implementacja algorytmu sortowania stogowego ................................................ 309 Spis treści 7 7.7. Zestawienie algorytmów sortowania przez scalanie, sortowania szybkiego i sortowania stogowego...................................................m............................................. 316 7.8. Dolne ograniczenia dla algorytmów sortujących wyłącznie na podstawie operacji porównania kluczy ...................................................m...................................... 317 7.8.1. Drzewa decyzyjne dla algorytmów sortujących ...................................................m 317 7.8.2. Dolne ograniczenia dla najgorszego przypadku ...................................................m 320 7.8.3. Dolne ograniczenia dla średniego przypadku...................................................m.... 323 7.9. Sortowanie przez podział (sortowanie pozycyjne) ...................................................m...... 328 Ćwiczenia ...................................................m...................................................m................ ......... 332 Rozdział 8. Więcej o złożoności obliczeniowej: problem przeszukiwania ...................339 8.1. Dolne ograniczenia dla przeszukiwania wyłącznie na podstawie porównywania wartości kluczy...................................................m................................. 340 8.1.1. Dolne ograniczenia dla najgorszego przypadku ...................................................m 343 8.1.2. Dolne ograniczenia dla średniego przypadku...................................................m.... 345 8.2. Przeszukiwanie przez interpolację...................................................m............................... 351 8.3. Przeszukiwanie w drzewach ...................................................m........................................ 354 8.3.1. Drzewa wyszukiwania binarnego ...................................................m...................... 355 8.3.2. B-drzewa...................................................m...................................................m......... 360 8.4. Mieszanie...................................................m...................................................m........... ....... 361 8.5. Problem wyboru: wprowadzenie metody dyskusji z adwersarzem................................ 367 8.5.1. Znajdowanie największego klucza ...................................................m.................... 367 8.5.2. Znajdowanie zarówno najmniejszego, jak i największego klucza ....................... 369 8.5.3. Znajdowanie drugiego największego klucza ...................................................m..... 376 8.5.4. Znajdowanie k-tego najmniejszego klucza...................................................m........ 381 8.5.5. Algorytm probabilistyczny dla problemu wyboru................................................ 390 ......... 395 Ćwiczenia ...................................................m...................................................m................ Rozdział 9. Złożoność obliczeniowa i trudność problemów: wprowadzenie do teorii o zbiorze NP ...................................................h..401 9.1. Trudność ...................................................m...................................................m............ ....... 402 9.2. Ponowne omówienie zagadnienia rozmiaru danych wejściowych................................. 404 9.3. Trzy główne kategorie problemów...................................................m.............................. 409 9.3.1. Problemy, dla których wynaleziono algorytmy wielomianowe ........................... 409 9.3.2. Problemy, których trudność została udowodniona............................................... 410 9.3.3. Problemy, których trudność nie została udowodnionam, jednak nie udało się znaleźć rozwiązujących je algorytmów wielomianowych................................. 411 9.4. Teoria o zbiorze NP ...................................................m...................................................m. . 411 9.4.1. Zbiory P i NP ...................................................m...................................................m.. 414 9.4.2. Problemy NP-zupełne...................................................m........................................ 419 9.4.3. Problemy NP-trudne, NP-łatwe i NP-równoważne .............................................. 431 9.5. Sposoby rozwiązywania problemów NP-trudnych ...................................................m..... 435 9.5.1. Algorytm przybliżony dla problemu komiwojażera............................................. 436 9.5.2. Przybliżony algorytm dla problemu pakowania ...................................................m 441 Ćwiczenia ...................................................m...................................................m................ ......... 446 Rozdział 10. Algorytmy teorii liczb ...................................................h........................449 10.1. Przegląd teorii liczb...................................................m.................................................... 450 10.1.1. Liczby złożone i liczby pierwsze ...................................................m................... 450 10.1.2. Największy wspólny dzielnik...................................................m......................... 451 10.1.3. Rozkładanie liczb całkowitych na czynniki pierwsze ....................................... 455 10.1.4. Najmniejsza wspólna wielokrotność ...................................................m.............. 457 10.2. Wyznaczanie największego wspólnego dzielnika...................................................m...... 457 10.2.1. Algorytm Euklidesa...................................................m........................................ 458 10.2.2. Rozszerzenie algorytmu Euklidesa...................................................m................. 462 8 Podstawy algorytmów z przykładami w C++ 10.3. Przegląd arytmetyki modularnej...................................................m................................. 465 10.3.1. Teoria grup ...................................................m...................................................m.. 465 10.3.2. Kongruencja modulo n ...................................................m................................... 467 10.3.3. Podgrupy ...................................................m...................................................m..... 473 10.4. Rozwiązywanie modularnych równań liniowych ...................................................m...... 479 10.5. Obliczanie modularnych potęg...................................................m................................... 485 10.6. Znajdowanie wielkich liczb pierwszych ...................................................m.................... 488 10.6.1. Szukanie liczby pierwszej ...................................................m.............................. 488 10.6.2. Sprawdzanie, czy dana liczba całkowita jest liczbą pierwszą........................... 489 10.7. System szyfrowania RSA z publicznym kluczem...................................................m...... 508 10.7.1. Systemy szyfrowania z kluczem publicznym...................................................m. 508 10.7.2. System szyfrowania RSA...................................................m............................... 509 Ćwiczenia ...................................................m...................................................m................ ......... 512 Rozdział 11. Wprowadzenie do algorytmów równoległych..........................................517 11.1. Architektury równoległe...................................................m............................................. 521 11.1.1. Mechanizm sterowania...................................................m................................... 521 11.1.2. Organizacja przestrzeni adresowej ...................................................m................. 522 11.1.3. Sieci łączące ...................................................m...................................................m 524 11.2. Model PRAM ...................................................m...................................................m..........527 11.2.1. Projektowanie algorytmów dla modelu CREW PRAM.................................... 531 11.2.2. Projektowanie algorytmów dla modelu CRCW PRAM.................................... 538 ......... 541 Ćwiczenia ...................................................m...................................................m................ Dodatek A Przegląd niezbędnej wiedzy matematycznej...........................................543 ........ 543 ....... 545 A.1. Notacja...................................................m...................................................m.............. A.2. Funkcje ...................................................m...................................................m.............. A.3. Indukcja matematyczna ...................................................m............................................... 546 A.4. Twierdzenia i lematy ...................................................m...................................................m 553 A.5. Logarytmy...................................................m...................................................m............ ..... 554 A.5.1. Definicja i właściwości logarytmów...................................................m................. 554 A.5.2. Logarytm naturalny...................................................m........................................... 557 A.6. Zbiory ...................................................m...................................................m............... A.7. Permutacje i kombinacje...................................................m.............................................. 560 A.8. Prawdopodobieństwo...................................................m...................................................m 563 A.8.1. Losowość ...................................................m...................................................m....... 569 A.8.2. Wartość oczekiwana ...................................................m......................................... 573 ........ 559 Ćwiczenia ...................................................m...................................................m................ ......... 575 Dodatek B Rozwiązywanie równań rekurencyjnych na potrzeby analizy algorytmów rekurencyjnych ....................................581 B.1. Rozwiązywanie rekurencji za pomocą indukcji ...................................................m.......... 581 B.2. Rozwiązywanie rekurencji z zastosowaniem równań charakterystycznych................... 585 B.2.1. Homogeniczna rekurencja liniowa...................................................m.................... 585 B.2.2. Niehomogeniczna rekurencja liniowa...................................................m............... 594 B.2.3. Zamiana zmiennej (przekształcenie dziedziny) ...................................................m 600 B.3. Rozwiązywanie rekurencji przez podstawianie...................................................m........... 603 B.4. Rozszerzanie wyników dla n będącego potęgą dodatniej stałej b do wyników dla dowolnego n ...................................................m................................... 605 B.5. Dowody twierdzeń...................................................m...................................................m.... 611 Ćwiczenia ...................................................m...................................................m................ ......... 614 Dodatek C Struktury danych dla zbiorów rozłącznych .............................................621 Dodatek D Bibliografia ...................................................h.......................................631 Rozdział 3. Programowanie dynamiczne Jak zapewne Czytelnik pamięta, liczba składników obliczanych przez algorytm typu dziel i zwyciężaj w celu określenia n-tego wyrazu ciągu Fibonacciego (algo- rytm 1.6) jest wykładnicza w stosunku do n. Wynika to z faktu, że podejście typu dziel i zwyciężaj rozwiązuje realizację problemu poprzez jej podział na mniejsze realizacje, a następnie bezpośrednie rozwiązywanie owych mniejszych realizacji. Jak stwierdzono w rozdziale 2., jest to podejście zstępujące. Sprawdza się ono w przy- padku problemów w rodzaju sortowania przez scalanie, gdzie mniejsze instancje nie są ze sobą powiązane. Dzieje się tak, ponieważ każda z nich składa się z tablicy kluczy, które muszą zostać posortowane niezależnie. Jednakże w przypadku pro- blemów takich, jak n-ty wyraz ciągu Fibonacciego, mniejsze instancje są ze sobą powiązane. Przykładowo, zgodnie z tym, co przedstawiono w podrozdziale 1.2, obliczenie piątego wyrazu ciągu Fibonacciego wymaga obliczenia wyrazu trze- ciego i czwartego. Jednak procesy określania czwartego i trzeciego wyrazu są ze sobą związane o tyle, że oba wymagają znajomości wyrazu drugiego. Ze względu na fakt, że algorytm typu dziel i zwyciężaj wykonuje oba procesy niezależnie, drugi wyraz ciągu Fibonacciego jest obliczany wielokrotnie. W przypadku problemów, 112 Podstawy algorytmów z przykładami w C++ w których mniejsze realizacje są ze sobą powiązane, często okazuje się, że algo- rytm typu dziel i zwyciężaj wielokrotnie rozwiązuje te same realizacje i w efekcie jest on bardzo niewydajny. Programowanie dynamiczne (ang. dynamic programming), technika omawiana w niniejszym rozdziale, opiera się na przyjęciu odwrotnego podejścia. Progra- mowanie dynamiczne jest podobne do podejścia typu dziel i zwyciężaj o tyle, że realizacja problemu zostaje podzielona na mniejsze realizacje. Jednak tym razem najpierw są rozwiązywane małe realizacje, a ich wyniki zostają przechowane; póź- niej, kiedy zajdzie taka potrzeba, algorytm może się do nich bezpośrednio odwoły- wać, zamiast obliczać je ponownie. Pojęcie programowanie dynamiczne wywo- dzi się z teorii sterowania i w tym kontekście programowanie oznacza użycie tablicy (tabeli), w ramach której jest konstruowane rozwiązanie. Jak wspomniano w rozdziale 1., wydajny algorytm (algorytm 1.7) obliczania n-tego wyrazu ciągu Fibonacciego jest przykładem programowania dynamicznego. Algorytm ten określa n-ty wyraz ciągu Fibonacciego poprzez konstruowanie po kolei pierwszych n+1 wyrazów w tablicy f indeksowanej od 0 do n. W przypadku algorytmu programowa- nia dynamicznego konstruujemy rozwiązanie „od dołu” tablicy (lub ciągu tablic). Programowanie dynamiczne stanowi więc podejście wstępujące (ang. bottom-up). Niekiedy, jak w przypadku algorytmu 1.7, po opracowaniu algorytmu wykorzy- stującego tablicę (lub ciąg tablic) istnieje możliwość ulepszenia go, tak aby zwolnić wiele niepotrzebnie przydzielonej przestrzeni pamięCciowej. Opracowanie algorytmu programowania dynamicznego polega na wykonaniu na- stępujących działań: 1. Określamy właściwość rekurencyjną, która pozwala znaleźć rozwiąCzanie realizacji problemu. 2. Rozwiązujemy realizację problemu zgodnie z podejściem Cwstępującym, najpierw rozwiązując mniejsze realizacje. W celu zilustrowania tych działań w podrozdziale 3.1 przedstawiono kolejny prosty przykład programowania dynamicznego. W pozostałych podrozdziałach przedsta- wiono bardziej zaawansowane przykłady wykorzystaniaC tego typu programowania. 3.1. Współczynnik dwumianowy Współczynnik dwumianowy (ang. binomial coefficient), który omówiono w pod- rozdziale A.7 w dodatku A, jest pokreślony zależnością:    n k  =  ! n − (! knk 0 dla )! ≤≤ k n Dla wartości n i k, które nie są małe, nie możemy obliczyć współczynnika dwu- mianowego bezpośrednio z tej definicji, ponieważ wartość n! jest bardzo duża nawet dla średnich wartości n. W ćwiczeniach zostanie wykazane, że: Rozdział 3.  Programowanie dynamiczne 113    n k  =          n k − − 1  +  1  − n   k  1   1 k 0 n = k lub 0 k = n (3.1) Możemy wyeliminować konieczność obliczania wyrażenia n! lub k!, wykorzy- stując właściwość rekurencyjną. Sugeruje to zdefiniowanie poniższego algoryt- mu typu dziel i zwyciężaj. Algorytm 3.1. Obliczanie współczynnika dwumianowego przy użyciu podejścia typu dziel i zwyciężaj Problem: oblicz współczynnik dwumianowy. Dane wejściowe: nieujemne liczby całkowite n i k, gdzie k ≤ n. Dane wyjściowe: bin — wartość współczynnika dwumianowego    n k    . KPVDKP KPVPKPVM ] KH M^^PM TGVWTP GNUG TGVWTPDKP PŌM DKP PŌM  _ Podobnie jak w przypadku algorytmu 1.6 (n-ty wyraz ciągu Fibonacciego) algo- rytm ten jest bardzo niewydajny. W ćwiczeniach Czytelnik zostanie poproszony o wykazanie, że algorytm oblicza   2  n k  −  1 wyrazów w celu obliczenia wartości    n k    . Problem polega na tym, że te same re- alizacje są rozwiązywane w każdym wywołaniu rekurencyjnym. Przykładowo wywołania bin(n–1, k–1) oraz bin(n–1, k) wiążą się z obliczeniem wartości bin(n–2, k–1) i realizacja ta jest rozwiązywana niezależnie w każCdym wywołaniu. Jak wspomniano w podrozdziale 2.8, podejście typu dziel i zwyciężaj nigdy nie jest wydajne, kiedy realizacja jest dzielona na dwie mniejsze realizacje, których rozmiar jest zbliżony do rozmiaru oryginalnej realizaCcji. Poniżej opracujemy bardziej wydajny algorytm, wykorzystujący programowanie dynamiczne. W równaniu 3.1 określiliśmy już właściwość rekurencyjną. Wyko- rzystamy ją do skonstruowania rozwiązania wykorzystującego tablicę B, gdzie B[i][j] będzie zawierać wartość    i j    . Poniżej opisano kolejne etapy tworzenia algo- rytmu, opartego na programowaniu dynamicznym. 114 Podstawy algorytmów z przykładami w C++ 1. Określamy właściwość rekurencyjną. Dokonaliśmy już tego w równanCiu 3.1. Zapisując je w kontekście użycia tablicy B otrzymujemy: iB ][[ j ] =    [ iB − 1 ][ j +− 1 ] [ iB − 1 ][ j ] 1 j 0 = j i 0 lub j = i 2. Rozwiązujemy realizację problemu w porządku wstępującym, rozpoczynając od pierwszego wiersza i wyliczając po kolei wartoścCi w wierszach tablicy B. rencyjnej, określonej w etapie 1. Ostatnia obliczana wartość, B[n][k] to Na rysunku 3.1 zilustrowano przebieg etapu 2. (Czytelnik powinien rozpoznać w przedstawionej tablicy trójkąt Pascala). Każdy następny wiersz jest wyliczany na podstawie wartości wiersza poprzedzającego przy użyciu właściwości reku-    Przykład 3.1 stanowi odzwierciedlenie tych działań. Należy zauważyć, że są w nim obliczane tylko dwie pierwsze kolumny. Wynika to z faktu, że k = 2 i, ogólnie rzecz biorąc, musimy obliczyć wartości w każdym wierszu tylko do k-tej kolumny. W przykładzie 3.1 obliczono wartość B[0][0], ponieważ współczynnik dwumianowy jest zdefiniowany dla n = k = 0. Stąd algorytm wykonuje ten etap, nawet jeśli wartość nie jest wykorzystywana w dalszycCh obliczeniach.    n k . Rysunek 3.1. Tablica B, używana do obliczenia współczynnika dwumianowego Przykład 3.1. Obliczamy wartość B[4][2] =    4 2    . Obliczamy wiersz 0.: {Etap ten jest wykonywany wyłącznie w celu dokładnego odwzorowania algorytmu}. Rozdział 3.  Programowanie dynamiczne 115 {Wartość B[0][0] nie jest potrzebna w dalszych obliczeniach}. Obliczamy wiersz 1.: Obliczamy wiersz 2.: Obliczamy wiersz 3.: Obliczamy wiersz 4.: B[0][0] = 1 B[1][0] = 1 B[1][1] = 1 B[2][0] = 1 B[2][1] = B[1][0]+B[1][1] = 1+1 = 2 B[2][2] = 1 B[3][0] = 1 B[3][1] = B[2][0]+B[2][1] = 1+2 = 3 B[3][2] = B[2][1]+B[2][2] = 2+1 = 3 B[4][0] = 1 B[4][1] = B[3][0]+B[3][1] = 1+3 = 4 B[4][2] = B[3][1]+B[3][2] = 3+3 = 6 W przykładzie 3.1 obliczaliśmy po kolei coraz większe wartości współczynnika dwumianowego. W każdym przebiegu wartości potrzebne do wykonania bieżących działań były już obliczone i zachowane. Procedura ta ma fundamentalne znaczenie dla programowania dynamicznego. Poniższy algorytm stanowi implementację opisa- nego podejścia do obliczania współczynnika dwumianowego. Algorytm 3.2. Obliczanie współczynnika dwumianowego przy użyciu programowania dynamicznego Problem: oblicz współczynnik dwumianowy. Dane wejściowe: nieujemne liczby całkowite n i k, gdzie k ≤ n. Dane wyjściowe: bin2 — wartość współczynnika dwumianowego    n k    . KPVDKP KPVPKPVM ] KPFGZKL KPV$=P?=M? HQT KKPK HQT LLOKPKOWO KM L KH L^^LK $=K?=L? GNUG $=K?=L?$=K?=L? $=K?=L? TGVWTP$=P?=M? _ 116 Podstawy algorytmów z przykładami w C++ Parametry n i k nie są rozmiarem danych wejściowych w przypadku tego algo- rytmu. Stanowią one dane wejściowe, natomiast rozmiarem danych wejściowych jest liczba symboli użytych do ich zakodowania. Z podCobną sytuacją mieliśmy do czynienia w podrozdziale 1.3, gdzie omawialiśmy algorytm obliczający n-ty wyraz ciągu Fibonacciego. Jednakże wciąż możemy zyskać wgląd w wydajność działania algorytmu poprzez określenie ilości wykonywanych dzCiałań w funkcji zmiennych n i k. Dla danego n i k obliczymy liczbę przebiegów pętli HQT-j. W poniższej tabeli 3.1 zawarto liczby przebiegów dla każdej wartości i. Tabela 3.1. Liczba przebiegów pętli for-j w zależności od wartoścui zmiennej i i 0 Liczba przebiegów 1 1 2 2 3 3 4 … … k k+1 k+1 k+1 … … n k+1 Całkowitą liczbę przebiegów określa więc zależność: 4321 ++++ K ++ k ( 1 ) k 1 ++ 44444 k ( ++ ) 1 + ( k + ) 1 K 2 44444 3 kn +− 1 razy Wykorzystując wynik otrzymany w przykładzie A.1 w dodatku A otrzymujemy następujące wyrażenie: ( kk + ) 1 2 + ( kn +− )( 1 k + ) 1 = ( 2 kn +− 2 )( k + ) 1 2 Θ∈ ( nk ) Wykorzystując programowanie dynamiczne zamiast podejścia typu dziel i zwy- ciężaj udało nam się opracować znacznie wydajniejszy algorytm. Jak wcześniej wspomniano, programowanie dynamiczne jest podobne do metody dziel i zwyciężaj o tyle, że szukamy właściwości rekurencyjnej, która dCzieli realizację problemu na mniejsze realizacje. Różnica polega na tym, że w przypadku programowania dy- namicznego wykorzystujemy właściwość rekurencyjną w celu iteracyjnego roz- wiązania realizacji w kolejnych krokach, rozpoczynając od najmniejszej realizacji, zamiast nieuzasadnionego nadużywania rekurencji. W ten sposób każdą mniejszą realizację rozwiązujemy tylko raz. Programowanie dynamiczne jest dobrym roz- wiązaniem do wypróbowania w sytuacji, gdy metoda dziel i zwyciężaj daje w wyni- ku bardzo mało wydajny algorytm. Najprostszym sposobem przedstawienia algorytmu 3.2 jest utworzenie dwuwy- miarowej tablicy B. Jednak kiedy obliczy się wartości w danym wierszu, nie są już potrzebne wartości obliczone w wierszu poprzednim. Stąd algorytm można zapisać przy użyciu tablicy jednowymiarowej, indeksowanej od 0 do k. Tego ro- dzaju modyfikację zawarto w ćwiczeniach. Kolejnym ulepszeniem algorytmu jest wykorzystanie faktu, że    n k  =     n − kn    . Rozdział 3.  Programowanie dynamiczne 117 3.2. Algorytm Floyda określania najkrótszej drogi w grafie Częstym problemem podróżnych latających samolotami jest znalezienie najkrót- szej drogi z jednego miasta do drugiego w przypadku, gdy nie istnieje połączenie bezpośrednie. Poniżej opracujemy algorytm rozwiązywania tego typu problemów. Najpierw jednak przedstawimy nieformalne wprowadzenie do teorii grafów. Na rysunku 3.2 przedstawiono ważony graf skierowany. W graCficznej reprezentacji grafu kółka oznaczają wierzchołki (ang. vertices), natomiast linie łączące jeden wierz- chołek z drugim to krawędzie (ang. edges). Jeżeli do wszystkich krawędzi zostanie przypisany odpowiedni kierunek, graf jest określany mianem grafu skierowanego (ang. directed graph) lub digrafu. Rysując krawędź w takim grafie używamy strzałki w celu przedstawienia kierunku. W digrafie mogą istnieć dwie krawędzie między dwoma wierzchołkami, każda biegnąca w innym kierunku. Na przykład na ry- sunku 3.2 mamy krawędź z wierzchołka v1 do wierzchołka v2 oraz z wierzchołka v2 do v1. Jeżeli krawędzie posiadają związane ze sobą wartości, są one nazywane wagami (ang. weights), zaś graf określa się mianem grafu ważonego (ang. weighted graph). Zakładamy, że wagi są nieujemne. Choć określa się je zwykle mianem wag, w wielu zastosowaniach reprezentują one odległości. Stąd mówimy o drodze z jed- nego wierzchołka do innego. W grafie skierowanym droga (ang. path) to sekwencja wierzchołków, taka że istnieje krawędź z każdego wierzchołka do jego następnika. Przykładowo, na rysunku 3.2 sekwencja [v1, v4, v3] jest drogą, gdyż istnieje kra- wędź z wierzchołka v1 do v4 oraz z v4 do v3. Sekwencja [v3, v4, v1] nie jest drogą, gdyż nie istnieje krawędź z wierzchołka v4 do v1. Droga z wierzchołka do niego samego nosi nazwę cyklu (ang. cycle). Droga [v1, v4, v5, v1] na rysunku 3.2 jest cyklem. Jeżeli graf zawiera cykl, jest grafem cyklicznym (ang. cyclic). W prze- ciwnym wypadku nosi nazwę acyklicznego (ang. acyclic). Droga jest nazywana drogą prostą (ang. simple), jeżeli nie przechodzi dwa razy przez ten sam wierz- chołek. Na rysunku 3.2 droga [v1, v2, v3] jest prosta, ale droga [v1, v4, v5, v1, v2] nie jest prosta. Należy zauważyć, że droga prosta nigdy nie zawiera poddrogi, która byłaby cykliczna. Długością (ang. length) drogi w grafie skierowanym jest suma wag krawędzi należących do drogi. W przypadku grCafu nieważonego jest to po prostu liczba krawędzi należących do drogi. Rysunek 3.2. Graf skierowany z podanymi wagami Często spotykanym problemem jest znalezienie najkrótszych dróg z każdego wierz- chołka do wszystkich innych wierzchołków. Oczywiście, najkrótsza droga musi być drogą prostą. Na rysunku 3.2 istnieją trzy drogi proCste z wierzchołka v1 do v3: [v1, v2, v3], [v1, v4, v3] oraz [v1, v2, v4, v3]. Z uwagi na fakt, że: 118 Podstawy algorytmów z przykładami w C++ długość [ vvv 2 1 3 , , , , , , 31] =+= 4 21] =+= 3 221] =++= 5 [ vvv 4 1 3 długość , [ długość vvvv 1 2 4 3 najkrótszą drogą z v1 do v3 jest [v1, v4, v3]. Jak wcześniej wspomniano, jednym z często wykorzystywanych zastosowań problemu najkrótszej drogi jest określanie najkrótszych tras między miastami. Problem najkrótszej drogi to problem optymalizacji (ang. optimization problem). Może istnieć więcej niż jedno rozwiązanie kandydujące dCo miana najlepszego dla problemu optymalizacji. Każde rozwiązanie kandydujące posiada związaną ze sobą wartość i rozwiązaniem realizacji jest rozwiązanie kandydujące o optymalnej warto- ści. W zależności od problemu wartością optymalną może być minimum lub maksi- mum. W przypadku problemu najkrótszej drogi rozwiązaniem kandydującym (ang. candidate solution) jest droga z jednego wierzchołka do drugiego, wartością jest długość tej drogi, zaś wartością optymalną jest minimum tych długości. Ze względu na fakt, że może istnieć wiele najkrótszych dróg z jednego wierz- chołka do drugiego, rozwiązanie problemu polega na Cznalezieniu dowolnej z tych najkrótszych dróg. Oczywistym algorytmem rozwiązania problemu byłoby określe- nie dla każdego wierzchołka długości wszystkich dróg z niego do innych wierz- chołków i znalezienie minimum wśród tych długości. Jednak algorytm taki byłby wykonywany w czasie gorszym od wykładniczego. Na przykład załóżmy, że ist- nieje krawędź z jednego wierzchołka do wszystkich innych wierzchołków. Po- nadto podzbiór wszystkich dróg z tego wierzchołka do innych wierzchołków jest zbiorem tych wszystkich dróg, które rozpoczynają siCę od pierwszego wierzchołka i kończą na innych wierzchołkach, przechodząc przez wszystkie pozostałe. Z uwagi na fakt, że drugim wierzchołkiem w takiej drodze może być dowolny spośród n–2 wierzchołków, trzecim wierzchołkiem w takiej drodze może być dowolny spo- śród n–3 wierzchołków itd., przedostatnim wierzchołkiem w takiej drodze może być tylko jeden wierzchołek, całkowita liczba dróg z jednego wierzchołka do in- nych wierzchołków, które przechodzą przez wszystkieC inne wierzchołki, wynosi: ( n − 2 )( n − ) 3 1 K ( = n − 2 )! Wynik ten jest gorszy od wykładniczego. Z tą samą sytuacją mamy do czynienia w przypadku wielu problemów optymalizacji, to znaczy oczywisty algorytm roz- patrujący wszystkie możliwości jest wykładniczy lub gorszy. Naszym celem jest znalezienie bardziej wydajnego algorytmu. Wykorzystując programowanie dynamiczne opracujemy algorytm wykonywany w czasie sześciennym, stanowiący rozwiązanie problemu najkrótszej drogi. Naj- pierw opracujemy algorytm określający tylko długości najkrótszych dróg. Później zmodyfikujemy go tak, aby dawał na wyjściu również same najkrótsze drogi. Wa- żony graf skierowany, zawierający n wierzchołków, reprezentujemy za pomocą tablicy W, gdzie: Rozdział 3.  Programowanie dynamiczne 119 waga krawędzi, jeżeli istnieje krawędź z iW ][[ j ] ∞= ,      0, jeżeli jeżeli nie = i istnieje j krawędź v i j v do v z i v do j O wierzchołku vj mówimy, że jest przyległy (ang. adjacent) do wierzchołka vi wów- czas, gdy istnieje krawędź z vi do vj. Taką tablicę określa się mianem reprezentacji grafu w postaci macierzy przyległości (ang. adjacency matrix). Graf z rysunku 3.2 przedstawiono w tej postaci na rysunku 3.3. Tablica D na rysunku 3.3 zawiera długości najkrótszych dróg w grafie. Przykładowo, D[3][5] wynosi 7, ponieważ 7 jest długością najkrótszej drogi z v3 do v5. Jeżeli będziemy w stanie znaleźć sposób obliczania wartości w D na podstawie wartości w W, otrzymamy algorytm roz- wiązujący problem najkrótszej drogi. Osiągniemy to, tworząc sekwencję n+1 tablic D , gdzie 0 ≤ k ≤ n oraz (k) (k) D [i][j] = długość najkrótszej drogi z vi do vj, zawierającej jako wierzchołki pośrednie tylko wierzchołki należące do zbioru {v1,v2,...vk}. Rysunek 3.3. Tablica W reprezentuje graf z rysunku 3.2, zaś tablica D zawiera długości najkrótszych dróg. Opracowywany algorytm rozwiązania problemu najkrótszej drogi oblicza wartości w D na podstawie wartości w W Zanim wykażemy, że pozwala nam to na obliczenie wartości w D na podstawie wartości w W, zilustrujemy znaczenie poszczególnych elementów wC tych tablicach. Przykład 3.2. Obliczmy pewne przykładowe wartości w tablicy D [i][j] dla grafu z rysunku 3.2. (k) (0) D (1) D [2][5] = length [v2, v5] = ∞ [2][5] = minimum (length [v2, v5], length [v2, v1, v5]) minimum (∞, 14) = 14 (2) D [2][5] = D (1) [2][5] = 14 (3) D [2][5] = D (2) [2][5] = 14 {Dla dowolnego grafu są one równe, ponieważ} {najkrótsza droga rozpoczynająca się w v2} {nie może przechodzić przez v2.} {Dla tego grafu są one równe, ponieważ} {uwzględnienie wierzchołka v3 nie daje żadnej} {nowej drogi z v2 do v5.} 120 Podstawy algorytmów z przykładami w C++ (4) D [2][5] = minimum (length [v2, v1, v5], length [v2, v4, v5]) length [v2, v1, v4, v5], length [v2, v3, v4, v5]) minimum (14, 5, 13, 10)+5 (5) D [2][5] = D (4) [2][5] = 5 {Dla tego grafu są one równe, ponieważ} {najkrótsza droga kończąca się w v5 nie może} {przechodzić przez v5.} [2][5], jest długością najkrótszej drogi z v2 do v5, Ostatnia obliczona wartość, D która może przechodzić przez dowolny inny wierzchołek. Oznacza to, że jest ona długością najkrótszej drogi. (5) (n) [i][j] jest długością najkrótszej drogi z vi do vj, która może przechodzić przez D dowolne wierzchołki, więc jest długością najkrótszej drogi z vi do vj. D [i][j]jest długością najkrótszej drogi, która nie może przechodzić przez inne wierzchołki, więc jest wagą przypisaną do krawędzi, wiodącej od vi do vj. Określiliśmy, że (0) )( 0 D W = oraz ( ) n D D = Stąd w celu określenia D na podstawie W musimy jedynie znaleźć sposób otrzymy- . Poniżej opisano poszczególne etapy zmierza- wania wartości D jących do tego działań, w których wykorzystamy programowanie dynamiczne. na podstawie D (n) (0) 1. Określamy właściwość rekurencyjną (proces), dzięki której możemyC obliczyć (k–1) . (k) D na podstawie D 2. Rozwiązujemy realizację problemu w porządku wstępującym poprzez powtarzanie procesu (określonego w etapie 1.) dla k = 1 do n. Daje to sekwencję: 0 1 , DDD ↑ , W 2 , K , Dn ↑ D (3.2) Etap 1. wykonujemy, rozpatrując dwa przypadki. Przypadek 1. Przynajmniej jedna najkrótsza droga z vi do vj, zawierająca jako wierzchołki pośrednie tylko wierzchołki ze zbioru {v1, v2, …, vk}, nie zawiera wierzchołka vk. Wówczas ( ) k iD ][[ j ] = D ( k 1− ) ][[ i j ] (3.3) Przykładem tej sytuacji na rysunku 3.2 jest D )( 5 31 ] ][ [ D = ( 4 ) 31 ] ][ [ 3 = ponieważ kiedy uwzględnimy wierzchołek v5, najkrótsza droga z v1 do v3 to wciąż [v1, v4, v3]. Rozdział 3.  Programowanie dynamiczne 121 Przypadek 2. Wszystkie najkrótsze drogi z vi do vj, zawierające jako wierzchołki pośrednie tylko wierzchołki ze zbioru {v1, v2, …, vk}, zawierają wierzchołek vk. W takim przypadku dowolna najkrótsza droga ma postać podobną do przedsta- wionej na rysunku 3.4. vk nie może być wierzchołkiem pośrednim na poddrodze z vi do vk, więc taka poddroga zawiera jako wierzchołki pośrednie jedynie wierz- chołki ze zbioru {v1, v2, …, vk–1}. To implikuje, że długość poddrogi musi być równa D [i][k] jest długością najkrótszej drogi z vi do vk, może być mniejsza, gdyż D zawierającej tylko wierzchołki ze zbioru {v1, v2, …, vk–1}. Po drugie, długość poddrogi nie może być większa, ponieważ gdyby tak było, moglibyśmy ją zastą- pić na rysunku 3.4 najkrótszą drogą, co stałoby w sprzeczności z faktem, że cała droga z rysunku 3.4 jest najkrótszą drogą. Podobnie długość poddrogi z vk do vj na rysunku 3.4 musi być równa D [i][k] z poniżej podanego powodu. Po pierwsze, długość poddrCogi nie [k][j]. Stąd w drugim przypadku: (k–1) (k–1) (k–1) ( iD ][[ k ) j ] = D ( k 1 − ) Dki ][[ ] + ( k 1 − ) [ k ][ j ] (3.4) Przykładem drugiego przypadku na rysunku 3.2 jest D ( 2 ) ] [ 35 ][ =+== 34 7 D )( 1 ] [ 25 ][ + D )( 1 [ ] 32 ][ Ponieważ przypadek 1. lub 2. musi występować, wartością D [i][j] jest minimum wartości, znajdujących się po prawej stronie równań 3.3 oraz 3.4. Oznacza to, że możemy określić D w następujący sposób: na podstawie D (k–1) (k) (k) )( k iD ][[ j ] = minimum ( D ( k )1 − i ][[ Dj ,] ( k )1 − Dki ][[ ] 143421 4444 4444 3 ( k )1 − [ k ][ j )] + 2 przypadek 1. przypadek 2. W ten sposób wykonaliśmy etap 1. opracowywania algoryCtmu, wykorzystującego programowanie dynamiczne. W celu wykonania etapu 2. wykorzystamy właści- wość rekurencyjną z etapu 1. w celu utworzenia sekwencji tablic, przedstawionej w wyrażeniu 3.2. Poniżej przyjrzymy się przykładowi sposobu obliczania warto- ści każdej z tych tablic na podstawie poprzedniej tabClicy. Jeśli mamy dany graf z rysunku 3.2, reprezentowany przez macierz przyległości W na rysunku 3.3, niektóre obliczenia wykonuje się w następujący sposób (należy pamiętać, że D = W): (0) Rysunek 3.4. Najkrótsza droga, zawierająca wierzchołek vk Przykład 3.3. 122 Podstawy algorytmów z przykładami w C++ )1( D ]4][2[ )1( D ]2][5[ )1( D ]4][5[ = = = = = = minimum )0( ( D ],4][2[ D )0( ]1][2[ + D )0( ])4][1[ minimum )19,2( + 2 = minimum )0( ( D ],2][5[ D )0( ]1][5[ + D )0( ])2][1[ minimum ( )13, +∞ = 4 minimum )0( ( D ],4][5[ D )0( ]1][5[ + D )0( ])4][1[ minimum ( , 3 +∞ )1 = 4 Kiedy cała tablica D obliczenie ma postać: (1) zostanie wyliczona, obliczamy tablicę D (2) . Przykładowe )2( D ]4][5[ = = minimum )1( ( D ],4][5[ D )1( ]2][5[ + D )1( ])4][2[ minimum ,4( 4 + )2 = 4 Po obliczeniu wszystkich wyrazów w tablicy D do momentu wyliczenia D szych dróg. Na rysunku 3.3 umieszczono ją po prawej stronie. kontynuujemy działania po kolei . Końcową tablicą jest D, która zawiera długości najkrót- (5) (2) Poniżej przedstawimy algorytm opracowany przez Floyda (1962), znany jako algo- rytm Floyda (ang. Floyd’s algorithm). Później wyjaśnimy, dlaczego korzysta on tylko z jednej tablicy D oprócz tablicy wejściowej W. Algorytm 3.3. Algorytm Floyda określania najkrótszej drogi Problem: oblicz najkrótsze drogi z każdego wierzchołka w grafie ważonym do wszystkich innych wierzchołków. Wagi są liczbami nieCujemnymi. Dane wejściowe: ważony graf skierowany oraz n, liczba wierzchołków w grafie. Graf jest reprezentowany przez tablicę dwuwymiarową W, której wiersze i ko- lumny są indeksowane od 1 do n, gdzie W[i][j] jest wagą krawędzi, prowadzącej od i-tego do j-tego wierzchołka. Dane wyjściowe: dwuwymiarowa tablica D, której wiersze i kolumny są indekso- wane od 1 do n, gdzie D[i][j] jest długością najkrótszej drogi, prowadzącej od i-tego do j-tego wierzchołka. XQKFHNQ[F KPVP EQPUVPWODGT9=?=? PWODGT =?=? ] KPFGZKLM  9 HQT MMPM HQT KKPK HQT LLPL  =K?=L?OKPKOWO =K?=L? =K?=M? =M?=L?  _ Rozdział 3.  Programowanie dynamiczne 123 Możemy wykonać nasze obliczenia przy użyciu tylko jednej tablicy D, ponieważ wartości w k-tym wierszu oraz k-tej kolumnie nie są wymieniane w czasie k-tego przebiegu pętli. Oznacza to, że w k-tym przebiegu algorytm dokonuje przypisania: kiD ][[ ] = minimum ( co jest oczywiście równe D[i][k] oraz kkDkiDkiD + ][[ ] ][[ ], [ ][ ]) kD [ ][ j ] = minimum ( kD [ ][ kDkkDj ], ][ [ ] [ + ][ j ]) co jest oczywiście równe D[k][j]. W czasie k-tego przebiegu element D[i][j] jest obliczany tylko na podstawie własnej wartości oraz wartości w k-tym wierszu i k-tej kolumnie. Wartości te zostały przypisane w (k–1). przebiegu, więc są poszuki- wanymi przez nas wartościami. Jak wspomniano wcześniej, czasem po opraco- waniu algorytmu programowania dynamicznego istnieje możliwość jego popra- wienia, tak aby był bardziej wydajny pod względem zaCjętości pamięci. Poniżej zostanie przedstawiona analiza algorytmu FloyCda. Złożoność czasowa w każdym przypadku (algorytm Floyda na ynajkrótszą drogę) Operacja podstawowa: instrukcja w pętli HQT-j. Rozmiar danych wejściowych: n, liczba wierzchołków w grafie. Mamy do czynienia z pętlą w pętli w pętli, z których każda jest związana z wy- konaniem n przebiegów, tak więc: Analiza algorytmu 3.3. )( nT Θ∈=××= nnn n 3 3 ( n ). Poniższa modyfikacja algorytmu 3.3 pozwala na obliczeniCe najkrótszej drogi. Algorytm 3.4. Algorytm Floyda określania najkrótszej drogi 2 Problem: podobnie jak w przypadku algorytmu 3.3. Oprócz tego tworzone są również najkrótsze drogi. Dodatkowe dane wyjściowe: tablica P, której wiersze i kolumny są indeksowane od 1 do n, gdzie najwyższy indeks wierzchoł ka pośrednieg wo najkrótsze drodze j iP j ),( = v do , j jeżeli istnieje co najmniej jeden wier zchołek pośredni   v  od i   0, jeżeli nie istnieje żaden wier zchołek pośredni XQKFHNQ[F KPVP EQPUVPWODGT9=?=? PWODGT =?=? KPFGZ2=?=? 124 Podstawy algorytmów z przykładami w C++ ] KPFGZKLM HQT KKPK HQT KKPK 2=K?=L?  9 HQT MMPM HQT KKPK HQT LLPL KH =K?=M? =M?=L? =K?=L? ] 2=K?=L?M  =K?=L? =K?=M? =M?=L?  _ _ Na rysunku 3.5 przedstawiono tablicę P, która jest tworzona w przypadku zasto- sowania algorytmu dla grafu z rysunku 3.2. Rysunek 3.5. Tablica P, utworzona w przypadku zastosowania algorytmu 3.4 dla grafu z rysunku 3.2 Poniższy algorytm tworzy najkrótszą drogę od wierzchołka vq do vr na podstawie tablicy P. Algorytm 3.5. Wyświetlenie najkrótszej drogi Problem: wyświetl wierzchołki pośrednie w najkrótszej drodze od jednego wierz- chołka do innego w grafie ważonym. Dane wejściowe: tablica P, utworzona przez algorytm 3.4 oraz dwa indeksy (q i r) wierzchołków w grafie, który stanowi dane wejściowe Calgorytmu 3.4. najwyższy indeks wierzchoł ka najkrótsze drodze j pośrednieg wo   v  od i   0, iP j ),( = v do , j jeżeli istnieje co najmniej jeden wier zchołek pośredni jeżeli nie istnieje żaden wier zchołek pośredni Dane wyjściowe: wierzchołki pośrednie w najkrótszej drodze z vq do vr. XQKFRCVJ KPFGZST ] KH 2=S?=T? ] RCVJ S2=S?=T?  EQWVX2=S?=T? Rozdział 3.  Programowanie dynamiczne 125 RCVJ 2=S?=T?T  _ _ RCVJ ST  Warto przypomnieć konwencję określoną w rozdziale 2., zgodnie z którą danymi wejściowymi podprogramów rekurencyjnych mogą być tylko takie zmienne, któ- rych wartość może ulegać zmianie w wywołaniach rekurencyjnych. Stąd tablica P nie stanowi danych wejściowych procedury path. Gdyby algorytm zaimplemento- wano definiując P globalnie i chcielibyśmy określić najkrótszą drogę z wierzchołka vq do wierzchołka vr, to wywołanie procedury path na najwyższym poziomie miałoby postać: Dla danej wartości P z rysunku 3.5, jeżeli wartości q i r wynosiłyby, odpowiednio, 5 i 3, dane wyjściowe miałyby postać: v1 v4 Są to wierzchołki pośrednie w najkrótszej drodze z wiCerzchołka v5 do wierzchołka v3. W ćwiczeniach zostanie określone, że W(n) ∈ Θ(n) w przypadku algorytmu 3.5. 3.3. Programowanie dynamiczne a problemy optymalizacyjne Należy przypomnieć, że algorytm 3.4 nie tylko pozwala określić długości najkrót- szych dróg, ale również konstruuje najkrótsze drogi. Konstrukcja optymalnego rozwiązania jest trzecim etapem w procesie opracowywania algorytmu progra- mowania dynamicznego dla problemu optymalizacji. Oznacza to, że w procesie opracowywania takiego algorytmu można wyróżnić nastęCpujące etapy: 1. Określenie właściwości rekurencyjnej, która daje rozwiązanie opCtymalne dla realizacji problemu. 2. Obliczenie wartości rozwiązania optymalnego w porząCdku wstępującym. 3. Skonstruowanie rozwiązania optymalnego w porządku wstępującym. Etapy 2. oraz 3. są zwykle wykonywane mniej więcej w tym samym miejscu algo- rytmu. Ze względu na fakt, że algorytm 3.2 nie jest problemem optymalizacji, nie występuje w nim trzeci etap. Choć może się wydawać, że problem optymalizacji może zawsze zostać rozwiązany przy użyciu programowania dynamicznego, nie jest to prawdą. Aby tak było, w przy- padku danego problemu musi mieć zastosowanie zasada optymalności. Zasadę tę można wyrazić następująco: 126 Podstawy algorytmów z przykładami w C++ Definicja O zasadzie optymalności (ang. principle of optimality) mówi się, że ma zasto- sowanie w problemie wówczas, gdy rozwiązanie optymalne realizacji problemu zawsze zawiera rozwiązania optymalne dla wszystkich ópodrealizacji. Zasada optymalności jest trudna do jednoznacznego zdefiniowania i łatwiej jest ją zrozumieć poprzez analizę konkretnego przykładu. W przypadku problemu naj- krótszej drogi pokazaliśmy, że jeżeli vk jest wierzchołkiem należącym do drogi optymalnej z vi do vj, to poddrogi z vi do vk oraz z vk do vj również muszą być optymalne. Stąd optymalne rozwiązanie realizacji zawiera rozwiązania optymalne wszystkich podrealizacji i ma tu zastosowanie zasadCa optymalności. Jeżeli zasada optymalności ma zastosowanie w przypadku danego problemu, mo- żemy określić właściwość rekurencyjną, która będzie dawać optymalne rozwią- zanie realizacji w kontekście optymalnych rozwiązań podrealizacji. Istotnym, choć subtelnym powodem, dla którego możemy wówczas wykorzystać programowanie dynamiczne w celu skonstruowania optymalnego rozwiązania realizacji, jest to, że optymalne rozwiązania podrealizacji mogą być dowolnymi optymalnymi roz- wiązaniami. Przykładowo, w przypadku problemu najkrótszej drogi: jeżeli pod- drogami są dowolne najkrótsze drogi, połączona droga będzie optymalna. Możemy więc wykorzystać właściwość rekurencyjną w celu skonstruowania rozwiązań opty- malnych coraz większych realizacji w porządku wstępującym. Każde tak otrzy- mane rozwiązanie jest optymalne. Choć zasada optymalności może wydawać się oczywista, w praktyce konieczne jest wykazanie, że zasada ma zastosowanie, zanim jeszcze założy się, że rozwiązanie optymalne może zostać otrzymane dzięki programowaniu dynamicznemu. Poniż- szy przykład pokazuje, że nie ma ona zastosowania w przypadku każdego pro- blemu optymalizacji. Przykład 3.4. Rozważmy problem najdłuższej drogi, polegający na znalezieniu najdłuższych pro- stych dróg wiodących od każdego wierzchołka do wszystkich innych wierzchoł- ków. Problem ograniczamy do prostych dróg, ponieważ w przypadku cykli zawsze możemy utworzyć dowolnie długą drogę poprzez powtarzalne przechodzenie przez cykl. Na rysunku 3.6 optymalna (najdłuższa) prosta droga z v1 do v4 to [v1, v3, v2, v4]. Jednak poddroga [v1, v3] nie jest optymalną (najdłuższą) drogą z v1 do v3, ponieważ [ długość , vv 1 3 1] = oraz [ długość , vvv 2 1 , ] 3 4 = Zatem zasada optymalności nie ma zastosowania. Wynika to z faktu, że optymalne drogi z v1 do v3 oraz z v3 do v4 nie mogą zostać razem powiązane, aby utworzyć optymalną drogę z v1 do v4. Spowodowałoby to utworzenie cyklu, a nie optymal- nej drogi. Rozdział 3.  Programowanie dynamiczne 127 Rysunek 3.6. Ważony graf skierowany z cyklem Pozostałą część rozdziału poświęcimy problemom optymalizacji. Opracowując algorytmy nie będziemy wymieniać wcześniej opisanych etapów działania. Powinno być rzeczą oczywistą, że postępujemy zgodnie z nimi. 3.4. Łańcuchowe mnożenie macierzy Załóżmy, że chcemy pomnożyć macierz o wymiarach 2×3 przez macierz o roz- miarach 3×4 w sposób następujący:    321 654  ×       1987 5432 9876      =    29 35 41 74 89 104  38   83 Macierz wynikowa ma rozmiary 2×4. Jeżeli użyjemy standardowej metody mno- żenia macierzy (opartej na definicji mnożenia macierzy), obliczenie każdego elementu iloczynu wymagać będzie wykonania trzech podstawowych operacji mnożenia. Przykładowo, pierwszy element w pierwszej kColumnie to: 632271 444 3 444 21 ×+×+× 3 mnożenia Ze względu na fakt, że w iloczynie występuje 2×4 = 8 pozycji, całkowita liczba elementarnych operacji mnożenia wynosi 342 =×× 24 Ogólnie rzecz biorąc, w celu pomnożenia macierzy o wymiarach i×j przez ma- cierz o wymiarach j×k przy użyciu metody standardowej musimy wykonać i j ×× k elementarnych operacji mnożenia Rozważmy operację mnożenia następujących macierzy: 128 Podstawy algorytmów z przykładami w C++ A × B × C × D 20 × 2 2 × 30 30 12 × 12 × 8 Wymiary każdej macierzy zapisano pod nimi. Mnożenie macierzy jest operacją łączną, co oznacza, że kolejność, w jakiej wykonujemy mnożenie, nie ma zna- czenia. Przykładowo, operacje A(B(CD)) oraz (AB)(CD) dają ten sam wynik. Ist- nieje pięć różnych kolejności, w jakich możemy pomnożyć cztery macierze i które dadzą zwykle różną liczbę elementarnych operacji mnożenia. W przypadku po- wyższych macierzy mamy następujące liczby elementarnych operacji mnożenia dla różnych kolejności działań: A(B(CD)) 30×12×8+ 2×30× 8+20× 2×8 = 3680 (AB)(CD) 20×2×30+30×12× 8+20× 30×8 = 8880 A((BC)D) 2×30×12+ 2×12× 8+20× 2×8 = 1232 ((AB)C)D 20×2×30+20×30×12+20×12×8 = 10320 (A(BC))D 2×30×12+20× 2× 12+20× 12×8 = 3120 Trzecia kolejność jest optymalna w przypadku mnożenia Cczterech macierzy. Naszym celem jest opracowanie algorytmu, który będzie określał optymalną ko- lejność mnożenia n macierzy. Kolejność ta zależy tylko od rozmiarów macierzy. Stąd oprócz n rozmiary te stanowią jedyne dane wejściowe dla algorytmu. Algo- rytm wykorzystujący metodę siłową polegałby na rozważeniu wszystkich możli- wych kolejności i wybraniu minimum — tak jak postąpiliśmy powyżej. Wyka- żemy, że taki algorytm jest wykonywany co najmniej w czasie wykładniczym. Niech tn będzie liczbą różnych kolejności, w jakich możemy pomnożyć n macie- rzy: A1, A2, …, An. Jednym z podzbiorów wszystkich kolejności jest zbiór kolej- ności, dla których macierz A1 jest ostatnią mnożoną macierzą. Jak pokazano po- niżej, liczba różnych kolejności w tym podzbiorze wynosi tn–1, ponieważ jest to liczba kolejności, w jakich możemy pomnożyć macierze oCd A2 do An: ( 1 AAA 3 A n 43421 K 2 ) różnych 1 t kolejności −n Drugi podzbiór wszystkich kolejności jest zbiorem kolejności, w przypadku któ- rych macierz An jest ostatnią mnożoną macierzą. Oczywiście, liczba różnych ko- lejności w tym podzbiorze również wynosi tn–1. Stąd: t n ≥ t 1 − n + t 1 − n = 2 t 1 − n Ze względu na fakt, że istnieje tylko jeden sposób pomnożenia dwóch macierzy, t2 = 1. Wykorzystując techniki opisane w dodatku B możemy rozwiązać tę reku- rencję, wykazując, że: ≥ n 22 − t n Rozdział 3.  Programowanie dynamiczne 129 Nietrudno zauważyć, że zasada optymalności ma zastosowanie w przypadku tego problemu. Oznacza to, że optymalna kolejność mnożenia n macierzy zawiera opty- malną kolejność mnożenia dowolnego podzbioru zbioru n macierzy. Przykłado- wo, jeżeli optymalna kolejność mnożenia sześciu macierCzy ma postać (((( A 1 AAAAA 6 5 2 4 ) 3 ) ) ) to ( AAA 4 2 3 ) musi być optymalną kolejnością mnożenia macierzy od A2 do A4. Oznacza to, że w celu skonstruowania rozwiązania możemy wykorzystać programowanie dy- namiczne. Ze względu na fakt,
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Podstawy algorytmów z przykładami w C++
Autor:
,

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: