jueves, 24 de octubre de 2013

El algoritmo de la burbuja

El algoritmo de la burbuja es uno de los métodos de ordenación más conocidos. Sin embargo, no se trata de un algoritmo eficiente desde el punto de vista computacional, ni tampoco se trata de un algoritmo que sea fácil de entender, y por tanto, que pueda utilizarse con fines pedagógicos. Se trata, simplemente, de un algoritmo malo con un nombre divertido. El mundo es así. Veamos el algoritmo:
función burbuja(v, n)
    repetir desde i:=n hasta 1
        repetir desde j:=1 hasta i-1    
            si v[j+1] < v[j] entonces
                aux    := v[j]
                v[j]   := v[j+1]
                v[j+1] := aux
            fin si
        fin repetir
    fin repetir
fin función
El algoritmo se basa en dos bucles que están anidados uno dentro de otro. Al final de cada iteración del primer bucle nos aseguramos que el i-ésimo elemento es el mayor de los i-1 primeros elementos del vector, y el segundo bucle es el encargado de que esto sea así, mediante el intercambio de los números que sean necesarios. Imaginemos, por ejemplo, que tenemos que ordenar la siguiente secuencia de números:
    [12, 23, 14, 19, 3]
Cuando i vale 5, el bucle interior va desde 1 hasta 4, comparando cada elemento con su siguiente, y en el caso de que el siguiente sea menor, intercambiándolos. Primero comparamos el 12 con el 23, y como están ordenados no sucede intercambio; después comparamos el 23 con el 14, que al ser menor, hay que intercambiarlos; a continuación comparamos el 23 (que había sido intercambiado) con el 19, y también hay que intercambiarlos. Y finalmente comparamos nuevamente el 23 con el 3, y lo volvemos a intercambiar. Tal y como muestra la siguiente figura:


Como podemos comprobar, el 23 ya está situado en su posición (para i=5 nos aseguramos que la posición 5 contiene el valor correcto). En la siguiente iteración situaríamos el 19 en su posición correcta, y así sucesivamente hasta ordenar completamente el vector. Se llama algoritmo de la burbuja por la forma en que tienen los números mayores de subir hacia arriba en el vector, como si fueran burbujas flotando en un líquido.

lunes, 21 de octubre de 2013

Las ocho reinas y la vuelta atrás

En una entrada anterior vimos cómo solucionar el problema de las ocho reinas utilizando la fuerza bruta. En esta ocasión vamos a ver cómo se solucionaría el mismo problema utilizando una técnica diferente: la vuelta atrás.
El método de resolución de problemas de vuelta atrás (del inglés backtracking) se basa en la idea de que no siempre es necesario terminar de construir completamente una solución candidata para determinar que ésta no es válida. Para ciertos problemas es posible que con soluciones parcialmente construidas ya sea posible determinar que estas son incorrectas. En el caso concreto del problema de las ocho reinas, si por ejemplo colocamos la primera reina en la primera columna y primera fila, y la segunda reina en la segunda columna y la segunda fila, no es necesario colocar ninguna de las otras 6 reinas restantes (en cualquiera de sus combinaciones posibles), porque ya sabemos que esta solución no es válida, porque las dos reinas ya colocadas se atacan mutuamente. Si en este momento abortamos la búsqueda en esta línea, nos ahorraríamos de examinar 6! ó 720 soluciones candidatas. Una vez que hemos encontrado que una combinación es incorrecta, y hemos determinado que vamos a abortarla, lo que hacemos es volver un paso hacia atrás, hasta la última reina que colocamos, y continuamos la búsqueda por donde la dejamos.
A continuación vamos a estudiar el algoritmo que resuelve el problema de las ocho reinas utilizando la técnica de la vuelta atrás. Primero, y al igual que en el caso del algoritmo de la fuerza bruta, necesitamos una función que dada una posición nos indique si esta es válida o no.
función posición_válida(x, k)
    para i desde 1 hasta k-1
        si x[i]=x[k] ó |i-k|=|x[i]-x[k]| entonces
            retorna falso
        fin si
    fin para
    retorna cierto
fin función
La primera diferencia que observamos con respecto a la función de validación del apartado anterior es que ésta recibe dos argumentos, a saber, el tablero (x) y el número de reinas colocadas en el mismo (k). Esto es así porque las posiciones que les pasamos a la función son posiciones parcialmente construidas, es decir, que no todas las piezas están colocadas en el tablero, y por tanto, tenemos que decirle cuantas piezas hay. Otra gran diferencia es que la función sólo cuenta con un único bucle, en lugar de los dos bucles anidados del caso anterior. Esto es así porque no es necesario comprobar si cada reina ataca a todas las demás, ya que el algoritmo va construyendo progresivamente la solución, y por tanto, cuando es invocada la función con, por ejemplo, 4 reinas, sabemos que las tres primeras no se atacan entre sí: la función ya fue invocada anteriormente para el caso k:=3, y si alguna de las tres reinas se hubiese atacado, no habríamos llegado a este punto. Por tanto, nos bastaría con comprobar que esta nueva y última reina no ataca a las demás. Finalmente, y para no complicarnos la vida con las temidas permutaciones, nuestro algoritmo de búsqueda sólo nos garantizará que las reinas no comparten columna, y por tanto, la función de validación ha de comprobar explícitamente que las reinas no comparten filas (x[i]=x[k]).
Una vez que tenemos la función posición_válida(), podemos abordar el algoritmo:
x   := [0, 0, 0, 0, 0, 0, 0, 0]
k   := 1
fin := falso
mientras (fin = falso) hacer
    mientras no posición_válida(k, x) hacer
        x[k] := x[k] + 1
        si x[k] > 8 entonces
           k := k – 1
           si k = 0 entonces
               fin := cierto
               salir
           si no
               x[k] := x[k] + 1
           fin si
    fin mientras
    si k = 8 entonces
        escribir(x)
    si no
        k := k + 1
        x[k] := 1
    fin si
fin mientras
Aunque el algoritmo parezca muy complejo, la idea subyacente al mismo es muy sencilla. Básicamente lo que tenemos que hacer para calcular todas las combinaciones posibles de reinas, con una reina por columna, es contar desde la posición [1,1,1,1,1,1,1,1] hasta la posición [8,8,8,8,8,8,8,8], de la misma forma que hacemos cuando contamos números naturales (la única diferencia es que en lugar de contar desde 0 hasta 9 como hacemos habitualmente, contamos desde 1 hasta 8).
Sin embargo, hay que tener en cuenta que con el algoritmo de vuelta atrás, la cuenta se ve interrumpida cada vez que encontramos una posición que no es válida con las reinas que llevamos hasta el momento colocadas. Por ejemplo, de la posición [1,1,1,1,1,1,1,1] nos saltaríamos a la posición [1,2,1,1,1,1,1,1] sin necesidad de pasar por todas las posiciones intermedias [1,1,X,X,X,X,X,X] ya que sabemos que son todas inválidas independientemente de los valores que adopten las X, porque las dos primeras reinas se atacan (comparten la primera fila).
Es sorprendente que algo tan sencillo como contar requiera de un algoritmo tan complejo. Pero esto es una situación muy habitual en informática.

jueves, 17 de octubre de 2013

Las ocho reinas y la fuerza bruta

