Programmation dynamique et probabilités

Question

Je regarde ce problème depuis des heures et je suis toujours aussi perdu qu'au début. Cela fait un moment que j'ai pris des maths ou des statistiques discrètes alors j'ai essayé de regarder des vidéos sur youtube, mais je n'ai rien trouvé qui m'aiderait à résoudre le problème en moins de temps qui semble exponentiel. Tous les conseils sur la façon d'aborder le problème ci-dessous seraient très appréciés!

Une certaine espèce de fougère prospère dans les régions pluvieuses luxuriantes, où il pleut généralement presque tous les jours. Cependant, une sécheresse est attendue au cours des prochains jours, et une équipe de botanistes est préoccupée par la survie de l'espèce à travers la sécheresse. Plus précisément, l'équipe est convaincue de l'hypothèse suivante: la population de fougères survivra si et seulement s'il pleut au moins n/2 jours au cours de la sécheresse n-day . En d'autres termes, pour que l'espèce survive, il doit y avoir au moins autant de jours pluvieux que les jours non pluvieux . Les experts météorologiques locaux prédisent que la probabilité qu'il pleuve un jour i ∈ {1,. . . , N} est p _i ∈ [0, 1], et que ces événements aléatoires n sont indépendants. En supposant que les botanistes et les experts en météorologie sont corrects, montrez comment calculer la probabilité que les fougères survivent à la sécheresse. Votre algorithme devrait fonctionner dans le temps O (n).

Answer 1

Avoir une matrice (n + 1) × n telle que C[i][j] est la probabilité que, après i e jour il y aura eu j jours de pluie (i se déroulera du 1 à n, j va de 0 à n). Initialiser:

• C[1][0] = 1 - p[1]
• C[1][1] = p[1]
• C[1][j] = 0 pour j > 1

boucle Maintenant, au cours des jours et définissez les valeurs de la matrice comme ceci:

• C[i][0] = (1 - p[i]) * C[i-1][0]
• C[i][j] = (1 - p[i]) * C[i-1][j] + p[i] * C[i - 1][j - 1] pour j > 0

Enfin, la somme des valeurs de C[n][n/2] à C[n][n] pour obtenir la probabilité de survie de fougère.

Answer 2

problèmes de programmation dynamiques peuvent être résolus en haut en bas ou de bas en haut de la mode.

Vous avez déjà eu la version ascendante décrite. Pour ce faire, la version haut vers le bas, écrire une fonction récursive, puis ajoutez une couche de mise en cache de sorte que vous ne recalculez aucun résultat que vous avez déjà calculé. En pseudo-code:

cache = {} 
function whatever(args) 
    if args not in cache 
     compute result 
     cache[args] = result 
    return cache[args] 

Ce processus est appelé "memoization" et de nombreuses langues ont les moyens de memoizing automatiquement les choses.

Voici une implémentation Python de cet exemple spécifique:

def prob_survival(daily_probabilities): 
    days = len(daily_probabilities) 
    days_needed = days/2 

    # An inner function to do the calculation. 
    cached_odds = {} 
    def prob_survival(day, rained): 
     if days_needed <= rained: 
      return 1.0 
     elif days <= day: 
      return 0.0 
     elif (day, rained) not in cached_odds: 
      p = daily_probabilities[day] 
      p_a = p * prob_survival(day+1, rained+1) 
      p_b = (1- p) * prob_survival(day+1, rained) 
      cached_odds[(day, rained)] = p_a + p_b 
     return cached_odds[(day, rained)] 

    return prob_survival(0, 0) 

Et vous qualifieraient comme suit:

print(prob_survival([0.2, 0.4, 0.6, 0.8])