Transformacion de Cadenas - El camino a seguir

En el siguiente programa se complementa la clase ProblemaDistanciaCadenas para agregar un método que recorre la matriz de distancias para encontrar el camino de transformaciones que lleva de una cadena a la otra. Este método, que recibe el nombre de getCamino, recorre hacia atrás la matriz, mirando los elementos adyacentes que sean menores o que el elemento actual.

public class ProblemaDistanciaCadenas {
    String cadena1;
    String cadena2;
    int[][] distancia;

    ProblemaDistanciaCadenas(String c1, String c2) {
        cadena1=c1;
        cadena2=c2;
        distancia=new int[cadena1.length()+1][cadena2.length()+1];
    }

    public void mostrarMatriz() {
        System.out.print("      ");
        for(int i=0; i<cadena2.length(); i++) System.out.printf("%6s", cadena2.charAt(i));
        System.out.println();
        for(int i=0; i<distancia.length; i++) {
            if(i==0) System.out.print("  ");
            else System.out.printf("%2s", cadena1.charAt(i-1));
            for(int j=0; j<distancia[i].length; j++) {
                System.out.printf("%,4d  ", distancia[i][j]);
            }
            System.out.println();
        }
    }

    private int minimo(int... v) {
        int menor = Integer.MAX_VALUE;
        for(int x: v) if(x<menor) menor=x;
        return menor;
    }

    private void calcularDistancias() {
        char[] cad1 = cadena1.toCharArray();
        char[] cad2 = cadena2.toCharArray();
        for(int i=0; i<=cad1.length; i++) distancia[i][0]=i;
        for(int j=0; j<=cad2.length; j++) distancia[0][j]=j;
        for(int i=1; i<=cad1.length; i++) {
            for(int j=1; j<=cad2.length; j++) {
                int cambio=0;
                if(cad1[i-1]!=cad2[j-1]) cambio=1;
                distancia[i][j] = minimo(distancia[i-1][j]+1,           // borrar
                                         distancia[i][j-1]+1,           // insertar
                                         distancia[i-1][j-1]+cambio);   // cambiar
            }
        }
    }

    public int getDistancia() {
        int respuesta = distancia[distancia.length-1][distancia[0].length-1];
        return respuesta;

    }

    public void getCamino() {
        int i=distancia.length-1;
        int j=distancia[0].length-1;
        String[] ruta = new String[Math.max(cadena1.length(), cadena2.length())+1];
        int k=ruta.length;
         while(i+j>0) {
            if(i>0 && distancia[i-1][j]  < distancia[i][j]) {
                ruta[--k] = "Elimina '" + cadena1.charAt(--i)+"'";
            }
            else if(j>0 && distancia[i][j-1]  < distancia[i][j]) {
                ruta[--k] = "Inserta '" + cadena2.charAt(--j)+"'";
            }
            else if(i > 0 && j > 0 && distancia[i - 1][j - 1] < distancia[i][j]) {
                ruta[--k] = "Reemplaza '" + cadena1.charAt(--i) + "' por '" + cadena2.charAt(--j) + "'";
                continue;
            }
            else if(i > 0 && j > 0 && distancia[i - 1][j - 1] == distancia[i][j]) {
                ruta[--k] = "Avanza sin cambios";
                i--;
                j--;
            }
        }
       for(String x: ruta) System.out.println(x);
    }

    public static void main(String [] args) {
        ProblemaDistanciaCadenas pdc = new ProblemaDistanciaCadenas("algoritmos", "logaritmo");
        pdc.calcularDistancias();
        pdc.getCamino();
    }
}

La complejidad continúa siendo cuadrática pues la nueva función agregada solo recorre tantos elementos como filas o columnas tenga la matriz y no toda la matriz.

Transformación de Cadenas

Este algoritmo responde a la pregunta de cuántas transformaciones unitarias se deben hacer para convertir una cadena de caracteres en otra. Las transformaciones unitarias pueden ser de tres tipos: insertar, eliminar o reemplazar un caracter.

El algoritmo a implementar es conocido como la Distancia de Levenshtein, el cual implementa una solución por programación dinámica en la cual, con la ayuda de una matriz que tiene tantas filas como la cantidad de caracteres de una cadena más uno, y tantas columnas como la cantidad de caracteres de la otra cadena más uno, se calcula el número de transformaciones que se deben hacer para  transformar los N prefijos de la primera cadena en los M prefijos de la segunda cadena.

public class ProblemaDistanciaCadenas {
    String cadena1;
    String cadena2;
    int[][] distancia;

    ProblemaDistanciaCadenas(String c1, String c2) {
        cadena1=c1;
        cadena2=c2;
        distancia=new int[cadena1.length()+1][cadena2.length()+1];
    }

    public void mostrarMatriz() {
        System.out.print("      ");
        for(int i=0; i<cadena2.length(); i++) System.out.printf("%6s", cadena2.charAt(i));
        System.out.println();
        for(int i=0; i<distancia.length; i++) {
            if(i==0) System.out.print("  ");
            else System.out.printf("%2s", cadena1.charAt(i-1));
            for(int j=0; j<distancia[i].length; j++) {
                System.out.printf("%,4d  ", distancia[i][j]);
            }
            System.out.println();
        }
    }

    private int minimo(int... v) {
        int menor = Integer.MAX_VALUE;
        for(int x: v) if(x<menor) menor=x;
        return menor;
    }

    private void calcularDistancias() {
        char[] cad1 = cadena1.toCharArray();
        char[] cad2 = cadena2.toCharArray();
        for(int i=0; i<=cad1.length; i++) distancia[i][0]=i;
        for(int j=0; j<=cad2.length; j++) distancia[0][j]=j;
        for(int i=1; i<=cad1.length; i++) {
            for(int j=1; j<=cad2.length; j++) {
                int cambio=0;
                if(cad1[i-1]!=cad2[j-1]) cambio=1;
                distancia[i][j] = minimo(distancia[i-1][j]+1,           // borrar
                                         distancia[i][j-1]+1,           // insertar
                                         distancia[i-1][j-1]+cambio);   // cambiar
            }
        }
    }

    public int getDistancia() {
        int respuesta = distancia[distancia.length-1][distancia[0].length-1];
        return respuesta;

    }

    public static void main(String [] args) {
        ProblemaDistanciaCadenas pdc = new ProblemaDistanciaCadenas("Hola", "Colas");
        pdc.calcularDistancias();
        pdc.mostrarMatriz();
        System.out.println(pdc.getDistancia());
    }
}

La complejidad del algoritmo es cuadrática, o más exactamente, O(NxM), donde N es el tamaño de la primera cadena y M el de la segunda.

Problema de las Reinas - Version 2

Image via Wikipedia

Teniendo en cuenta que en cada fila del tablero de ajedrez solo puede ir una reina, entonces es posible modelar el problema utilizando un solo vector, en el que hay tantas posiciones como filas, y el valor para cada posición es la columna en la cual se encuentra ubicada la reina de dicha fila.

La sugerencia (sin código)  para realizar esta solución está en el blog de prothotype.  La estrategia a utilizar está basada en backtracking y recursividad al igual que la solución presentada anteriormente.

public class ProblemaReinas2 {
    final int numFilas;
    int[]   tablero;
    int     contador;
    int     correctas=0;

    public ProblemaReinas2(int nf) {
        numFilas    = nf;
        tablero     = new int[nf];
        for(int i=0; i<tablero.length; i++) tablero[i]=-1;
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero.length; j++) {
                if(tablero[i]==j) System.out.printf("  %2d  |", tablero[i]+1);
                else System.out.printf("      |");
            }
            System.out.println();
            for(int j=0; j<tablero.length; j++) System.out.print("------+");
            System.out.println();
        }
        System.out.println();
    }

    public boolean resolverProblema(int fila, int columna) {
        //mostrarTablero();
        contador++;
        tablero[fila]=columna;
        correctas++;
        if(correctas==numFilas) return true;
        int[] posibles = buscarPosibles(fila+1);
        for(int c: posibles) {
            if(resolverProblema(siguienteFila(), c)) return true;
        }
        tablero[fila]=-1;
        correctas--;
        return false;
    }

    public int siguienteFila() {
        for(int i=0; i<tablero.length; i++) if(tablero[i]==-1) return i;
        return -1;
    }

    int[] buscarPosibles(int num) {
        int[] resp = new int[numFilas];
        int pos=numFilas;
        for(int i=0; i<resp.length; i++) resp[i]=i;
        for(int i=0; i<numFilas; i++) {
            if(tablero[i]!=-1) {
                resp[tablero[i]]=-1;
                pos--;
            }
        }
        for(int i=0; i<resp.length; i++) {
            if(resp[i]==-1) continue;
            for(int j=0; j<num; j++) {
                double fabs = Math.abs((num-j)*1.0/(resp[i]-tablero[j]));
                if(fabs==1.0 && resp[i]!=-1) {
                    resp[i]=-1;
                    pos--;
                    break;
                }
            }
        }
        int[] tmp = new int[pos];
        int i=0;
        for(int x: resp) if(x!=-1) tmp[i++] = x;
        return tmp;
    }

    public static void main(String[] args) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas2 pr = new ProblemaReinas2(numFilas);
        pr.resolverProblema(filaInicial, colInicial);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}

Problema de las Reinas

El siguiente programa muestra como resolver el problema de las 8 reinas, generalizado para cualquier tamaño de tablero. El problema en sí trata de encontrar una forma de posicionar n reinas en un tablero de ajedrez de tamaño n x n, de tal manera que ninguna de las reinas ataque a ninguna de las otras. Una reina ataca todas las casillas que se encuentren en la misma fila, en la misma columna, o en las diagonales de la casilla en que está ubicada.

Este problema utiliza un esquema igual al utilizado en la solución del problema del salto del caballo, modelando el tablero como una matriz de n x n y utilizando un enfoque de backtracking para marcar una casilla, generar una lista de las siguientes casillas que no están amenazadas y revisar dicha lista en forma recursiva; si no se llega a la respuesta correcta, se devuelve el proceso para continuar con las siguiente casillas de la lista.

public class ProblemaReinas {
    final int numFilas;
    final int numColumnas;
    int[][] tablero;
    int     contador;