El problema de las ocho reinas es muy fácil de describir, sólo hay que colocar ocho reinas del juego del ajedrez en un tablero estándar de 8x8 de tal manera que no se ataquen entre ellas. Recordemos que las reinas pueden desplazarse cualquier número de casillas en horizontal, vertical, o diagonal. Por tanto, para que que el problema esté resuelto, las reinas no pueden compartir ni filas, ni columnas, ni diagonales. A modo de ejemplo, y para asegurarnos de que todos estamos hablando de lo mismo, la siguiente figura muestra la solución al problema para un caso más simple, el de 4 reinas en un minitablero de 4x4 casillas.
Una técnica de resolución de problemas para la que los ordenadores están especialmente bien dotados es la conocida como fuerza bruta. Básicamente la idea cosiste en dado un problema, intentar de manera sistemática todas las soluciones candidatas hasta dar con la solución buscada. El método de la fuerza bruta aplicado al problema de las reinas consistiría en calcular todas las formas posibles de colocar las ocho piezas en el tablero, y para cada una de ellas comprobar si se trata de una posición legal, es decir, no hemos colocado más de una reina en la misma casilla, y que las reinas no se atacan entre sí (no hay dos reinas situadas en la misma fila, columna, o diagonal). De esta manera, la primera pieza la podríamos colocar en cualquiera de las 64 casillas; la segunda, también se podría colocar en cualquiera de las 64 casillas (y después ya comprobaremos si las hemos colocado en la misma), con lo que tendríamos 64x64 posibilidades; con la tercera pieza tendríamos 64x64x64 posibilidades; y cuando coloquemos la última, tendríamos 64x64x64x64x64x64x64x64 posibilidades, que nos da el astronómico número de 281.474.976.710.656 posiciones a examinar, algo que está fuera del alcance de la mayoría de los ordenadores de hoy en día.
Llegados a este punto, lo que tenemos que hacer es aplicar algunas técnicas heurísticas, para ver hasta dónde podemos reducir el número de soluciones candidatas a calcular. La primera mejora, y la más evidente, es evitar colocar dos piezas en la misma casilla. La primera reina la podemos poner en cualquiera de las 64 casillas, la segunda en cualquiera de las 63 restantes, y así sucesivamente, por lo que tendríamos un total de 64x63x62x61x60x59x58x57 posiciones, que nos da el número 178.462.987.637.760.
A continuación vamos a añadir la restricción de que sólo puede haber una reina en cada columna, ya que de lo contrario se atacarían. En este caso, la primera reina podría ir a cualquiera de las 8 casillas de la primera columna, la segunda reina a cualquiera de las 8 casillas de la segunda, y así sucesivamente. Para este caso lo que tenemos son 8x8x8x8x8x8x8x8 combinaciones, que hace un total de 16.777.216 posibilidades, un número bastante más asequible para un ordenador.
La siguiente mejora que podemos añadir es la de no permitir que dos reinas estén en la misma fila. En este caso, la primera reina puede ocupar cualquiera de las 8 casillas de la primera columna como estudiamos en el caso anterior, pero ahora la segunda reina sólo puede ocupar una de las 7 casillas libres, es decir, puede estar en cualquier lugar de la segunda columna excepto en la fila que ya está ocupada por la primera reina. De igual manera, a la tercera reina le quedarían 6 casillas libres para ocupar, y así sucesivamente. Es decir, tendríamos que evaluar 8x7x6x5x4x3x2x1 u 8! combinaciones, lo que nos da 40.320 posibles posiciones.
Veamos, por tanto, el algoritmo que soluciona el problema de las ocho reinas mediante la fuerza bruta, al que le añadiremos las mejoras de evitar colocar dos reinas en la misma columna y en la misma fila.
En primer lugar vamos a implementar una función que dada una posición determinada (una configuración concreta de reinas) determine si es una solución válida o no al problema. Dado que nuestro algoritmo de búsqueda se encarga de eliminar todas aquellas posiciones en las que dos o más reinas ocupan la misma casilla, la misma columna, y la misma fila, a la función de validación sólo le quedaría por comprobar que no ocupen la misma diagonal.
Para poder trabajar, nuestra función de validación necesita conocer en qué posición se encuentra cada reina, es decir, necesitamos algún mecanismo que nos permita codificar los tableros. Para ello enumeraremos por orden a las reinas, de tal manera que la reina número 1 es la que ocupa la primera columna, la reina 2 la segunda, etc. Y a continuación creamos un array con las filas que ocupan cada una de las reinas dentro del tablero. De esta manera, si la primera reina está en la fila 4, tendremos que el array en su posición 1 contendrá el valor 4, es decir, x[1]:=4. Así por ejemplo el siguiente array:
[5, 7, 8, 4, 2, 7, 3, 1]
se correspondería con el siguiente tablero:
Para que dos reinas, i y j, ocupen la misma diagonal se debe cumplir que la distancia (número de casillas) que hay entre sus respectivas columnas (valores de i y de j) sea igual a la distancia que hay entre sus respectivas filas (valores x[i] y x[j]). Y dado que la distancia entre dos números cualesquiera es el valor absoluto de la diferencia entre ambos, tenemos que para que dos reinas ocupen la misma diagonal se debe cumplir que |i-j| = |x[i]-x[j]|.
Por tanto, nuestra función para el cálculo de posiciones válidas sería:
función posición_válida(x)
    para i desde 1 hasta 7
        para j desde i+1 hasta 8
            si |i-j| = |x[i]-x[j]| entonces
                retorna falso
            fin si
        fin para
    fin para
    retorna cierto
