Co to jest programowanie dynamiczne?

Jeśli chodzi o programowanie komputerowe, programowanie dynamiczne jest równie wszechstronne, co matematyczne. Richard Bellman stworzył tę technikę w latach 50. i od tego czasu znalazła zastosowanie we wszystkim, od inżynierii lotniczej po ekonomię.

W obu kontekstach słowo to odnosi się do podzielenia skomplikowanego tematu na łatwe do opanowania fragmenty. Wieloletnie decyzje zwykle rozpadają się rekurencyjnie. W informatyce problem ma optymalną podstrukturę, jeśli można go optymalnie rozwiązać, dzieląc go na podproblemy i rekurencyjnie znajdując najlepsze rozwiązania.

Istnieje związek między wartością głównego problemu a wartościami podproblemów, jeśli podproblemy mogą być rekurencyjnie zagnieżdżane w głównym problemie, a do rozwiązania głównego problemu można zastosować techniki programowania dynamicznego. W dziedzinie optymalizacji równanie Bellmana jest dobrze znanym sposobem mówienia o tym konkretnym powiązaniu dla lepszej strategii.

Możesz nauczyć się inżynierii oprogramowania za pomocą kursów online.

Optymalizacja matematyczna

Dzięki rozłożeniu złożonego wyboru na szereg przyrostowych, jak ma to miejsce w programowaniu dynamicznym, problem optymalizacji matematycznej może być znacznie łatwiejszy do opanowania dla operacji. Aby to osiągnąć, definiujemy zestaw funkcji wartości V1, V2,…, Vn, z których każda przyjmuje y jako argument opisujący stan systemu w pewnym momencie I od 0 do n. Vn(y) to wartość w czasie n, która została uzyskana ze stanu y. Wykorzystując połączenie rekurencyjne zwane równaniem Bellmana, możemy wyznaczyć wartości Vi w poprzednich okresach I = n1, n2,…, 2, 1. Maksymalizując prostą funkcję (często sumę) korzyści z wyboru w czasie I 1 i funkcji Vi w nowym stanie układu, możemy wyprowadzić Vi1 w dowolnym stanie y z Vi, gdzie I = 2,…, n. Ta procedura zwraca Vi1 dla wymaganych stanów, ponieważ Vi zostało już dla nich obliczone. I wreszcie, optymalna wartość rozwiązania, V1, znajduje się w warunkach początkowych systemu. Odtwarzając kroki z wcześniejszych obliczeń, optymalne wartości wybranych zmiennych mogą być pobierane pojedynczo.

Aby programowanie dynamiczne było użyteczne, problem musi mieć dwie cechy: optymalną podstrukturę i nakładające się podproblemy. Termin „dziel i zwyciężaj” jest używany w odniesieniu do techniki, w której trudność jest dzielona na mniejsze, niezależne problemy, a następnie rozwiązywana poprzez łączenie najlepszych odpowiedzi na każdy z nich. Dlatego nie uważamy sortowania przez scalanie i sortowanie szybkie za trudności w programowaniu dynamicznym.

Program certyfikacji inżynierii oprogramowania może poprawić twoje umiejętności.

Problem optymalizacji z optymalną podstrukturą można rozwiązać, łącząc rozwiązania jego podproblemów. Idealne podstruktury są zwykle definiowane za pomocą rekurencji. Każdy wierzchołek pośredni wygrał najkrótszą ścieżkę p od wierzchołka u do wierzchołka v w grafie G=(V,E) jest przykładem optymalnej podstruktury. Jeśli ścieżka p jest najkrótsza, można ją podzielić na dwie ścieżki, p1 od u do w i p2 od w do v, które są również najkrótsze między odpowiednimi parami wierzchołków. Tak więc algorytmy Bellmana-Forda i Floyda-Warshalla wykorzystują rekurencję do znajdowania najkrótszych ścieżek.

Jaka jest logika stosowania metody programowania dynamicznego?

Procedura programowania dynamicznego wygląda następująco:

1. W ten sposób zmniejsza złożoność wszystkich aspektów pierwotnego wydania.
2. Aby rozwiązać te mniejsze problemy, określa najlepszą możliwą odpowiedź.
3. Śledzi rozwiązania mniejszych wyzwań (zapamiętywanie). Zapamiętywanie to akt zapamiętywania rozwiązań mniejszych problemów.
4. Przetwarza je w taki sposób, że ta sama część problemu może być rozwiązana kilka razy.
5. Po tym wszystkim musisz znaleźć odpowiedź na trudne pytanie.

1. Optymalne podstruktury i zagadnienia z nakładającymi się podproblemami. W tym kontekście termin „optymalna podstruktura” odnosi się do metody, za pomocą której można rozwiązać problemy optymalizacyjne poprzez integrację najlepszych rozwiązań ich składowych podproblemów.
2. Ponieważ wyniki pośrednie muszą być przechowywane, złożoność przestrzenna programowania dynamicznego rośnie nawet wtedy, gdy spada złożoność czasowa.