Rekurencje i funkcje generujące w algorytmach

Kombinatoryka odgrywa ważną rolę w informatyce. Często stosujemy metody kombinatoryczne zarówno w analizie, jak i projektowaniu w algorytmach. Na przykład jedna metoda znajdowania zestawu okładek $k$ -vertex na wykresie może po prostu sprawdzić wszystkie możliwe podzbiory . Podczas gdy funkcje dwumianowe rosną wykładniczo, jeśli jest jakąś stałą stałą, w wyniku analizy asymptotycznej otrzymujemy algorytm wielomianowy.$\binom{n}{k}$$k$

Często rzeczywiste problemy wymagają bardziej złożonych mechanizmów kombinatorycznych, które możemy zdefiniować w kategoriach nawrotów. Jednym znanym przykładem jest sekwencja Fibonacciego (naiwnie) zdefiniowana jako:

$f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \\ f(n-1) + f(n-2) & \text{otherwise} \end{cases}$

Teraz obliczenie wartości $n$ tego terminu rośnie wykładniczo przy tej rekurencji, ale dzięki programowaniu dynamicznemu możemy obliczyć ją w czasie liniowym. Teraz nie wszystkie rekurencje nadają się do DP (z ręki, funkcja czynnikowa), ale jest to potencjalnie użyteczna właściwość, gdy określa się, że niektóre liczą się jako rekurencja, a nie funkcja generująca.

Generowanie funkcji to elegancki sposób sformalizowania pewnej liczby dla danej struktury. Być może najbardziej znaną jest funkcja generowania dwumianowego zdefiniowana jako:

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Na szczęście ma to rozwiązanie w formie zamkniętej. Nie wszystkie funkcje generujące pozwalają na tak zwięzły opis.

Teraz moje pytanie brzmi: jak często generowane są funkcje wykorzystywane w projektowaniu algorytmów? Łatwo jest zobaczyć, jak można je wykorzystać do zrozumienia tempa wzrostu wymaganego przez algorytm za pomocą analizy, ale co mogą nam powiedzieć o problemie podczas tworzenia metody rozwiązania jakiegoś problemu?

Jeśli wiele razy ta sama liczba może zostać przeformułowana jako powtórzenie, może ulec programowaniu dynamicznemu, ale znowu być może ta sama funkcja generująca ma postać zamkniętą. Więc nie jest tak równomiernie cięty.

Funkcje generujące są przydatne podczas projektowania algorytmów liczenia. Oznacza to, że nie tylko szukasz liczby obiektów mających określoną właściwość, ale także szukasz sposobu wyliczenia tych obiektów (i być może wygenerowania algorytmu zliczania obiektów). Bardzo dobra prezentacja znajduje się w rozdziale 7 konkretnej matematyki autorstwa Ronalda Grahama, Donalda Knutha i Orena Patashnika . Poniższe przykłady pochodzą z tych książek (błędy i brak jasności są moje).

