Matrix multiplication order

Question

There is such an article, the results of which I want to use: http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/

The program from there works correctly: https://ideone.com/5ezfkL

And here is the result of the work of the same program that I am trying to run from VS 2010:

// Матрица Ai имеет размерность p[i-1] xp[i] для i = 1..n int MatrixChainOrder(int p[], int n) { /* Для простоты программы, в m[][] одна дополнительаня строка и один дополнительный столбец]. Нулевая строка и нулевой столбец в m[][] не используются */ int **m = new int* [n]; for(int i = 0; i < n; i++) m[i] = new int [n]; int i, j, k, L, q; /* m[i,j] = минимальное число скалярных умножений, необходимое для вычисления матрицы A[i]A[i+1]...A[j] = A[i..j], где размерность A[i] равна p[i-1] xp[i] */ // Стоимость равна нулю, когда умножаем одну матрицу for (i = 1; i < n; i++) m[i][i] = 0; // L - длина цепочки for (L=2; L<n; L++) { for (i=1; i<=n-L+1; i++) { j = i+L-1; m[i][j] = INT_MAX; for (k=i; k<=j-1; k++) { // q = стоимость/скалярные умножения q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if (q < m[i][j]) m[i][j] = q; } } } return m[1][n-1]; }

Example of running the program:

 int main(){ const int n = 10; int p[n] = {10, 50, 30, 7, 25, 60, 15, 80, 55, 30}; int cost = 0; cost = MatrixChainOrder(p, n); //std::cout << "Solution for m and s: " << std::endl; std::cout << "min cost: " << cost << std::endl; int pause; std::cin >> pause; }

In the debugger, I could not figure out anything: at the last iterations of filling the table, the program suddenly crashes with an access violation, and a file with locks opens. Indexes, as I have noticed, do not go beyond the permissible limits.

And also: in the function we have a memory leak, because the dynamic array is not deleted. But you cannot delete it, because you need to return the value of its cell. What can be done with this?

Accepted Answer · 2015-11-28T23:58:38

Algorithm is invalid.

Consider your example call with n = 10 . Consider a cycle

 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 = стоимость/скалярные умножения 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; } } }

Let at the first iteration L = 2 . Then i changes from 1 to 10 - 2 + 1 = 9 . When i = 9 , j = i + 2 - 1 = 10 . Calculating q refers to p[j] , that is, a non-existent index. The same applies to the expression m[i][j] .

Regarding the dynamic array - why not copy the value of the cell before returning from a function to an auxiliary variable, delete the array, and return the saved value?

Corrected indexing. I have such a code that runs without any problems:

 int MatrixChainOrder(int p[], int n) { int **m = new int*[n]; for (int i = 0; i < n; i++) m[i] = new int [n]; for (int i = 0; i < n; i++) m[i][i] = 0; // L - длина цепочки // !! у Кормена тут <= for (int L = 2; L <= n; L++) { for (int i = 1; i <= n - L + 1; i++) { int j = i + L - 1; m[i - 1][j - 1] = INT_MAX; for (int k = i; k <= j - 1; k++) { // q = стоимость/скалярные умножения int q = m[i - 1][k - 1] + m[k][j - 1] + p[i - 1] * p[k] * p[j]; if (q < m[i - 1][j - 1]) m[i - 1][j - 1] = q; } } } int result = m[0][n - 1]; for (int i = 0; i < n; i++) delete[] m[i]; delete[] m; return result; } int main() { const int n = 10; // добавил ещё одно значения, у Кормена там [p0..pn] int p[n + 1] = {10, 50, 30, 7, 25, 60, 15, 80, 55, 30, 99}; int cost = MatrixChainOrder(p, n); ...

Check if result is considered correct.

Perhaps it would be more correct to index from scratch. Rewrote the central piece, reducing by 1 the values of i , j , k :

 int MatrixChainOrder(int p[], int n) { int **m = new int*[n]; for (int i = 0; i < n; i++) m[i] = new int [n]; for (int i = 0; i < n; i++) m[i][i] = 0; // L - длина цепочки for (int L = 2; L <= n; L++) { for (int i = 0; i < n - L + 1; i++) { int j = i + L - 1; m[i][j] = INT_MAX; for (int k = i; k <= j - 1; k++) { // q = стоимость/скалярные умножения int 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; } } } int result = m[0][n - 1]; for (int i = 0; i < n; i++) delete[] m[i]; delete[] m; return result; }

It looks like a fatal error that cannot be fixed by adjusting the range of indexes.
And it is at Cormen so, the implementation is almost verbatim.
Although maybe this condition i <= n-L + 1 just guarantees that there is no way out of the array.
It makes sense to take the algorithm as it is, and simply subtract one at each indexing.
After all, indices are not important if my matrices m and s are inside other large matrices.
For example, the matrix m 7x7 is in the middle of the matrix 20x20.

Matrix multiplication order

1 answer 1

More articles: