Programmation Dynamique
J'utilise un tableau qui, pour chaque borne (entre 0 et 100) et chaque état possible (nombre de chevaux vivants et quantité de nourriture), me dit si je peux arriver à la fin ou non.
Les éléments de ce tableau sont reliés par une récurrence. Actions possibles
Je remplis le tableau itérativement (ordre décroissant de nombre de kilomètres parcourus et ordre croissant de nombre de chevaux).
Le résultat souhaité est déterminé facilement du tableau final.
Facile à généraliser à calculer aussi (une) stratégie valable pour chaque situation d'où je peux sortir.
le temps de calcul aurait été déterminé par le nombre de façons de commencer le voyage
sans doute plusieures minutes de calcul
que la programmation dynamique a réduits à une fraction d'une seconde.
Le temps pour visiter les derniers i villes dépend de quelles villes elles sont et d'où il se trouve après la (n-i)ième visite
forme générale de la récurrence:
V(E,i) = minj ∈
E-i(c(i,j)+V(E-i,j))
La programmation dynamique ne donne pas d'algorithme très performant mais aucun meilleur n'est connu qui garantit de donner toujours le parcours optimal.
Si, en outre, chaque élément d'une colonne ne
dépend que des
éléments de l'autre colonne qui sont en dessus (ou en
dessous),
il suffit de garder une colonne qui, à chaque moment, peut
contenir
un partie de l'ancienne colonne et une partie de la nouvelle!
(vrai pour la traversée, le sac-à-dos et peut-être
le voyageur)
Placer des fonds dans des placements de haut, moyen ou bas risque de façon à maximiser les bénéfices (en moyenne) mais sous une contrainte de résultat garanti:
Pour chaque placement, décider s'il est permis
(c'est-à-dire si dans
le pire des cas on est garanti de finir avec les 1200 euros au moins);
si oui évaluer la moyenne des résultats finaux pour
toutes les
possibilités de la prochaine année;
et, bien sûr, choisir le placement qui donne le meilleur moyen et
noter que ce placement est optimal dans cette situation.
En ce cas, la programmation dynamique comme décrite fait des calculs inutiles qui n'auraient pas été faits par la méthode récursive citée avant. Mais il est toujours vrai que cette méthode récursive fait BEAUCOUP plus de calculs parce qu'elle fait très souvent le même calcul plusieurs fois.
Il existe une méthode mixte qui ne fait que les calculs utiles et ne les fait qu'une fois: elle consiste à utiliser la structure récursive et un tableau; la première fois qu'un résultat est calculé il est inséré dans le tableau; les fois suivants, cette valeur est récupérée du tableau.
Nécessite une méthode de savoir quels éléments du tableau contiennent des résultats valables; ou une valeur impossible pour les non valables ou un tableau auxiliaire booléen.