Quelles propriétés devrait avoir le problème afin que je puisse décider quelle méthode utiliser la programmation dynamique ou la méthode gourmande?Solutions aux problèmes d'utilisation de la programmation dynamique ou des méthodes gourmandes?
Les problèmes de programmation dynamique présentent une sous-structure optimale. Cela signifie que la solution au problème peut être exprimée en fonction de solutions à des sous-problèmes strictement plus petits. Un exemple d'un tel problème est le matrix chain multiplication.
Les algorithmes gourmands ne peuvent être utilisés que lorsqu'un choix localement optimal conduit à une solution totalement optimale. Cela peut être plus difficile à voir tout de suite, mais généralement plus facile à mettre en œuvre car vous n'avez qu'une seule chose à considérer (le choix gourmand) au lieu de multiple (les solutions à tous les petits sous-problèmes).
Un algorithme glouton célèbre est Kruskal's algorithm pour trouver un arbre recouvrant minimum.
Tout problème pouvant être résolu par récursion "peut être exprimé en fonction de solutions à des sous-problèmes strictement plus petits". Pour que le DP soit applicable, un problème doit avoir à la fois une sous-structure optimale * et des sous-problèmes qui se chevauchent. La dernière partie est ce qui fait qu'il vaut la peine de stocker les solutions aux sous-problèmes déjà résolus. +1 lorsque vous mentionnez ceci. –
Il y a une règle très stricte pour le savoir. Comme quelqu'un l'a déjà dit, il y a certaines choses qui devraient allumer le feu rouge, mais à la fin, seule l'expérience sera en mesure de vous le dire.
La deuxième édition du livre Algorithmes de Cormen, Leiserson, Rivest et Stein comporte une section (16.4) intitulée «Fondements théoriques des méthodes avides» qui traite du moment où les méthodes gloutonnes donnent une solution optimale. Il couvre de nombreux cas d'intérêt pratique, mais tous les algorithmes gloutons qui donnent des résultats optimaux ne peuvent pas être compris en termes de cette théorie. J'ai aussi rencontré un article intitulé "De la programmation dynamique aux algorithmes gourmands" lié here qui parle de certains algorithmes gourmands peut être vu comme des raffinements de programmation dynamique. D'un balayage rapide, il peut vous intéresser.
Nous appliquons la méthode gourmande quand une décision peut être prise sur l'information locale disponible à chaque étape. Nous sommes sûrs que suite à l'ensemble des décisions à chaque étape, nous trouverons la solution optimale. Cependant, dans l'approche dynamique, nous pouvons ne pas être sûr de prendre une décision à un moment donné, donc nous portons un ensemble de décisions probables, l'un des éléments probables pouvant mener à une solution.
ressemble un peu à une question de devoirs. –