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