ćwiczenie programowania dynamicznego na cięciach

16

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.

znak
źródło

Odpowiedzi:

10

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:

mino(s,C)={|s|,|C|=1|s|+mincC[mino(s1,c,{cCc<c}) + mino(sc+1,|s|,{ccCc>c})], else

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.

Raphael
źródło
1

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;
  3.   jeszcze
  4.     opt = nieskończoność;
  5.     dla każdego docC
  6.       D={dC:d<c}
  7.       E={ec:eD,e>c}
  8.       opt=min{opt,f(D,c)+f(E,nc)}
  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ść.(n2)Ef

Dimitar Stratiev
źródło
0

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

sk

KWillets
źródło