    public ProblemaReinas(int nf) {
        numFilas    = nf;
        numColumnas = nf;
        tablero     = new int[nf][nf];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                if(tablero[i][j]>0) System.out.printf("  %2d  |", tablero[i][j]);
                else System.out.printf("      |", tablero[i][j]);
            }
            System.out.println();
            for(int j=0; j<tablero[i].length; j++) System.out.print("------+");
            System.out.println();
        }
    }

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas) return true;
            int[][] posibles = buscarPosibles();
            for(int i=0; i<posibles.length; i++) {
                if(resolverProblema(posibles[i][0], posibles[i][1], num+1)) return true;
            }
            tablero[f][c]=0;
            return false;
    }

    int[][] buscarPosibles() {
        int[][] resp = new int[numFilas*numColumnas][2];
        int[] sumaFilas = new int[numColumnas];
        int[] sumaColumnas = new int[numFilas];
        int     pos  = 0;
        for(int i=0; i<numFilas; i++) {
            for(int j=0; j<numColumnas; j++) {
                if(tablero[i][j]>0) {
                    sumaFilas[i]++;
                    sumaColumnas[j]++;
                }
            }
        }
        for(int i=0; i<numFilas; i++) {
            if(sumaFilas[i]>0) continue;
            for(int j=0; j<numColumnas; j++) {
                if(sumaColumnas[j]>0) continue;
                if(i>0 && j>0             && tablero[i-1][j-1] > 0) continue;
                if(i>0 && j<numColumnas-1 && tablero[i-1][j+1] > 0) continue;
                if(i<numFilas-1 && j>0    && tablero[i+1][j-1] > 0) continue;
                if(i<numFilas-1 && j<numColumnas-1 && tablero[i+1][j+1] > 0) continue;
                resp[pos][0]=i;
                resp[pos][1]=j;
                pos++;
            }
        }
        int[][] tmp = new int[pos][2];
        for(int i=0; i<pos; i++) { tmp[i][0] = resp[i][0]; tmp[i][1]=resp[i][1]; }
        return tmp;
    }

    boolean esValido(int f, int c) {
        if(f<0 || f>numFilas-1 || c<0 || c>numColumnas-1) return false;
        if(tablero[f][c]!=0) return false;
        return true;
    }

    public static void main(String[] args) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas pr = new ProblemaReinas(8);
        pr.resolverProblema(filaInicial, colInicial,1);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}

Máquina Virtual con AntLR

A continuación se presenta una primera versión de una máquina virtual escrita en ANTLR que reconoce un lenguaje con las siguientes posibles instrucciones: ADD, SUB, MUL, DIV, EXP, AND, OR, PUSH, STORE, WRITE, WRITELN, GOTO y JZERO:

grammar maquinavirtual;

@header {
 import java.util.Vector;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Stack;
}
@members{
 enum TipoInstruccion { vPUSH, cPUSH, STORE, ADD, SUB, MUL, DIV, EXP, AND, OR, cWRITE, WRITE, vWRITE, WRITELN, GOTO, JZERO }
 class Instruccion{
  TipoInstruccion tipo;
  int     operador;
  Instruccion(TipoInstruccion t, int o) { tipo = t; operador = o; }
  Instruccion(TipoInstruccion t)   { this(t,-1); }
 }
 
 Vector<Instruccion> tablaPrograma  = new Vector<Instruccion>();
 Vector<String>   tablaCadenas   = new Vector<String>();
 Vector<Double>   tablaConstantes = new Vector<Double>();
 Vector<String>   tablaVariables  = new Vector<String>();
 Stack<Double>   pila     = new Stack<Double>();
 Map<String,Double> memoria    = new HashMap<String,Double>();
 
 public void agregar(TipoInstruccion t) { tablaPrograma.add(new Instruccion(t)); }
 public void agregarStore(String var) {
  if(!tablaVariables.contains(var)) tablaVariables.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.STORE, tablaVariables.indexOf(var)));
 }
 public void agregarVPush(String var) {
  if(!tablaVariables.contains(var)) tablaVariables.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.vPUSH, tablaVariables.indexOf(var)));
 }
 public void agregarcPush(String val) {
  double num = Double.parseDouble(val);
  if(!tablaConstantes.contains(num)) tablaConstantes.add(num);
  tablaPrograma.add(new Instruccion(TipoInstruccion.cPUSH, tablaConstantes.indexOf(num)));
 }
 public void agregarWrite(String var) {
  var=var.substring(1,var.length()-1);
  if(!tablaCadenas.contains(var)) tablaCadenas.add(var);
  tablaPrograma.add(new Instruccion(TipoInstruccion.cWRITE, tablaCadenas.indexOf(var)));
 }
 public void agregarGoto(String val) {
  int num = (int) Double.parseDouble(val);
  tablaPrograma.add(new Instruccion(TipoInstruccion.GOTO, num));
 }
 public void agregarJZero(String val) {
  int num = (int) Double.parseDouble(val);
  tablaPrograma.add(new Instruccion(TipoInstruccion.JZERO, num));
 }
 public void ejecutar() {
  double a, b;
  for(int i=0; i<tablaPrograma.size(); i++) {
   Instruccion ins = tablaPrograma.get(i);
   switch(ins.tipo) {
    case ADD: b=pila.pop(); a=pila.pop(); pila.push(a+b); break;
    case SUB: b=pila.pop(); a=pila.pop(); pila.push(a-b); break;
    case DIV: b=pila.pop(); a=pila.pop(); pila.push(a*b); break;
    case MUL: b=pila.pop(); a=pila.pop(); pila.push(a/b); break;
    case EXP: b=pila.pop(); a=pila.pop(); pila.push(Math.pow(a,b)); break;
    case AND: b=pila.pop(); a=pila.pop(); pila.push(a==1.0 && b==1.0 ? 1.0: 0.0); break;
    case OR:  b=pila.pop(); a=pila.pop(); pila.push(a==1.0 || b==1.0 ? 1.0: 0.0); break;
    case WRITE:  System.out.print(pila.pop()); break;
    case WRITELN: System.out.println(); break;
    case cWRITE: System.out.print(tablaCadenas.get(ins.operador)); break;
    case cPUSH: pila.push(tablaConstantes.get(ins.operador)); break;
    case vPUSH: pila.push(memoria.get(tablaVariables.get(ins.operador))); break;
    case STORE: memoria.put(tablaVariables.get(ins.operador), pila.pop()); break;
    case GOTO: i=(int) ins.operador-2; break;
    case JZERO: if(pila.pop()==0) i=(int) ins.operador-2; break;
   }
  }
 }
}

programa  : instruccion+  { ejecutar(); } ;

instruccion : 'push' VARIABLE { agregarVPush($VARIABLE.text); }
    | 'push' NUMERO { agregarcPush($NUMERO.text); }
    | 'store' VARIABLE { agregarStore($VARIABLE.text); }
    | 'add'     { agregar(TipoInstruccion.ADD);}
    | 'sub'     { agregar(TipoInstruccion.SUB);}
    | 'mul'     { agregar(TipoInstruccion.MUL);}
    | 'div'     { agregar(TipoInstruccion.DIV);}
    | 'exp'     { agregar(TipoInstruccion.EXP);}
    | 'and'     { agregar(TipoInstruccion.AND);}
    | 'or'     { agregar(TipoInstruccion.OR);}
    | 'write' CADENA { agregarWrite($CADENA.text); }
    | 'write'    { agregar(TipoInstruccion.WRITE); }
    | 'writeln'  { agregar(TipoInstruccion.WRITELN); }
    | 'goto' NUMERO { agregarGoto($NUMERO.text); }
    | 'jzero' NUMERO { agregarJZero($NUMERO.text); }
    ;
    
fragment DIGITO : '0'..'9';
fragment LETRA  : 'a'..'z'|'A'..'Z';
NUMERO    :  DIGITO+('.' DIGITO+)?;
VARIABLE    : LETRA ( LETRA|DIGITO)*;
CADENA    : '"'.*'"';
ESPACIO    : (' '|'\t'|'\n'|'\r') { skip(); } ;
RESTO     : . ;      

Puede probar la máquina virtual desde AntLR con el siguiente programa de prueba:

push 4
store  a
push 3
store b
push a
push b
add
write
writeln
write "El fin"

El problema del recorrido del caballo de ajedrez - heuristicas

La solución al problema del recorrido del caballo de ajedrez encontrada con el método de backtracking se tarda un tiempo considerable porque evalúa demasiadas alternativas que no forman parte de la solución. La prueba en un computador con procesador Intel core i5 con Windows 7 tardó cerca de 40 minutos con 67,890,999,999,999 de ensayos.

Una solución utilizando heurísticas para este problema se enfoca en la manera en cómo se evalúan las celdas una vez se ha marcado una de ellas y propone que la asignación del orden en que se evalúan las casillas dependa de la cantidad de casillas a la que cada una de ellas tenga alcance. Es decir, por ejemplo, que si una vez marcada una casilla, ésta tiene 5 posibles celdas a las que el caballo puede saltar, se debe ir primero a aquella casilla que tenga menos saltos posibles.

Para implementar esta solución, sólo debe agregarse a la solución propuesta anteriormente un método que ordene el arreglo de posibles casillas y llamar a dicha función una vez se calcule dicho arreglo así:

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas*numColumnas) return true;
            int[][] posibles = buscarPosibles(f, c);
            ordenarPosibles(posibles);              // llamado a la nueva función
            for(int i=0; i<posibles.length; i++) {
                if(resolverProblema(posibles[i][0], posibles[i][1], num+1)) return true;
            }
            tablero[f][c]=0;
            return false;
    }

    // nuevo método: ordena el arreglo de posibles casillas a saltar
    void ordenarPosibles(int[][] posibles) {
        for(int i=0; i<posibles.length; i++) {
            for(int j=i+1; j<posibles.length; j++) {
                int cuantosPosiblesI = buscarPosibles(posibles[i][0], posibles[i][1]).length;
                int cuantosPosiblesJ = buscarPosibles(posibles[j][0], posibles[j][1]).length;
                if(cuantosPosiblesJ<cuantosPosiblesI) {
                    int tmp0 = posibles[i][0];
                    posibles[i][0] = posibles[j][0];
                    posibles[j][0] = tmp0;
                    int tmp1 = posibles[i][1];
                    posibles[i][1] = posibles[j][1];
                    posibles[j][1] = tmp1;
                }
            }
        }
    }

Con este cambio el proceso tarda algo menos de un segundo y sólo tiene que entrar 64 veces al proceso de marcado de casillas, es decir, no hace ningún retroceso.

El problema del recorrido del caballo de ajedrez - backtracking

La peregrinación del caballo de ajedrez consiste en su paseo por todas las casillas del tablero sin pasar dos veces por la misma, utilizando sus movimientos: dos casillas horizontales y una vertical o a la inversa. Cuando desde la última casilla podamos pasar a la primera se trata de una "peregrinación cerrada".

Para resolver este problema se puede utilizar la técnica de backtracking con un algoritmo recursivo relativamente simple: marcar la posición solicitada, hacer una lista de las siguientes posiciones vacías a las que se puede saltar desde la posición marcar, y tomar la primera de ellas, marcándola entonces en forma recursiva. Si en alguno de los pasos recursivos no se alcanza una solución, la casilla se desmarca y se pasa a la siguiente que estaba en la lista. Si se termina la lista y no se llega a una solución, entonces se devuelve a la casilla anterior desde la que se hizo el llamado.

La solución en JAVA para esta solución es la siguiente:

public class ProblemaCaballo {
    final int numFilas;
    final int numColumnas;
    int[][] tablero;
    int     contador;

    public ProblemaCaballo(int nf, int nc) {
        numFilas = nf;
        numColumnas = nc;
        tablero     = new int[nf][nc];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                System.out.printf("  %2d  |", tablero[i][j]);
            }
            System.out.println();
            for(int j=0; j<tablero[i].length; j++) System.out.print("------+");
            System.out.println();
        }
    }

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas*numColumnas) return true;
            int[][] posibles = buscarPosibles(f, c);
            for(int i=0; i<posibles.length; i++) {
                if(resolverProblema(posibles[i][0], posibles[i][1], num+1)) return true;
            }
            tablero[f][c]=0;
            return false;
    }

    int[][] buscarPosibles(int f, int c) {
        int[][] resp = new int[8][2];
        int     pos  = 0;
        if(esValido(f-2,c-1)){ resp[pos][0]=f-2; resp[pos++][1]=c-1; }
        if(esValido(f-2,c+1)){ resp[pos][0]=f-2; resp[pos++][1]=c+1; }
        if(esValido(f-1,c-2)){ resp[pos][0]=f-1; resp[pos++][1]=c-2; }
        if(esValido(f-1,c+2)){ resp[pos][0]=f-1; resp[pos++][1]=c+2; }
        if(esValido(f+2,c-1)){ resp[pos][0]=f+2; resp[pos++][1]=c-1; }
        if(esValido(f+2,c+1)){ resp[pos][0]=f+2; resp[pos++][1]=c+1; }
        if(esValido(f+1,c-2)){ resp[pos][0]=f+1; resp[pos++][1]=c-2; }
        if(esValido(f+1,c+2)){ resp[pos][0]=f+1; resp[pos++][1]=c+2; }
        int[][] tmp = new int[pos][2];
        for(int i=0; i<pos; i++) { tmp[i][0] = resp[i][0]; tmp[i][1]=resp[i][1]; }
        return tmp;
    }

    boolean esValido(int f, int c) {
        if(f<0 || f>numFilas-1 || c<0 || c>numColumnas-1) return false;
        if(tablero[f][c]!=0) return false;
        return true;
    }

    public static void main(String[] args) {
        ProblemaCaballo pc = new ProblemaCaballo(8,8);
        pc.resolverProblema(0,0,1);
        pc.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pc.contador);
    }
}

Problema de la mochila - Algoritmos Voraces

Si bien la solución por backtracking permite obtener la mejor solución al problema de la mochila, existe el problema de que cuando la cantidad de elementos a evaluar es relativamente grande, los tiempos de respuesta se vuelven prohibitivos. Por otro lado, la solución de agregar primero los elementos más costosos, o lo más livianos, no garantiza una solución óptima, o por lo menos parecida a la óptima.

Estas dos aproximaciones representan el concepto de algoritmos voraces, donde se selecciona una estrategia que permite decidir si un elemento se agrega o no a la solución. En los casos mencionados se utilizaba la estrategia del mayor costo o la del menor peso. Una mejor solución se presenta cuando se utiliza el costo por unidad de peso para ordenar los elementos, de esta manera, un elemento muy caro no se agrega si pesa demasiado en comparación con otro de menor valor, pero de mucho menor peso. La función resolverProblema queda entonces de la siguiente manera:

    public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor/x.peso - y.valor/y.peso);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

En cuanto al desempeño de este método, su complejidad es la equivalente al proceso de ordenación de la lista de elementos por su valor por unidad de peso, que es O(N log N), ya que el proceso de llenado de la mochila es lineal.

En el caso de ejemplo, este método da una respuesta con un peso total de 18 Kg y un costo de $945, mientras que la respuesta obtenida por backtracking es de 20 Kg con un costo de $955, lo que muestras que se obtiene un valor muy cercano al óptimo en una fracción del tiempo.

