Matrix Chain Multiplication

Q: Quelle est la complexité temporelle de la multiplication en chaîne de matrices ?

Le tableau comporte environ n²/2 intervalles et chacun essaie jusqu’à n découpages ; la programmation dynamique s’exécute donc en temps O(n³) et utilise O(n²) de mémoire. Une récursion simple sans mémoïsation effectue 3^(n-1) appels pour n matrices.

Q: Pourquoi l’ordre de la multiplication matricielle est-il important ?

La multiplication matricielle est associative, donc (AB)C et A(BC) donnent la même matrice, mais les matrices intermédiaires diffèrent en taille. Dans le premier exemple, (AB)C construit une matrice de 4 × 3 et coûte 264, tandis que A(BC) construit une matrice de 10 × 12 et coûte 840.

Q: Comment trouver la parenthésisation optimale elle-même ?

Enregistre le découpage optimal dans choice[left][right] à côté de best[left][right] . Pour l’affichage, une matrice seule affiche son nom ; une séquence plus longue affiche une parenthèse ouvrante, la partie jusqu’à choice[left][right] , la partie qui suit, puis une parenthèse fermante. Cela ajoute une mémoire de O(n²) .

DifficileProgrammation dynamique

+10

Une chaîne de matrices est décrite par dims : la matrice i a dims[i] lignes et dims[i+1] colonnes, de sorte que chaque matrice peut être multipliée par la suivante. Multiplier une matrice p × q par une matrice q × r nécessite p × q × r multiplications scalaires et donne une matrice p × r. Toutes les façons de placer les parenthèses donnent le même produit final, mais pas au même coût. Retourne le nombre minimal de multiplications scalaires nécessaires pour multiplier toute la chaîne.

Fonction

matrixChainOrder(dims: integer-array) → integer

dimsinteger-array: les dimensions le long de la chaîne : la matrice i est dims[i] × dims[i+1]
Renvoieinteger: le plus petit nombre de multiplications scalaires nécessaire pour multiplier toute la chaîne

Contraintes

2 ≤ dims.length ≤ 100, la chaîne contient donc entre 1 et 99 matrices.
1 ≤ dims[i] ≤ 100
La réponse est au plus égale à 98 × 10⁶, bien en deçà de la limite d’un entier signé sur 32 bits.

Exemples

Entrée: dims = [4, 10, 3, 12]
Sortie: 264
Explication: Multiplier les deux premières coûte 4 × 10 × 3 = 120 et laisse une matrice de 4 × 3, qui, multipliée par la matrice de 3 × 12, ajoute 144 : 264. L’autre ordre coûte 360 + 480 = 840.

Pour aller plus loin

Peux-tu également compter combien de parenthésages différents atteignent le coût minimal ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

L’ordre change le coût : 264 contre 840 dans le premier exemple. Regarde la dernière multiplication. Elle combine les produits d’une partie gauche et d’une partie droite de la chaîne, et chaque partie correspond au même problème sur une chaîne plus courte. Un tableau couvrant les segments de la chaîne résout chaque problème une seule fois, en O(n³).

Essaie chaque découpage avec une récursion simple

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Numérotez les frontières de la chaîne de 0 à m-1, où m = dims.length : la frontière k a pour taille dims[k]. Les matrices entre les frontières left et right se multiplient pour former une matrice dims[left] × dims[right], quel que soit l’ordre. Ainsi, si la dernière étape divise cette portion au niveau de split, son coût est de dims[left] × dims[split] × dims[right], peu importe ce qui s’est passé à l’intérieur des deux blocs. Chaque bloc doit être construit au coût le plus faible possible ; cheapest(left, right) est donc la plus petite somme des coûts des deux blocs et de cette dernière étape, parmi toutes les valeurs de split. Essayer chaque dernière étape garantit la justesse de l’algorithme.

Il résout les mêmes portions encore et encore : n matrices nécessitent 3^(n-1) appels, soit environ 1.2 × 10^9 pour 20 matrices, alors qu’il n’existe qu’environ m²/2 portions différentes.

Algorithme

Écris cheapest(left, right) pour les matrices entre les bornes left et right.
Si right - left < 2, il y a une seule matrice : renvoie 0.
Pour chaque split strictement compris entre les deux, additionne cheapest(left, split), cheapest(split, right) et dims[left] × dims[split] × dims[right].
Renvoie la plus petite somme.
La réponse est cheapest(0, m-1).

def matrixChainOrder(dims):
    def cheapest(left, right):
        # The fewest multiplications for the matrices between boundaries left and right
        if right - left < 2:
            return 0  # a single matrix costs nothing
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        return best

    return cheapest(0, len(dims) - 1)

Récursion avec mémoïsation

Intuition

Un appel dépend uniquement de left et right. Enregistre son résultat dans memo[left][right], chaque cellule commençant à -1, une valeur qu’aucun coût réel ne peut prendre, et les appels ultérieurs lisent la cellule au lieu de récursiver. Chacune des quelque m²/2 paires est résolue une seule fois avec moins de m divisions : O(n³), soit 161 700 vérifications de division pour 99 matrices. La récursion n’est jamais plus profonde que la longueur de la chaîne, donc 100 frontières tiennent dans n’importe quelle pile d’appels.

Algorithme

Allouez memo avec m lignes et m colonnes, chaque cellule valant -1.
Dans cheapest(left, right), une séquence d’une seule matrice renvoie 0, et une cellule différente de -1 renvoie le coût enregistré.
Sinon, évaluez chaque split exactement comme le fait la récursion simple et prenez le minimum.
Écrivez ce minimum dans memo[left][right] avant de le renvoyer.
La réponse est cheapest(0, m-1).

def matrixChainOrder(dims):
    m = len(dims)
    # memo[left][right]: the answer for boundaries left and right, -1 while unknown
    memo = [[-1] * m for _ in range(m)]

    def cheapest(left, right):
        if right - left < 2:
            return 0  # a single matrix costs nothing
        if memo[left][right] != -1:
            return memo[left][right]
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        memo[left][right] = best
        return best

    return cheapest(0, m - 1)

Remplissez le tableau en étirant sa largeur

Intuition

Chaque cellule dépend uniquement de segments plus étroits, donc les boucles peuvent remplir best[left][right] en allant des segments les plus étroits aux plus larges. Une largeur de 1 correspond à une seule matrice et reste à 0 ; lorsque tu arrives à un segment plus large, les deux parties de chaque découpage ont déjà été traitées. Avec dims = [6, 2, 7, 3, 5] :

Largeur 2 : best[0][2] = 84, best[1][3] = 42, best[2][4] = 105.
Largeur 3 : best[0][3] vaut 78 (découpage 1 : 0 + 42 + 36), best[1][4] vaut 72 (découpage 3 : 42 + 0 + 30).
Largeur 4 : les découpages 1, 2 et 3 donnent 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 et 78 + 0 + 90 = 168 ; donc best[0][4] = 132.

Le découpage optimal à la frontière 1 signifie que la matrice 6 × 2 est multipliée en dernier, comme dans le deuxième exemple. Le temps d’exécution et la mémoire utilisée sont identiques à ceux de la version avec mémoïsation, sans récursion.

Algorithme

Soit m = dims.length et allouez un tableau de zéros m × m nommé best.
Faites varier width de 2 à m-1. À l’intérieur de cette boucle, faites varier left en augmentant sa valeur à partir de 0 tant que right = left + width reste une limite.
Pour cette portion, calculez best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right] pour chaque valeur de split de left+1 à right-1, et stockez le minimum dans best[left][right].
La réponse se trouve dans best[0][m-1].

def matrixChainOrder(dims):
    m = len(dims)
    # best[left][right]: the fewest multiplications for the matrices
    # between boundary left and boundary right (0 for a single matrix)
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            low = None
            for split in range(left + 1, right):
                # the last product joins a dims[left] x dims[split] block
                # with a dims[split] x dims[right] block
                cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
                if low is None or cost < low:
                    low = cost
            best[left][right] = low
    return best[0][m - 1]

Pièges et cas limites

Multiplier d’abord la paire la moins coûteuse. Pour [10, 10, 1, 9], la dernière paire est la moins coûteuse (90), mais l’étape suivante coûte 900, soit un total de 990. Commencer par la première paire coûte 190.
Lire la réponse dans la mauvaise cellule. dims contient une entrée de plus qu’il n’y a de matrices ; la réponse est donc best[0][m-1], et non best[0][m].
Faire croître left dans la boucle externe. La ligne left lit alors best[split][right] depuis une ligne ultérieure qui vaut encore 0. Place la largeur dans la boucle externe, ou compte left à rebours.
Oublier la matrice unique. [3, 7] doit renvoyer 0, et en R, la boucle 2:(m-1) devient 2:1 et s’exécute à rebours : il faut donc la protéger.

Questions fréquentes3

Quelle est la complexité temporelle de la multiplication en chaîne de matrices ?

Le tableau comporte environ n²/2 intervalles et chacun essaie jusqu’à n découpages ; la programmation dynamique s’exécute donc en temps O(n³) et utilise O(n²) de mémoire. Une récursion simple sans mémoïsation effectue 3^(n-1) appels pour n matrices.

Pourquoi l’ordre de la multiplication matricielle est-il important ?

La multiplication matricielle est associative, donc (AB)C et A(BC) donnent la même matrice, mais les matrices intermédiaires diffèrent en taille. Dans le premier exemple, (AB)C construit une matrice de 4 × 3 et coûte 264, tandis que A(BC) construit une matrice de 10 × 12 et coûte 840.

Comment trouver la parenthésisation optimale elle-même ?

Enregistre le découpage optimal dans choice[left][right] à côté de best[left][right]. Pour l’affichage, une matrice seule affiche son nom ; une séquence plus longue affiche une parenthèse ouvrante, la partie jusqu’à choice[left][right], la partie qui suit, puis une parenthèse fermante. Cela ajoute une mémoire de O(n²).

def matrixChainOrder(dims):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

dims = [4, 10, 3, 12]

Résultat attendu

Matrix Chain Multiplication

Fonction

Contraintes

Exemples

Indices

Solution

Essaie chaque découpage avec une récursion simple

Récursion avec mémoïsation

Remplissez le tableau en étirant sa largeur

Pièges et cas limites

Questions fréquentes3

Problèmes similaires