Skip to content

Solución: Contenedores en el puerto

by en 03/02/2014

¡Hola!

¡Qué debate más interesante hemos tenido esta semana en los comentarios! Muchas gracias a todos por participar… ¡y enhorabuena por acertar! David abrió la veda y el resto se subió al carro; ¡vamos a tener que empezar a poner acertijos más difíciles, que esto se está convirtiendo en una rutina! 🙂

Para los demás, vamos con la solución. En esta ocasión, os hablábamos de los problemas de logística en un puerto marítimo de carga, donde llegan los camiones con grandes contenedores que deben ser estibados en enormes barcos. Nos enfrentamos al problema de organizar los contenedores (apilables); llegan todos por tierra, debemos depositarlos en el puerto, y luego meterlos en los barcos correctamente. Los barcos reciben como identificadores letras (de la ‘A’ a la ‘Z’) y deben ser cargados en orden alfabético. Sin embargo al puerto los camiones llegan en otro orden, y tenemos que decir el mínimo número de pilas de contenedores que necesitamos formar para que en la fase de la carga de los barcos no haya que retirar contenedores que molesten para acceder a los que hay que meter en el barco que se está estibando.

Como ocurría la semana pasada, en este caso para llegar a la solución (al número) es necesario saber cuáles son esas pilas que se forman. Es decir, aunque no nos lo pregunten, para poder contestar que si los contenedores que nos llegan son SUPERCALIFRAGILISTICOESPIALIDOSO necesitamos como mínimo ocho pilas (tal y como nos contó Gualterio), necesitamos encontrar esas ocho pilas. Es más, necesitamos encontrar esas ocho pilas de tal manera que estemos seguros de que no hay ninguna una distribución posible con menos (siete) pilas. ¡Y eso tiene su emoción! Al fin y al cabo, ¿cómo saber que es imposible hacerlo con siete pilas? Dicho con un ejemplo físico, ¿cómo estar seguro de que en un pajar no hay agujas? ¿Estás seguro de que has buscado bien?

En el caso del problema que nos ocupa, lo que tenemos que hacer es ir “construyendo las pilas” según nos van llegando contenedores en los camiones. Así, para la primera pregunta que os hacíamos, CBACBA, nos llega el primer contenedor para el barco ‘C’, y la única opción que nos queda es empezar una pila con él. Lo divertido llega con el siguiente, el contenedor destinado al barco ‘B’. Ahora tenemos dos opciones: podemos colocarlo encima del contenedor ‘C’ (y seguir teniendo una única pila) o podemos colocarlos en una pila nueva y tener dos. ¿Cómo saber qué opción será la mejor a largo plazo?

Ante este dilema, en informática hay dos aproximaciones. La primera es la de búsqueda que, básicamente, consiste en probar las dos opciones usando recursión. Consiste en que el ordenador se pregunte “¿Qué pasaría si …?” con cada una de las opciones posibles. De este tipo de algoritmos hay diferentes variantes (búsqueda exhaustiva, vuelta atrás, ramificación y poda, minimax, …) y son muy útiles, pues aprovechan la velocidad de cálculo de los ordenadores para encontrar, por ejemplo, la mejor forma de meter las canciones de un CD en una cinta de dos caras, el camino más corto para salir de un laberinto, la solución de un sudoku, o la siguiente jugada más beneficiosa en una partida de ajedrez.

Sin embargo, debido a su tarea sistemática de búsqueda, son horriblemente aburridos para ser realizados manualmente y, por tanto, no son buena idea para nuestros acertijos que queremos que puedan resolverse tanto programando como manualmente 🙂

La otra alternativa son los ya conocidos algoritmos voraces. Los algoritmos de este tipo toman en cada paso la decisión más eficiente en ese momento, y no se plantean nunca más si fue o no correcta. En el caso que nos ocupa, diríamos, sin posibilidad de arrepentimiento: “El contenedor ‘B’ lo ponemos sobre el contenedor ‘C’, porque de otro modo tendríamos una pila más y queremos tener cuantas menos mejor”. Y no nos plantearemos nunca qué habría pasado si hubiéramos hecho otra cosa. Los problemas que se pueden resolver con algoritmos voraces son menos habituales, porque para estar seguros de que con decisiones tan poco informadas (sin mirar al futuro) vamos a llegar a la solución óptima (en este caso, la del menor número de pilas) el problema tiene que adaptarse a eso. Por ejemplo, es imposible saber si es mejor girar o no girar en una esquina de un laberinto si no sabemos qué hay más allá. A cambio, aunque sean menos habituales, para los problemas que se resuelven con un algoritmo voraz se pueden encontrar soluciones muchísimo más deprisa, porque no hay que probar. De modo que, como ya sabéis, son mucho más aptos para nuestros acertijos 🙂

