Java - ¿Cómo puedo mejorar la velocidad de ejecucion(rendimiento) de este programa en java?

¿Cómo puedo mejorar la velocidad de ejecucion(rendimiento) de este programa en java?
Hola Amigos el programa es el siguiente:

public class Test {

public static void main ( String[] dfg)
{
System.out.println("Matriz, camino menos costoso");
for ( int k=10;k<23;k++)
new Matriz(k);
}


}

//ESTA ES LA LLAMADA A LA MATRIZ


--------------------------------------…
//ESTE ES EL NUCLEO DEL PROGRAMA
Matriz(int n)
{ N=n;
mejorCosto = 999999999;
M = new int[N][N];
llenarmatriz();
imprimir();
buscamelo(0,0,1,0);
System.out.println(" y="+y) ;

}
private void llenarmatriz()
{
java.util.Random alLote = new java.util.Random();
for ( int i=0;i < N ; i++)
for ( int j=0; j<N ; j++)
M[i][j] = alLote.nextInt(9);
}
private void imprimir()
{
for ( int i=0;i < N ; i++)
{
System.out.println();
for ( int j=0; j<N ; j++)
System.out.print(M[i][j]+" ");
}
System.out.println();
}
private void pausa()
{ try { Thread.sleep(34);
}catch ( Exception e) {
}
}
public void buscamelo(int i, int j, int pasos, int costoActual)
{ y++;
// System.out.println("i="+i+" j="+j+ " pasos="+pasos + " y="+y) ;
// pausa();
if ((( i>-1)&&( j>-1)&&( i<N)&&( j<N)) &&
(pasos < N*N/4)&&
( costoActual<mejorCosto))
{
if (( i==N-1)&&(j==N-1))
{
if ( costoActual<mejorCosto)
{ mejorCosto = costoActual ;

System.out.println("costo="+costo… ;
System.out.println( " pasos="+pasos + " y="+N) ;
}
//
}

if ( i+1 <N) buscamelo(i+1,j,pasos+1,costoActual + Math.abs(M[i][j] - M[i+1][j]));
if ( j+1 <N) buscamelo(i,j+1,pasos+1,costoActual + Math.abs(M[i][j] - M[i][j+1]));
if ( i-1 >-1) buscamelo(i-1,j,pasos+1,costoActual + Math.abs(M[i][j] - M[i-1][j]));
if ( j-1 > -1) buscamelo(i,j-1,pasos+1,costoActual + Math.abs(M[i][j] - M[i][j-1]));
}
}
}

--------------------------------------…
DETALLES:
1)El programa lo que hace es buscar el camino menos costoso en una matriz , es decir si en la posicion Matriz(i,j)=5 y la posicion q sigue Matriz(i+1,j)=11 EL COSTO ES 6 (11-5=6) y asi va avanzando casilla por casilla sumando los costos hasta llegar al final y va impriendo los costos de cada uno de los caminos que realizo.
2)el programa realiza primero una matriz de 10x10 despues una de 11x11 y asi hasta llegar a una de 22x22, en cada una d ellas se muestra el costo de sus respectivos caminos.
3)el problema esta en que llega a la matriz 12x12 y se demora mucho en mostrar los resultados, nisiquiera llega a a de 22x22, para mi el problema esta en las llamadas recursivas.
4)me dijeron que el rendimiento se podia mejorar incluso solo cambiando las posciones de las llamadas recursivas, tambien que se puede utilizar bactrack (no se que es eso), poda o branch and bound (tampoco se que es eso).

Espero que alguien me pueda ayudar,de verdad que estoy aproblemado con esto :SS,
saludos , de antemano muchas gracias