Załóżmy, że szukasz sposobów na zmianę za pomocą danego zestawu monet. Na przykład w przypadku wspólnych nominałów amerykańskich¹ możliwe monety to . Aby dać ¢ 42 w zamian, jedną z możliwości jest ; inną możliwością jest . Napiszemy . Mówiąc bardziej ogólnie, możemy napisać funkcję generującą dla wszystkich sposobów wprowadzania zmian: w bardziej technicznych[ 25 ] [ 10 ] [ 5 ] [ 1 ] [ 1 ] [ 10 ] [ 10 ] [ 10 ] [ 10 ] [ 1 ] [ 1 ] 42 ⟨ [ 25 ] [ 10 $[1], [5], [10], [25], [100]$$[25][10][5][1][1]$$[10][10][10][10][1][1]$H = Σ H ≥ 0 Σ q ≥ 0 Σ d ≥ 0 Σ n ≥ 0 Σ s ≥ 0 [ 100 ] H [ 25 ] q [ 10 ] d [ 5 ] n [ 1 ] $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$

$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$ [ 100 ] , [ 25 ] , [ 10 ] , [ 5 ] , [ 1 ] ⟨ [ 100 ] H [ 25 ] q [ 10 ] d [ 5 ], N [ 1 ] s ⟩ = 100 H + 25 P + 10 d + 5 n + p v v H $H$ jest terminem w przestrzeni szeregów mocy dla pięciu zmiennych$[100], [25], [10], [5], [1]$. Zdefiniuj wycenę monomialu w tej przestrzeni przez Zatem sposobami podania centów w zamian jest liczba monomialów, których wyceną jest . Możemy wyrazić w sposób przyrostowy, pisząc najpierw, w jaki sposób daje zmianę tylko w groszach, a potem w jaki sposób daje zmianę w groszach i monetach i tak dalej. ( myśli brak monety). $$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$ $v$$v$$H$$P$I P = I + [ 1 ] + [ 1 ] 2 + [ 1 ] 3 + … = $N$$I$ $$\begin{gather*} P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\ N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\ D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\ Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\ H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\ \end{gather*}$$ Jeśli chcesz liczyć, a nie tylko wyliczyć sposoby wprowadzania zmian, istnieje prosty sposób na wykorzystanie uzyskanych przez nas serii formalnych. Zastosuj homomorfizm Współczynnik w to liczba sposobów podania centów w zamian. $$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100}$$ $X^v$$S(C)$$v$

Trudniejszy przykład: załóżmy, że chcesz przestudiować wszystkie sposoby układania prostokątów domino 2 × 1. Na przykład istnieją dwa sposoby na ułożenie prostokąta 2 × 2 za pomocą dwóch poziomych domino lub dwóch pionowych domino. Zliczanie liczby sposobów na kafelkowanie prostokąta jest dość łatwe, ale przypadek szybko staje się nieoczywisty. Możemy wyliczyć wszystkie możliwe nachylenia poziomego pasma wysokości 3, sklejając domino razem, co szybko daje powtarzalne wzory: $2 \times n$$3 \times n$

$$\begin{cases} U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\ V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\ \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\ \end{cases}$$ gdzie śmieszne kształty reprezentują elementarne aranżacje domina: to nie domino, to pionowe domino na górze lewej części poziomego domina, to pionowe domino wyrównane do dolnej części pasma o wysokości 3, to poziome domino wyrównane do górnej części pasma plus dwa poziome domino poniżej i jeden krok w prawo, itd. Mnożenie reprezentuje konkatenację poziomą i nie jest przemienne, ale istnieją równania między wzorcami elementarnymi, które tworzą zmienne w tej serii mocy. Tak jak poprzednio w przypadku monet, możemy zastąpić każdym domino i uzyskać serię generującą liczbę przechyleń$\mathsf{o}$$\mathsf{L}$$\substack{\strut\\\mathsf{I}}$$\substack{\:-\\=}$$X$$3 \times (2n/3)$Prostokąt (tj. Współczynnik to liczba sposobów na ułożenie prostokąta o powierzchni , która zawiera domina i ma szerokość ). Z tej serii można również korzystać w bardziej uniwersalny sposób; na przykład, rozróżniając domino pionowe i poziome, możemy liczyć przechylenia z określoną liczbą domino pionowych i poziomych.$X^{3k}$$6k$$3k$$2k$

Ponownie przeczytaj Matematykę konkretną, aby uzyskać mniej pochopną prezentację.

¹ _{Wiem, że moja lista jest niekompletna; Załóżmy, że USA są uproszczone i odpowiednie dla przykładów matematycznych.}
² ² _{Także, jeśli się pojawi, załóż monety sferyczne.}
³ _{I lepszy skład.}

Pamiętam problem, który musiałem rozwiązać podczas konkursu programistycznego w 2001 roku. Problem był następujący:

Biorąc pod uwagę masy 1, 7, 13, ... (Nie pamiętam, które masy, ale był skończony, określony zbiór mas), zaprojektuj funkcję, która określa, czy daną masę można ważyć za pomocą tej wagi zestaw mas.

