Tengo un algoritmo que me saca la forma mas optima de resolver la multiplicacion de matrices.
Tengo un vector de matrices y luego una matriz de posición que me indica donde colocar los paréntesis para que me quede la asociacion mas optima para la multiplicacion.
El algoritmo esta en java.
Para empezar, mi fichero de entrada es :
4
3 2
10 7
5 1
8 3
2 4
2 10 3 1
6 8 1 0
4 5
1 0 2 3 0
5 1 1 0 0
3 0 1 0 2
0 3 4 1 0
5 3
1 0 1
0 2 0
3 1 1
0 1 0
2 0 0
El fichero de datos de entrada consta de: Una primera línea que indica el valor de n que es el número de matrices a multiplicar. Para cada una de las matrices:
o Una línea con las dimensiones de la matriz separadas por un blanco. Las componentes de la matriz (cada fila en una línea y separando los componentes por blancos dentro de cada línea).
Ok, mi algoritmo para esta entrada me saca una solucion optima tal que :
Asociacion: (M0 x (( M1 x M2) x M3))
La matriz pos de posicionamiento de los parentesis es :
00000
00111
00023
00003
00000
Mi problema viene al hacer el algoritmo recursivo para la multiplicación de esta sucesión según me indica mi matriz pos, el algoritmo que uso es el siguiente :
public float[][] multiplicacion(int [][] pos,int i,int j){
int k;
if (i>=j){
return vectormatrices[i-1].Getmatriz();
}else{
k = pos[ i ] [ j ];
A=multiplicacion(pos,i,k);
B=multiplicacion(pos,k+1,j);
return mult_matriz_normal(A,B);
}La llamada se hace desde otro metodo como multiplicacion(pos,1,N)
pos= matriz de posiciones de los parentesis
N= el numero de matrices, en el ejemplo 4
Añadir, que vectormatrices es mi vector de matrices y que mult_matriz_normal funciona bien, el problema surge en la ultima llamada recursiva, parece que la pila de recursividad no guarda la primera asignación a A que seria la de la matriz M0, en papel sale perfecto, pero ejecutándolo, la ultima multiplicación recursiva que debería ser M0 x ((M1xM2))xM3) la recursividad me hace la ultima multiplicación como (M1xM2)X((M1xM2))xM3)) es como si le faltase deshacer la llamada en la que A=M0.
Estoy bastante perdido,y es para una practica obligatoria,solo me falta esto y ya lo tengo todo realizado.
Agradecería muchísimo la ayuda, gracias.