Optimiser la multiplication de la chaîne matricielle

Ce défi consiste à calculer l' ordre de multiplication le plus efficace pour un produit de plusieurs matrices.

La taille des matrices est spécifiée sur une seule ligne d'entrée standard. Vous devez imprimer sur la sortie standard une liste d'entiers indiquant l'ordre dans lequel effectuer les multiplications pour minimiser le coût total de multiplication.

Exemple 1

contribution

5x6 6x12 12x100 100x7

production

3 2 1

La ligne d'entrée sera une liste de tailles de matrice séparées par des espaces, chacune étant le nombre de lignes, suivi d'un x, suivi du nombre de colonnes. Pour l'exemple, il y a 4 matrices à multiplier ensemble (donc 3 multiplications totales), et comme la multiplication matricielle est associative, elles peuvent se faire dans n'importe quel ordre.

La sortie doit être l'ordre dans lequel effectuer les multiplications pour minimiser le coût total. Il doit s'agir d'une liste d'entiers séparés par des espaces représentant l'indice de la multiplication à effectuer ensuite. Pour N matrices, cette liste doit contenir les nombres 1 à N-1 inclus. Par exemple 1, la sortie 3 2 1signifie que vous devez d'abord faire la 12x100 * 100x7multiplication, puis la 6x12 * 12x7multiplication (la deuxième matrice multiplie le résultat de l'étape précédente), puis enfin la 5x6 * 6x7multiplication résultante .

Les multiplications matricielles seront toujours compatibles, c'est-à-dire que le nombre de colonnes d'une matrice correspondra au nombre de lignes de la matrice suivante. Supposons que le coût de multiplication de deux matrices AxB * BxCsoit A*B*C.

Votre code doit gérer des listes pouvant contenir jusqu'à 100 matrices, chacune d'une dimension allant jusqu'à 999, et le faire dans un délai raisonnable.

exemple 2

contribution

5x10 10x5 5x15 15x5

production

1 3 2

ou

3 1 2

exemple 3

contribution

22x11 11x78 78x123 123x666 666x35 35x97 97x111 111x20 20x50

production

2 3 4 5 6 7 8 1

Remarque: pour la vérification, le meilleur coût total pour les trois exemples est 9114, 750 et 1466344.

Le code le plus court gagne!

Rubis, 176 172 205 205 caractères

Voici une autre version (plusieurs caractères de plus) qui fonctionnera également pour une entrée volumineuse dans un délai raisonnable.

q=(gets.split<<$_[/\d+$/]).map &:to_i
r=Hash.new{|h,i|h[i]=Hash.new{|h,j|h[j]=1e12;h[j]=i==j ?[0,[]]:(i...j).map{|k|a,c=r[i][k];b,d=r[k+1][j];[a+b+q[i-1]*q[k]*q[j],c+d+[k]]}.min}}
$><<r[1][q.size-1][1]*' '

Première version: implémentation récursive directe dans Ruby. Il effectue une recherche complète et peut donc être lent sur de grandes entrées.

k=->m{m[2]?(1..m.size-2).map{|l|s=k[m[0,l]+m[l+1..-1]];[m[l-1]*m[l]*m[l+1]+s[0],[l]+s[1].map{|u|u<l ?u:u+1}]}.min: [0,[]]}
$><<k[(gets.split<<$_[/\d+$/]).map &:to_i][1]*' '