Problema de la mochila - Backtracking

Resolver el problema de la mochila seleccionando los elementos más caros en primer lugar, o los más livianos, no necesariamente garantiza llegar a una solución ideal, pues es posible que otras combinaciones de elementos produzcan mejores resultados.

Para obtener la solución ideal se deben revisar todas las alternativas; y en este caso, se puede utilizar una estrategia de retroceso, o backtracking. En esta implementación, iniciando en el primer elemento del almacén, se evalúan dos posibilidades, agregar o no agregar el elemento a la mochila, y llamando recursivamente el método hasta que la mochila se llena; una vez llena, se compara con el máximo calculado anteriormente y se guarda la lista de elementos que genere el mayor valor en la mochila. Esta solución requiere una mochila temporal (tmpMochila) que se crea en forma similar a la mochila definitiva, y dos métodos que calculen el valor y el peso acumulado de dicha mochila temporal. La implementación queda entonces de la siguiente manera:

// Solución por backtracking
    public void resolverProblemaBT(int posicion) {
        double  pesoMochila=getPeso(tmpMochila);    // peso de la solucion temporal
        double valorMochila=getValor(tmpMochila);   // valor de la solucion temporal

        if( posicion>=almacen.size() ) {            // si ya se tuvieron en cuenta todos los elementos
            if(valorMochila>valorMaximo) {          // si el valor es mayor que el máximo anterior
                valorMaximo=valorMochila;           // se actualiza el valor mayor
                mochila.clear();
                mochila.addAll(tmpMochila);
            }
            return;
        }
        Elemento e = almacen.get(posicion);
        // Si el elemento se puede agregar, se envía a la mochila temporal
        if(pesoMochila + e.peso <= pesoMaximo) {
                tmpMochila.add(e);                  // Se agrega a la mochila temporal
                resolverProblemaBT(posicion+1);     // se revisa para el siguiente elemento
                tmpMochila.remove(e);               // Se retira el elemento
        }
        // Si no se pudo agregar, o ya se agregó y se retiró, se revisa para el siguiente
        resolverProblemaBT(posicion+1);
    }

    double getPeso(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.peso;
        return respuesta;
    }

    double getValor(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.valor;
        return respuesta;
    }

El método de invocación quedaría de la siguiente manera (no olvidar crear el vector tmpMochila como un Vector de objetos de tipo Elemento):

    public static void main(String[] args) {
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblemaBT(0);       // Inicia en el primer elemento disponible
        pm.mostrarMochila();
    }

Este método devuelve la solución óptima, puesto que evalúa todas las posibilidades, sin embargo, cuando el número de elementos disponibles es relativamente grande, la cantidad de operaciones a realizar hace prácticamente imposible utilizar el algoritmo, ya que su complejidad es del orden de O(N!), donde N es la cantidad de elementos del almacén.

Problema de la mochila

El problema de la mochila es un problema típico de programación entera que responde a la siguiente situación: imagínese que un ladrón entra a un almacén para substraer una serie de elementos con una única mochila que tiene una capacidad limitada en cuanto al peso que puede contener. Cada objeto que se introduce carga la mochila con más peso, pero a su vez representa un beneficio económico por el valor del mismo. El problema surge cuando se debe elegir qué objetos seleccionar para llevar en la mochila de forma que el beneficio sea máximo.

Esta situación se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar la restricción presupuestaria (cantidad máxima de recursos económicos de los que se dispone) y donde la utilidad de los objetos seleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertas acciones.

Para modelar este problema se utilizará una clase denominada Elemento que contendrá solamente la descripción de cada elemento, su peso y su valor, así:

class Elemento {
    String nombre;
    double valor;
    double peso;
    Elemento(String n, double v, double p) {
        nombre=n;
        valor =v;
        peso  =p;
    }
    public String toString() {
        return String.format("%-15s %,12.2f %,12.2f", nombre, valor, peso);
    }
}

La modelación termina con una clase denominada ProblemaMochila en la que se crearán dos vectores para simular el almacén, es decir, los elementos disponibles, y la mochila, dónde se ubicarán los elementos a ser substraídos. Se tienen métodos adicionales para mostrar el contenido de la mochila, así como para llenar el almacén con los elementos iniciales:

import java.util.*;

public class ProblemaMochila {
    Vector<Elemento> almacen = new Vector<Elemento>();
    Vector<Elemento> mochila = new Vector<Elemento>();
    final double  pesoMaximo;

    public ProblemaMochila(int pm) {
        pesoMaximo = pm;
        cargarDatos();
    }

    public void cargarDatos() {
        almacen.add(new Elemento("TV",        300, 15));
        almacen.add(new Elemento("PS3",       100,  3));
        almacen.add(new Elemento("Libro Java", 10,  1));
        almacen.add(new Elemento("DVD Player",  5,  0.5));
        almacen.add(new Elemento("Blu-Ray",    50,  0.5));
        almacen.add(new Elemento("Balon",      30,  0.5));
        almacen.add(new Elemento("iPod",      150,  1));
        almacen.add(new Elemento("Printer",    20,  4));
        almacen.add(new Elemento("VideoBeam", 200,  4));
        almacen.add(new Elemento("LapTop",     20,  3));
        almacen.add(new Elemento("iPad",      150,  2));
        almacen.add(new Elemento("PC",        100,  5));
        almacen.add(new Elemento("BlackBerry",150,  0.5));
   }

