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

Escrito por el 13 mayo, 2013

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.

Fundamentos

¿Cómo programar un algoritmo que resuelva el problema de las cifras? Para los programadores amateurs, a primera vista, parece un problema imposible de resolver por ellos. Intuyen que seguro habrá alguna forma, pero que se les escapa. Y así es. A no ser que seas una puta máquina, antes de poder resolver ese problema, habría que tener ciertos fundamentos de la programación claros, como son las estructuras de datos y algoritmos básicos. En el grado de informática, y en la antigua ingeniería, en segundo curso hay una asignatura dedicada exclusivamente a crear esos pilares: La tan temida como odiada “Algoritmos y estructuras de datos”. Algunas universidades la parten en dos asignaturas, pero el horror es el mismo.

Pues bien, en estructuras de datos, te enseñan lo que son las pilas, colas, diccionarios, tablas de dispersión, árboles, árboles trie, árboles B, grafos, etc. Y en algoritmos, te enseñan a operar esas estructuras de datos mediante técnicas algorítmicas avanzadas para resolver problemas, como divide y vencerás, bactracking, ramificación y poda, programación voraz, programación dinámica, ramificación y poda, algoritmos genéticos, etc. En resumen, es imposible aprender un algoritmo avanzado si no conoces las estructuras de datos disponibles; y tampoco es posible sacarle el máximo partido a las estructuras de datos si no conoces los algoritmos con los que exprimirlas.

Backtracking, también conocido como vuelta atrás, es uno de los primeros algoritmos decentes que todo estudiante se encuentra por el camino. Básicamente, el algoritmo backtracking no es más que un recorrido en profundidad o anchura de un árbol de soluciones, combinando unos elementos dados inicialmente, buscando la mejor solución de todas. Si el árbol combinatorio de soluciones está correctamente generado, backtracking garantiza SIEMPRE encontrar la mejor solución.

El árbol combinatorio de soluciones lo va generando el propio algoritmo backtracking al mismo tiempo que lo recorre.

Árbol combinatorio de soluciones y cómo recorrerlos

¿Qué es un árbol? Pues como su nombre indica, es una estructura tipo grafo dirigido en el que no hay ciclos. El árbol comienza en un sólo nodo, conocido como nodo raíz. De ese nodo raíz pueden colgar hijos, y de esos hijos pueden colgar más hijos, hasta llegar a los nodos hoja, que son nodos que no tienen hijos. Los nodos hermanos, son nodos que tienen el mismo padre.

¿Qué es un árbol de soluciones? Pues a partir de un conjunto de elementos finito, es una estructura de datos capaz de representar todas las combinaciones posibles usando esos elementos. Voy a explicarlos mejor con un ejemplo: Imaginad que tenemos las siguientes letras: OSL, y nos piden combinar dichas letras para formar todas las palabras posibles sin repetirlas. Pues un árbol combinatorio de soluciones sería la siguiente imagen:

letras
Entre corchetes están las letras que puedo usar a partir de ese nodo del árbol, y lo que no está entre corchetes, es la solución parcial que llevo generada hasta el momento. En los nodos hoja estan las soluciones totales, es decir, soluciones donde he utilizado todas las letras. Según el enunciado del problema, la solución puede estar en cualquier hoja, si no hace falta usar todos los elementos, o sólo en las hojas finales, si estamos obligados a consumir todos los elementos.

El árbol de soluciones puede ser recorrido en anchura, que es recorrer el árbol dando preferencia a los hermanos antes que a los hijos. En el ejemplo de las letras, un recorrido en anchura sería: O, S, L, OS, OL, SO, SL, LO, LS, OSL, OLS, SOL, SLO, LOS, LSO.

El recorrido en profundidad es la otra posibilidad, que es recorrer el árbol dando preferencia a los nodos hijos. Por ejemplo: O, OS, OSL, OL, OLS, S, SO, SOL, SL, SLO, L, LO, LOS, LS, LSO.

Según el tipo de problema, recorrer en anchura o en profundidad el árbol de soluciones puede garantizar encontrar una solución óptima mucho antes. Si el problema requiere de recorrer el árbol entero siempre, en los casos que puede que no exista una solución óptima, no importará cómo lo recorramos.

OJO: Un árbol de soluciones es un árbol con todas las combinaciones posibles de los elementos entre sí. Nada más. No confundir con la “solución del problema” o resultado válido que queremos obtener usando backtracking. Encontrar soluciones válidas al problema serán en la mayoría de los casos buscar un camino válido desde el nodo raíz a alguno de los nodos intermedios u hojas de dicho árbol de soluciones.

Técnica backtracking de resolución de problemas

Ahora que tenemos un árbol de soluciones, hay que encontrar un camino que vaya desde el nodo raíz hasta un nodo intermedio u hoja, según el enunciado del problema. El algoritmo backtracking puede ser recursivo, con llamadas recursivas, o iterativo, sólo mediante bucles. Evidentemente el iterativo es sensiblemente más rápido, porque almacenar llamadas recursivas en la pila de la memoria tiene un coste muy superior a recorrer bucles. Sin embargo, el algoritmo recursivo puede ser inicialmente más sencillo de programar, y será la técnica que veamos. Cualquier algoritmo recursivo se puede reconvertir a iterativo, aunque esa temática se escapa al objetivo de este tutorial, que es una simple introducción.

Hay dos tipos de problemas: Los que sabemos que tienen solución óptima (solución exacta), y los que sabemos que quizás no la tengan (entonces la solución algunas veces será exacta, y otras aproximada, según los elementos a combinar). Para las soluciones óptimas, en cuanto encontremos una solución válida, podemos para la ejecución de backtracking ya que tenemos un resultado válido. Para las soluciones no óptimas, tenemos dos posibilidades: Si en algún momento encontramos la solución óptima, podemos parar backtracking. Pero si la solución encontrada no es óptima, la almacenamos en una variable auxiliar y seguimos buscando más soluciones. Cuando encontremos otra solución, comprobamos si es exacta de nuevo. Si lo es, paramos. Si no lo es, vemos si esa nueva solución mejora la solución almacenada anteriormente. Si la mejora, guardamos en esa misma variable auxiliar la nueva mejor solución hallada hasta el momento.

El algoritmo recursivo de backtracking siempre tiene el mismo esqueleto, que a brocha gorda, es el siguiente: A partir de un nodo dado, almacenado como alguna estructura de datos que nos sea útil, generamos todos sus posibles hijos. Con cada hijo generado, comprobamos si da solución al problema, o al menos mejora la mejor solución encontrada hasta el momento. Si es así, almacenamos esa solución. Y por último, según queramos recorrer el árbol en anchura o profundidad, elegimos el próximo nodo hermano o hijo para volver a llamar a backtracking con ese nodo. Y aquí viene toda la magia: Si ya no hay más nodos hermanos o hijos, entonces el algoritmo deja de hacer llamadas recursivas, y va volviendo hacia atrás en la pila de llamadas. Es decir, subiría al padre del nodo hoja en el que estábamos, y le buscaría mas hermanos o hijos según el tipo de recorrido. Así, hasta que el árbol haya sido recorrido completamente (en problemas con soluciones no óptimas) o hasta que encuentre la solución exacta (problemas óptimos). Y por eso también se le conoce como “vuelta atrás” a este algoritmo.

Como puedes ver, éste algoritmo es del tipo “fuerza bruta”, es decir, prueba todas las combinaciones posibles hasta hallar alguna solución válida que resuelva el problema. Así que dependiendo del número de elementos a combinar que tenemos, el tamaño del árbol puede ser desorbitante. Incluso hasta el punto de hacer que el algoritmo backtracking sea inviable, pues en árboles gigantescos, el tiempo que tardaría backtracking en generarlos y recorrerlos completamente puede ser descabellado (minutos, horas, días…). Aunque no es una solución definitiva, sí hay una cosa que el programador puede hacer para reducir el tamaño del árbol: Podarlo, descartar las “ramas del árbol” que estemos seguros no nos conducirán a ninguna solución válida. Qué nodos hay que descartar dependerá del problema, y en la mayoría de las ocasiones, no es una tarea nada fácil pensar en todas las podas posibles que podemos realizar al árbol mientras lo vamos generando. Una buena poda puede aligerar mucho la ejecución del backtracking, así que es fundamental escurrirte los sesos en este aspecto.

Si el problema tiene solución óptima, otro truco que alguna vez se puede usar es ordenar los elementos de alguna manera lógica antes de ejecutar backtracking, y que quizás ayuden a encontrar la solución del problema antes.

En pseudo-código, el algoritmo que recorre el árbol en profundidad, con soluciones en cualquier hoja, tiene que tener esta pinta en esencia:

VARIABLE SOLUCION;
FUNCION BACKTRACKING(NODO){
    SI ES_HOJA(NODO) VOLVER;

    GENERAR_NODOS_HIJOS(NODO);
    PARA CADA HIJO DE NODO{
        SI_ES_SOLUCION(HIJO) Y MEJOR_SOLUCION(HIJO,SOLUCION){
            SOLUCION=HIJO;
        }
        BACKTRACKING(HIJO);
    }
}

Es tarea del programador que use backtracking crear sus funciones auxiliares ES_HOJA, GENERAR_NODOS_HIJOS, SACAR_HIJO, ES_SOLUCION, MEJOR_SOLUCION y METER_HIJO personalizadas al problema que tiene que resolver. La idea fundamental siempre es ésta, pero el programador es el encargado de adaptar el algoritmo a su “mundo”. En resumen, backtracking es una IDEA para resolver ciertos tipos de problemas. Si esperabas encontrar un algoritmo de copiar y pegar, te has equivocado de blog, forastero. GENERAR_NODOS_HIJOS también deberá podar el árbol, cuando encuentre nodos que estemos seguros no conducirán a ninguna solución óptima, o que tampoco mejoren la mejor solución que hallamos encontrado hasta el momento.

Caso práctico: Cifras y letras

Vamos a aplicar backtracking a un problema real. Los problemas típicos de ejemplos de backtracking son sobre todo el ejercicio de las 8 reinas, que consiste en programar un algoritmo por backtracking que consiga poner 8 reinas sobre un tablero de ajedrez sin que se maten entre ellas. Resolverlo por fuerza bruta mediante backtraking consistiría en poner la primera reina en la casilla A1, la segunda en la siguiente que se pueda, que sería B3 (pues toda la fila A y la columna 1 y B2 estarían ocupadas porque la reina ataca en horizontal, vertical y diagonal), y así sucesivamente. Cuando sea imposible colocar una de las reina, se coge la última reina que pudimos poner, y se la coloca en la siguiente posición válida (vuelta atrás), hasta encontrar una de sus casi 100 soluciones válidas del problema.

Pero estaba hasta los mismísimos de programar las 8 reinas en doscientos millones de lenguajes, así que me decidí por otra opción; y me acordé de la ronda de los números del concurso de televisión Cifras y Letras, que nunca había intentado hacer. Además introducía un extra de dificultad que hacía un poco mas divertido el reto; y es que a diferencia del ejercicio de las 8 reinas, donde los elementos iniciales (el tablero y las 8 reinas) eran siempre los mismos, en cifras y letras el número de elementos se va modificando conforme recorremos el árbol haciendo combinaciones.

La prueba de cifras consistía en hacer operaciones elementales entre un conjunto de 6 números con el objetivo de hallar otro número de 3 cifras dado, o aproximarse a él todo lo posible. Las operaciones eran sumar, restar, multiplicar y dividir, y los resultados de dichas operaciones siempre debían ser números enteros positivos (no valen divisiones con decimales ni restas negativas). Cada número sólo podía ser usado una vez.

Lo que hacían los concursantes era coger dos de los números, realizar alguna operación, y meter ese resultado como número disponible para realizar más operaciones, junto a los otros 4 números de inicio que aún no habían usado. Así es la forma en la que yo he afrontado el problema.

Pero antes de empezar, hay que pensar en la estructura de datos a utilizar. Backtracking genera y recorre un árbol de soluciones, pero eso no significa que necesitemos crear un árbol. Como ya dije, el algoritmo backtracking es en esencia una IDEA, y no hay ninguna implementación escrita en las sagradas escrituras que sea la palabra de dios que sirva para todo. Cada cual la implementa como pueda o como sepa. Y como en todo, unas serán fantásticas y otras apestarán, pero mientras cumplan con su trabajo, arreando que es gerundio. De lo único que dispongo, es de un conjunto de 6 números. Un simple array parece una estructura perfecta para almacenarlos. También dispongo del número objetivo, de 3 cifras. Me basta con una variable normal y corriente.

Después de pensar cómo almacenar la información con la que vamos a trabajar, hay que pensar qué tipo de backtracking vamos a usar. Ya dije que básicamente hay dos: Backtracking para soluciones óptimas, y bactracking para soluciones no óptimas. En este caso, es evidente que no podemos garantizar encontrar la solución exacta. Imagina que nos salen seis doses, y que la cifra a obtener es 100. Ni Einstein en 200 años podría obtener tal cifra si resucitara sólo para trabajar en ello. Así que necesitaremos variables extra para ir almacenando el mejor resultado encontrado mientras se va generando y recorriendo el árbol combinatorio de soluciones.

Además, toda la gracia del concurso consistía en decir qué cálculos se habían hecho para hallar la cifra obtenida por el concursante, porque aunque la fe y confianza en los demás está muy bien, a veces no viene mal un poco de escepticismo. Si el concursante la cagaba al reproducir dichos cálculos, entonces los puntos de la prueba los ganaba su rival. Por lo tanto, necesitamos almacenar de alguna manera qué cálculos hemos ido haciendo a lo largo del camino.

Aquí suele ser el momento donde digo que le eches un par de huevos y te pongas a programar el algoritmo por tu cuenta, o que al menos lo intentes; pero para qué, si nadie me va ha hacer ni puto caso. Veámos las variables que he necesitado antes de empezar con el algoritmo backtracking:

var obtener=952;
var numeros=[25, 50, 75, 100, 3, 6];

var solucionActual=[], resultadoActual=0;
var solucionMejor=[], resultadoMejor=0;

Para combinar los números, tenemos las 4 operaciones que he nombrado varias veces, así que como ayuda, he utilizado un enumerador y una función auxiliar para realizar los cálculos. A dicha función le paso los dos operadores, y el enumerador con la operación que quiero realizar. Esta función no es tan simple como parece, porque la hice teniendo en cuenta las restricciones que tengo para obtener resultados (números enteros positivos únicamente). La suma y la resta no tienen problemas. Asumiendo de que los operadores siempre serán enteros positivos, la suma y la multiplicación siempre darán otros enteros positivos. La resta, por el contrario, requiere que el primer operador sea mayor que el segundo.

Entonces fue cuando las aguas del mar rojo se abrieron en dos (hoy estoy mesiánico) y pensé ¿qué coño hago? Tengo dos opciones: Puedo descartar la solución negativa, es decir, podar esa rama del árbol, o puedo simplemente restar el mayor al menor (u obtener el valor absoluto de la resta, que es lo mismo y más rápido). Si descarto la resta, entonces el generador de hijos del backtracking debería de generar todas las posibilidades combinatorias.

Por ejemplo, tenemos sólo 3 números [2,1,3] en el array. ¿Cómo combinarlos para realizar todas las restas posibles entre ellos?
Pues tendría las operaciones 2-1, 2-3, 1-2, 1-3, 3-2, 3-1. Pero como puedes ver, muchas de ellas darían resultados negativos inservibles. Además, me obligarían a hacer un doble for que recorra ambos arrays desde 0 hasta su length-1. Entonces fue cuando se me apareció la virgen y pensé ¿Y por qué no combiar el array de forma escalonada? Recorrer un array de forma escalonada consiste en que el bucle “de fuera” recorre desde i=0 hasta length-2, y el de dentro, recorre j=i hasta length-1. Así, hago sólo la mitad de combinaciones, pero estoy cubriendo todas las combinaciones de operaciones con los números porque… ¡Las operaciones válidas son conmutativas! A + B es igual que B + A, A * B es igual que B * A, A – B no es igual que B – A, pero alguna de las dos dará negativo, algo que resuelvo si obtengo el valor absoluto de la resta, así que ABS(A – B) es igual a ABS(B – A). Así también haría que la resta siempre arroje valores válidos. Y por último, la división, que no es conmutativa. Pero no dejé que una maldita división me jodiera el chiringuito. Y lo que hice fue hacer que el dividendo fuera el número mayor, y el divisor el menor. Antes de dividir, compruebo el resto de la operación con MOD (%), y si la división era exacta, devolvía su resultado. Si no lo era, devolvía un cero para indicar a bactracking que esa operación no era válida, y que por lo tanto esa rama del árbol de soluciones debía ser podada.

Más tarde me di cuenta que multiplicar o dividir por la unidad es una estupidez, ya que gastas dos números para obtener un único número que ya tenías. Asi que las utilicé también como poda.

Y tras todas esta elucubraciones, ésto es lo que parí;

var OP = { SUM:0, RES:1, MUL:2, DIV:3 };
function calcula(op1,op2,operador)
{
    switch(operador)
    {
        case OP.SUM:
            return op1+op2;
        case OP.RES:
            return Math.abs(op1-op2);
        case OP.MUL:
            if (op1==1 || op2==1)
            {
                return 0;
            }
            else
            {
                return op1*op2;
            }
        default:
            var aux=0;
            if (op2>op1)
            {
                aux=op1;
                op1=op2;
                op2=aux;
            }
            if (op2>1 && op1%op2==0)
            {
                return op1/op2;
            }
            else
            {
                return 0;
            }
    }
}

Antes de empezar con la función bactracking, voy a describir lo que pretendía hacer, la idea feliz que tuve para resolver el problema. A bactracking le pasamos como parámetro de entrada un array con los valores disponibles con los que se pueden realizar todas las combinaciones y operaciones. Si el array sólo tiene un número, no podemos hacer nada, y hacemos return. Si hay más de un número, mediante un par de bucles escalonados, como ya dije, cojo dos de los números. El doble bucle hará que haga todas las combinaciones posibles de entre cada par de números del array. Como ya dije, cuando coja el número A y el número B, no necesito coger posteriormente el número B y el número A, porque los posibles resultados de las operaciones que pueda realizar sobre ellos son los mismos que ya obtuve. Teniendo ya el par de números, necesito otro bucle interno que recorra las cuatro posibles operaciones. Saco del array de valores disponibles los dos números que he escogido, y calculo la operación de la vuelta del bucle donde esté. Por eso recorro el array de forma escalonada. Si la solución de la operación es válida (no es cero, si vemos la función de calcula de arriba) entonces comparo esa solución con la exacta. Si es la exacta, ya he terminado, ya podemos chuparnos las pollas unos a otros, como decía el lobo de pulp fiction. Si no lo es, entonces lo comparamos con el mejor resultado obtenido hasta el momento. Si lo mejora, lo almacenamos.

A continuación metemos el resultado válido recién calculado al array de valores, y llamamos de nuevo a bactracking con ese array. OJO, si pasamos como parámetroa una función un array, y el array es modificado por la función, cuando la ejecución de la función termine y vuelva, el array estará modificado, ya que es un objeto y actúa como tal (si a estas alturas te tengo que explicar lo que es el paso de argumentos por valor o por referencia, mejor dedícate a la petanca). Así que debemos de confiar que cuando se vuelva de la función bactracking, el array contendrá exactamente los mismos valores que tenía antes de llamar a la función con él. Tenemos varios caminos para conseguir ésto: El más fácil es crear una copia del array pasado como argumento al principio de la función, y trabajar sobre la copia. Pero tened en cuenta que esta función será llamada recursivamente miles, millones de veces, y cuanto menos trabajo deba hacer, mejor. Otro problema sería que ocupará mas memoria, al necesitar cada llamada recursiva crear un array nuevo. Meteríamos en memoria decenas o cientos de copias del array, tantos como llamadas recursivas en profundidad tenga nuestro algoritmo. Así que opté por una solución mas trabajada, pero que consigue que sólo halla un array en memoria todo el tiempo. Consiste en usar siempre el mismo array de valores, usando PUSH para meterle valores por el final, POP para sacarles valores del final, SPLICE para sacarle valores de una posición determinada, y SPLICE también para meterle valores una posición determinada. Con los índices i y j de los dos primeros bucles, yo sé qué posición de array de valores voy a extraer. Antes de volver a llamar a backtracking, hago un push (añadir por el final) con el resultado. Así que cuando vuelva del bactracking, asumiendo de que el array estará tal y como lo mandé, debo de hacer las siguientes operaciones para dejarlo en un estado válido para poder seguir generando los hijos restantes: Hago un POP, que elimina el último valor intruducido (que debería de ser rel resultado de la operación que hicimos). Cuando el bucle que realiza las combinaciones de las operaciones, también tengo que volver a meter los dos valores con los que hice las operaciones, para generar sus hermanos en las siguientes vueltas de los bucles correctamente.

Y por fin, el gran momento: La función bactracking en todo su esplendor. Seguro que cuando la veas pensarás que al final la cosa no era para tanto. Si ésta ha sido tu primera impresión, cuidado, no todo es tan fácil como parece. Y si no la ha sido, prepárate para sufrir.

function backtracking(valores){
    var nlengh=valores.length;
    if (nlengh==1)
    {
        return;
    }

Si el array sólo contiene un valor, no podemos calcular nada, regresamos.

    for (var i=0;i<nlengh-1;i++)
    {
        for (var j=i+1; j<nlengh; j++)
        {
            var op1=valores[i], op2 =valores[j];
            valores.splice(j,1);
            valores.splice(i,1);

Bucle escalonado para combinar todos los elementos de un array entre sí, evitando repetir relaciones. (Cuando operemos con A y B, no necesitamos repetir las operaciones con B y A porque obtendremos los mismos resultados). tras el doble bucle, sacamos los elementos elegidos del array de valores para operar con ellos.

            for (var op=0; op<4;op++)
            {

Bucle interno para ir realizando las operaciones. Las tenemos en un enumerador numeradas secuencialmente del 0 al 3.

                var res = calcula(op1,op2,op);
                if (res>0)
                {
                    solucionActual.push({op1:op1, op2:op2, op: op, res: res});
                    if (Math.abs(obtener-resultadoMejor)>Math.abs(obtener-res) || resultadoMejor==res && solucionMejor.length>solucionActual.length)
                    {
                        solucionMejor=solucionActual.slice(0);
                        resultadoMejor=res;
                    }
                    valores.push(res);
                    backtracking(valores);
                    valores.pop();

                    solucionActual.pop();
                }

Aquí tenemos el trozo más interesante. Nada más empezar, obtenemos el resultado de la operación escogida con los operadores que correspondan. Si la solución es válida, la metemos en solucionActual la operación en el array donde almacenamos las operaciones que llevamos realizadas hasta el momento. Para ello estamos creando “a pelo” un objeto anónimo de javascript, diciendo qué operadores hemos usado, la operación que hemos hecho, y el resultado de la misma. Este array nos servirá para mostrar las operaciones que se han realizado cuando se encuentre la mejor solución.

Que es justo lo que hacemos si el resultado que acabamos de calcular está mas próximo a la variable obtener, que contiene el número de 3 cifras a hallar. Además, es posible que encontremos una solución a pesar de haber hecho operaciones no necesarias por el camino. Así que para garantizar que encontraremos la solución mas corta, si el resultado actual es igual que el mejor resultado encontrado hasta el momento, pero el número de operaciones realizadas es menor (mirando el length de los arrays de solucionMejor, y solucionActual), nos quedamos con éste porque es evidente que obtener el mismo resultado con menos operaciones es mucho mejor.

En resumen, si tenemos un resultado mejor que el ya almacenado, sustituimos el array y el valor del mejor resultado encontrado, por el resultado que llevamos calculado hasta el momento. para clonar un array podemos usar slice(0). En realidad SLICE parte el array por el indice que le digamos, y nos devuelve una copia del trozo final sin modificar el original. Si le decimos que lo parta por 0, conseguiremos clonar al completo el array.

A continuación, llamamos recursivamente a bactracking. Pero antes de llamar, metemos en el array el resultado que acabamos de calcular, para que lo utilice en el futuro. Cuando se vuelva de ejecutar las llamadas recursivas, sabemos que la última posición del array de valores contendrá el resultado que acabamos de meterle, así que con POP se lo sacamos. Pero también hay que sacarle al array solucionActual la última de las operaciones que hemos realizado hasta el momento, así que le hacemos otro POP.

            }
            valores.splice(i,0,op1);
            valores.splice(j,0,op2);
        }

    }
}

Cuando el bucle interno que realiza las combinaciones con las operaciones finaliza, hay que reestablecer el array de valores original. Para ello sólo hay que volver a meter en ese array los valores que acabamos de utilizar para realizar las operaciones. SPLICE sirve para eliminar posiciones del array determinadas, pero también para meter nuevos elementos en el array en posiciones determinadas. SPLICE acepta dos, o tres y más parámetros. El primero, es el índice del array sobre el que va a realizar los cambios. El segundo, es el número de elementos que va a eliminar a partir del índice que le dijimos. Si le pasamos un positivo, será hacia adelante. Si le pasamos un negativo, los eliminará hacia atrás. Como no queremos eliminar ninguno, le pasamos un cero.

El tercer parámetro (y el cuarto, y el quinto, y el sexto, y todos los que queramos) serán los elementos que añadirá en esa misma posición después de las eliminaciones. Pero OJO, para sacar los elementos al principio de la función sabiendo en qué índice están, primero hay que sacar el que más cerca del final esté (índice j porque nuestro bucle es escalonado y i siempre será menor que j), y después el que más cerca del inicio esté (i). Pero para volver a meterlos donde estaban, hay que hacerlo justo del revés, primero i, y luego j. Es una trivialidad, pero más de uno puede cagarla si no está atento con ésto.

Y ya está, el algoritmo recursivo de bactracking generará y recorrerá el árbol de soluciones en profundidad, e irá podando las ramas cuyos resultados no sean válidos. Hoy estoy repetitivo, pero es importante recalcar que si no podamos el árbol todo lo que podamos, el tiempo de ejecución del algoritmo puede ser bestialmente alto. Por ejemplo, si abres el ejemplo e introduces a mano 7 u 8 cifras en vez de seis, el tiempo de ejecución se disparará.

Las podas que hemos realizado para este bactracking son:

  • Bucle escalonado para evitar duplicar operaciones. Esto supone una poda brutal, eliminando la mitad de las ramas del árbol, y es posible gracias a las propiedades conmutativas de varias de las operaciones que debemos realizar
  • Podar ramas con divisiones con decimales
  • Podar ramas de multiplicaciones por la unidad, o la división por la unidad

Seguro que hay alguna poda más que se me ha escapado, pero hoy no doy pa más. Y como el tiempo de ejecución del algoritmo con 6 números es razonablemente rápido, así se queda. Si encuentras alguna poda con la que enriquecer el código, déjame un comentario con la increíble idea. Realizaré el sorteo de un viaje a disney world con los 3 mejores aportes, el próximo 31 de junio.

Ah sí; cuando el algoritmo finaliza, tengo una función que lee el array de las operaciones realizadas, y las convierte en una cadena que facilite su lectura, para imprimirlas en algún elemento HTML como un textarea.

La función tiene esta pinta, no necesita de ninguna explicación:

function imprimirResultado()
{
    var cadena="";
    var n=solucionMejor.length;
    for (var i=0;i<n;i++)
    {
        switch(solucionMejor[i].op)
        {
            case OP.SUM:
                cadena+=solucionMejor[i].op1+" + "+solucionMejor[i].op2;
                break;
            case OP.RES:
                if (solucionMejor[i].op1>=solucionMejor[i].op2)
                {
                    cadena+=solucionMejor[i].op1+" - "+solucionMejor[i].op2;
                }
                else
                {
                    cadena+=solucionMejor[i].op2+" - "+solucionMejor[i].op1;
                }
                break;
            case OP.MUL:
                cadena+=solucionMejor[i].op1+" x "+solucionMejor[i].op2;
                break;
            default:
                if (solucionMejor[i].op1>=solucionMejor[i].op2)
                {
                    cadena+=solucionMejor[i].op1+" / "+solucionMejor[i].op2;
                }
                else
                {
                    cadena+=solucionMejor[i].op2+" / "+solucionMejor[i].op1;
                }
                break;
        }
        cadena+=" = "+solucionMejor[i].res+"\n";
    }
    return cadena;
}

Para que el ejemplo no fuera tan soso, también he incluido una función que resetean las variables globales que necesita el sistema para ejecutar backtracking:

function reset(){
    solucionActual=[];
    resultadoActual=0;
    solucionMejor=[];
    resultadoMejor=0;
}

Y un par de botones para generar nuevos números y resultado a obtener, y para calcular la solución. No tienen ninguna complejidad, así que su explicación no la veo necesaria.

window.onload=function(){
    valoresNPT=document.getElementById("valores");
    btnCalcular=document.getElementById("calcular");
    textarea=document.getElementById("solucion");
    obtenerNPT=document.getElementById("obtener");
    btnGenerar=document.getElementById("generar");

    btnCalcular.onclick=function(){
        numeros = valoresNPT.value.split(",");
        var n = numeros.length;
        for (var i=0;i<n;i++)
        {
            numeros[i]=parseInt(numeros[i]);
            if (isNaN(numeros[i]) || numeros[i]<1)
            {
                textarea.value="Alguno de los numeros no es un entero positivo";
                return;
            }
        }
        obtener=parseInt(obtenerNPT.value);
        if (isNaN(obtener))
        {
            obtener=100;
        }
        obtenerNPT.value=obtener;

        reset();
        backtracking(numeros);
        textarea.value=resultadoMejor+"\n\n"+imprimirResultado();
    };
    btnGenerar.onclick=function(){
        var validos=[1,2,3,4,5,6,7,8,9,10,25,50,75,100];
        var valores=[];
        textarea.value="";
        obtenerNPT.value=Math.floor(Math.random()*900+100);
        for (var i=0;i<6;i++)
        {
            valores.push(validos[Math.floor(Math.random()*validos.length)]);
        }
        valoresNPT.value=valores.join(",");
    };
};

Y hasta aquí este primer capítulo de algoritmos famosos en javascript. Para el próximo, estoy entre una segunda parte del tiro parabólico, que os va a emocionar; o el algoritmo MiniMax, muy útil para IA’s de juegos de dos jugadores por turnos, como el Tic Tac Toe, más conocido por estos lares como el tres en raya.

Etiquetas: , , ,

Comentarios (6)

  • Vaya pasada, jamás pensé que fuera posible sacar a la luz el algoritmo de este concurso, me dejas sin palabras, wow!!

  • Me abriste mucho la cabeza y estoy pisando nuevo terreno, mil gracias!…

  • Excelente, esto me lo pidieron como proyecto….. Gracias

  • Wow tio! Vaya pedazo de codigo!

    Muy bueno! Voy a estudiarmelo para aprenderlo, de veras no veas como te lo agradezco!! Genail trabajo! 😀

  • Una cosa mas, me he dado cuenta usando este codigo, que para hallar la solucion, calcula TODAS, y se queda con la mas corta, lo que es elegante, pero afecta TOTALMENTE al tiempo de computacion. Para los que quieran quedarse solo con la primera solucion posible, anadir en

    var res = calcula(op1,op2,op);
    if (res>0)
    {
    solucionActual.push({op1:op1, op2:op2, op: op, res: res});
    if (Math.abs(obtener-resultadoMejor)>Math.abs(obtener-res) || resultadoMejor==res && solucionMejor.length>solucionActual.length)
    {
    solucionMejor=solucionActual.slice(0);
    resultadoMejor=res;
    }
    if(resultadoMejor == targetValue){ //SIENDO targetValue EL VALOR BUSCADO!!!
    return
    }
    valores.push(res);
    backtracking(valores);
    valores.pop();

    solucionActual.pop();
    }

    Solo queria a;adir este peque;o aporte.

  • Una pasada. En cuanto me conecte al pc cuenta con esa birra por PayPal.

    De todos modos una preguntita: ¿cómo forzaría al código para que me entregara la solución más larga?

    Es decir: ¿que utilice todos los elementos posibles?

    Muchísimas gracias

¿Tienes algo que decir?

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