Programmation dynamique (DP)

C'est l'un des problèmes souvent posés dans les concours de programmation tels que LeetCode et AtCoder, et lors du codage par round-robin (force bleue), cela devient une quantité exponentielle de calcul (par exemple, $ O (2 ^ n) $ ). Vous pouvez réduire considérablement la quantité de calcul de code (par exemple, $ O (n ^ 2) $, etc.). Par conséquent, je pense que c'est un concept qui peut être utile non seulement pour la programmation de concours, mais aussi pour le codage quotidien.

Mise en garde)

Cet article décrit la procédure permettant aux débutants d'utiliser la planification dynamique pour résoudre des problèmes algorithmiques dans un laps de temps limité. Par conséquent, nous soulignons la facilité de compréhension en peu de temps et ne donnons pas d'explication mathématique stricte.
Le pseudo code est écrit en Python. De plus, les termes associés utilisent la description de wikipedia.
Pour ceux qui veulent en savoir systématiquement, ici et wikipedia % E7% 9A% 84% E8% A8% 88% E7% 94% BB% E6% B3% 95), veuillez donc vous y référer.
Cet article fait également référence à MIT Lecture. Très facile à comprendre et recommandé.

Pourquoi la planification dynamique est difficile à comprendre à première vue

La planification dynamique est généralement décrite comme:

Par exemple, dans le cas de wikipedia : ** Définition **

L'algorithme n'est pas défini en détail, mais est un terme général pour les algorithmes qui satisfont aux deux conditions suivantes. ** Définition 1. ** Utilisation de relations inductives: Utilisez des solutions pour des exemples de problèmes plus petits (problèmes partiels) et des résultats de calcul pour résoudre des exemples de problèmes plus larges en utilisant des relations inductives. ** Définition 2. ** Enregistrez les résultats des calculs: enregistrez les exemples de petits problèmes, les résultats des calculs et évitez de répéter le même calcul. Afin de faire référence efficacement dans une relation récursive, les résultats des calculs sont gérés avec des en-têtes tels que des entiers, des caractères et leurs combinaisons.

** Définition 2. ** En ce qui concerne l'enregistrement des résultats des calculs, vous pouvez comprendre intuitivement que les résultats des calculs sont mis en cache. Je pense que c'est intuitif de prendre des notes, alors je l'appellerai "mémo".
Le problème est la ** Définition 1. **, mais il peut être difficile à comprendre pour les débutants.
Qu'est-ce qu'un exemple de problème plus petit (sous-problème)?
Pourquoi pouvons-nous utiliser des problèmes partiels pour résoudre des problèmes plus importants (problèmes eux-mêmes) en utilisant des relations inductives?
Savez-vous pourquoi la planification dynamique peut être utilisée?
Je ne comprends pas la signification du mot programmation dynamique en premier lieu!
M. Bellman, qui a inventé le terme de programmation dynamique, l'a nommé ainsi pour cacher ses recherches en mathématiques au secrétaire à la Défense, qui détestait la recherche à moyen et long terme [^ 1]… C'est une chose, donc c'est difficile à comprendre, bien sûr: la sueur:

Tout en expliquant ces choses, nous examinerons la procédure pour résoudre le problème de la planification dynamique.

Méthode de planification dynamique Procédure de réponse aux questions

Exemple: problème de sac à dos

Prenons l'exemple du fameux problème du sac à dos. problème: Tu es un voleur Je me suis faufilé dans un magasin de montres pour voler ma montre. En exprimant le tableau des montres en $ S $, il existe un grand nombre de montres chères de différents prix jusqu'à $ S [0], ... S [i], ..., S [n-1] $. Oui, mais il y a un poids fixe de $ W $ que vous pouvez emporter chez vous. Comment puis-je trouver le prix total le plus élevé dans la limite de poids de contrainte de $ W $?

組み合わせ.png Figure 1 Problème de sac à dos

Par exemple, si vous avez 1000 horloges ($ n = 1000 $), si vous essayez toutes les combinaisons d'horloges, vous envisagerez deux façons pour toutes les horloges, y compris ou non chaque horloge, donc $ 2 ^ {n} = 2 ^ {1000} ≒ 10 ^ {301} $, ce qui représente une quantité de calcul exponentiellement énorme.

1. Déterminer si la planification dynamique peut être utilisée

