dynamic-programming
Multiplication de la chaîne matricielle

Solution récursive

La multiplication de chaînes matricielles est un problème d'optimisation pouvant être résolu à l'aide de la programmation dynamique. Étant donné une séquence de matrices, le but est de trouver le moyen le plus efficace de multiplier ces matrices. Le problème n'est pas réellement d'effectuer les multiplications, mais simplement de décider de la séquence des multiplications de matrice impliquées.

Disons que nous avons deux matrices A ₁ et A ₂ de dimension m * n et p * q . A partir des règles de multiplication matricielle, on sait que,

1. On peut multiplier A ₁ et A ₂ si et seulement si n = p . Cela signifie que le nombre de colonnes de A ₁ doit être égal au nombre de lignes de A ₂ .
2. Si la première condition est satisfaite et que nous multiplions A ₁ et A ₂ , nous aurons une nouvelle matrice, appelons-la A ₃ de dimension m * q .
3. Pour multiplier A ₁ et A ₂ , il faut faire des multiplications de scaler. Le nombre total de multiplications de scaler, nous devons effectuer est ( m * n * q ) ou ( m * p * q ).
4. A ₁ * A ₂ n'est pas égal à A ₂ * A ₁ .

Si nous avons trois matrices A ₁ , A ₂ et A ₃ ayant respectivement la dimension m * n , n * p et p * q , alors A ₄ = A ₁ * A ₂ * A ₃ aura la dimension de m * q . Maintenant, nous pouvons effectuer cette multiplication de deux manières:

• Nous multiplions d'abord A ₁ et A ₂ , puis avec le résultat, nous multiplions A ₃ . C'est-à-dire: ( A ₁ * A ₂ ) * A ₃ .
• Nous multiplions d'abord A ₂ et A ₃ , puis avec le résultat, nous multiplions A ₁ . C'est-à-dire: A ₁ * ( A ₂ * A ₃ ).

Vous pouvez remarquer que l'ordre de la multiplication reste le même, c'est-à-dire que nous ne multiplions pas ( A ₁ * A ₃ ) * A ₂ car cela pourrait ne pas être valide. Nous ne modifions que la parenthèse pour multiplier un ensemble avant de le multiplier par le reste. La manière dont nous plaçons ces parenthèses est importante. Pourquoi? Disons que la dimension de 3 matrices A ₁ , A ₂ et A ₃ est 10 * 100 , 100 * 5 , 5 * 50 . Alors,

1. Pour ( A ₁ * A ₂ ) * A ₃ , le nombre total de multiplications de scaler est: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 fois.
2. Pour A ₁ * ( A ₂ * A ₃ ), le nombre total de multiplications de scaler est: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 fois.

Pour le 2ème type, le nombre de multiplicateurs est 10 fois plus élevé que le 1er type! Donc, si vous pouvez trouver un moyen de déterminer l'orientation correcte des parenthèses nécessaire pour minimiser la multiplication totale de l'échelle, cela réduira le temps et la mémoire nécessaires à la multiplication de la matrice. C'est là que la multiplication de la chaîne de matrices est utile. Ici, nous ne nous intéresserons pas à la multiplication réelle des matrices, nous ne trouverons que l'ordre correct des parenthèses afin que le nombre de multiplications de scaler soit minimisé. Nous aurons les matrices A ₁ , A ₂ , A ₃ ........ A _n et nous trouverons le nombre minimum de multiplications de scaler nécessaires pour les multiplier. Nous supposerons que les dimensions données sont valides, c'est-à-dire qu'elles satisfont à notre première exigence pour la multiplication matricielle.

Nous utiliserons la méthode de diviser et conquérir pour résoudre ce problème. La programmation dynamique est nécessaire à cause des sous-problèmes communs. Par exemple: pour n = 5 , nous avons 5 matrices A ₁ , A ₂ , A ₃ , A ₄ et A ₅ . Nous voulons connaître le nombre minimum de multiplications nécessaires pour effectuer cette multiplication matricielle. A ₁ * A ₂ * A ₃ * A ₄ * A ₅ . Parmi les nombreuses façons, concentrons-nous sur un seul: ( A ₁ * A ₂ ) * ( A ₃ * A ₄ * A ₅ ).

Pour celui-ci, nous découvrirons A _left = A ₁ * A ₂ . A _droite = A ₃ * A ₄ * A ₅ . Ensuite, nous trouverons une _réponse = A _gauche * A _droite . Le nombre total de multiplications de scaler nécessaires pour trouver une _réponse : = Le nombre total de multiplications de scaler nécessaires pour déterminer A _left + Le nombre total de multiplications de scaler nécessaires pour déterminer A _right + Le nombre total de multiplications de scaler nécessaires pour déterminer A _left * Un _droit

Le dernier terme, le nombre total de multiplications scaler nécessaires pour déterminer A _gauche * Un _droit peut être écrit: Le nombre de lignes en A _gauche * le nombre de colonnes dans A _gauche * le nombre de colonnes dans un _droit. (Selon la 2ème règle de la multiplication matricielle)

Mais nous pourrions également définir la parenthèse autrement. Par exemple:

• A ₁ * ( A ₂ * A ₃ * A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ ) * ( A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ * A ₄ ) * A ₅ etc.

Pour chaque cas possible, nous déterminerons le nombre de multiplicateurs nécessaires pour trouver A _gauche et A _droite , puis A _gauche * A _droite . Si vous avez une idée générale de la récursivité, vous avez déjà compris comment effectuer cette tâche. Notre algorithme sera:

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

Pourquoi c'est un problème de programmation dynamique? Pour déterminer ( A ₁ * A ₂ * A ₃ ), si vous avez déjà calculé ( A ₁ * A ₂ ), cela vous sera utile dans ce cas.

Pour déterminer l'état de cette récursivité, nous pouvons voir que pour résoudre chaque cas, nous devons connaître la gamme de matrices avec lesquelles nous travaillons. Nous avons donc besoin d'un début et d'une fin . Comme nous utilisons diviser et conquérir, notre scénario de base aura moins de 2 matrices ( begin > = end ), où nous n'avons pas besoin de les multiplier. Nous aurons 2 tableaux: ligne et colonne . la ligne [i] et la colonne [i] stockeront le nombre de lignes et de colonnes de la matrice A _i . Nous aurons un tableau dp [n] [n] pour stocker les valeurs déjà calculées et l'initialiser avec -1 , où -1 représente la valeur qui n'a pas encore été calculée. dp [i] [j] représente le nombre de multiplications de scaler nécessaires pour multiplier A _i , A _{i + 1} , ....., A _j inclus. Le pseudo-code ressemblera à:

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

Complexité:

La valeur de début et de fin peut aller de 1 à n . Il y a n ² états différents. Pour chaque état, la boucle à l'intérieur sera exécutée n fois. Complexité temporelle totale: O(n³) et complexité de la mémoire: O(n²) .