Czym różni się programowanie dynamiczne od siły Brute?

Czytałem o Programowaniu dynamicznym, kiedy natknąłem się na następujący cytat

Algorytm programowania dynamicznego zbada wszystkie możliwe sposoby rozwiązania problemu i wybierze najlepsze rozwiązanie. Dlatego z grubsza możemy myśleć o programowaniu dynamicznym jako inteligentnej metodzie brutalnej siły, która pozwala nam przejść przez wszystkie możliwe rozwiązania, aby wybrać najlepsze . Jeśli zakres problemu jest taki, że przejście przez wszystkie możliwe rozwiązania jest możliwe i wystarczająco szybkie, programowanie dynamiczne gwarantuje znalezienie optymalnego rozwiązania

Podano następujący przykład

Załóżmy na przykład, że musisz dotrzeć z punktu A do punktu B tak szybko, jak to możliwe, w danym mieście, w godzinach szczytu. Algorytm programowania dynamicznego zajmie się całym raportem drogowym, sprawdzając wszystkie możliwe kombinacje dróg, którymi możesz się udać, i dopiero wtedy powie ci, która droga jest najszybsza. Oczywiście być może będziesz musiał poczekać chwilę, aż algorytm się skończy, i dopiero wtedy możesz rozpocząć jazdę. Ścieżka, którą wybierzesz, będzie najszybsza (przy założeniu, że w środowisku zewnętrznym nic się nie zmieniło)

Brute Force wypróbowuje wszystkie możliwe rozwiązania, zanim zdecyduje się na najlepsze rozwiązanie.

Czym różni się Programowanie dynamiczne od Brute Force, jeśli przechodzi przez wszystkie możliwe rozwiązania przed wybraniem najlepszego , jedyną różnicą, którą widzę, jest to, że Programowanie dynamiczne bierze pod uwagę dodatkowe czynniki (w tym przypadku warunki na drodze).

Czy mam rację twierdząc, że Programowanie Dynamiczne jest podzbiorem metody Brute Force?

Algorytm programowania dynamicznego zbada wszystkie możliwe sposoby rozwiązania problemu i wybierze najlepsze rozwiązanie.

To stwierdzenie jest po prostu błędne.

Dynamiczne nawroty programowania czy (często) rozważenia wszystkich możliwych sposobów, aby podzielić danej instancji problemu na mniejsze przypadkach według pewnego schematu. Jednak nie połączy ze sobą wszystkich rozwiązań wszystkich częściowych problemów i wybierze najlepsze - łączy tylko optymalne rozwiązania częściowe (i wybiera najlepsze z nich).

Fakt, że daje to optymalne rozwiązanie pierwotnego problemu, nie jest trywialny i w rzeczywistości dotyczy tylko niektórych problemów. Mianowicie te, które spełniają zasadę optymalności Bellmana (jedna z najbardziej podejrzanych, niezrozumianych „definicji”, które są regularnie cytowane). Zobacz tutaj więcej przemyśleń na ten temat.

Jako konkretny przykład rozważmy algorytm Bellmana-Forda na pełnym wykresie z wagami jednostkowymi: zawsze uwzględnia ścieżki o długości jeden i dwa (tj. Θ ( n 2 ) wiele), ponieważ te, które używają jednej krawędzi, są optymalne . Ale istnieje nieskończenie wiele rozwiązań, jeśli nie ograniczysz maksymalnej dozwolonej liczby krawędzi i nadal ≫ ( n - 1 ) ! wielu, jeśli zezwolisz na użycie każdego węzła tylko raz. Tak więc wyraźnie, Bellman-Ford - algorytm programowania dynamicznego - nie wykonuje wyszukiwania metodą brute-force.$K_n$$\Theta(n^2)$$\gg (n-1)!$

Programowanie dynamiczne jest sprytne, ponieważ wykorzystuje ponownie obliczenia, podczas gdy brutalna siła nie. Załóżmy, że rozwiązujesz, f (6), musisz rozwiązać 2 podproblemy, które oba wywołują f (3). Metoda brutalnej siły obliczy f (3) dwa razy, marnując w ten sposób wysiłek, podczas gdy programowanie dynamiczne wywoła ją raz, zachowując wynik na wypadek, gdyby przyszłe obliczenia z niego skorzystały. W wielu problemach dynamika poprawia wykładniczą złożoność brutalnej siły do ​​złożoności wielomianowej.

