Ciąg Fibonacciego i programowanie dynamiczne

Poproś komputer o 40. liczbę Fibonacciego w najprostszy sposób, a wykona ponad 331 milionów wywołań. Poproś o nią z użyciem tablicy, a wystarczy mu 39 dodawań. Ta różnica to programowanie dynamiczne, a prawie każdy spotyka je po raz pierwszy właśnie przy liczbach Fibonacciego.

Rząd komórek tablicy z liczbami Fibonacciego; wypełniana komórka jest pomarańczowa, a dwie komórki, które dodaje, są niebieskie
Rząd komórek tablicy z liczbami Fibonacciego; wypełniana komórka jest pomarańczowa, a dwie komórki, które dodaje, są niebieskie

Problem

Liczby Fibonacciego zaczynają się od 0, 1, a każda kolejna liczba jest sumą dwóch poprzednich: 0, 1, 1, 2, 3, 5, 8, 13, 21 i tak dalej. Zapisane jako reguła: F(0) = 0, F(1) = 1 i F(n) = F(n − 1) + F(n − 2). Reguła jest rekurencyjna i łatwo zamienić ją wprost w program rekurencyjny, ale taki program okazuje się bardzo wolny.

Dlaczego rekurencja się powtarza

Aby znaleźć F(5), program prosi o F(4) i F(3). F(4) prosi o F(3) i F(2), więc F(3) jest obliczane dwa razy, F(2) trzy razy, a F(1) pięć razy. Narysowane jako drzewo, wywołania niemal podwajają się na każdym poziomie, a łącznie F(n) wymaga 2·F(n + 1) − 1 wywołań. Mniejsze problemy nakładają się: te same wracają wciąż od nowa. To znak, że programowanie dynamiczne pomoże.

Dwa sposoby zapamiętywania

Memoizacja zachowuje rekurencję, ale zapisuje każdą odpowiedź w tablicy, a każde wywołanie zagląda do tablicy, zanim cokolwiek obliczy. Tablicowanie wypełnia tablicę od dołu: najpierw F(0) i F(1), potem z nich F(2), F(3) z F(2) i F(1) i tak dalej aż do F(n). Tak czy inaczej każdy wyraz jest obliczany raz, więc F(n) kosztuje n − 1 dodawań zamiast wykładniczej liczby wywołań.

Przykład

Metoda wstępująca dla F(7): zacznij od 0 i 1. Potem 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 i 5 + 8 = 13, więc F(7) = 13 po sześciu dodawaniach. Zwykła rekurencja wykonałaby 2·F(8) − 1 = 41 wywołań, aby uzyskać tę samą odpowiedź. W metodzie zstępującej pierwsze wywołania schodzą aż do F(1) wzdłuż lewej krawędzi drzewa; w drodze powrotnej prawie co drugie wywołanie znajduje odpowiedź już w tablicy.

Skąd pochodzi nazwa

Richard Bellman nadał nazwę programowaniu dynamicznemu na początku lat 50. XX wieku, gdy pracował w RAND Corporation. Później napisał, że wybrał słowo „programowanie” w dawnym znaczeniu planowania, a „dynamiczne”, bo brzmiało imponująco i trudno było mu cokolwiek zarzucić. Sama metoda, czyli rozwiązywanie problemu za pomocą odpowiedzi na jego mniejsze wersje, działa dziś w korektorach pisowni, planerach tras i porównywaniu DNA.

Richard Bellman w 1962 roku, fotografia Alfreda Eisenstaedta. Nazwał programowanie dynamiczne na początku lat 50., gdy pracował w RAND Corporation.
Richard Bellman w 1962 roku, fotografia Alfreda Eisenstaedta. Nazwał programowanie dynamiczne na początku lat 50., gdy pracował w RAND Corporation.

Sprawdź w praktyce

Otwórz aplikację i naciśnij Krok. W metodzie Wstępująca pomarańczowa komórka jest właśnie wypełniana, a dwie niebieskie komórki to wyrazy, które dodaje. Przełącz na Zstępująca i obserwuj, jak stos wywołań pod tablicą rośnie do n, a potem maleje, gdy wracają odpowiedzi; podpowiedź pod kafelkiem Dodawania pokazuje, ile wywołań dostało odpowiedź prosto z tablicy.

Często zadawane pytania

Czym są nakładające się podproblemy?

To mniejsze problemy, których rozwiązanie potrzebuje więcej niż raz. F(n) i F(n − 1) potrzebują F(n − 2), więc zwykła rekurencja oblicza je dwa razy, a niżej marnotrawstwo się mnoży. Programowanie dynamiczne rozwiązuje każdy z nich raz i zapamiętuje odpowiedź.

Czy memoizacja jest szybsza od tablicowania?

Obie wykonują te same dodawania. Tablicowanie jest zwykle trochę szybsze, bo nie wykonuje wywołań i nie może mu zabraknąć miejsca na stosie; memoizacja przydaje się, gdy potrzebne są tylko niektóre mniejsze odpowiedzi, bo oblicza tylko je.

Czy liczby Fibonacciego można obliczać jeszcze szybciej?

Tak. Dzięki wzorom F(2k) = F(k)·(2·F(k + 1) − F(k)) oraz F(2k + 1) = F(k)² + F(k + 1)² metoda szybkiego podwajania potrzebuje tylko około log₂ n kroków. Wzór Bineta ze złotą proporcją daje te same liczby, ale błędy zaokrągleń sprawiają, że dla dużych n jest zawodny.

Ile pamięci potrzebuje tablica?

Pełna tablica przechowuje n + 1 liczb, ale każdy nowy wyraz potrzebuje tylko dwóch poprzednich, więc pętla, która pamięta dwie liczby, wykonuje to samo zadanie w stałej pamięci. Przechowywanie całej tablicy przydaje się, gdy chcesz mieć wszystkie wyrazy albo zobaczyć, jak działa metoda.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj liczby Fibonacciego z programowaniem dynamicznym