Zapamiętywanie bez tablicy

W Cormen et al .'s Wprowadzenie do algorytmów , sekcja 15.3 Elementy programowania dynamicznego wyjaśniają zapamiętywanie w następujący sposób:

Zapamiętany algorytm rekurencyjny zachowuje pozycję w tabeli dla rozwiązania każdego podproblemu. Każdy wpis w tabeli początkowo zawiera specjalną wartość wskazującą, że wpis musi jeszcze zostać wypełniony. Gdy podproblem zostanie napotkany po rozwinięciu się algorytmu rekurencyjnego, jego rozwiązanie jest obliczane, a następnie zapisywane w tabeli. Za każdym razem, gdy napotykamy ten podproblem, po prostu wyszukujemy wartość przechowywaną w tabeli i zwracamy ją.

I dodaje, w przypisie:

Podejście to zakłada, że ​​znamy zestaw wszystkich możliwych parametrów podproblemów i że ustaliliśmy związek między pozycjami tabeli i podproblemami. Innym, bardziej ogólnym podejściem jest zapamiętywanie za pomocą mieszania z parametrami podproblemu jako kluczami.

Czy są jakieś dobrze znane problemy z DP, które wymagają (lub ułatwiają) zapisywanie zapamiętanych wartości w słowniku zamiast w (wielowymiarowej) tablicy?

Tło: jeśli jest to przydatne, powodem tego pytania jest to, że próbuję uzasadnić pojęcie (samowyważących) drzew wyszukiwania binarnego osobom, które właśnie widziały programowanie dynamiczne.

Prawdopodobnie są lepsze przykłady, ale oto jeden, z góry mojej głowy:

$S,T$$\le d$$>d$

Chciałbym podać 2 przykłady.

0-1 Problem z plecakiem

W przypadku problemu plecakowego 0-1 (gdzie W oznacza pojemność plecaka, a N to ilość przedmiotów), czasem lepiej jest używać odgórnego programowania dynamicznego z zapamiętywaniem, zamiast systematycznego wyliczania od dołu do góry całej tablicy 2D o rozmiarze WxN (szczególnie w przypadku, gdy pojemność plecaka W jest duża, ale liczność zestawu dozwolonych kombinacji wag przedmiotów jest znacznie mniejsza niż W ).

W tym przypadku, ze względu na oszczędność pamięci, można użyć słownika do zapamiętywania zamiast tablicy 2D.

Algorytm parsowania Earleya

Algorytm parsowania Earleya może być wykorzystywany do parsowania instrukcji należących do gramatyki bezkontekstowej. W przeciwieństwie do algorytmu CYK (który opiera się na podejściu DP typu bottom-up i korzysta z tabeli 2D do zapamiętywania) - parser Earley stosuje podejście top-down w połączeniu z tabelą analizy do zapamiętywania.

Tabela analizy zawiera częściowo przeanalizowane produkcje gramatyczne (np .: biorąc pod uwagę produkcję X → AB , a po udanym dopasowaniu części A tej produkcji, przechowujemy częściowo dopasowaną produkcję w tabeli analizy: X → A • B , gdzie kropka wskazuje do już dopasowanej części).

Liczba kolumn w tabeli analizowania równa liczbie tokenów. Jednak w ogólnym przypadku oszacowanie ilości częściowo przeanalizowanych produkcji gramatycznych na kolumnę może być bardzo trudne (zależy to od gramatyki i konkretnej sekwencji tokenów).

Dlatego wygodniej jest wdrożyć tabelę analizującą w oparciu o strukturę danych słownika.

W dziedzinie przetwarzania języka naturalnego zwykle bardziej wygodny jest pareser Earley, ponieważ nie wymaga on normalnej formy Chomsky'ego dla gramatyki (a CYK ma takie wymagania).

Z mojego doświadczenia związanego z programowaniem konkurencyjnym, używanie tablicy skrótów (Python dictlub podobnej) jest często wygodniejsze niż używanie tablicy, ponieważ dowolny klucz danych typu skrótu może być używany jako klucz, taki jak ciągi znaków, zbiory ( frozensetw Pythonie) lub krotki (string, int)itp. Jeśli używasz tablicy, musisz ręcznie przetłumaczyć wszystkie klucze na liczby całkowite (zaczynając od 0), co wymaga dodatkowej pracy i, jak zauważa twoje źródło, może nie być możliwe, jeśli nie znasz z góry miejsca na klucze. Słowniki są więc bardziej ogólne niż tablice.

Oczywiście, jeśli można uniknąć używania tablic, jest to prawdopodobnie szybsze, ponieważ unika się wielokrotnego obliczania skrótów (z drugiej strony wymaga najpierw zainicjowania całej tablicy, co zajmuje czas i pamięć), ale napisanie kodu może potrwać dłużej ponieważ musisz wykonać dodatkową pracę, tłumacząc wszystkie klucze na liczby całkowite.