Prerrequisito: Programación Dinámica | Conjunto 8 (Multiplicación de strings de arrays)
Dada una secuencia de arrays, encuentre la forma más eficiente de multiplicar estas arrays entre sí. El problema no es realmente realizar las multiplicaciones, sino simplemente decidir en qué orden realizar las multiplicaciones.
Tenemos muchas opciones para multiplicar una string de arrays porque la multiplicación de arrays es asociativa. En otras palabras, no importa cómo pongamos entre paréntesis el producto, el resultado será el mismo. Por ejemplo, si tuviéramos cuatro arrays A, B, C y D, tendríamos:
(ABC)D = (AB)(CD) = A(BCD) = ....
Sin embargo, el orden en que colocamos entre paréntesis el producto afecta el número de operaciones aritméticas simples necesarias para calcular el producto o la eficiencia. Por ejemplo, suponga que A es una array de 10 × 30, B es una array de 30 × 5 y C es una array de 5 × 60. Después,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Claramente, el primer paréntesis requiere menos número de operaciones.
Dada una array p[] que representa la string de arrays tal que la i-ésima array Ai es de dimensión p[i-1] xp[i]. Necesitamos escribir una función MatrixChainOrder() que devuelva el número mínimo de multiplicaciones necesarias para multiplicar la string.
Input: p[] = {40, 20, 30, 10, 30}
Output: Optimal parenthesization is ((A(BC))D)
Optimal cost of parenthesization is 26000
There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
Let the input 4 matrices be A, B, C, and D. The minimum number of
multiplications are obtained by putting the parenthesis in the following way
(A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30
Input: p[] = {10, 20, 30, 40, 30}
Output: Optimal parenthesization is (((AB)C)D)
Optimal cost of parenthesization is 30000
There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30.
Let the input 4 matrices be A, B, C, and D. The minimum number of
multiplications are obtained by putting the parenthesis in the following way
((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30
Input: p[] = {10, 20, 30}
Output: Optimal parenthesization is (AB)
Optimal cost of parenthesization is 6000
There are only two matrices of dimensions 10x20 and 20x30. So there
is only one way to multiply the matrices, the cost of which is 10*20*30
Este problema es principalmente una extensión de Encontrar el costo óptimo de la multiplicación de strings de arrays . Aquí también necesitamos imprimir corchetes.
Hemos discutido una solución en una publicación que usa dos arrays. En esta publicación, se analiza una solución optimizada para el espacio que utiliza una sola array.
1) Para encontrar el costo óptimo, creamos una array cuyo único triángulo superior se llena y el resto de las celdas no se utilizan.
2) La idea es utilizar la parte inferior triangular de la misma array (que no se utiliza) para guardar brackets.
La idea es almacenar el punto de ruptura óptimo para cada subexpresión (i, j) en m [ j ] [ i ] y el costo óptimo en m [ i ] [ j ].
A continuación se muestra la implementación de los pasos anteriores.
C++
// A space optimized C++ program to print optimal
// parenthesization in matrix chain multiplication.
#include<bits/stdc++.h>
using namespace std;
// Function for printing the optimal
// parenthesization of a matrix chain product
void printParenthesis(int i, int j, int n,
int *bracket, char &name)
{
// If only one matrix left in current segment
if (i == j)
{
cout << name++;
return;
}
cout << "(";
// Recursively put brackets around subexpression
// from i to bracket[j][i].
// Note that "*((bracket+j*n)+i)" is similar to
// bracket[j][i]
printParenthesis(i, *((bracket+j*n)+i), n,
bracket, name);
// Recursively put brackets around subexpression
// from bracket[j][i] + 1 to i.
printParenthesis(*((bracket+j*n)+i) + 1, j,
n, bracket, name);
cout << ")";
}
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
void matrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra
row and one extra column are allocated in
m[][]. 0th row and 0th column of m[][]
are not used */
int m[n][n];
/* m[i,j] = Minimum number of scalar multiplications
needed to compute the matrix A[i]A[i+1]...A[j] =
A[i..j] where dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (int i=1; i<n; i++)
m[i][i] = 0;
// L is chain length.
for (int L=2; L<n; L++)
{
for (int i=1; i<n-L+1; i++)
{
int j = i+L-1;
m[i][j] = INT_MAX;
for (int k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
int q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
{
m[i][j] = q;
// Each entry m[j,ji=k shows
// where to split the product arr
// i,i+1....j for the minimum cost.
m[j][i] = k;
}
}
}
}
// The first matrix is printed as 'A', next as 'B',
// and so on
char name = 'A';
cout << "Optimal Parenthesization is: ";
printParenthesis(1, n-1, n, (int *)m, name);
cout << "\nOptimal Cost is : " << m[1][n-1];
}
// Driver code
int main()
{
int arr[] = {40, 20, 30, 10, 30};
int n = sizeof(arr)/sizeof(arr[0]);
matrixChainOrder(arr, n);
return 0;
}
Java
// A space optimized Java program to print optimal
// parenthesization in matrix chain multiplication.
import java.util.*;
class GFG
{
static char name;
// Function for printing the optimal
// parenthesization of a matrix chain product
static void printParenthesis(int i, int j, int n, int[][] bracket)
{
// If only one matrix left in current segment
if (i == j)
{
System.out.print(name++);
return;
}
System.out.print('(');
// Recursively put brackets around subexpression
// from i to bracket[j][i].
// Note that "*((bracket+j*n)+i)" is similar to
// bracket[i][j]
printParenthesis(i, bracket[j][i], n, bracket);
// Recursively put brackets around subexpression
// from bracket[j][i] + 1 to i.
printParenthesis(bracket[j][i] + 1, j, n, bracket);
System.out.print(')');
}
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
static void matrixChainOrder(int[] p, int n)
{
/*
* For simplicity of the program, one extra row and one extra column are
* allocated in m[][]. 0th row and 0th column of m[][] are not used
*/
int[][] m = new int[n][n];
/*
* m[i,j] = Minimum number of scalar multiplications needed to compute the
* matrix A[i]A[i+1]...A[j] = A[i..j] where dimension of A[i] is p[i-1] x p[i]
*/
// cost is zero when multiplying one matrix.
for (int L = 2; L < n; L++)
{
for (int i = 1; i < n - L + 1; i++)
{
int j = i + L - 1;
m[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
{
m[i][j] = q;
// Each entry m[j,ji=k shows
// where to split the product arr
// i,i+1....j for the minimum cost.
m[j][i] = k;
}
}
}
}
// The first matrix is printed as 'A', next as 'B',
// and so on
name = 'A';
System.out.print("Optimal Parenthesization is: ");
printParenthesis(1, n - 1, n, m);
System.out.print("\nOptimal Cost is :" + m[1][n - 1]);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 40, 20, 30, 10, 30 };
int n = arr.length;
matrixChainOrder(arr, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# A space optimized python3 program to
# print optimal parenthesization in
# matrix chain multiplication.
def printParenthesis(m, j, i ):
# Displaying the parenthesis.
if j == i:
# The first matrix is printed as
# 'A', next as 'B', and so on
print(chr(65 + j), end = "")
return;
else:
print("(", end = "")
# Passing (m, k, i) instead of (s, i, k)
printParenthesis(m, m[j][i] - 1, i)
# (m, j, k+1) instead of (s, k+1, j)
printParenthesis(m, j, m[j][i])
print (")", end = "" )
def matrixChainOrder(p, n):
# Creating a matrix of order
# n*n in the memory.
m = [[0 for i in range(n)]
for i in range (n)]
for l in range (2, n + 1):
for i in range (n - l + 1):
j = i + l - 1
# Initializing infinity value.
m[i][j] = float('Inf')
for k in range (i, j):
q = (m[i][k] + m[k + 1][j] +
(p[i] * p[k + 1] * p[j + 1]));
if (q < m[i][j]):
m[i][j] = q
# Storing k value in opposite index.
m[j][i] = k + 1
return m;
# Driver Code
arr = [40, 20, 30, 10, 30]
n = len(arr) - 1
m = matrixChainOrder(arr, n) # Forming the matrix m
print("Optimal Parenthesization is: ", end = "")
# Passing the index of the bottom left
# corner of the 'm' matrix instead of
# passing the index of the top right
# corner of the 's' matrix as we used
# to do earlier. Everything is just opposite
# as we are using the bottom half of the
# matrix so assume everything opposite even
# the index, take m[j][i].
printParenthesis(m, n - 1, 0)
print("\nOptimal Cost is :", m[0][n - 1])
# This code is contributed by Akash Gupta.
C#
// A space optimized C# program to print optimal
// parenthesization in matrix chain multiplication.
using System;
class GFG{
static char name;
// Function for printing the optimal
// parenthesization of a matrix chain product
static void printParenthesis(int i, int j,
int n, int[,] bracket)
{
// If only one matrix left in current segment
if (i == j)
{
Console.Write(name++);
return;
}
Console.Write('(');
// Recursively put brackets around subexpression
// from i to bracket[j,i].
// Note that "*((bracket+j*n)+i)" is similar to
// bracket[i,j]
printParenthesis(i, bracket[j, i], n, bracket);
// Recursively put brackets around subexpression
// from bracket[j,i] + 1 to i.
printParenthesis(bracket[j, i] + 1, j, n, bracket);
Console.Write(')');
}
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
static void matrixChainOrder(int[] p, int n)
{
/*
* For simplicity of the program, one extra
* row and one extra column are
* allocated in m[,]. 0th row and 0th
* column of m[,] are not used
*/
int[,] m = new int[n, n];
/*
* m[i,j] = Minimum number of scalar
* multiplications needed to compute the
* matrix A[i]A[i+1]...A[j] = A[i..j]
* where dimension of A[i] is p[i-1] x p[i]
*/
// Cost is zero when multiplying one matrix.
for(int L = 2; L < n; L++)
{
for(int i = 1; i < n - L + 1; i++)
{
int j = i + L - 1;
m[i, j] = int.MaxValue;
for(int k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
int q = m[i, k] + m[k + 1, j] +
p[i - 1] * p[k] * p[j];
if (q < m[i, j])
{
m[i, j] = q;
// Each entry m[j,ji=k shows
// where to split the product arr
// i,i+1....j for the minimum cost.
m[j, i] = k;
}
}
}
}
// The first matrix is printed as 'A', next as 'B',
// and so on
name = 'A';
Console.Write("Optimal Parenthesization is: ");
printParenthesis(1, n - 1, n, m);
Console.Write("\nOptimal Cost is :" + m[1, n - 1]);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 40, 20, 30, 10, 30 };
int n = arr.Length;
matrixChainOrder(arr, n);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// A space optimized python3 program to
// print optimal parenthesization in
// matrix chain multiplication.
function printParenthesis(m, j, i){
// Displaying the parenthesis.
if(j == i){
// The first matrix is printed as
// 'A', next as 'B', and so on
document.write(String.fromCharCode(65 + j), end = "")
return;
}
else{
document.write("(", end = "")
// Passing (m, k, i) instead of (s, i, k)
printParenthesis(m, m[j][i] - 1, i)
// (m, j, k+1) instead of (s, k+1, j)
printParenthesis(m, j, m[j][i])
document.write(")")
}
}
function matrixChainOrder(p, n){
// Creating a matrix of order
// n*n in the memory.
let m = new Array(n).fill(0).map(()=>new Array(n).fill(0))
for(let l=2;l<n + 1;l++){
for(let i=0;i<(n - l + 1);i++){
let j = i + l - 1
// Initializing a very value
m[i][j] = Number.MAX_VALUE
for(let k=i;k<j;k++){
let q = (m[i][k] + m[k + 1][j] +
(p[i] * p[k + 1] * p[j + 1]));
if (q < m[i][j]){
m[i][j] = q
// Storing k value in opposite index.
m[j][i] = k + 1
}
}
}
}
return m;
}
// Driver Code
let arr = [40, 20, 30, 10, 30]
let n = arr.length - 1
let m = matrixChainOrder(arr, n) // Forming the matrix m
document.write("Optimal Parenthesization is: ")
// Passing the index of the bottom left
// corner of the 'm' matrix instead of
// passing the index of the top right
// corner of the 's' matrix as we used
// to do earlier. Everything is just opposite
// as we are using the bottom half of the
// matrix so assume everything opposite even
// the index, take m[j][i].
printParenthesis(m, n - 1, 0)
document.write("</br>","Optimal Cost is :", m[0][n - 1])
// This code is contributed by shinjanpatra
</script>
Producción:
Optimal Parenthesization is : ((A(BC))D) Optimal Cost is : 26000
Complejidad temporal: O(n^3)
Espacio auxiliar: O(n^2): El valor asintótico sigue siendo el mismo, pero reducimos el espacio auxiliar a la mitad.