5.3.3. Multiplicación encadenada de matrices.

• Tablas usadas por el algoritmo.

  • Sea M una matriz [1..n, 1..n] de enteros. El algoritmo usará la mitad de la matriz.

• Forma de rellenar la tabla.
  • Inicializar la matriz. Para todo i, desde 1 hasta n. M[i, i] = 0
  • Aplicar la ecuación de recurrencia por diagonales.
    M[i, j] = min (M[i, k] + M[k+1, j] + d[i-1]·d[k]·d[j])

i?k<j

• Ejemplo. n= 4, d = (10, 20, 50, 1, 100)

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica