Hinduska legenda podaje ze boog Brahma stworzył świat i równocześnie wyznaczył jego koniec. Brahma ułożył wieżę z 64 złotych pierścieni. Każdy pierścień wieży posiadał odmienną średnicę z największym na dnie a najmniejszym na szczycie. Brahma kazał mnichowi przekładać po jednym pierścieniu od góry budując nowa wieżę. Mnich może tylko przekładać je po jednym pierścieniu używając trzecią pośrednią wieżę ale nie wolno mu położyć większego pierścienia na mniejszy. Kiedy cala wieża z jednego miejsca będzie przeniesiona na drugie będzie to koniec świata.
Model wieży Brahmy z 10 pierścieniami.
Można łatwo udowodnić, że liczba potrzebnych ruchów (przełożenie jednego pierścienia wieży) z n pierścieniami wynosi T(n)=2 (do potęgi n) minus 1. Zakładając, że mnisi przekładają jeden pierścień na sekundę i nie popełnią pomyłki czas przełożenia 64 pierścieni wynosi około 500 miliardów lat. A wiec nie musimy się zbytnio martwic.
Fascynującym problemem, który opiszę w tym eseju jest metoda zwana rekursywną, a dotycząca policzenia ruchów w której zamieniamy problem wieży z n pierścieniami na dwa problemy z n-1 pierścieniami. Można ten proces redukcji kontynuować aż do momentu kiedy mamy przełożyć wieżę z dwoma pierścieniami co jest trywialnym zadaniem. Umówimy się ze pręty z pierścieniami maja nazwę A,B,C od strony lewej do prawej. Przeniesienie wieży z dwoma pierścieni z A do C wymaga trzech ruchów.
mały górny pierścień z A do B.
dolny z A do C.
mały z B do C.
Podobnie jeśli mamy na przykład 50 pierścieni na A i chcemy je przenieść na C to możemy to zrobić tak.
przenieść 49 z A do B.
przenieść największy z A do C
przenieść 49 z B do C.
Zredukowaliśmy problem z 50 pierścieniami na dwa mniejsze z 49 pierścieniami. Teraz możemy zredukować dwa problemy z 49 pierścieniami na cztery z 48 pierścieniami. Ilość problemów rośnie wykładniczo ale ich wielkość się zmniejsza. Jeśli to powtórzymy 46 razy to będziemy mieli bardzo dużo problemów z dwoma pierścieniami z których każdy wymaga 3 ruchy.
Taki proces redukcji nazywa się rekursją i jest stosowany do rozwiazywania praktycznych problemów. Procedura redukcji nosi też nazwę dynamiczne programowanie i została stworzona przez amerykańskiego matematyka Ryszarda Bellmana w 1953 roku.
Dla przykładu policzymy ilość ruchów malej wieży składającej się z 4 pierścieni. Symbolicznie możemy napisać T(4)=2T(3)+1; to znaczy liczba ruchów potrzebnych do przeniesienia wieży złożonej z 4 pierścieni wynosi dwa razy tyle ile wymaga przeniesienie wieży z trzema pierścieniami plus 1. Wiemy ze T(3)=2T(2)+1. Wiemy tez ze T(2)=3.
Cofając się od T(2) do T(4) możemy policzyć T(3)=7 oraz T(4)=15.
Jeśli wykonujemy jeden ruch na sekundę to czas w sekundach przeniesienia wieży jest równy liczbie ruchów. Czas przeniesienia 50 pierścieni wynosi około 31.7 milionów lat. Mniej niż długość istnienia świata według Brahmy, ale za długo nie tylko dla mnichów lecz nawet dla starego PC. Nowoczesny PC może symbolicznie przekładać pierścienie szybciej niż jeden na sekundę i skróci czas do kilku lat lub miesięcy.
Jaki jest wniosek z tych rozważań na temat wieży Brahmy? Ważne spostrzeżenie dotyczy granic obliczeń najszybszymi komputerami. Jeśli nasz problem wymaga wykładniczo rosnącej ilości operacji to mamy do czynienia z nieprzekraczalną barierą czasową która uniemożliwia rozwiązywanie dużych problemów. Możemy też zauważyć, że proces redukcji można wykonywać równolegle .
Ból- skandal czy błogosławieństwo? Postawy wobec bólu a ogólna wizja świata i człowieka (na przykładzie ateistów, buddystów i katolików) Sylwia Wojas Instytut…
Dostrzegam w naszym kraju pewną tendencję do zamierania dyskusji i polemiki między reprezentantami równych ideologii politycznych. Jako liberał i eks-konserwatysta jestem tym faktem dość zaniepokojony,…
Amerykański wrzesień to okres, kiedy pod hasłem „back to school” wraca się do corocznej rutyny, ale jednocześnie dużo się dzieje, a w szkołach znowu spotyka…
Konserwatysta krytykuje polityczny konstruktywizm i nawiązuje do przeszłości, ale często jest to pewna wyidealizowana lub nawet przekłamana wizja przeszłości, co skutkuje tym, że…
Janusz Kowalik jest emerytowanym profesorem matematyki i informatyki na Washington State University oraz byłym kierownikiem organizacji badań informatyki w firmie lotniczej Boeing Company w Seattle.
Adres internetowy Janusza:
j.kowalik@comcast.net
13 Odpowiedź na “Hinduski bóg Brahma i programowanie dynamiczne”
W literaturze popularnej matmy ten problem jest tez zwany Wieza Hanoi (miasto w Wietnamie).
Pytalem kilku wyksztalconych kolegow ile moze trwac przekladanie 64 pierscieni .Co im podpowiada intuicja bez liczenia.Nikt nie przekroczyl liczby kilku godzin. Nasza intuicja oceny wzrostu funkcji wykladniczej jest bezuzyteczna .Jedynie poprawna analiza daje obraz bardzo szybkiego wzrostu ktory polozy na lopatki szybkie komputery. Dlatego uzytkownik komputerow trzyma kciuki
z nadzieja ze jego problem nie ma rozwiazania wymagajacego wykladniczej ilosci operacji.
Super! Bardzo fajnie, że takie eseje pojawiają się na R.tv. Warto by też napisać o problemach NP, NP-zupełnych, bo to zarówno problem praktyczny, jak i filozoficzny.
Rekursja to nie jest to samo co programowanie dynamiczne (DP). Rekursja to sposob rozwiązywania problemu o naturze „programowania dynamicznego”. Inną metodą jest np. metoda iteracyjna. Tak wiec problem „dynamiczny” mozna rozwiązac przy pomocy rekursji albo iteracji.
Nie wiem tez skąd autor stwierdzenie, ze „proces redukcji mozna wykonywac rownolegle”. To byłaby sensacja na miare nagrody Nobla (choc matematycy Nobla nie dostają). Natura CAŁEGO problemu DP własnie polega na tym, ze nie mozna go rozwiązac w sposob rownoległy. Chodzi tu pewnie o to, ze problemy DP mozna rozwiązac tez iteracyjnie (niekoniecznie w sposob rekursyjny), albo pewne czesci DP mozna wykonac rownolegle. Ale sama natura CAŁEGO DP wyklucza rownoległosc.
Rozwiązanie rekurencyjne i programowanie dynamiczne mają jedna wspólną cechę: podział problemu na podzadania aż do zadania trywialnego, a następnie scalanie wyników do wyniku końcowego. Różnią się tym, że w rekursji podzadania są niezależnie, a w programowaniu dynamicznym powtarzają się. Zadania, które rozwiązuje się programowaniem dynamicznym, można rozwiązać też rekursją, ale jest to wyjątkowo nieefektywne, bo wielokrotnie liczy się to samo. Zwykle pokazuje się to studentom na przykładzie liczb Fibonacciego, które można z definicji wyliczać rekurencyjnie, ale jest to niewydajne, i liczy się programując dynamicznie.
Nie slyszalem aby liczby Fibonnaciego mozna/trzeba bylo obliczac przy pomocy DP (Dynamic Programming) . Nie ma takiej potrzeby. Mozna obliczac rekurencyjnie albo iteracyjnie. Jak przechodzisz z jednego stanu w tylko jeden nastepny stan, itd. to DP jest niepotrzebne.
Rowniez cecha na ktora sie powolujesz jest nieprawdziwa. DP nie prowadzi do zadania trywialnego. DP po prostu w ostatnim kroku dopiero moze zdecydowac ktore rozwiazanie jest optymalne, bo ostatni krok moze „wszystko” zmienic.
Rekursja/rekurencja nadaje sie idealnie do sformulowania rozwiazania problemu DP, ale do rozwiazania DP nie trzeba uzyc rekursji.
Rekursja to tylko sposob obliczen, natomiast w DP odrzucasz po drodze czesc potencjalnych rozwiazan, ktore na pewno wiesz, ze nie beda optymalne i ten sposob oszczedzasz na obliczeniach (czasie). W samej rekursji „nic nie odrzucasz”.
Liczby Fibonacciego są zdefiniowane rekurencyjnie. Liczba n-ta jest sumą dwóch liczb poprzednich, (n – 1)-szej i (n – 2)-giej. Skoro liczby Fibonacciego są zdefiniowane rekurencyjnie, to da się je obliczyć rekurencyjnie. Program jest króciusieńki, ale potrafi się wykonywać (bardzo) długo, bo dla wyznaczenia tysięcznej liczby, np. liczba piąta jest wyznaczana wielokrotnie, zupełnie bez sensu, bo można wyznaczyć raz i zapisać wynik.
.
Można zaimplementować algorytm optymalnego nawiasowania ciągu macierzy w sposób rekurencyjny. I będzie działać, ale wolno, bo mnóstwo rzeczy będzie liczonych wielokrotnie. Można częściowe optymalne wyniki zapisywać i z nich korzystać. Wtedy algorytm, dzięki programowaniu dynamicznemu, będzie wykonywał się dużo dużo szybciej.
Tak, ale u Fibonnaciego nie widze nic wspolnego z originalną ideą Bellmana (oprocz tego ze Fibonacci ladnie ilustruje rekurencje).
„liczba piąta jest wyznaczana wielokrotnie, zupełnie bez sensu, bo można wyznaczyć raz i zapisać wynik.” –
To jest jedyne zauwazenie, ze jak cos juz policzylismy to nie ma sensu liczyc jeszcze raz. Wg mnie NIE jest to DP. U Bellmana „programming” znaczy „algorytm”, a „dynamic” to tylko fajne słowo, zeby zaimponowac zleceniodawcom. Samo „dynamic” nie nie wyjasnia ani nie tłumaczy. U Bellmana najwazniejsza jest zasada optymalnosci ( Bellman’s Principle of Optimality). W tym sensie przyklad z Fibonacci jest trywialny bo nic nie odrzuca (nie musi wybierac czegos optymalnego, bo poprzedni mozliwy stan jest tylko jeden), jedynie ilustruje rekurencje.
Programowanie dynamiczne ma dwie cechy:
(1) optymalność struktury, czyli scalenie optymalnych rozwiązań podzadań daje także optymalne rozwiązanie i
(2) podzadania przynajmniej częściowo się pokrywają, a nawet mogą się powtarzać (wspólne podzadania).
Jeżeli spełniona jest tylko pierwsza cecha, to algorytm jest typu ,,dziel i zwyciężaj” (np. sortowanie szybkie, sortowanie przez scalanie). Jeżeli spełnione są obie cechy, to optymalne rozwiązania powtarzających się podzadań zapisuje się, zamiast powtórnie je rozwiązywać.
Przynajmniej tak to opisuje Cormen w swoim ,,Wprowadzeniu do algorytmów”.
ZORRO I LUCYAN najpierw pisza jakies wlasne zdanie a potem sie z nim nie zgadzaja. Recursywny algorytm jest pokrewny metodzie Bellmana ale nie identyczny. Rowniez liczby Fibonacci nie sa liczone algorytmem dynamicznego programowania. Napisalem o Bellmanie bo jego algorytm tez jest recursywny i byl uzywany do rozwiazan problemow optymalizacji. Ciesze sie ze ten problem poruszony w eseju zainteresowal kilku czytelnikow ale sugeruje aby nawet w dyskusji popularnej matematyki
zachowac pewna precyzje i ostroznosc.
Algorytm Bellmana nie jest rekursywny, moze byc sformulowany i rekursywnie i nierekursywnie.
Rekursja czy iteracja to sposoby rozwiazania problemu ale nie sa to metody na cos same w sobie.
Zreszta, czy nie jest tak ze wszystko co sie da rozwiazac/zapisac rekursywnie, to mozna zapisac iteracyjnie, i vice versa?
„a potem sie z nim nie zgadzaja” – Ja tam nie widze, zebym sobie zaprzeczal.
Sednem Bellmana i DP jest zasada optymalnosci, ale nie wszystkie problemy da sie sformulowac w
ten sposob.
Co redukujemy u Bellmana? Wg mnie redukcja polega na odrzuceniu na kazdym etapie duzej ilosci rozwiązan ktore na pewno nie mogą wchodzi w koncowe optymalne rozwiązanie. Redukcja to chyba nie jest „zredukowanie” problemow na mniejsze, tylko odrzucenie rozwiąan nieoptymalnych.
Widze ( w internecie), ze wielu autorow odstepuje od oryginalej definicji Bellmana i wszystko co sie „rusza”, co sie zmienia, co skraca czas obliczen, nazywają „dynamic programming”. Tam gdzie w problemie nie ma funkcji min czy max to trudno mowic o tradycyjnym DP.
Ogolna idea rekursji polega na rozbiciu duzego problemu sa mniejsze ktore sa tak samo sformulowane .Problem wiezy Hanoi jest dokladnie ilustracja tej metody.Jest to odwleczenie rozwiazania do momentu kiedy skladniki sa male i maja znane rozwiazanie. W wiezy Hanoi zaczynamy od duzej wiezy i zastepujemy go dwoma m niejszymi wierzami . Ten proces jest kontyn uowany az do momentu kiedy rozwiazanie jest wyrazone potezna iloscia prostych problemow z dwoma pierscieniami. Na samym koncu rekursji duzy problem sklada sie z problemow ktorych rozwiazszanie jest znane. To jest idea rekursywnego algorytmu. Oczywiscie problem wiezy mozna rozwiazac iteracyjnie bez rekursji . W algorytmie iteracyjnym mamy regoly przekladania pierscieni. Ilosc ruchow jest identyczna ale proces obliczenia jest rozny. Podczas redakcxji artykulu nastapila zmiana rysunku wiezy .Aby rysunek i tekst pasowaly trzeba nazwac w rysunku lewy pret B, srodkowy A i prawy C. Problem Wiezy jest symetryczny i zmiana nazw trzech pretow z pierscieniami nie robi roznicy w ilosci minimalnych ruchow ale zmienia opis rekursji bo przekladamy z A do C i A jest srodkowym pretem zwanym source Zrodlo a jeden z pozostalych pretow jest destination docedlowym pretem C. Jedna z trudnosci opisu rekursji w tym artykule jest ograniczenie zapisu matematycznego .W normalnym zurnalu matematycznym mozna uzyc jasny zapis (notation) rownan ktory ulatwia zrozumienie.
Czytelnicy ktorzy lubia matematyke i znaja podstawowe
idee matematyki moga sprawdzic ze na przyklad problem z 50 pierscieniami jest zredukowany metoda rekursji do 2(potegi 48)problemow z dwoma pierscieniami z ktorych kazdy wymaga 3 ruchy.Jak duza jest liczba 2(do potegi48)?Jest to okolo 10(do potegi 16) czyli 10 milionow miliardow.
Ta eksplozja ilosci problemow jest cena jaka placimy
zamieniajac duzt y problem z 50 pierscieniami na olbrzymia ilosc prostych problemow .Tu lezy centralna idea rekursywnego algorytmu. Dlatego programy rekursywne wymagaja ostroznego uzycia aby nie
wymagaly zbyt duzej pamieci i operacji.
W matematyce czesto zamieniamy trudny problem na wiele ,miejszych.Jesli ta redukcja powoduje wykladnicza eksplozje to mamy doczynienia z trudnym problemem ktory moze wymagac przyblizonego rozwiazania zamiast rozwiazania dokladnego.
Problem wież z Hanoi to klasyka, jak to mówio. Każdy szanujący się ćwiczeniowiec wspomina go na zajęciach z pierwszoroczniakami na analizie lub na teorii mnogości. To dobre ćwiczenie z indukcji matematycznej. Jednocześnie to elementarz dla każdego studenta specjalności informatyki i piękny przykład problemu z zakresu obliczalności, który ma wpisaną w swoją naturę rekurencyjność. Zapisanie algorytmu dla wież z Hanoi w każdym z podstawowych języków programowania (np. C), to dokładnie trzy linijki. Problem z rekurencją zawsze polegał na tym, że prowadziła do szybkiego stack overflow. Dlatego w celach dydaktycznych zawsze zadawało się studenciakom pisanie na przykład silni iteracyjnie i rekurencyjnie. Współczesny hardware i optymalizacja kompilatorów powodują, że komputer jest pewnie w stanie „łyknąć” większe obliczenia rekurencyjne. Wzorek 2^n-1 to dobry przykład szybko ronącej, bo wykładniczej, złożoności obliczeniowej. Swoją drogą czas dla 64 pierścieni wyszedł mi cirka 37,5 miliarda lat (ale może mi się cuś omskło). Ale to pikuś przy innych funkcjach znanych w teorii obliczalności. Z wykładu z teorii mnogości przypominam sobie osobiście przykład funkcji Ackermanna. Cudeńko. To pierwszy taki skonstruowany przykład funkcji w pełni wyliczalnej i nie należącej do zbioru odwzorowań PR (podstawowo rekursywnych, czy jak tam tłumaczą na polski primitive recursive).
W literaturze popularnej matmy ten problem jest tez zwany Wieza Hanoi (miasto w Wietnamie).
Pytalem kilku wyksztalconych kolegow ile moze trwac przekladanie 64 pierscieni .Co im podpowiada intuicja bez liczenia.Nikt nie przekroczyl liczby kilku godzin. Nasza intuicja oceny wzrostu funkcji wykladniczej jest bezuzyteczna .Jedynie poprawna analiza daje obraz bardzo szybkiego wzrostu ktory polozy na lopatki szybkie komputery. Dlatego uzytkownik komputerow trzyma kciuki
z nadzieja ze jego problem nie ma rozwiazania wymagajacego wykladniczej ilosci operacji.
Super! Bardzo fajnie, że takie eseje pojawiają się na R.tv. Warto by też napisać o problemach NP, NP-zupełnych, bo to zarówno problem praktyczny, jak i filozoficzny.
Rekursja to nie jest to samo co programowanie dynamiczne (DP). Rekursja to sposob rozwiązywania problemu o naturze „programowania dynamicznego”. Inną metodą jest np. metoda iteracyjna. Tak wiec problem „dynamiczny” mozna rozwiązac przy pomocy rekursji albo iteracji.
Nie wiem tez skąd autor stwierdzenie, ze „proces redukcji mozna wykonywac rownolegle”. To byłaby sensacja na miare nagrody Nobla (choc matematycy Nobla nie dostają). Natura CAŁEGO problemu DP własnie polega na tym, ze nie mozna go rozwiązac w sposob rownoległy. Chodzi tu pewnie o to, ze problemy DP mozna rozwiązac tez iteracyjnie (niekoniecznie w sposob rekursyjny), albo pewne czesci DP mozna wykonac rownolegle. Ale sama natura CAŁEGO DP wyklucza rownoległosc.
Rozwiązanie rekurencyjne i programowanie dynamiczne mają jedna wspólną cechę: podział problemu na podzadania aż do zadania trywialnego, a następnie scalanie wyników do wyniku końcowego. Różnią się tym, że w rekursji podzadania są niezależnie, a w programowaniu dynamicznym powtarzają się. Zadania, które rozwiązuje się programowaniem dynamicznym, można rozwiązać też rekursją, ale jest to wyjątkowo nieefektywne, bo wielokrotnie liczy się to samo. Zwykle pokazuje się to studentom na przykładzie liczb Fibonacciego, które można z definicji wyliczać rekurencyjnie, ale jest to niewydajne, i liczy się programując dynamicznie.
Nie slyszalem aby liczby Fibonnaciego mozna/trzeba bylo obliczac przy pomocy DP (Dynamic Programming) . Nie ma takiej potrzeby. Mozna obliczac rekurencyjnie albo iteracyjnie. Jak przechodzisz z jednego stanu w tylko jeden nastepny stan, itd. to DP jest niepotrzebne.
Rowniez cecha na ktora sie powolujesz jest nieprawdziwa. DP nie prowadzi do zadania trywialnego. DP po prostu w ostatnim kroku dopiero moze zdecydowac ktore rozwiazanie jest optymalne, bo ostatni krok moze „wszystko” zmienic.
Rekursja/rekurencja nadaje sie idealnie do sformulowania rozwiazania problemu DP, ale do rozwiazania DP nie trzeba uzyc rekursji.
Rekursja to tylko sposob obliczen, natomiast w DP odrzucasz po drodze czesc potencjalnych rozwiazan, ktore na pewno wiesz, ze nie beda optymalne i ten sposob oszczedzasz na obliczeniach (czasie). W samej rekursji „nic nie odrzucasz”.
Liczby Fibonacciego są zdefiniowane rekurencyjnie. Liczba n-ta jest sumą dwóch liczb poprzednich, (n – 1)-szej i (n – 2)-giej. Skoro liczby Fibonacciego są zdefiniowane rekurencyjnie, to da się je obliczyć rekurencyjnie. Program jest króciusieńki, ale potrafi się wykonywać (bardzo) długo, bo dla wyznaczenia tysięcznej liczby, np. liczba piąta jest wyznaczana wielokrotnie, zupełnie bez sensu, bo można wyznaczyć raz i zapisać wynik.
.
Można zaimplementować algorytm optymalnego nawiasowania ciągu macierzy w sposób rekurencyjny. I będzie działać, ale wolno, bo mnóstwo rzeczy będzie liczonych wielokrotnie. Można częściowe optymalne wyniki zapisywać i z nich korzystać. Wtedy algorytm, dzięki programowaniu dynamicznemu, będzie wykonywał się dużo dużo szybciej.
Tak, ale u Fibonnaciego nie widze nic wspolnego z originalną ideą Bellmana (oprocz tego ze Fibonacci ladnie ilustruje rekurencje).
„liczba piąta jest wyznaczana wielokrotnie, zupełnie bez sensu, bo można wyznaczyć raz i zapisać wynik.” –
To jest jedyne zauwazenie, ze jak cos juz policzylismy to nie ma sensu liczyc jeszcze raz. Wg mnie NIE jest to DP. U Bellmana „programming” znaczy „algorytm”, a „dynamic” to tylko fajne słowo, zeby zaimponowac zleceniodawcom. Samo „dynamic” nie nie wyjasnia ani nie tłumaczy. U Bellmana najwazniejsza jest zasada optymalnosci ( Bellman’s Principle of Optimality). W tym sensie przyklad z Fibonacci jest trywialny bo nic nie odrzuca (nie musi wybierac czegos optymalnego, bo poprzedni mozliwy stan jest tylko jeden), jedynie ilustruje rekurencje.
Programowanie dynamiczne ma dwie cechy:
(1) optymalność struktury, czyli scalenie optymalnych rozwiązań podzadań daje także optymalne rozwiązanie i
(2) podzadania przynajmniej częściowo się pokrywają, a nawet mogą się powtarzać (wspólne podzadania).
Jeżeli spełniona jest tylko pierwsza cecha, to algorytm jest typu ,,dziel i zwyciężaj” (np. sortowanie szybkie, sortowanie przez scalanie). Jeżeli spełnione są obie cechy, to optymalne rozwiązania powtarzających się podzadań zapisuje się, zamiast powtórnie je rozwiązywać.
Przynajmniej tak to opisuje Cormen w swoim ,,Wprowadzeniu do algorytmów”.
ZORRO I LUCYAN najpierw pisza jakies wlasne zdanie a potem sie z nim nie zgadzaja. Recursywny algorytm jest pokrewny metodzie Bellmana ale nie identyczny. Rowniez liczby Fibonacci nie sa liczone algorytmem dynamicznego programowania. Napisalem o Bellmanie bo jego algorytm tez jest recursywny i byl uzywany do rozwiazan problemow optymalizacji. Ciesze sie ze ten problem poruszony w eseju zainteresowal kilku czytelnikow ale sugeruje aby nawet w dyskusji popularnej matematyki
zachowac pewna precyzje i ostroznosc.
Algorytm Bellmana nie jest rekursywny, moze byc sformulowany i rekursywnie i nierekursywnie.
Rekursja czy iteracja to sposoby rozwiazania problemu ale nie sa to metody na cos same w sobie.
Zreszta, czy nie jest tak ze wszystko co sie da rozwiazac/zapisac rekursywnie, to mozna zapisac iteracyjnie, i vice versa?
„a potem sie z nim nie zgadzaja” – Ja tam nie widze, zebym sobie zaprzeczal.
Sednem Bellmana i DP jest zasada optymalnosci, ale nie wszystkie problemy da sie sformulowac w
ten sposob.
Co redukujemy u Bellmana? Wg mnie redukcja polega na odrzuceniu na kazdym etapie duzej ilosci rozwiązan ktore na pewno nie mogą wchodzi w koncowe optymalne rozwiązanie. Redukcja to chyba nie jest „zredukowanie” problemow na mniejsze, tylko odrzucenie rozwiąan nieoptymalnych.
Widze ( w internecie), ze wielu autorow odstepuje od oryginalej definicji Bellmana i wszystko co sie „rusza”, co sie zmienia, co skraca czas obliczen, nazywają „dynamic programming”. Tam gdzie w problemie nie ma funkcji min czy max to trudno mowic o tradycyjnym DP.
Ogolna idea rekursji polega na rozbiciu duzego problemu sa mniejsze ktore sa tak samo sformulowane .Problem wiezy Hanoi jest dokladnie ilustracja tej metody.Jest to odwleczenie rozwiazania do momentu kiedy skladniki sa male i maja znane rozwiazanie. W wiezy Hanoi zaczynamy od duzej wiezy i zastepujemy go dwoma m niejszymi wierzami . Ten proces jest kontyn uowany az do momentu kiedy rozwiazanie jest wyrazone potezna iloscia prostych problemow z dwoma pierscieniami. Na samym koncu rekursji duzy problem sklada sie z problemow ktorych rozwiazszanie jest znane. To jest idea rekursywnego algorytmu. Oczywiscie problem wiezy mozna rozwiazac iteracyjnie bez rekursji . W algorytmie iteracyjnym mamy regoly przekladania pierscieni. Ilosc ruchow jest identyczna ale proces obliczenia jest rozny. Podczas redakcxji artykulu nastapila zmiana rysunku wiezy .Aby rysunek i tekst pasowaly trzeba nazwac w rysunku lewy pret B, srodkowy A i prawy C. Problem Wiezy jest symetryczny i zmiana nazw trzech pretow z pierscieniami nie robi roznicy w ilosci minimalnych ruchow ale zmienia opis rekursji bo przekladamy z A do C i A jest srodkowym pretem zwanym source Zrodlo a jeden z pozostalych pretow jest destination docedlowym pretem C. Jedna z trudnosci opisu rekursji w tym artykule jest ograniczenie zapisu matematycznego .W normalnym zurnalu matematycznym mozna uzyc jasny zapis (notation) rownan ktory ulatwia zrozumienie.
Czytelnicy ktorzy lubia matematyke i znaja podstawowe
idee matematyki moga sprawdzic ze na przyklad problem z 50 pierscieniami jest zredukowany metoda rekursji do 2(potegi 48)problemow z dwoma pierscieniami z ktorych kazdy wymaga 3 ruchy.Jak duza jest liczba 2(do potegi48)?Jest to okolo 10(do potegi 16) czyli 10 milionow miliardow.
Ta eksplozja ilosci problemow jest cena jaka placimy
zamieniajac duzt y problem z 50 pierscieniami na olbrzymia ilosc prostych problemow .Tu lezy centralna idea rekursywnego algorytmu. Dlatego programy rekursywne wymagaja ostroznego uzycia aby nie
wymagaly zbyt duzej pamieci i operacji.
W matematyce czesto zamieniamy trudny problem na wiele ,miejszych.Jesli ta redukcja powoduje wykladnicza eksplozje to mamy doczynienia z trudnym problemem ktory moze wymagac przyblizonego rozwiazania zamiast rozwiazania dokladnego.
Problem wież z Hanoi to klasyka, jak to mówio. Każdy szanujący się ćwiczeniowiec wspomina go na zajęciach z pierwszoroczniakami na analizie lub na teorii mnogości. To dobre ćwiczenie z indukcji matematycznej. Jednocześnie to elementarz dla każdego studenta specjalności informatyki i piękny przykład problemu z zakresu obliczalności, który ma wpisaną w swoją naturę rekurencyjność. Zapisanie algorytmu dla wież z Hanoi w każdym z podstawowych języków programowania (np. C), to dokładnie trzy linijki. Problem z rekurencją zawsze polegał na tym, że prowadziła do szybkiego stack overflow. Dlatego w celach dydaktycznych zawsze zadawało się studenciakom pisanie na przykład silni iteracyjnie i rekurencyjnie. Współczesny hardware i optymalizacja kompilatorów powodują, że komputer jest pewnie w stanie „łyknąć” większe obliczenia rekurencyjne. Wzorek 2^n-1 to dobry przykład szybko ronącej, bo wykładniczej, złożoności obliczeniowej. Swoją drogą czas dla 64 pierścieni wyszedł mi cirka 37,5 miliarda lat (ale może mi się cuś omskło). Ale to pikuś przy innych funkcjach znanych w teorii obliczalności. Z wykładu z teorii mnogości przypominam sobie osobiście przykład funkcji Ackermanna. Cudeńko. To pierwszy taki skonstruowany przykład funkcji w pełni wyliczalnej i nie należącej do zbioru odwzorowań PR (podstawowo rekursywnych, czy jak tam tłumaczą na polski primitive recursive).