Zacząłem od zagnieżdżonych pętli, ale szybko uderzyłem w ścianę. Potem zdałem sobie sprawę, że musiałem zacząć od wyliczenia, co można zrobić z lżejszymi masami, zanim zacznę z cięższymi. Mógłbym rozwiązać problem z dużą ilością nieotwartych pętli.

Gdybym w tym czasie nie był młodzieńczo arogancki i samowystarczalny (i gdybym wiedział i ćwiczył funkcje generowania), mógłbym zdefiniować problem z generowaniem funkcji jako takich:

Zdefiniuj jako OGF dla wielu sposobów ważenia masy przy danym zbiorze mas.$f(x)$$n$

Jaką wagę na prawej szalce mogę zważyć przy pojedynczej masie 1?

Trzy możliwości:

• Jeśli położę masę na lewej patelni, mogę zważyć 1.
• Jeśli położę masę na prawej szalce, mogę zważyć -1.
• Jeśli nie użyję masy, mogę zważyć 0.

Jest więc jeden sposób ważenia , jeden sposób ważenia i jeden sposób ważenia . Funkcja generująca dla tej masy to coś w rodzaju , co odpowiada:$-1$$0$$1$$x^{-1} + 1 + x$

$$\frac{1 - x^3}{x(1-x)}$$

Funkcja generująca dla pojedynczej masy to , co oznacza:$m$$x^{-m} + 1 + x^m$

$$\frac{1 - x^{3m}}{x^m(1-x^m)}$$

Biorąc pod uwagę wielokrotność mas, wyraża się jako iloczyn funkcji generujących pojedynczą masę:$M$$f$

$$f(x) = \frac{\prod_{m \in M}(1 - x^{3m})}{x^{\sum_{m \in M}m}\prod_{m \in M}(1 - x^{m})}$$

Teraz, biorąc pod uwagę pakiet, który może wykonywać operacje na wielomianach, wystarczy:

• Oblicz oba produkty.
• Dokonaj podziału tych produktów, zaczynając od najniższego stopnia. (która kończy się)
• $x^k$

$w \ge 0$$w$$M$

Algorytm zaprojektowałem przy użyciu matematycznie poprawnych komponentów. Główna część algorytmu, która jest podziałem wielomianowym o najniższym stopniu jako pierwszym, jest liniowa i może być zaimplementowana w gotowym pakiecie. Może nie jest optymalny, ale z pewnością działa lepiej niż to, co zrobiłem na zawodach i w mniej podatny na błędy sposób.

Jeśli przyjrzysz się uważnie procesowi podziału, szybko zauważysz, że reszta może być postrzegana jako „bieżący stan ukryty” w każdym stanie procesu, a iloraz jako wynik. Proces kończy się, gdy „bieżący stan ukryty” wszędzie osiąga zero.

Możesz implementować wielomiany jako tablice lub, jeśli są one naprawdę rzadkie, jako listy uporządkowane według współczynnika indeksu, a to nie zmieni algorytmu.

$$\ell \gamma^{(m)}_{\ell+1} = (2\ell-m) \gamma^{(m)}_\ell + (m - \ell + 1) \gamma^{(m)}_{\ell-1}, \quad \gamma^{(m)}_0 = 1, \quad \gamma^{(m)}_{m+1} = e.$$ $\gamma^{(m)}_\ell = m(\gamma^{(m-1)}_\ell - \gamma^{(m-1)}_{\ell-1})$$\gamma^{(0)}$$\gamma^{(m)}$, ponownie za pomocą funkcji generujących. Możesz znaleźć rozwiązanie w gazecie, jeśli jesteś ciekawy, chociaż nigdy nie zadaliśmy sobie trudu, aby zawrzeć tę pochodną.

Być może najobszerniejszym przykładem jest obszerne studium Quicksort i jego wielu wariantów. Istnieją rozważania kombinatoryczne rządzące rozważaniem alternatyw, a analiza rozwiązań dość skomplikowanych równań wykazuje zalety (lub nie) wydajności.