Translate

viernes, 28 de octubre de 2011

Ejemplo memorización Uva online judge Problema 11151 Longest Palindrome


11151 Longest Palindrome

Autor: Rodrigo Burgos Domínguez.



La lectura del problema es simple aun que resolverlo no es algo trivial, el problema dice en pocas palabras.

   Que dada una cadena uno puede eliminar caracteres de esta cadena ( y digo caracteres por que pueden ser cualquier carácter consonantes, vocales, espacios, signos de puntuación, etc. ), el objetivo de borrar caracteres es formar un palíndromo.

  Wikipedia define a un palíndromo como:

Un palíndromo (del griego palin dromein, volver a ir hacia atrás) es una palabra, número o frase que se lee igual hacia adelante que hacia atrás. Si se trata de un número, se llama capicúa. Habitualmente, las frases palindrómicas se resienten en su significado cuanto más largas son.

Bueno en pocas palabras debemos obtener una cadena que sea un palíndromo ( que se escriba igual de izquierda a derecha que de derecha a izquierda) y no solo encontrar una, si no obtener el tamaño del palíndromo mas grande que encontremos.

Bueno primero debemos resolver el problema de leer una cadena con sus espacios , como yo utilizo el lenguaje C se puede leer con un gets o una modificación a un scanf, por simplicidad utilizaremos el gets.

¿Como seria el main de nuestro programa?  Seria algo como esto

main(){
  int ncases, cases;
  for( gets(word), sscanf(word, "%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    gets( word );
    memset(  din, -1, sizeof( din ));
   printf("%d\n", solve( 0 , strlen( word ) - 1));
  }
  return 0;     
}

leo con un gets la primera cadena luego con un sscanf leo de esta cadena (Word) el numero de casos de prueba en ncases, ¿por que hacerlo así?, esto se hace para leer solo una línea del archivo de entra así como su enter al fina ( con un scanf seria algo asi scanf(“%d\n”, &ncases); si nos garantizaran que no hay espacios después de los casos de entrada, o para leer una cadena con todo y el enter omitirlo como el gets seria scanf(“%[^\n]%*c”, word); , esto significa que voy a leer una cadena hasta encontrar el enter  y ahí paro, y además voy a leer un carácter adicional sin guardarlo).
Luego  leemos la palabra, con scanf(“%s”, word); esta palabra a lo mucho va a tener 1000 caracteres.

Para resolver este problema voy a utilizar programación dinámica, aun que en su versión de memorization, con memorization lo único que cambia es que va a ser de forma recursiva y yo voy a memorizar las posición ya procesadas, y es por eso que inicializo la matriz din en menos unos (-1), esto lo hago con un memset que es una función para cadenas , lo que hace es que para cada byte de memoria del objeto puesto al inicio de los parametros lo cambia por el valor que hay en el centro, cuantos de estos bytes , pues los que indiques en el tercer parámetros, entonces este memset( din, -1, sizeof(din)) dice que a din le vas a asignar a todos los bytes -1. Por que funciona si es por bytes y din puede ser un int o long, pues por que un -1 en binario son todos los bits prendidos y como pone todos los bits en 1 para cualquier tipo de dato se vuelve siempre -1, también sirve para poner a todos en cero, pero no para otro valor.


Luego imprimimos el resultado de llamar la función solve( 0 , strlen( word)  - 1) , mandamos de la posición 0 al tamaño de word – 1.


Veamos la parte superior del programa:


# include <stdio.h>
# include <string.h>

int din[1001][1001];
char word[1002];

int max( int a, int b ){ return a > b ? a : b;}

int solve( int pizq, int pder ){
   int res = 0;
   if( pizq == pder ) return 1;
   if( pizq > pder ) return 0;
   if( din[pizq][pder] != -1) return din[pizq][ pder ];
   if( word[ pizq ] == word[ pder ]) res = max( res, solve( pizq + 1, pder -1 ) + 2);
   res = max( res, solve( pizq , pder - 1) );
   res = max( res, solve( pizq + 1, pder ) );
   return din[pizq][pder] = res;
}


   
vemos declarado la matriz din y la palabra Word

se tiene una función max que recibe dos enteros y regresa el mayor de ellos.

En la función solve recibe pizq y pder, indicando la posición izq y la posicoin derecha que vamos a evaluar.

Que pasa cuando pizq es igua a pder , esto quiere decir que son el mismo elemento y por lo tanto tienen el mismo carácter, entonces su máximo largo es 1.

Que pasa cuando pizq es mayor a pder, esto quiere decir que la posición izquierda ya sobre paso la derecha y ya no hay mas que buscar, entonces regresamos 0 como el largo del máximo palíndromo encontrado entre estas dos posiciones.

El siguiente if solo valida si no he procesado antes esta posición , si ya la procese entonces ya no lo vuelvo a hacer por que ya conozco el resultado.

Después de esto viene la lógica que resuelve el problema, ¿que pasa si la palabra Word en la posición pizq es igual al carácter en la posición pder?  Esto quiere decir que podemos utilizar estos dos caracteres para formar un palíndromo y ahora explorar si encontramos en medio de ellos en pizq +1 y pder – 1 otro palíndromo para asi incremetar su tamaño ,  solve( pizq +1 , pder – 1) + 2, el mas dos es por que se agregan dos caracteres mas a un posible palidromo. 

Independientemente de que la pizq y pder sus caracteres sean igual podrimos encontrar una solución si descartamos el carácter en la posición izquierda o derecha y por eso calculamos las siguientes dos lines (   res = max( res, solve( pizq , pder - 1) );
   res = max( res, solve( pizq + 1, pder ) ); ) .


Al final regresamos res que es el palíndromo mas grande que enctromos en el rango [pizq, pder], y también se lo asignamos a la matriz din.


Bueno aquí concluye la explicación del algoritmo.


Que es la memorización, pues como su nombre lo indica memoriza posición ya procesadas para no volverlas a procesar esto hace que un algoritmo que tarda hora pueda tardar segundos. Pero el gran reto de la programación dinámica y la memorización es guardar la información necesaria, no toda , si tienes una dinámica de 5 valores a guardar y hay dos que se deducen con los otros tres solo necesitarías guardar 3 valores y no 5, esto hace que el numero de nodos distintos a crear sean menos y así el numero de iteración decrementan sustancialmente. (Si tiene algún problema de programación dinámica que quieran que sea analizado lo pueden sugerir, no prometo poderlo resolver pero si prometo analizarlo y explicar lo que encontré, si no les gusta la explicación y quieren que se mejore también se aceptan sugerencias, este es mi correo rodrigo.burgos@gmail.com)

Gracias.

1 comentario:

Anónimo dijo...

interesante