Teoretyczne podstawy podziału i podboju

Przy projektowaniu algorytmów często stosuje się następujące techniki:

• Programowanie dynamiczne
• Chciwa strategia
• Dziel i rządź

Podczas gdy w przypadku dwóch pierwszych metod istnieją dobrze znane podstawy teoretyczne, a mianowicie zasada optymalności Bellmana i teoria matroidów (odpowiednio greedoid), nie mogłem znaleźć takiej ogólnej struktury algorytmów opartych na D&C.

Po pierwsze, zdaję sobie sprawę z czegoś, co my (a raczej prof) wprowadziliśmy do funkcjonalnej klasy programowania, zwanej „szkieletem algorytmicznym”, która powstała w kontekście kombinatorów. Jako przykład podaliśmy taki szkielet algorytmów D&C w następujący sposób:

Definicja : Niech będą niepustymi zbiorami. Nazywamy elementy rozwiązań , a elementy (to znaczy podzbiory ) są nazywane problemami . Następnie szkielet D & C to 4-krotka , gdzie:$A,S$$S$ $P:=\mathfrak{P}(A)$$A$$(P_\beta, \beta, \mathcal{D}, \mathcal{C})$

• $P_\beta$ jest predykatem w stosunku do zestawu problemów i mówimy, że problem jest podstawowy iff utrzymuje.$p$$P_\beta(p)$
• $\beta$ to mapowanie które przypisuje rozwiązanie każdego podstawowego problemu.$P_\beta \rightarrow S$
• $\mathcal{D}$ to mapowanie które dzieli każdy problem na zestaw podproblemów.$P \rightarrow \mathfrak{P}(P)$
• $\mathcal{C}$ jest mapowaniem który łączy rozwiązania (w zależności od rodzaju „problemu przestawnego”) podproblemów w celu uzyskania rozwiązania.$P\times \mathfrak{P}(S) \rightarrow S$

Następnie dla danego szkieletu i problemu , następująca funkcja ogólna oblicza rozwiązanie (w formalnym sens) dla :p f s : P → S $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$$p$$f_s: P\rightarrow S$$p$

$f_s(p)= \left\{ \begin{array}{l l} \beta(p) & \quad \text{if $p$ is basic}\\ \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise} \end{array} \right.$

gdzie w drugim wierszu używamy zapisu dla podzbiorów kodomainy odwzorowania .X $f(X) := \{f(x) : x\in X\}$$X$$f$

Jednak nie zbadaliśmy dalej podstawowych „strukturalnych” właściwości problemów, które można sformułować w ten sposób (jak powiedziałem, była to funkcjonalna klasa programowania i to był tylko mały przykład). Niestety nie mogłem znaleźć dalszych odniesień do tego właśnie podejścia. Dlatego nie sądzę, aby powyższe definicje były dość standardowe. Jeśli ktoś rozpozna to, co powiedziałem powyżej, byłbym zadowolony z powiązanych artykułów.

Po drugie, w przypadku chciwej strategii mamy słynny wynik, że ogólny algorytm zachłanności poprawnie rozwiązuje problem tylko wtedy, gdy jego rozwiązania stanowią ważoną matroidę. Czy istnieją podobne wyniki dla algorytmów D i C (niekoniecznie oparte na metodzie opisanej powyżej)?

Formalne traktowanie podmiotu (nieco przypominające model zaproponowany w pytaniu) przy użyciu tak zwanych pseudomorfizmów (czyli funkcji, które są prawie morfizmami, z pewnymi wykonanymi przed i po obliczeniach), a także rozważania dotyczące złożoności analiza i równoległa implementacja takich algorytmów są podane w:

Model algebraiczny podziału i podboju oraz jego równoległość autorstwa Zhijing G. Mou i Paula Hudaka (w The Journal of Supercomputing , tom 2, wydanie 3, str. 257-278, listopad 1988)

Nie znam czegoś tak konkretnego, jak zasada optymalności Bellmana dla algorytmów dzielenia i podbijania. Jednak podstawową zasadą dziel i zwyciężaj wydaje mi się rekurencyjna (lub indukcyjna) definicja wkładu problemu, a następnie sposób łączenia rozwiązań problemu z większymi rozwiązaniami. Kluczowy wgląd tutaj polega na rekurencyjnym myśleniu o problemach i wykorzystaniu ich w rekurencyjnych algorytmach D&C.

$n$

• $n=0$
• $n=1$
• $n>1$$\lceil{\frac{n}{2}}\rceil$$\lfloor{\frac{n}{2}}\rfloor$

$n\leq1$

Należy zauważyć, że nie musi to prowadzić do tego, czego oczekujesz od algorytmów D&C. Możemy zdefiniować strukturę tablicy w następujący sposób:

• $n=0$
• $n>0$$n-1$

Postępując zgodnie z tą samą strategią, którą zastosowaliśmy tutaj w przypadku scalania, prowadzi się do sortowania rekurencyjnego. Tak więc zazwyczaj opracowujemy definicje rekurencyjne, które obejmują wiele elementów rekurencyjnych, tj. Przecinamy zestaw danych na pół lub trzeci.

Obecnie istnieje Master Theorem do analizy algorytmów D&C, co rzuca nieco światła na oczekiwania dotyczące wydajności dla podelementów algorytmu D&C o szczególnej ogólnej wydajności w czasie wykonywania.