En quoi la programmation dynamique est-elle différente de la force brute

19

Je lisais sur la programmation dynamique lorsque je suis tombé sur la citation suivante

Un algorithme de programmation dynamique examinera toutes les façons possibles de résoudre le problème et choisira la meilleure solution. Par conséquent, nous pouvons grosso modo penser la programmation dynamique comme une méthode intelligente, par force brute, qui nous permet de passer par toutes les solutions possibles pour choisir la meilleure . Si l'ampleur du problème est telle que passer par toutes les solutions possibles est possible et assez rapide, la programmation dynamique garantit de trouver la solution optimale

L'exemple suivant a été donné

Par exemple, disons que vous devez vous rendre du point A au point B le plus rapidement possible, dans une ville donnée, aux heures de pointe. Un algorithme de programmation dynamique examinera l'intégralité du rapport de circulation, en examinant toutes les combinaisons possibles de routes que vous pourriez emprunter, et ne vous indiquera alors que le chemin le plus rapide. Bien sûr, vous devrez peut-être attendre un certain temps jusqu'à ce que l'algorithme se termine, et ce n'est qu'alors que vous pourrez commencer à conduire. Le chemin que vous emprunterez sera le plus rapide (en supposant que rien n'a changé dans l'environnement externe)

Brute Force essaie toutes les solutions possibles avant de décider de la meilleure solution.

En quoi la programmation dynamique est-elle différente de Brute Force si elle passe également par toutes les solutions possibles avant de choisir la meilleure , la seule différence que je vois est que la programmation dynamique prend en compte les facteurs supplémentaires (conditions de circulation dans ce cas).

Ai-je raison de dire que la programmation dynamique est un sous-ensemble de la méthode Brute Force ??

Ballot d'ordinateur
la source
1
Les conditions de circulation sont un hareng rouge. Vous pouvez les considérer dans n'importe quel algorithme.
Yuval Filmus
Réponse connexe .
Raphael
Votre premier devis ne définit pas la programmation dynamique.
reinierpost
@reinierpost Eh bien, il essaie d'y arriver intelligent, brute force, mais oublie ensuite de décrire la partie "intelligente"
Izkata
@Izkata Par ce raisonnement, chaque algorithme est une "force brute intelligente" (qui est de toute façon un oxymore).
Raphael

Réponses:

17

Un algorithme de programmation dynamique examinera toutes les façons possibles de résoudre le problème et choisira la meilleure solution.

Cette déclaration est tout simplement fausse.

Récurrences de programmation dynamique ne (souvent) d' examiner tous les moyens possibles pour diviser l'instance de problème donné dans des cas plus petits selon un système. Cependant, il ne combinera pas toutes les solutions à tous les problèmes partiels les uns avec les autres et choisira les meilleures - il ne combine que des solutions partielles optimales (et sélectionne les meilleures d'entre elles).

Le fait que cela donne une solution optimale pour le problème d'origine n'est pas anodin et ne vaut en fait que pour certains problèmes. À savoir ceux qui remplissent le principe d'optimalité de Bellman (l'une des «définitions» les plus louche et incomprise qui sont régulièrement citées). Voir ici pour plus de réflexions à ce sujet.