fin función
Finalmente, lo que necesitamos es otra función que genere los distintos tableros a examinar. Dicho de otra manera, que genere todas las combinaciones posibles de reinas. Dados los números del 1 al 8, queremos calcular todas las formas posibles que existen de ordenarlos, sin que se repitan. A esto en matemáticas se le conoce con el nombre de permutaciones. Supondremos la existencia de una función llamada permutaciones() que nos devuelve un array con todas las permutaciones posibles.
Una vez tenemos disponible la función que comprueba la validez de un tablero, y una función para la generación de permutaciones, podemos implementar el algoritmo que soluciona el problema de las ocho reinas:
p := permutaciones(8)
para i desde 1 hasta longitud(p) hacer
    k := perm[i]
    si posición_valida(k) entonces
        escribir(k)
    fin si
fin para
Se trata de un algoritmo muy sencillito, que simplemente genera la totalidad de las permultaciones, y después va comprobando una a una si se trata de una solución válida.

lunes, 14 de octubre de 2013

Búsqueda Binaria

¿Quién no ha jugado alguna vez al juego de adivinar un número? Se trata de un juego muy sencillo: el primer jugador piensa un número al azar, por ejemplo, desde 1 hasta 100, y el segundo jugador tiene que adivinarlo. Para ello va diciendo en voz alta distintos números, y el primer jugador le dice si el número que ha pensado es mayor, o menor. La pregunta es ¿cual es la mejor estrategia que podemos utilizar para adivinar el número secreto en el menor número de intentos posibles? Una posible estrategia, que funciona muy bien, sería decir como número el punto intermedio del intervalo que nos queda por buscar. Si hablamos de números desde 1 hasta 100, nuestro primer intento debería ser el 50; supongamos que el número buscado es menor, en este caso, y dado que el intervalo de búsqueda se ha reducido desde 1 hasta 50, nuestro segundo intento debería ser el 25, y así sucesivamente.
Imaginemos ahora que el departamente de recursos humanos de una determinada empresa tiene almacenadas en un ordenador las fichas de todos sus empleados, ordenadas alfabéticamente, y que desde la dirección necesitan una ficha concreta. En este caso, ¿cual es el mejor algoritmo para buscar la ficha deseada? A poco que pensemos un poco nos daremos cuenta de que se trata exactamente del mismo problema que en el caso anterior, y por tanto, ya tendríamos una estrategia de búsqueda válida. Supongamos que lo que buscamos es la ficha del señor Fernández, y que tenemos en total 1.000 fichas; por tanto seleccionamos la ficha 500 (el punto intermedio) y vemos que corresponde a la señora Jiménez, que según el orden alfabético es mayor; el siguiente paso sería continuar con la búsqueda utilizando las fichas desde la 1 hasta la 500. El algoritmo que implementa esta estrategia se llama búsqueda binaria.
Veamos nuestro algoritmo de búsqueda binaria:
función búsqueda(A, x)
    p := 1
    r := longitud(A)
    mientras p <= r hacer
        q := int((p+r)/2)
        si A[q] = x entonces
            retorna q
        si no
            si A[q]> x entonces
                r := q-1
            si no
                p := q+1
            fin si
        fin si
    fin para
    retorna NO_ENCONTRADO
fin función
La función de búsqueda recibe como primer parámetro un array de números enteros que han de estar necesariamente ordenados, y como segundo parámetro el valor que queremos encontrar en el array. Como salida nos devuelve la posición (o índice) en la que dicho valor se encuentra dentro el array, o la constante NO_ENCONTRADO si es que el elemento no se ha encontrado. Lo primero que hacemos es establecer los límites del intervalo en los que empieza nuestra búsqueda, siendo p la variable que contiene el valor menor (1 al empezar), y r la variable que contiene el valor mayor (que al empezar es la longitud del array, que viene determinada por la fución longitud()). La función siguiría iterando mientras el intervalo de búsqueda tenga una longitud mayor o igual que 1 (p<=r).
Para cada iteración del bucle lo que hacemos es calcular la posición intermedia del intervalo y comparamos su valor allí almacenado con el valor buscado. Si ambos valores son iguales, hemos encontrado lo que buscábamos y por tanto retornamos el índice. Si el valor es menor modificamos el extremo inferior del intervalo, y si es mayor, el extremo superior.

jueves, 10 de octubre de 2013

Los Conejos de Fibonacci

Nuestro siguente algoritmo trata sobre dinámica de poblaciones, pero no se asuste el lector, porque se trata de un algoritmo muy sencillito. La dinámica de poblaciones se encarga del análisis de las poblaciones biológicas, y entre otras cosas, estudia como varía el tamaño de una población con el tiempo. Uno de los primeros modelos matemáticos de cómo crece una población fue propuesto por Leonardo Pisano (también conocido como Fibonacci) en el año 1202, en su libro Liber Abaci.
Fibonacci propuso el siguiente modelo para la cría de conejos:

  • Empezamos con una pareja de conejos recién nacidos,
  • los conejos nacen de dos en dos, y de sexo opuesto,
  • los conejos alcanzan la madurez sexual al mes de vida, y 
  • el tiempo de gestación es de 1 mes.

De acuerto con este modelo en el primer mes tendremos una única pareja de conejos, la pareja de conejos con la que partimos, luego:

    F[1] = 1

En el segundo mes, tendremos nuevamente a nuestra pareja de conejos. Pero en este caso ya están maduros sexualmente, y por tanto, pueden reproducirse:

    F[2] = 1

En el tecer mes tendremos a nuestra pareja original, junto con una nueva pareja de conejos recién nacidos:

    F[3] = 1+1 = 2

En el cuarto mes nuestra pareja original vuelve a tener otra descendencia, y la primera descendencia ya estarán maduros sexualmente. Es decir:

    F[4] = 2+1 = 3

En el quinto mes, las cosas se empiezan a complicar un poco. Tenemos a la pareja original que vuelven a tener descendencia, a los primeros conejos que acaban de tener su primera descendencia, y a los segundos conejos que ya están maduros sexualmente. Simplificando:

    F[5] = 3+2 = 5

Los lectores más atentos, y aquellos que ya conociese la sucesión de Fibonacci, habrán notado que F[5] = F[4] + F[3], al igual que F[4] = F[3] + F[2], y en general, podemos decir que en el mes N tenemos:

    F[N] = F[N-1]+F[N-2]

Lo cual se puede razonar diciendo que en un mes dado, habrá tantos conejos como en el mes anterior (F[N-1]) a los que habrá que sumarle los nacimientos de la generación de hace dos meses (F[N-2]). El algoritmo que calcula la sucesión de Fibonacci es muy sencillo:

leer(N)
f1 := 1
escribir(f1)
f2 := 1
escribir(f2)
para i desde 3 hasta N hacer
    f := f1 + f2
    escribir(f)
    f2 := f1
    f1 := f
fin para

El algoritmo empieza leyendo el número de elementos de la sucesión que queremos calcular. A continuación incializa y muestra los dos primeros términos de la sucesión, que como hemos dicho, ambos son la unidad. Y finalmente, entramos en un bucle de tipo para que va calculando sistemáticamente cada nuevo valor de la sucesión, mediante la suma de los dos valores anteriores (almacenados en las variables f1 y f2), y actualizando los valores de f1 y f2 con los nuevos términos de la serie recién calculados.
La serie de Fibonacci ha sido ampliamente estudiada tanto por matemáticos como por informáticos, y son muchas las propiedades interesantes que se le han encontrado, como su relación con el número áureo, o sus aplicaciones prácticas, que van desde la generación de números pseudoaleatorios, hasta los algoritmos de ordenación. También se han encontrado numerosos ejemplos de la serie de Fibonacci en la naturaleza, como en la ramificación de los árboles, o la distribución de las hojas de una alcachofa. El interés por la serie de Fibonacci ha llegado tan lejos como los mercados financieros, donde son muchos los traders que creen que los precios de los activos financieros evolucionan según la serie. Pero lo más curioso de todo es que seguramente Fibonacci nunca llegó a imaginar que uno de los ejercicios propuestos en su libro, algo a lo que él no le dio la mayor importancia, iba a despertar tanto interés.

