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

19

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?

Computernerd
źródło
1
Warunki drogowe to czerwony śledź. Możesz rozważyć je w dowolnym algorytmie.
Yuval Filmus
Twój pierwszy cytat nie definiuje programowania dynamicznego.
reinierpost
@reinierpost Cóż, stara się tam dotrzeć intelligent, brute force, ale potem zapomina opisać „inteligentną” część
Izkata
@Izkata Zgodnie z tym rozumowaniem każdy algorytm jest „inteligentną brutalną siłą” (zresztą oksymoronem).
Raphael

Odpowiedzi:

17

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Θ(n2))(n-1)!

Raphael
źródło
„To stwierdzenie jest po prostu błędne” - Napraw to .
nmclean
4
@nmclean Moje doświadczenia z edytowaniem artykułów związanych z algorytmem na Wikipedii były mniej niż przyjemne, więc nie. Wolę zainwestować tu swój czas.
Raphael
Próbowałem szczęścia i zredagowałem artykuł. Mam nadzieję, że teraz jest mniej źle.
C4stor
9

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.

Tuszar
źródło
9
To jest zapamiętywanie , które jest tylko jedną z wielu sztuczek, które stosuje DP.
Ben Voigt,
4
Brutalna siła z zapamiętywaniem jest wciąż nieefektywna; tylko dodatkowa struktura / przycinanie zapewniane przez powtarzające się DP powoduje, że zapamiętywanie jest opłacalne.
Raphael
3
Nie wiem nic o programowaniu dynamicznym, ale jestem pewien, że jest w tym coś więcej niż tylko dodawanie pamięci podręcznych do algorytmu brute-force. Myślę, że programowanie dynamiczne unika testowania każdej możliwej kombinacji, dzieląc przestrzeń problemową, znajdując optymalne rozwiązanie dla każdego małego podziału, a następnie łącząc je, aby stworzyć ogólnie najlepsze rozwiązanie. (Może to robić rekurencyjnie, nurkowanie pod-dywizje). Działa to tylko wtedy, gdy można wyrazić problem w sposób, który pozwala na kombinację takich rozwiązań i nadal uzyskać ogólne optymalne.
Jonathan Hartley,
1
Ta odpowiedź jest właściwie dość dokładna. Radzę przeczytać podręcznik taki jak Cormen i in .: „Wprowadzenie do algorytmów”, aby dowiedzieć się więcej o programowaniu dynamicznym, ta książka zawiera całkiem przyzwoity rozdział. W skrócie, wydajne programowanie dynamiczne wykorzystuje dwie właściwości problemu (optymalizacji), który chcesz rozwiązać: optymalne rozwiązania można zbudować z optymalnych rozwiązań mniejszych podproblemów, a całkowita liczba mniejszych podproblemów jest raczej raczej mały. Następnie możesz zbudować wszystkie rozwiązania podprogramów oddolnie, przyspieszając obliczenia kosztem pamięci.
MRA
Lub, mówiąc prościej: jeśli wiesz, jak obliczyć współczynnik dwumianowy za pomocą trójkąta Pascala , wiesz wszystko, co musisz wiedzieć o programowaniu dynamicznym.
MRA
3

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.

ttt+1t

Yuval Filmus
źródło
A potem jest usunięcie kandydata z rozpatrzenia bez pełnego przetworzenia. Na przykład, znajdując zbiór liczb nieujemnych z minimalną sumą, tak naprawdę nie musisz sumować każdego zestawu całkowicie, tylko idź, aż suma przekroczy bieżącą najlepszą. Jest to podobny pomysł do przycinania, ale ortogonalny. Połączenie tych dwóch pomysłów daje „odgałęzienie”, w którym problem zmniejszonej złożoności zostaje rozwiązany i wykorzystany do uzasadnienia przycinania.
Ben Voigt,
0

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.

DW
źródło
5
To konsekwencja, a nie wyjaśnienie.
Raphael
-2

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.

nomen
źródło
„Jeśli nie ma rozwiązania w przestrzeni wyszukiwania, programowanie dynamiczne (zwykle) przeszukuje każdy element przestrzeni wyszukiwania”. - źle, zobacz moją odpowiedź.
Raphael
-2

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.

Tal
źródło
1
„będziesz używał brutalnej siły, aby rozwiązać każdy mały kawałek” - źle. Zazwyczaj będziesz stosować to samo podejście rekurencyjnie.
FrankW