     public void mostrarMochila() {
        double pesoMochila=0;
        double valorMochila=0;
        System.out.println();
        for(Elemento e: mochila) {
            System.out.println(e);
            pesoMochila+=e.peso;
            valorMochila+=e.valor;
        }
        System.out.println("------");
        System.out.printf("Peso  = %,12.2f %n", pesoMochila);
        System.out.printf("Valor = %,12.2f %n", valorMochila);
    }

    public static void main(String[] args) {
        // Crear una mochila que soporta hasta 20 Kg. de peso
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblema();
        pm.mostrarMochila();
    }
}

Para resolver el problema existen varias estrategias, entre las cuales pueden estar la de ir llenando la mochila con los elementos más costosos, o con los elementos menos pesados. En el caso de llenar la mochila con los elementos más costosos primero, el método resolverProblema se plantearía así:

public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor - y.valor);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

Si se quiere ordenar usar otra estrategia, como la de ir llenando la mochila en primer lugar con los elementos más livianos, bastaría cambiar el comparador cmp para que reste pesos en lugar de valores

Proximamente se publicarán otros enfoques para resolver este problema.

Gramática de Lenguaje con Acciones Semánticas en ANTLR

La siguiente gramática en AntLR permite reconocer un pequeño lenguaje de programación que implementa desde el punto de vista léxico, números (enteros o reales positivos), variables y cadenas de caracteres.

Desde el punto de vista sintáctico, los programas se ven como una lista de instrucciones que, a su vez, pueden ser del tipo asignación, escritura, condicional, iterativa, de incremento o de decremento. La asignación de variables se hace sobre expresiones algebraicas que permiten el uso de variables, números, sumas, restas, multiplicaciones, divisiones y potencias, al igual que subexpresiones entre paréntesis.

Desde el punto de vista semántico, esta gramática traduce el texto recibido en un conjunto de instrucciones para ser ejecutado por una máquina virtual.

@header{
 package analizadores;
 import java.util.Vector;
 import java.util.HashSet;
}
@lexer::header{
 package analizadores;
}


// FUNCIONES PROPIAS DEL LENGUAJE
@members {
 Vector< String > vectorSalida=new Vector< String >();
 HashSet< String > variablesInicializadas=new HashSet< String >();
 
 public void escribir(String mensaje) {
  vectorSalida.add(mensaje);
 }
 public String getSalida() {
  String salida="";
  for(String x: vectorSalida) {
   salida+=(x+"\n");
  }
  return salida;
 }
 String errores="";
 public void emitErrorMessage(String mensaje) {
  errores+=(mensaje+"\n");
 }
 public String getErrores() { return errores; }
}

// REGLAS GRAMATICALES O SINTACTICAS
programa    : instruccion+ { System.out.println(getSalida()); };

instruccion   : v=VARIABLE '=' expresion ';'   { escribir("store \t"+$v.text); variablesInicializadas.add($v.text); } 
      | WRITE elemento (',' elemento)* ';' { escribir("writeln"); }
      |  condicional
      | iterativa
      | incremento
      | decremento
      ;
      
condicional   : IF '(' condicion ')' { int linea1 = vectorSalida.size(); escribir("jeq"); }
         bloque      { int linea2 = vectorSalida.size(); escribir("jump"); }
                { vectorSalida.set(linea1, "jeq\t" + (linea2+2)) ; }
         ( ELSE bloque )?  { vectorSalida.set(linea2, "jump\t" + (vectorSalida.size()+1)); }
      ;
      
iterativa   : WHILE       { int linea1 = vectorSalida.size(); }
        '('condicion ')'   { int linea2 = vectorSalida.size(); escribir("jeq"); }
        bloque      { escribir("jump\t"+ (linea1+1)); vectorSalida.set(linea2, "jeq\t"+(vectorSalida.size()+1));}
      ;
      
bloque    : instruccion 
      | '{' instruccion* '}'
      ;      
      
elemento    : expresion { escribir("write"); }
      | s=STRING  { escribir("write\t"+ $s.text); }
      ;      
      
expresion   : termino ( '+' termino {escribir("add");}
                             | '-' termino {escribir("sub");})* 
                  ;
                                  
termino    : factor ( '*' factor  {escribir("mul");}
          | '/' factor  {escribir("div");})* 
          ;
          
factor    : valor ( '^' valor {escribir("exp");} )*
      ;          
          
valor     : a=NUMERO      { escribir("push \t"+ $a.text); }
      | v=VARIABLE     { if(variablesInicializadas.contains($v.text)) escribir("push \t"+ $v.text); 
                 else emitErrorMessage($v.line+", "+$v.getCharPositionInLine()+": Variable no inicializada: " + $v.text);}
      | '(' expresion ')'
      ;

condicion   : expresion ( '>=' expresion { escribir("ge"); }
           | '<=' expresion { escribir("le"); }
           | '>'  expresion  { escribir("gt"); }
           | '<'  expresion  { escribir("lt"); }
           | '==' expresion  { escribir("eq"); }
           | '!=' expresion  { escribir("ne"); }
           ) ;

incremento   : v=VARIABLE '++' ';' {escribir("inc\t"+$v.text); } ;
decremento   : v=VARIABLE '--' ';' {escribir("dec\t"+$v.text); } ;

// REGLAS LEXICAS
fragment DIGITO : '0'..'9';
fragment LETRA  : 'a'..'z'|'A'..'Z';
NUMERO    : DIGITO+ '.'? DIGITO* ;
WRITE     : 'write'|'escriba'|'imprima'|'print';
IF      : 'if'|'si';
ELSE     : 'sino'|'else';
WHILE     : 'while'|'mientras'|'mientras que';
VARIABLE    : LETRA ( LETRA|DIGITO)* ;
ESPACIO    : (' '|'\t'|'\r'|'\n')  { skip(); } ;

COMMENT    :   '//' ~('\n'|'\r')* '\r'? '\n'      {$channel=HIDDEN;}
         |   '/*' ( options {greedy=false;} :  . )* '*/' {$channel=HIDDEN;}
         ;

STRING    :  '"' ( ESC_SEQ | ~('\\'|'"') )* '"'  ;

fragment ESC_SEQ :  '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
      |   UNICODE_ESC
      |   OCTAL_ESC
      ;
fragment UNICODE_ESC
      : '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
      ;
fragment HEX_DIGIT: ('0'..'9'|'a'..'f'|'A'..'F') ;
fragment OCTAL_ESC: '\\' ('0'..'3') ('0'..'7') ('0'..'7')
      |  '\\' ('0'..'7') ('0'..'7')
      |   '\\' ('0'..'7')
      ;
OTROCARACTER  : .        { System.out.println("error"); } ;

En una próxima entrada se estará publicando el cógido en AntLR también de la máquina virtual y las instrucciones para compilar, ejecutar y probar el lenguaje.

Operaciones con números grandes - multiplicación

Para la multiplicación de dos números grandes se puede utilizar, además de los métodos disponibles en la clase BigInteger, un enfoque basado en la multiplicación de uno de los números grandes por cada uno de los dígitos del otro, y haciendo las sumas correspondientes.

A continuación se presentan dos funciones de multiplicación para números grandes. En la primera se implementa la multiplicación de un entero grande por un dígito, y en la segunda, la de dos enteros grandes utilizando el método anterior y el de la suma de enteros grandes publicado anteriormente:

public static String multiplicacion(String nA, String nB) {
        String respuesta="0";
        String ceros="";
        int posA = nA.length()-1;
        while(posA>=0) {
            respuesta=suma(respuesta,multiplicacion(nA.charAt(posA),nB)+ceros);
            ceros+="0";
            posA--;
        }
        return respuesta;
    }

    public static String multiplicacion(char digito, String nB) {
        String respuesta="";
        int digA=digito-'0';
        int posB=nB.length()-1;
        int digB;
        int resto=0;
        while(posB>=0) {
            digB = nB.charAt(posB)-'0';
            int c = digA*digB+resto;
            resto=c/10;
            c = c%10;
            respuesta=c+respuesta;
            posB--;
        }
        if(resto>0) respuesta=resto+respuesta;
        return respuesta;
    }
}

Operaciones con números grandes - suma

Los lenguajes de programación manejan tipos de datos enteros, en los cuales hay un valor determinado para el número entero más grande que se puede manejar, teniendo en cuenta que para su almacenamiento se utiliza un determinado número de posiciones de memoria. En el caso de JAVA, un número entero ocupa 64 bits de memoria, por lo que el mayor número entero que se puede manejar es 9,223,372,036,854,775,807 equivalente a dos elevado a la 63 menos 1 (más información en el tutotial oficial de java).

El manejo de operaciones aritméticas simples con números enteros mayores al límite máximo permitido se debe manejar utilizando otro tipo de estrategias. Se puede utilizar la clase BigInteger que tiene implementados métodos para suma y multiplicación de números enteros grandes, o se puede hacer un ejercicio de programación utilizando la cadenas de caracteres (ó arreglos de caracteres) y el procedimiento de suma elemental que consiste en alinear los números e ir sumando los dígitos menos significativos de cada número y acumulando la respuesta en una nueva cadena.

A continuación se presenta una primera versión del método de suma de números enteros grandes:

public static String suma(String nA, String nB) {
        String respuesta="";
        int posA = nA.length()-1;
        int posB = nB.length()-1;
        int resto = 0;
        int digA, digB;

        while(posA>=0 || posB>=0) {
            digA = (posA>=0) ? nA.charAt(posA)-'0': 0;
            digB = (posB>=0) ? nB.charAt(posB)-'0': 0;
            int c = digA+digB+resto;
            if(c>=10) { resto=1; c=c-10;}
            else resto=0;
            respuesta=c+respuesta;
            posA--;
            posB--;
        }
        if(resto>0) respuesta=resto+respuesta;
        return respuesta;
}