Lorsque l'on s'attaque à un problème dans un temps de réponse limité, je pense qu'il est nécessaire de déterminer d'abord si la méthode de planification dynamique peut être appliquée ou non pour éviter toute considération inutile. Par conséquent, le but ici n'est pas de prouver que la méthode de planification dynamique peut être appliquée, mais de se faire une idée quant à savoir si la méthode de planification dynamique peut être appliquée à ce problème en peu de temps.

Maintenant, si la méthode de planification dynamique peut être appliquée, c'est si ce qui est écrit dans la définition peut être appliqué ou non. Comment puis-je vérifier cela? Il est candidat à la planification dynamique si les ** conditions I ** et ** conditions II. ** suivantes sont susceptibles d'être trouvées dans les premières minutes.

Condition I.Un problème partiel peut être résolu

Selon la ** Définition 1. **, il est essentiel de pouvoir résoudre des problèmes partiels en décomposant de grands exemples de problèmes. Quel genre de cas signifie ce "problème partiel peut être résolu"? Autrement dit, si $ S $ est un tableau de données d'entrée, une solution peut être trouvée pour une partie de $ S $ dans les mêmes conditions que la solution entière.

Plus précisément, dans le problème du sac à dos, lorsque l'on considère uniquement les horloges après $ i $ (= $ S [i:] $) parmi les nombreuses horloges (= $ S $) dans le magasin de montres, par exemple, Cela signifie que vous pouvez trouver le prix total maximum qui rentrera dans un sac à dos sous la contrainte d'une limite de poids de $ w $. Nous écrirons $ V [i:, w] $ comme valeur à maximiser ou minimiser de cette manière. Dans le cas du problème du sac à dos, $ V [i:, w] $ est le prix total après le numéro d'horloge $ i $ ($ i à n $) lorsque la limite de poids restant pour entrer dans le sac à dos est $ w $. Bien que la quantité de calcul soit énorme, $ V [i:, w] $ est une approche round-robin (force bleue) comme décrit dans l'explication de l'exemple, et toutes les combinaisons d'horloges avec une limite de poids de $ w $ ou moins peuvent être considérées. Si tel est le cas, il peut être calculé comme la valeur avec le prix total le plus élevé. Par conséquent, il semble que cette condition soit remplie.

Les trois types suivants de séquences partielles font partie de la séquence.

$ S [: i] $ -Array prefix
$ S [i:] $ -Array suffixe (suffixe)
$ S [i: j] $ -subarray

Cette fois, à titre d'exemple, le cas du suffixe $ S [i:] $ -array (suffixe) est pris.

Condition II. Le problème peut être résolu de manière récursive

Deuxièmement, il est nécessaire de confirmer si le problème partiel qui peut être résolu par la ** Condition I **. Peut être résolu de manière récursive. C'est ce que l 'on appelle «relation inductive» dans la définition 1. Le fait qu'il puisse être résolu de manière récursive signifie que, par exemple, si le prix total maximum jusqu'à $ S [i:] $ est exprimé par $ V [i:] $, il existe une relation qui peut être exprimée par la formule graduelle suivante. C'est une chose.

$ V [i:] = V [i + 1:] + v_ {i + 1} $ ($ v_ {i + 1} $ est une constante) ・・・ ①

En d'autres termes, si vous pouvez deviner que $ V [i:] $ est susceptible d'être calculé par le montant du calcul $ O (1) $ en utilisant $ V [i + 1:] $, c'est bien à ce stade.

Dans le cas du problème du sac à dos, à ce stade, ce sera un peu compliqué compte tenu de la limite de poids, alors ignorez-la, et si vous pensez que $ v_ {i} $ est le prix de la montre $ i $, alors $ V [i:] $ par ① Vous pouvez trouver la valeur maximale de. Cela dit, puisque la limite de poids est ignorée, il s'agit simplement du prix total de toutes les montres, mais compte tenu de la limite de poids plus tard, nous avons pu confirmer une relation récursive, donc à ce stade, elle est dans la condition II. Supposons que vous ayez un indice.

2. Pensez à une fonction récursive (ou une expression graduelle)

Jusqu'à présent, en examinant la ** condition I. ** et la ** condition II. ** ci-dessus dans un court laps de temps, je suis parvenu à la conclusion que ce problème est susceptible d'être résolu par la méthode de planification dynamique. Par conséquent, nous considérons enfin un algorithme qui utilise la planification dynamique. Par souci d'explication ci-dessous, j'écrirai d'abord le code, puis le code, mais lors de la résolution du problème réel, vous pouvez penser à partir du code. Dans mon cas, le code est plus facile à penser que l'expression, et en fin de compte c'est le code qui est nécessaire pour résoudre le problème, donc je pense depuis le début.

