Bueno, llendo directo a mi discusion, les cuento:
Estoy haciendo un programa para una asignatura de la universidad, el cual consiste en buscar todos los caminos posibles y elegir el camino mas optimo, en cuanto a costo (diferencia entre el valor de una casilla y otro, que sea el minimo posible) y pasos que se dan dentro de una matriz de 20x20, partiendo del punto (0,0) hasta el punto (N-1,N-1). Para esto debo ocupar el algoritmo de backtracking, y lograr que este encuentre el camino en menos de 10 minutos (de ejecutado el programa).
E logrado reducir un poco los tiempos gracias a "tips" del profesor, como reducir la referencia de pasos y tambien tener una referencia de mejorCosto, todo esto con el fin de eliminar recursividades innecesarias, pero aun asi ya en la matriz de 11x11 se superan los 10 minutos de ejecucion del programa, llegando hasta los 20 minutos.
E leido que al algoritmo de backtracking se le puede aplicar "poda", pero tengo entendido que esta funciona en base a arboles, por lo que no se como adecuarlo a mi codigo de backtracking, ya que no ocupo arboles, y no me manejo mucho con ellos.
Mis preguntas son las siguientes: ¿Como puedo implementarle una poda a mi algoritmo? ¿Tengo que cambiar todo mi algoritmo y estructurarlo en base a arboles? ¿Hay alguna otra forma de optimizarlo?
El codigo es el siguiente:
Código PHP:
public class matriz
{
// Atributos //
int[][] M;
int N; // Tamaño de la matriz
int mejorCosto; // Referencia para comparar el costoActual
int y=0; // Numero de llamadas recursivas
// Constructor //
matriz(int n)
{
// Se asigna el valor ingresado como tamaño de la matriz
N=n;
// Se asigna un numero mayor al numero de digitos de los valores
// dentro de la matriz
mejorCosto = 99;
// Se crea el objeto matriz de tipo integer
M = new int[N][N];
// Se llena la matriz
llenar();
// Se muestra en pantalla la matriz resultante
imprimir();
// Se buscan todos los caminos posibles de la posicion (0,0)
// a la posicion (N-1,N-1)
buscar(0,0,1,0);
// Se muestra en pantalla el numero de llamadas recursivas resultantes
System.out.println(" y="+y) ;
}
// Metodos //
// Para llenar la matriz
private void llenar()
{
java.util.Random llenando = new java.util.Random();
for ( int i=0;i < N ; i++)
for ( int j=0; j<N ; j++)
M[i][j] = llenando.nextInt(9);
}
// Para imprimir la matriz
private void imprimir()
{
// Se recorre la matriz
for ( int i=0;i < N ; i++)
{
System.out.println();
for ( int j=0; j<N ; j++)
// Se muestra el pantalla la matriz resultante
System.out.print(M[i][j]+" ");
}
System.out.println();
}
// BACKTRACKING //
public void buscar(int i, int j, int pasos, int costoActual)
{
// Se cuenta el numero de llamadas recursivas
y++;
// Se comprueba que las posiciones señaladas esten dentro de la matriz
if ((( i>-1)&&( j>-1)&&( i<N)&&( j<N))
&&
// Se comprueba que el numero de pasos sea menor al tamaño total
// de la matriz para preferenciar la busqueda de caminos con menospasos,
// y asi finalizar llamadas recursivas innecesarias
(pasos < N*N/4)
&&
// Se comprueba que el costo actual es menor al mejor costo,
// para preferenciar la busqueda de caminos menos costosos,
// y asi finalizar llamadas recursivas innecesarias
(costoActual<mejorCosto))
{
// CASOS DIRECTOS //
// Se comprueba si se llego al final del camino
if (( i==N-1)&&(j==N-1))
{
System.out.println("llegue");
// Se comprueba si el costo actual es menor que el mejor costo
// para preferenciar la busqueda de caminos menos costosos
// y asi finalizar llamadas recursivas innecesarias
if ( costoActual<mejorCosto)
{
mejorCosto = costoActual;
System.out.println("costo="+costoActual);
System.out.println( " pasos="+pasos + " l="+N);
}
}
// CASOS RECURSIVOS //
if ( i+1 <N)
buscar(i+1,j,pasos+1,costoActual + Math.abs(M[i][j] - M[i+1][j]));
if ( j+1 <N)
buscar(i,j+1,pasos+1,costoActual + Math.abs(M[i][j] - M[i][j+1]));
if ( i-1 >-1)
buscar(i-1,j,pasos+1,costoActual + Math.abs(M[i][j] - M[i-1][j]));
if ( j-1 > -1)
buscar(i,j-1,pasos+1,costoActual + Math.abs(M[i][j] - M[i][j-1]));
}
}
public static void main(String[] args)
{
// Genero matrices de 2x2 hasta 20x20, para ir viendo los tiempos
for (int k=2;k<21;k++)
new matriz(k);
}
}
Saludos.
