Sobre backtracking

Hola!...
Tengo este código, muy simple y tosco, que me genera todas las posibles combinaciones de matrices 2x2 con unos y ceros, las 16 posibles. Mi pregunta es si puedo, por ejemplo, después de generar la primera fila (todo ceros), decir que esa no es la matriz que busco (solución) que no la acabé y que no me genere ninguna matriz que la primera fila sean ceros, es decir, hacer una "poda" ...
Es que no se me ocurre como...
Gracias
public class nanograma{
static int TOPE=2;
static int conta=0;
int fila,columna;
int mat[][];
public nanograma() {
mat=new int[TOPE][TOPE];
bactracking(1);
System.out.println("matrices generadas son "+conta);
}
private void bactracking(int nivel)
{
if (nivel>TOPE*TOPE)
mostrarMatriz();
else
{ for(int i=0;i<2;i++)
{ obtenerFilaColumna(nivel);
mat[fila][columna]=i;
bactracking(nivel+1);
}
}
}
private void obtenerFilaColumna(int k)
{ columna= k % TOPE;
fila= k / TOPE;
if (columna!=0) columna--;
else
{fila--;
columna=TOPE-1;
}
}
private void mostrarMatriz(){
for(int i=0;i<TOPE;i++)
{ for(int j=0;j<TOPE;j++)
System.out.print(mat[j]+" ");
System.out.println();
}
System.out.println();
conta++;
}
public static void main(String[] args) {
nanograma x=new nanograma();
}
}

1 respuesta

1
Respuesta de Anónimo
Hola,
Parece que el problema comienza a complicarse :P La verdad es que no tengo experiencia práctica con problemas de ramificación y acotación, pero quizá pueda explicártelo con palabras.
Tu algoritmo trabaja sobre un árbol cuyas hojas son las soluciones del problema. Empieza desde la raíz, que es el primer estado (la matriz vacía, en tu caso), y en cada iteración tiene que ir bajando a un nivel inferior por una de las ramas (es decir, debe elegir al nodo hijo más "prometedor", o a través del cual pueda llegar a la mejor solución). Por tanto, para saber qué nodo hijo elegir, lo primero que tienes que hacer es fijar un criterio de valoración para los nodos, de manera que puedas establecer un orden de preferencias.
En tu caso, veo que estás trabajando en un programa relacionado con los nanogramas, así que supongo que las matrices toman valores binarios que pueden ser correctos o erróneos. Por tanto, un posible criterio de valoración podría ser el número de aciertos posibles (es decir, el número de elementos de la matriz, M por N) menos el número de errores de la matriz actual, o, lo que es lo mismo, el número de elementos erróneos. El valor resultante no sería el valor final, sino una cota superior. Es decir, a cuánto puedes aspirar como máximo si sigues por esa rama.
Imagina que tienes una matriz 2 x 2 con la primera fila a cero, y uno de esos elementos es erróneo. En tal caso, el valor de ese nodo es 4 - 1 = 3 (número de posibles aciertos, 2 x 2, menos errores). Otro nodo podría tener un 1 y un 0 en la primera fila, siendo ambos elementos erróneos, de manera que el valor del nodo correspondiente fuese 4 - 2 = 2. Por tanto, tu algoritmo exploraría el subárbol cuya raíz es el primer nodo, el valorado en 3 unidades, que es una cota superior.
Tu programa seguiría bajando por el árbol hasta llegar a los nodos hoja (es decir, los que no tienen descendientes o ramificaciones) y de esos elegiría el mejor, siguiendo el mismo criterio de valoración que el utilizado en la exploración del resto del árbol. El mejor nodo sería la solución final.
Es complicado de implementar y me falta tiempo para escribirte el código, pero en resumen lo primero que tienes que hacer es fijar un criterio de valoración como el que te he dicho.
Empieza por crear una función que te devuelva el número de errores de una matriz, y otra que se sirva de la primera para determinar el valor de esa matriz (es decir, el número de aciertos posibles, M x N, menos el número de errores) y yo intentaré buscar un hueco cuando pueda para ayudarte con el algoritmo, ¿ok?
¡Mucha suerte! ;-)
Añade un comentario a esta respuesta
Añade tu respuesta
Haz clic para o
Escribe tu mensaje