Pour la ** Condition II. **, formulons-la en tenant compte de la limite de poids. Par exemple, puisque nous pensons cette fois à tableau partiel = suffixe, considérons chaque horloge $ S [i] $ dans l'ordre décroissant de $ i = n-1 $ à $ i = 0 $. Comme mentionné précédemment, vous devez vous demander si vous voulez mettre la montre $ i = n-1 $ dans le sac à dos en premier ou non. Dans la formule, ① peut être développé et exprimé comme suit. Si vous voulez mettre une montre $ i = n-1 $ dans un sac à dos: $ V [n-2:, w] = V [n-1:, w-poids_ {n-1}] + valeur_ {n-1} $ ・・・ ③ Si vous ne mettez pas $ S [n-1] $ dans le sac à dos: $ V [n-2:, w] = V [n-1:, w] $ ‥ ‥ ④ Où $ weight_ {n-1} $ représente le poids de la montre $ n-1 $ et $ value_ {n-1} $ représente le prix.

Si $ V [n-2:, w] $ est obtenu par la formule ci-dessus, considérons ensuite le cas où i = n-2 est mis dans le sac à dos ou non pour chacun des cas ③ et ④.

Par conséquent, pour appliquer cette relation à tout $ i = 0, ..., n-1 $, les formules ③ et ④ sont généralisées en les remplaçant par $ n-2 = i, n-1 = i + 1 $. Ensuite, vous pouvez écrire: Pour mettre $ S [i + 1] $ dans le sac à dos: $ V [i:, w] = V [i + 1:, w-poids_ {i + 1}] + valeur_ {i + 1} $ ・・・ ⑤ Si vous ne mettez pas $ S [i + 1] $ dans le sac à dos: $ V [i:, w] = V [i + 1:, w] $ ‥ ‥ ⑥

Veuillez noter que la limite de poids de $ w $ sera réduite du poids de la montre dans le sac à dos.

Si vous écrivez ceci sous forme de code python, cela ressemble à ceci: (* Ici, par souci de clarté, l'expression directe est convertie en code, et en réalité il est nécessaire de considérer les conditions aux limites, etc.)

# weight:Poids de chaque montre:
#Exemple)weight = [10, 20, 30, 35]
# value:Prix de chaque montre=
#Exemple)value = [5,12,17,20]

def V(i, w):
  #Lors de l'inclusion de la montre je:
  if w >= weight[i]:
    V1 = V(i+1, w-weight[i]) + value[i]    
  #Si la montre n'est pas incluse:
  V2 = V(i+1, w)

Nous avons deux formules graduelles, mais en considérant la ** Condition I **, nous pouvons combiner les deux formules graduelles en une seule.

3.Faire une fonction récursive (expression graduelle) qui résout un problème partiel

Dans la ** condition I. **, j'ai pensé qu'il était possible de trouver le prix total maximum sous la limite de poids de $ w $ par round robin (force brute) jusqu'au numéro de montre $ i $. Et il devrait être possible de le trouver en utilisant également l'équation graduelle. Lorsqu'il y a deux valeurs de prix total $ V [i:, w] $ comme dans les formules ⑤ et ⑥, si la limite de poids $ w $ est la même, celle avec le prix total le plus petit peut être la valeur maximale. Puisqu'il n'y a rien de tel, il peut être immédiatement déterminé que ce n'est pas nécessaire. Par conséquent, les deux équations graduelles (5) et (6) peuvent être résumées dans les équations suivantes. $ V [i:, w] = max (V [i + 1:, w-poids_ {i + 1}] + valeur_ {i + 1} $, $ V [i + 1:, w] $) ・・・ ⑦

Vous avez maintenant la formule pour trouver la valeur maximale du problème partiel. Ecrit en python, il ressemble à ceci:

# weight:Poids de chaque montre:
#Exemple)weight = [10, 20, 30, 35]
# value:Prix de chaque montre=
#Exemple)value = [5,12,17,20]

def V(i, w):
  #Lors de l'inclusion de la montre je:
  V1 = 0
  if w >= weight[i]:
    V1 = V(i+1, w-weight[i]) + value[i]    
  #Si la montre n'est pas incluse:
  V2 = V(i+1, w)
  return max(V1, V2)

Chaque fois que $ V (i, w) $ est appelé, nous considérons à la fois avec et sans la montre $ i $, mais celui avec la même limite de poids de $ w $ ou moins et le prix total le plus petit est le prix maximum total. Comme ce ne sera jamais le cas, seul celui avec le prix total le plus élevé est défini comme valeur de retour par $ max () $. De là, vous pouvez voir que la combinaison qui ne peut pas être la valeur maximale peut être déterminée au moment de $ i $.

À titre d'exemple concret, supposons que vous ayez un sac à dos avec une limite de poids de $ W = 5 $ et l'horloge suivante.

l'horloge	0	1	2	3
poids	2	4	2	3
prix	12	20	10	17

Un exemple concret de cet appel de fonction récursive est illustré dans la figure ci-dessous.

再帰関数呼び出し.png Figure 2 arbre d'appels récursifs

L'appel de fonction de la fonction récursive se fait de haut en bas, mais la valeur de retour sera renvoyée par l'appelé le plus profond. En conséquence, la limite de poids est calculée de haut en bas comme indiqué par la flèche bleue, mais le prix maximum est calculé de bas en haut comme indiqué par la flèche rouge. Chaque nœud a une flèche rouge provenant des deux nœuds enfants inférieurs, mais le nœud enfant droit met l'horloge $ i $ dans le sac à dos, et le nœud enfant gauche ne le fait pas. i:, w] Représente la valeur de retour de $. Seul celui avec le prix maximum le plus élevé renvoyé par le nœud enfant est adopté et renvoyé au nœud supérieur, et finalement le prix maximum 29 est obtenu.

Au fait, je comprends comment obtenir le prix maximum sans arrondir en utilisant l'expression graduelle (fonction récursive), mais en utilisant le mémo de ** Définition 2. **, la mémoire Au lieu de sacrifier l'utilisation, vous pouvez réduire la quantité de calcul.

4. Prenez note

Figure 2 Dans la ligne $ i = 2 $ dans l'arbre d'appels récursifs, il y a un nœud entouré de violet. Ces nœuds appellent deux fois $ V [i:, w] $, qui a la même limite de poids de $ w $ que l'horloge courante $ i $. Autrement dit, étant donné que tous les calculs des nœuds enfants de ce nœud sont les mêmes, si vous en prenez note lorsque vous l'appelez pour la première fois, vous pouvez omettre les calculs suivants. De combien de tailles de mémos avez-vous besoin? Si le poids de toutes les horloges est un entier, la plage de valeurs possibles pour $ w $ est $ 0 \ leq w \ leq W $, donc W + 1 mémos sont requis. Puisque la plage de valeurs possibles pour $ i $ est $ 0 \ leq i \ leq n-1 $, $ n $ vaut est requis. Par conséquent, la taille du mémo est $ W × (n-1) $.

Jusqu'à présent, nous n'avons pas considéré la condition aux limites du tableau, mais ici nous considérons également la condition aux limites du tableau. Écrit en Python, cela ressemble à ceci:


# weight:Poids de chaque montre:
weight = [2, 4, 2, 3]
# value:Prix de chaque montre:
value = [12,20,10,17]
n = len(value)
#Capacité limite du sac à dos:
W = 5

#Notes sécurisées
memo = [[0] * (W+1) for _ in range(n)] 

def V(i, w):
  if i >= n:
    #Après la fin du tableau
    return 0

  if memo[i][w]:
    #Si dans le mémo
    return memo[i][w]

  #Lors de l'inclusion de la montre je:
  V1 = 0
  if w >= weight[i]:
    V1 = V(i+1, w-weight[i]) + value[i]    
  #Si la montre n'est pas incluse:
  V2 = V(i+1, w)
  memo[i][w] = max(V1, V2)
  return memo[i][w]

V(0, W)

5. Confirmation du montant du calcul

S'il est déjà dans le mémo, vous n'avez pas à le calculer, vous n'avez donc qu'à calculer la fonction récursive pour le nombre de mémos. Par conséquent, le montant du calcul est de O $ (nW) $.

Cela s'explique souvent par l'indice de la disposition de l'axe horizontal, le graphique ou le tableau du poids de l'axe vertical, mais pour moi, il était plus intuitif d'expliquer avec la fonction récursive comme axe, donc j'admets un tel article Je l'ai essayé.

[^ 1]: depuis https://www.youtube.com/watch?v=OQ5jsbhAv_M

[PYTHON] Comment résoudre le problème de l'algorithme de planification dynamique (vu par les débutants)