W artykule w Wikipedii można rozróżnić trzy typy algorytmów:

1. Algorytmy, które obejmują wszystkie możliwe rozwiązania, wybierając optymalne.

2. Algorytmy, które przechodzą przez podzbiór wszystkich możliwych rozwiązań, wybrane tak, aby optymalne rozwiązanie należało do tego podzbioru.

3. Algorytmy, które przechodzą przez podzbiór wszystkich możliwych rozwiązań, bez gwarancji, że optymalne rozwiązanie należy do tego podzbioru.

Dwa pierwsze typy algorytmów dają optymalne rozwiązanie, podczas gdy trzeci typ ma na celu stworzenie „dobrego” rozwiązania, a nie rozwiązania optymalnego. Moim zdaniem rozróżnienie między dwoma pierwszymi rodzajami nie jest tak wyraźne.

Zacznę od podania prostych przykładów dla wszystkich trzech rodzajów algorytmów, w kontekście najkrótszej ścieżki (podany przykład).

1. Wypróbuj wszystkie możliwe ścieżki. Jest to znane jako brutalna siła .

2. Wypróbuj wszystkie możliwe ścieżki, śledząc jak dotąd minimalne rozwiązanie. Ilekroć budowana obecnie ścieżka jest droższa niż dotychczasowe minimalne rozwiązanie, porzuć ją i wybierz inną (wyobrażamy sobie, że odległość jest obliczana na podstawie segmentów). Nazywa się to przycinaniem .

3. Spójrz na mapę, rozważ kilka ścieżek i wybierz najlepszą spośród nich. Jest to algorytm dla człowieka, a nie komputera.

Te przykłady są dość prymitywne i być może nie malują bardzo dokładnego obrazu. Przycinanie ma kluczowe znaczenie w wielu sytuacjach, na przykład w szachach komputerowych. Jeśli jesteś ciekawy, poszukaj algorytmu A ^* , który jest faktycznie używany do najkrótszej ścieżki.

Programowanie dynamiczne to technika znacznego przyspieszenia algorytmu brutalnej siły. Jednak myślenie o tym w ten sposób jest nieco mylące. Jest to technika algorytmiczna do rozwiązywania problemów optymalizacyjnych. Przycinanie można wdrożyć w kontekście programowania dynamicznego.

$t$$t$$t+1$$t$

Programowanie dynamiczne jest znacznie szybsze niż brutalna siła. Brutalna siła może zająć wykładniczy czas, podczas gdy programowanie dynamiczne jest zwykle znacznie szybsze.

Analogia do brutalnej siły jest bardzo luźna. Programowanie dynamiczne nie jest magiczną srebrną kulą, która pozwala wziąć dowolny algorytm brutalnej siły i uczynić go wydajnym.

To jest proste. Programowanie dynamiczne to „strategia wyszukiwania”, która wykorzystuje dodatkowe czynniki w celu zawężenia wyszukiwania. Jeśli nie ma rozwiązania w przestrzeni poszukiwań, programowanie dynamiczne będzie (zazwyczaj) do wyszukiwania przez każdego elementu przestrzeni poszukiwań. Ale to nie znaczy, że jest to brutalne poszukiwanie siły.

Stwierdzenie, że programowanie dynamiczne jest inteligentną brutalną siłą, jest poprawne, ale z tym sformułowaniem jest nieco trudne do zrozumienia. Celem programowania dynamicznego jest na ogół podjęcie problemu i rozbicie go na mniejsze części w inteligentny sposób. Po wykonaniu tej czynności użyjesz brutalnej siły, aby rozwiązać każdy mały kawałek, a następnie ponownie użyjesz brutalnej siły, aby połączyć kawałki w ostateczne rozwiązanie. Tak więc, choć zdecydowanie można powiedzieć, że programowanie dynamiczne jest rodzajem brutalnej siły, sztuczka polega na tym, jak użyć tej brutalnej siły.