Quelle est la différence entre une programmation dynamique et une approche gourmande?

basé sur les articles de Wikipédia.

Approche Gourmande

un algorithme cupide est un algorithme qui suit la résolution de problème heuristique de faire localement choix optimal à chaque étape avec l'espoir de trouver un optimum global. Dans beaucoup de problèmes, une stratégie avide ne produit pas en général une solution optimale, mais néanmoins un heuristique avide peut produire localement des solutions optimales qui se rapprochent d'une solution globale optimale dans un raisonnable temps.

nous pouvons faire n'importe quel choix qui semble le meilleur pour le moment et ensuite résoudre les sous-problèmes qui surgissent plus tard. Le choix fait par un algorithme glouton peut dépendre des choix faits jusqu'à présent mais pas sur les choix futurs ou toutes les solutions au sous-problème. Il fait itérativement un choix gourmand après l'autre, réduisant chaque problème donné dans un plus petit.

programmation Dynamique

l'idée derrière la programmation dynamique est assez simple. En général, pour résoudre un problème donné, nous avons besoin pour résoudre les différentes parties du problème (sous-problèmes), puis combiner les solutions des sous-problèmes pour obtenir une solution globale. Souvent, lorsque l'utilisation d'une méthode plus naïve, beaucoup de sous-problèmes sont générés et résolus de nombreuses fois. L'approche de programmation dynamique cherche à résoudre chaque sous-problème une seule fois, réduisant ainsi le nombre de calculs: une fois la solution à un le sous-problème a été calculé, il est stocké ou "memo-ised": la prochaine fois que la même solution est nécessaire, il est simplement recherché. Cette approche est particulièrement utile lorsque le nombre de répétition de sous-problèmes croît de façon exponentielle en fonction de la taille de l'entrée.

Différence

Gourmand choix de la propriété

nous pouvons faire n'importe quel choix qui semble le meilleur pour le moment et ensuite résoudre les sous-problèmes qui surgissent plus tard. Le choix fait par un algorithme glouton peut dépend des choix faits jusqu'à présent, mais pas des choix futurs ou de toutes les solutions au sous-problème. Il fait itérativement un choix gourmand après l'autre, réduisant chaque problème donné dans un plus petit. En d'autres termes, un algorithme Cupide ne reconsidère jamais ses choix.

C'est la principale différence par rapport à la programmation dynamique, qui est exhaustive et garantie de trouver la solution. Après chaque étape, la programmation dynamique prend des décisions basées sur toutes les décisions prises dans le précédent et peut reconsidérer le chemin algorithmique de l'étape précédente vers la solution.

par exemple, disons que vous devez aller du point a au point B aussi vite que possible, dans une ville donnée, pendant les heures de pointe. Un algorithme de programmation dynamique examinera l'ensemble du rapport de trafic, en étudiant toutes les combinaisons possibles de routes que vous pourriez prendre, et vous indiquera seulement alors quel chemin est le plus rapide. Bien sûr, vous pourriez avoir à attendre un certain temps jusqu'à ce que l'algorithme termine, et seulement alors tu peux commencer à conduire. Le chemin que vous prendrez sera la plus rapide (en supposant que rien n'a changé dans l'environnement externe).

d'un autre côté, un algorithme cupide vous permettra de commencer à conduire immédiatement et de choisir la route qui semble la plus rapide à chaque intersection. Comme vous pouvez l'imaginer, cette stratégie pourrait ne pas conduire à l'heure d'arrivée la plus rapide, car vous pourriez prendre quelques rues "faciles" et puis se retrouver désespérément coincé dans un embouteillage.

Certains d'autres détails...

Dans l'optimisation mathématique, algorithmes cupides résoudre des problèmes combinatoires ayant les propriétés de matroids.

programmation Dynamique est applicable aux problèmes présentant le propriétés des sous-problèmes de chevauchement et de la sous-structure optimale.