ćwiczenie programowania dynamicznego na cięciach

Pracowałem nad następującym problemem z tej książki .

Pewien język przetwarzania ciągów oferuje prymitywną operację, która dzieli ciąg na dwie części. Ponieważ ta operacja polega na skopiowaniu oryginalnego ciągu, n zajmuje ciąg n jednostek czasu o długości n, niezależnie od lokalizacji cięcia. Załóżmy teraz, że chcesz rozbić sznurek na wiele części. Kolejność wykonywania przerw może mieć wpływ na całkowity czas działania. Na przykład, jeśli chcesz wyciąć 20-znakowy ciąg znaków na pozycjach $3$ i $10$ , to wykonanie pierwszego cięcia na pozycji $3$ wiąże się z całkowitym kosztem $20 + 17 = 37$ , podczas gdy wykonanie pozycji 10 ma lepszy koszt $20 + 10 = 30$.

Potrzebuję algorytmu programowania dynamicznego, który dał $m$ cięciom, znajdował minimalny koszt cięcia sznurka na $m +1$ kawałków.

Podstawową ideą jest: Wypróbuj wszystkie pozycje cięcia jako pierwszy wybór, rozwiązuj rekurencyjnie odpowiednie części, dodaj koszty i wybierz minimum.

We wzorze:

$\qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\ &\operatorname{mino}(s_{c+1,|s|}, \{c' - c \in C \mid c' > c\}) \end{align}\right] &, \text{ else} \end{cases}$

Zauważ, że zastosowanie zapamiętywania do tej rekurencji faktycznie oszczędza pracę, ponieważ zmiana kolejności dowolnej kolejno stosowanej pary cięć powoduje rozwiązanie tych samych trzech podproblemów.

Zawsze dobrze jest najpierw znaleźć algorytm rekurencyjny, a następnie przekształcić go w tabelę.

1. $f(C,n)$
2. $~~$jeśli (C = ) zwraca 0;$\emptyset$
3. $~~$jeszcze
4. $~~~~$opt = nieskończoność;
5. $~~~~$dla każdego do$c\in C$
6. $~~~~~~D=\{d\in C:d<c\}$
7. $~~~~~~E=\{e-c:e\in D,e>c\}$
8. $~~~~~~opt = min\{opt,f(D,c)+f(E,n-c)\}$
9. $~~~~$return ;$opt+n$

Więc możesz zapytać: czy nie ma zbyt wielu podzbiorów C, które można by umieścić w tabeli? Zauważ, że potrzebne są tylko „kolejne” podzbiory. I są tylko z nich (dlaczego) Innym problemem jest:.? Niektóre wpisy zmieni wartość wE. Możemy to obejść, wskazując początek i koniec każdegof,a nie tylko określając długość.$n \choose 2$$E$$f$

Jest to bardzo podobne do Quicksort na wielu zestawach; jest optymalny, gdy punkt cięcia znajduje się najbliżej środka, a następnie wracamy.

$s_k$