En el caso de esta semana, la forma de resolverlo era llevar la lista de las pilas ya construidas y, con cada nuevo contenedor, colocarlo en la primera que nos encontremos donde se pueda colocar para mantener el orden. Es decir, no vamos a querer que en una pila tengamos en la parte de arriba (cima) un contenedor que deba ser retirado para poder acceder a los que tiene abajo. Por ejemplo, si en una pila tenemos un contenedor destinado al barco ‘C’ no vamos nunca a querer poner encima un contenedor destinado al barco ‘R’, porque el barco ‘C’ se carga antes, y para poder obtener el contenedor de debajo tendremos que retirar el que va a ‘R’, rompiendo la restricción del acertijo. De modo que lo que haremos será ir colocando los contenedores en las pilas que tengan debajo contenedores para barcos que deben ser estibados más tarde. ¡Esto es precisamente lo que hacía el código en Python que nos puso David!

Veamoslo completo con la primera pregunta que os hacíamos, CBACBA. Al principio no hay ninguna pila de contenedores en el puerto, por lo que inauguramos la primera con la llegada del primer contenedor, el ‘C’. La situación es:

C

El siguiente es el ‘B’. Nos preguntamos, ¿podemos ponerlo encima de la única pila que tenemos sin que tengamos problemas más adelante? Es decir, ¿el nuevo contenedor ‘B’ va a ser estibado antes que todos los contenedores de alguna de las pilas que ya llevamos? La respuesta es que sí, que podemos colocarlo sobre ‘C’ sin problemas:

B
C

Llega el turno del tercer contenedor, ‘A’. Como antes, podemos ponerlo encima de la pila que llevamos sin problema:

A
B
C

Al llegar el cuarto, ‘C’, ya no podemos ponerlo en la misma pila, porque eso significaría que “taparíamos” el contenedor ‘A’, que debe ser retirado antes que el ‘C’ que estamos colocando. La única alternativa viable es comenzar una nueva pila:

A
B
C C

El siguiente ‘B’ irá en esa nueva pila también. El último contenedor, ‘A’, podemos en principio colocarlo en cualquiera de las dos. Sin embargo, nuestro algoritmo colocará los contenedores sobre la primera pila posible, por lo que el último contenedor acabará en la primera pila:

A
A
B B
C C

Como veis, tal y como nos dijo David en primer lugar, para los contenedores CBACBA necesitamos únicamente dos pilas. ¡Ahí las tenéis! Una cuestión importante aquí es que, aunque en este caso podríamos haber puesto el último contenedor ‘A’ en la segunda pila, nuestro algoritmo siempre lo colocará en la primera. Esto es importante porque nuestro algoritmo no se preocupa de qué vendrá después. Si tras la llegada de los contenedores CBACBA viniera un contenedor ‘B’, ¡sería un error poner el segundo ‘A’ en la segunda pila! Para evitar ese problema, nuestro algoritmo voraz debe obligatoriamente colocar los contenedores en la primera pila posible.

Para el resto de preguntas que os hacíamos, nuestros lectores, encabezados por David, también acertaron. Si lo hacéis (o programáis) veréis que para ‘ACERTIJO’ se necesitan 6 pilas, para ‘PROGRAMAME’ sólo 2, y para ‘MUCHOPORPROGRAMAR’ 5.

Lo complicado de los algoritmos voraces es estar seguros de que tomar la decisión óptima en cada paso nos llevará a la solución óptima general. Ante los contenedores CBACBA que hemos analizado, es obvio que no se puede hacer con menos pilas, pero ¿estamos seguros de eso en configuraciones más complicadas? Demostrar que un algoritmo voraz es óptimo es una cuestión que escapa a la programación, y, salvo que seamos muy formales y conozcamos las herramientas adecuadas, al final terminamos dejándonos llevar por la intuición.

De hecho, si pensáis con cuidado en este problema, quizá os surja una duda que merece la pena mencionar. En concreto, imaginemos que tenemos una situación de las pilas como la siguiente:

Z M

