Etiqueta: backtracking

Tutorial de algoritmos en javascript, backtracking recursivo: Cifras y letras

Escrito por el 13 Mayo, 2013 | 6 comentarios

En el último tutorial de Pong sobre IA hablé de algunos algoritmos útiles para encontrar soluciones. En esta nueva serie de tutoriales sobre algoritmos útiles, pretendo escribir un poco sobre varios de ellos, programando algún código donde haga uso de ellos a modo de ejemplo práctico. En esta primera lección, he pensado comenzar por ejemplo con el más sencillo de entender de todos, pero a costa de ser menos eficientes que otros algoritmos inteligentes.

Estos algoritmos se diseñaron para resolver problemas, pero también pueden ser usados para programar IAs de videojuegos, todo depende de la imaginación y capacidad de abstracción del programador. En este tutorial no pretendo hacer un análisis académico de la técnica backtracking, así que es posible que cometa algunos errores o mi implementación no sea la más eficiente de todas.

El código que va a servir de ejemplo es un algoritmo que resolverá la prueba de cifras de aquél gran concurso de televisión llamado “Cifras y Letras”, que daba por la segunda cadena de la televisión pública española hace la tira de años, y que actualmente aún sobrevive a nivel regional en algunas cadenas de televisión autonómicas.

La prueba de letras consistía en formar una palabra a partir de las 9 letras (vocales y consonantes) aleatorioas de las que disponían. Habían 3 condiciones: La palabra debía aparecer en el diccionario, no valían plurales, y no valían conjugaciones verbales a excepción del infinitivo, gerundio y participio (por ejemplo, jugar, jugando, jugado).

La prueba de cifras era parecida, pero con números. Disponían de 6 números de entre (1 al 9, 10, 25, 50, 75 y 100) con los que se podían realizar de dos en dos las siguientes operaciones: Sumar, restar, multiplicar y dividir. Los resultados siempre debían ser enteros positivos (la división tenía que ser exacta, y la resta siempre positiva), y esos resultados obtenidos podían usarse también para seguir haciendo operaciones. El objetivo era calcular un número lo más cercano posible, o el exacto, a otro número dado de 3 cifras.

Para el que no se acuerde, aquí van dos de los mejores concursantes de cifras de la historia:

Y en este link, el código que resuelve el problema, para que lo pruebes. He usado programación estructurada en vez de POO, porque la sencillez del código no requería un nivel de abstracción mayor.
» Leer la entrada entera

Etiquetas: , , ,

Gestionado con Wordpress y Stripes Theme Entradas (RSS) | Comentarios (RSS)