Decydowanie o problemach podrzędnych dla programowania dynamicznego

Wielokrotnie korzystałem z techniki programowania dynamicznego, ale dzisiaj mój przyjaciel zapytał mnie, jak zabrać się do definiowania moich pod-problemów, zdałem sobie sprawę, że nie mam możliwości udzielenia obiektywnej formalnej odpowiedzi. Jak formalnie zdefiniować pod-problem dotyczący problemu, który rozwiązalibyście za pomocą programowania dynamicznego?

algorithms dynamic-programming jozefg
źródło

Wygląda na to, że żadna z istniejących odpowiedzi (z kwietnia 2019 r.) Nie jest wystarczająco dobra, szczególnie dla początkujących. Poleciłbym tutoriale na innych stronach.

Apass.Jack

Odpowiedzi:

Zasadą programowania dynamicznego jest myślenie z góry na dół (tzn. Rekurencyjnie), ale rozwiązywanie z dołu do góry. Tak więc dobrą strategią projektowania DP jest rekurencyjne formułowanie problemu i generowanie w ten sposób podproblemów.

Suresh
źródło

Twierdzę, że to jedyna strategia.

JeffE

@JeffE Tak, czytałem i korzystałem z twoich notatek podczas nauczania moich klas algorytmów i było to skuteczne. Cytat: „Dynamika nie polega na wypełnianiu tabel. Chodzi o inteligentną rekurencję!”

Dai,

Na moje zrozumienie tego, jak uczyć DPs, MOCNIE wpływają notatki @ JeffE :)

Suresh

Możliwe jest również automatyczne przekształcenie z góry na dół procedury rekurencyjnej w algorytm programowania dynamicznego. Kiedy masz zamiar wrócić, zapisz odpowiedź w tabeli skrótów. Na początku każdego połączenia sprawdź, czy odpowiedź znajduje się już w tabeli skrótów, a jeśli tak, zwróć ją natychmiast. Wiele algorytmów staje się łatwych dzięki temu pomysłowi. Na przykład przy takiej tabeli algorytmy rekurencyjne przy próbach automatycznie działają na DAWG. Przechowując wartość wartownika w tabeli na początku połączenia, te same algorytmy mogą działać nawet na DFA. Algorytmy na BDD stają się bardzo łatwe do określenia rekurencyjnie.

Jules

Last but not least, może to mieć ogromne zalety w zakresie wydajności. Na przykład tradycyjny algorytm sumy podzbiorów typu bottom-up może obliczać tony niepotrzebnych wpisów tabeli. Dzięki tej metodzie obliczane będą tylko niezbędne wpisy tabeli.

Jules

Jak zauważył @Suresh, kiedy już wiesz, że twój problem może zostać rozwiązany przez DP (tj. Wykazuje optymalną podbudowę i nakładające się na siebie podproblemy), możesz pomyśleć o podzieleniu i pokonaniu rekurencyjnego rozwiązania.

Oczywiście dzielenie i podbijanie będzie wysoce nieefektywne, ponieważ każdy podproblem napotkany w powiązanym drzewie rekurencyjnym zostanie rozwiązany ponownie, nawet jeśli został już znaleziony i rozwiązany. Tutaj różni się DP: za każdym razem, gdy napotkasz podproblem, rozwiążesz go i zapiszesz w tabeli. Później, gdy ponownie spotkasz się z tym podproblemem, uzyskasz dostęp w czasie jego rozwiązania, zamiast go rozwiązać ponownie. Ponieważ liczba nakładających się podproblemów jest zwykle ograniczona wielomianem, a czas wymagany do rozwiązania jednego podproblemu jest również wielomianowy (w przeciwnym razie DP nie może zapewnić opłacalnego rozwiązania), można uzyskać rozwiązanie wielomianowe. $\mathcal{O}(1)$

Dlatego zastanowienie się nad rozwiązaniem typu „dziel i zwyciężaj” zapewni ci wgląd w to, jakie może być podproblemem dla twojego konkretnego problemu.

Massimo Cafaro
źródło

„optymalna podbudowa” (cokolwiek to oznacza) prawdopodobnie nie jest wystarczającym warunkiem dla rozpuszczalności DP. „Nakładające się na siebie podproblemy” z pewnością nie są konieczne.

Raphael

Zarówno optymalna podbudowa, jak i nakładające się na siebie problemy występują w problemach, które DP może skutecznie rozwiązać. Oczywiście sama optymalna podbudowa nie wystarcza do rozpuszczalności DP. Jeśli jednak nie masz nakładających się podproblemów, możesz rozwiązać problem przez zwykłe dzielenie i podbijanie przy takich samych kosztach: w rzeczywistości przewaga DP nad dzieleniem podboju polega na tym, że każdy podproblem jest rozwiązany dokładnie raz, gdy napotka się go w drzewie rekurencji .

Massimo Cafaro

To nie jest moje sformułowanie: znajdziesz je w „Wprowadzenie do algorytmów” Cormen, Leiserson, Rivest i Stein oraz w wielu innych podręcznikach na temat algorytmów.

Massimo Cafaro

Jup, a większość jest co najmniej częściowo w błędzie. Z przyjemnością opracuję, jeśli zadacie odpowiednie pytanie.

Raphael

Nie jestem pewien, czy dobrze rozumiem twój ostatni komentarz. Aby pokazać, że tego rodzaju charakterystyka jest błędna (nie może być częściowo błędna: albo jest poprawna, ani błędna), możesz po prostu pokazać jako kontrprzykład, problem, który nie wykazuje zarówno optymalnej podbudowy, jak i nakładających się podproblemów, a jednak jest podatny na wielomianowe rozwiązanie DP. Zauważ jednak, że w tym kontekście oznacza to rozwiązanie, które jest o wiele lepsze niż zwykłe dzielenie i podbijanie.

Massimo Cafaro

Moje doświadczenie polega na znalezieniu sposobu na „zmniejszenie zbędnego wyliczania za pomocą przechowywania użytecznej wartości już wyliczonej”. Nawiasem mówiąc, Programowanie dynamiczne jest bardzo popularne w ICPC (International Collegiate Programming Contest). Każdy może mieć własne zdanie na temat DP po przećwiczeniu kilku problemów ICPC.

Peng Zhang
źródło