Y que los siguientes contenedores que nos llegan son ‘A’ y ‘P’. Siguiendo el algoritmo voraz el contenedor ‘A’ iría sobre el ‘Z’, pues siempre colocamos los contenedores en la primera pila válida:

A
Z M

Y al llegar el ‘P’ tendríamos que crear una pila nueva pues no se puede colocar sobre ninguna de las dos que ya tenemos:

A
Z M P

Lo “preocupante” de este ejemplo es que si hubiéramos colocado el contenedor ‘A’ sobre el ‘M’ todo habría ido mucho mejor:

P A
Z M

¿Significa esto que nuestro algoritmo no funciona? ¡¡No, el algoritmo está bien!! La trampa de este ejemplo es que la situación de partida es imposible con él. Fijaos que tenemos el contenedor ‘M’ en una pila nueva, cuando ese contenedor podríamos haberlo puesto sobre el ‘Z’. Por tanto, la situación de partida no es válida, y las conclusiones a las que llegamos desde ella tampoco.

Para terminar, en los comentarios hubo un interesante debate sobre las implementaciones. En su código en Python, que usaba este mismo algoritmo, David tenía un array de pilas, de manera que al acabar no sólo nos decía el número mínimo de pilas, sino también su distribución, algo útil para comprobar que todo estaba correcto. Gualterio comentó, con razón, que para dar la respuesta no es necesario guardar las pilas; al fin y al cabo, lo que queremos es saber en qué pila ponemos el siguiente contenedor, y para eso es suficiente conocer el último contenedor de cada pila (la cima), no todas las que tiene debajo. Si el número de contenedores es grande, ¡eso puede ahorrarnos mucha memoria! En lugar de tener una lista de pilas, tenemos una lista de caracteres, y cada vez que colocamos el siguiente contenedor en una “pila” sustituimos el caracter de esa posición de la lista. El ahorro en memoria va a costa, obviamente, de no poder mostrar la distribución completa de las pilas al terminar pero, al fin y al cabo, eso no os lo preguntábamos 🙂

Por último, y quizá todavía más interesante, Gualterio habló de búsqueda binaria. En la explicación que hemos dado (y en la solución de David) con la llegada de cada contenedor recorremos todas las pilas que tenemos creadas, empezando por la de la izquierda, buscando un lugar donde ponerlo. Esa búsqueda es lineal: si tenemos un millón de pilas y resulta que el nuevo contenedor hay que colocarlo en la última, vamos a tener que hacer un montón de comprobaciones.

Gualterio aprovecha que, por la forma en la que funciona el algoritmo, la lista en la que guarda las cimas de las pilas está ordenada alfabéticamente. Esto no es tener los contenedores de cada pila ordenados (que lo están, y que él ni siquiera guardaba), sino la lista con las cimas. Sobre esa lista ordenada, hay que hacer una búsqueda para saber en qué posición meter el nuevo contenedor. Y para eso, Gualterio se aprovecha de la búsqueda binaria (de la que ya hablamos de pasada en otro acertijo) que es mucho más rápida al aprovecharse de que el array donde se busca está ordenado. Él, decía, se aprovechaba de la implementación de esta búsqueda en la librería de C++, y así se evita trabajo de programación. En ese caso puede merecer la pena utilizarla; de otro modo, quizá no compense el esfuerzo de implementarla. Fijaos que, aunque hemos hablado de tener que hacer una búsqueda un millón de pilas, en realidad como mucho tendremos 26, una por cada letra, y los beneficios no van a ser tan significativos 🙂

¡Esta vez el acertijo ha dado mucho de sí! Esperamos que os haya servido para aprender la idea general de lo que son los algoritmos voraces. Y, como siempre, si queréis programarlo (en C/C++, Java o Pascal), podéis probarlo aquí.

¡Hasta el próximo!

Anuncios

From → Soluciones

2 comentarios
  1. Gualterio permalink

    Hola,

    Aquí dejo la idea de implementación usando búsqueda binaria. Asume que hay un array de char’s que se llama word con la palabra/orden de los contenedores, y un vector que irá creciendo y que contiene las cimas de todas las pilas:

    int l = strlen(word);
    for (int i = 0; i < l; ++i) {

    vector::iterator it = lower_bound(tops.begin(), tops.end(), word[i]);
    if (it == tops.end())
    tops.push_back(word[i]);
    else
    *it = word[i];
    }

    La solución/número de pilas es tops.length().

    • Gualterio permalink

      Vaya, no salieron los tabuladores… Bueno, espero que más o menos se entienda 🙂

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: