Studia informatyka – Programowanie dynamiczne

Programowanie dynamiczne

Podejście do rozwiązywania problemów, wykorzystujące rozwiązania podproblemów do efektywnego rozwiązywania większych problemów.

Podproblem

Mniejsza wersja oryginalnego problemu, która jest łatwiejsza do rozwiązania i często pojawia się wielokrotnie.

Przykład problemu

Problem plecakowy: Optymalizacja wartości przedmiotów w plecaku o ograniczonej pojemności.

Zasada optymalności

Wyniki optymalne dla podproblemów prowadzą do rozwiązania optymalnego dla całego problemu.

Tablica pamięci

Struktura danych używana do przechowywania wyników podproblemów w programowaniu dynamicznym, aby uniknąć ich ponownego obliczania.

Funkcja rekurencyjna

Funkcja, która wywołuje sama siebie w celu rozwiązania podproblemów.

Budowa algorytmu

Składa się z definicji podproblemów, rekursji i łączenia wyników w celu uzyskania rozwiązania końcowego.

Przykład zastosowania

Obliczanie sekwencji Fibonacciego: $\displaystyle F(n) = F(n-1) + F(n-2)$, z pamięcią na wyniki.

Złożoność czasowa

Zwykle $\displaystyle O(n^2)$ lub lepsza, w zależności od implementacji algorytmu dynamicznego.

Algorytm Bellmana-Forda

Algorytm do znajdowania najkrótszych ścieżek w grafie z ujemnymi wagami krawędzi.

Rozwiązywanie problemu

Trzeba zdefiniować funkcję rekurencyjną i określić, kiedy można użyć wyników zapamiętanych.

Rodzaje problemów

Problemy optymalizacyjne, kombinatoryczne, a także zadania w grafach i ciągach.

Przykład algorytmu

Algorytm Knapsack: $\displaystyle K(i, w) = ext{max}(K(i-1, w), K(i-1, w-w_i) + v_i)$.

Wydajność

Programowanie dynamiczne jest zwykle bardziej wydajne niż podejścia brute-force ze względu na eliminację powtarzających się obliczeń.

Problem najdłuższego wspólnego podciągu

Oblicza najdłuższy wspólny podciąg dla dwóch ciągów, używając tablicy 2D do przechowywania wyników.

Uzupełnij zdanie: Algorytmy programowania dynamicznego są najczęściej stosowane w...

...problemach optymalizacji, takich jak plecak, najkrótsze ścieżki w grafach oraz w analizie ciągów.

Przykład z życia

Optymalizacja trasy dostaw w logistyce, gdzie celem jest minimalizacja kosztów transportu.

Różnica między DP a algorytmem zachłannym

DP rozwiązuje problem, dzieląc go na mniejsze, natomiast algorytm zachłanny podejmuje lokalne decyzje, które nie zawsze prowadzą do optymalnego rozwiązania.

Funkcja kosztu

Określa koszt rozwiązania danego podproblemu, kluczowa w dynamicznym programowaniu.

Przykład działania

Dla problemu plecakowego: zdefiniować wartości i wagi przedmiotów, a następnie obliczyć maksymalną wartość przy danej pojemności plecaka.

Zastosowanie w AI

Programowanie dynamiczne znajduje zastosowanie w strategiach gier, gdzie optymalizuje ruchy w oparciu o możliwe odpowiedzi przeciwnika.

Algorytm Floyd-Warshall

Służy do znajdowania najkrótszych ścieżek w grafie z n wierzchołkami, złożoność $\displaystyle O(n^3)$.

Prawda czy fałsz: Dynamic programming zawsze daje optymalne rezultaty.

Prawda, ponieważ opiera się na zasadzie optymalności.

Zastosowanie w bioinformatyce

Analiza sekwencji DNA, porównywanie z wykorzystaniem algorytmów najdłuższego wspólnego podciągu.

Przykład problemu transformacji

Obliczanie minimalnej liczby operacji potrzebnych do przekształcenia jednego ciągu w drugi.

Złożoność pamięciowa

Można ją zredukować, stosując podejście oparte na pamięci ograniczonej, zamiast tablic 2D.

Zastosowanie ekonomiczne

Optymalizacja wydatków w budżetach projektów i przewidywanie zysków.

Różnica między DP a brute-force

Brute-force bada wszystkie możliwe kombinacje, podczas gdy DP wykorzystuje zapamiętane wyniki.

Uzupełnij zdanie: W programowaniu dynamicznym kluczowe jest...

...zdefiniowanie podproblemów oraz ich relacji, aby móc efektywnie wykorzystać wyniki.