À titre d'exemple concret, considérons l' algorithme de Bellman-Ford sur un graphique complet avec des poids unitaires: il ne prend en compte que les chemins de longueur un et deux (c'est-à-dire Θ ( n 2 ) plusieurs) car ceux qui utilisent un bord sont tous optimaux . Mais il existe une infinité de solutions si vous ne limitez pas le nombre maximum d'arêtes autorisé, et toujours ( n - 1 ) ! plusieurs si vous autorisez chaque nœud à être utilisé une seule fois. Il est donc clair que Bellman-Ford - un algorithme de programmation dynamique - n'effectue pas de recherche par force brute.KnΘ(n2)(n1)!

Raphael
la source
"Cette déclaration est tout simplement fausse" - Corrigez-la .
nmclean
4
@nmclean Mon expérience avec l'édition d'articles sur les algorithmes sur Wikipedia a été moins qu'agréable, donc non. Je préfère investir mon temps ici.
Raphael
J'ai tenté ma chance et édité l'article. J'espère que c'est un peu moins mal maintenant.
C4stor
9

La programmation dynamique est intelligente car elle réutilise le calcul, contrairement à la force brute. Supposons que pour résoudre, f (6), vous devez résoudre 2 sous-problèmes qui appellent tous les deux f (3). La méthode de la force brute calculera f (3) deux fois, gaspillant ainsi l'effort tandis que la programmation dynamique l'appellera une fois, sauvegardez le résultat au cas où de futurs calculs devraient l'utiliser. Dans de nombreux problèmes, la dynamique améliore la complexité exponentielle de la force brute en complexité polynomiale.

Tushar
la source
9
C'est la mémorisation , qui n'est qu'une des nombreuses astuces que DP utilise.
Ben Voigt
4
La force brute avec mémoisation est toujours inefficace; seules les structures / élagages supplémentaires fournis par les récidives du DP font que la mémoisation est payante.
Raphael
3
Je ne connais rien à la programmation dynamique, mais je suis presque sûr qu'il y a plus que l'ajout de caches à un algorithme de force brute. Je pense que la programmation dynamique évite de tester toutes les combinaisons possibles en subdivisant l'espace du problème, en trouvant une solution optimale pour chaque petite subdivision, puis en les combinant pour créer une meilleure solution globale. (Il peut le faire récursivement, en plongeant les sous-divisions.) Cela ne fonctionne que si vous pouvez exprimer le problème d'une manière qui permet une combinaison de solutions comme celle-ci tout en obtenant un optimum global.
Jonathan Hartley
1
Cette réponse est en fait assez précise. Je conseille de lire un manuel comme Cormen et al: "Introduction aux algorithmes" pour en savoir plus sur la programmation dynamique, ce livre a un chapitre assez décent à ce sujet. En résumé, une programmation dynamique efficace utilise deux propriétés du problème (d'optimisation) que vous souhaitez résoudre: des solutions optimales peuvent être construites à partir des solutions optimales de sous-problèmes plus petits, et le nombre total de sous-problèmes plus petits est en fait plutôt petit. Ensuite, vous pouvez créer toutes les solutions de sous-problèmes de façon ascendante, accélérant le calcul au détriment de la mémoire.
MRA
Ou, pour le dire en termes encore plus simples: si vous savez comment calculer un coefficient binomial en utilisant le triangle de Pascal, vous savez tout ce que vous devez savoir sur la programmation dynamique.
MRA
3

La distinction que l'article Wikipedia essaie peut-être de faire est entre trois types d'algorithmes:

  1. Des algorithmes qui passent en revue toutes les solutions possibles, en choisissant la meilleure.

  2. Algorithmes qui parcourent un sous-ensemble de toutes les solutions possibles, choisis pour que la solution optimale appartient au sous-ensemble.

  3. Algorithmes qui parcourent un sous-ensemble de toutes les solutions possibles, sans la garantie que la solution optimale appartient au sous-ensemble.

Les deux premiers types d'algorithmes produisent la solution optimale, tandis que le troisième type vise à produire une «bonne» solution plutôt qu'une solution optimale. À mon avis, la distinction entre les deux premiers types n'est pas aussi nette.

Permettez-moi de commencer par donner des exemples simples pour les trois types d'algorithmes, dans le contexte du chemin le plus court (l'exemple que vous donnez).

  1. Essayez tous les chemins possibles. C'est ce qu'on appelle la force brute .

  2. Essayez tous les chemins possibles, en gardant une trace de la solution minimale jusqu'à présent. Chaque fois que le chemin actuel que vous construisez est plus cher que la solution minimale jusqu'à présent, abandonnez-le et choisissez-en un autre (nous imaginons que la distance est calculée segment par segment). C'est ce qu'on appelle l' élagage .

  3. Regardez la carte, considérez quelques chemins et choisissez le meilleur parmi eux. Il s'agit d'un algorithme pour un humain plutôt que pour un ordinateur.

Ces exemples sont plutôt grossiers et ne donnent peut-être pas une image très précise. L'élagage est crucial dans de nombreuses situations, par exemple dans les échecs informatiques. Si vous êtes curieux, recherchez l' algorithme A * , qui est en fait utilisé pour le chemin le plus court.

La programmation dynamique est une technique permettant d'accélérer considérablement l'algorithme de force brute. Il est cependant quelque peu trompeur de penser de cette façon. Il s'agit d'une technique algorithmique pour résoudre les problèmes d'optimisation. Vous pouvez implémenter l'élagage dans le contexte de la programmation dynamique.

ttt+1t

Yuval Filmus
la source
Et puis il y a retirer un candidat de la considération sans le traiter complètement. Par exemple, pour trouver l'ensemble de nombres non négatifs avec la somme minimale, vous n'avez pas réellement à additionner chaque ensemble complètement, allez seulement jusqu'à ce que la somme dépasse la meilleure valeur actuelle. C'est une idée similaire à l'élagage mais orthogonale. La combinaison des deux idées donne des "ramifications et des liaisons", où un problème de complexité réduite est résolu et utilisé pour justifier l'élagage.
Ben Voigt
0

La programmation dynamique est beaucoup plus rapide que la force brute. La force brute peut prendre un temps exponentiel, tandis que la programmation dynamique est généralement beaucoup plus rapide.

L'analogie avec la force brute est très vague. La programmation dynamique n'est pas une solution miracle qui vous permet de prendre n'importe quel algorithme de force brute que vous souhaitez et de le rendre efficace.

DW
la source
5
C'est une conséquence, pas une explication.
Raphael
-2

C'est simple. La programmation dynamique est une «stratégie de recherche» qui utilise des facteurs supplémentaires pour affiner une recherche. S'il n'y a pas de solution dans l'espace de recherche, programmation dynamique sera ( en général) effectuer une recherche dans tous les éléments de l'espace de recherche. Mais cela ne signifie pas qu'il s'agit d'une recherche par force brute.

pas d'hommes
la source
"S'il n'y a pas de solution dans l'espace de recherche, la programmation dynamique effectuera (généralement) une recherche dans tous les éléments de l'espace de recherche." - mal, voir ma réponse.
Raphael
-2

L'affirmation selon laquelle la programmation dynamique est une force brute intelligente est correcte, mais un peu difficile à comprendre avec cette formulation. Le but de la programmation dynamique est généralement de prendre un problème et de le décomposer en petits morceaux de manière intelligente. Après avoir fait cela, vous utiliserez la force brute pour résoudre chaque petit morceau, puis vous utiliserez à nouveau la force brute pour combiner les morceaux dans une solution finale. Donc, bien que vous puissiez certainement dire que la programmation dynamique est un type de solution de force brute, l'astuce réside dans la façon dont vous utilisez cette force brute.

Tal
la source
1
"vous utiliserez la force brute pour résoudre chaque petit morceau" - faux. Vous utiliserez généralement la même approche de manière récursive.
FrankW