viernes, 4 de octubre de 2013

El Algoritmo de Euclides

En la entrada enterior vimos un sencillo algoritmo para el cálculo del máximo común divisor de dos números enteros. En esta ocasión vamos a ver el Algoritmo de Euclides, que es una manera fácil, elegante, y rápida de calcular el máximo común divisor. El algoritmo de Euclides se basa en la siguiente propiedad:

Si a y b son dos números enteros cualesquiera, entonces MCD(a, b) = MCD(a-b, b).

Podríamos hacer unos cuantos ejemplos a mano (¡ánimo, hágalo!) para convencernos a nosotros mismos de que esta propiedad es cierta, y aquellos lectores que sean más hábiles con las matemáticas, podrían incluso intentar dar una demostración formal. Pero en realidad no hace falta complicarse la vida tanto. Sólo tenemos que pensar un poco qué es lo que realmente significa esta propiedad para darnos cuenta de que la idea es trivial.
Imaginemos que tenemos dos barras de acero de longitudes a y b respectivamente, y que queremos medirlas utilizando para ello una pequeña regla de madera. Si la regla de madera nos da un número entero de medidas en una de las barras es porque la regla es un divisor de dicha barra. Si después de medir nos sobra un poquito de barra, es porque la regla no es un divisor. De entre todas las reglas que miden a ambas barras a y b nos quedamos con la que tenga una longitud mayor, que será precisamente el máximo común divisor (véase la siguiente figura).

Ahora bien, si encontramos una regla que divide a la barra b, para ver si también divide a la barra a bastaría con comprobar que divide a aquella parte de la barra a que sobresale de la barra b (es decir b-a), ya que la otra parte ya ha sido medida. Si ahora cortamos lo que sobresale de la barra a, podríamos repetir de nuevo el proceso pero utizando la barra cortada b-a y la barra b. Se trataría de resolver el mismo problema pero invertidos los papeles de las barras.
Basándonos en esta idea, podemos escribir el siguiente Algoritmo de Euclides: la idea consiste en ir cortando alternativamente de la barra más larga la parte que sobresale de la barra más pequeña, hasta que ambas barras tengan exactamente la misma logitud, que será el máximo común divisor. El algoritmo puede ser mejorado todavía un poco más, utilizando para ello la función módulo que hemos en una entrada anterior, pero esta mejora se la dejo propuesta al lector como ejercicio.

A diferencia del algoritmo anterior donde conocíamos a priori el número de iteraciones que teníamos que realizar sobre el bucle (desde 1 hasta min), en este caso no conocemos cuantas iteraciones serán necesarias antes de dar con el máximo común divisor, ya que depende de los cortes que realicemos, por eso utilizamos un bucle de tipo mientras. La condición es que mientras las barras tengan longitudes diferentes tenemos que seguir cortando, y en el momento que sean iguales paramos (nos salimos del bucle), porque ese es el máximo común divisor.

leer(a)
leer(b)
mientras a != b hacer
    si a < b entonces
        a := a - b
    sino
        b := b - a
    finsi
fin mientras
escribir(a)

La genalidad del algoritmo de Euclides quizás no sea tan geneial si la vemos desde un punto de vista histórico. Me explico. No es que quiera restarle mérito al que es, probablemente, el primer algoritmo de la historia. Pero en la época de Euclides los matemáticos dedicaban gran parte de su tiempo a estudiar las razones entre las cosas, sobre todo entre figuras geométricas (recordemos que la razón entre dos cosas es el número de veces que contiene la una a la otra). Así, el máximo común divisor era entendido en términos geométricos, como la razón máxima común a dos segmentos dados. En este contexto es más natural que surga este algoritmo. Hoy en día, las razones (en ambos sentidos de la palabra) ya no son tan importantes, somos más dados a la solución algebráica de los problemas, y en este contexto, la idea subyacente al alogritmo de Euclides nos resulta más complicada de entender.