Angel "Java" Lopez en Blog

Publicado el 4 de Mayo, 2008, 16:21

Soy un "fan" de Adrian Monk, el detective patológicamente obsesivo, una de las pocas series de TV que veo cada semana. Siendo como es, tiene miedo a casi todo. Cuando contrata una caja fuerte en el banco, pide que sea de un número redondo, como 100. Si se encuentra con dos lapiceras, una más llena que la otra, usa la primera, hasta que las empareja. Cada servilleta, tenedor y elemento sobre la mesa, debe estar ordenado. Un cuchillo oblicuo a los demás, es capaz de sacarlo de quicio. Y la comida que come, debe estar separada dentro del plato: nada de mezclarla antes de comerla.

A Monk le disgusta pisar los bordes de las baldosas cuando camina. Debo confensar que a mí también... :-).... bueno, no tanto como a Monk. Ese es otro motivo para que quien lea esto infiera que, como se dice por aquí en Argentina, yo no tenga "todos los patitos en línea". Pero eso es tema para otro post. Mientras, les comento a todos que, con la medicación apropiada, no soy peligroso...:-)

En este fin de semana, estuve pensando en un problema matemático (el origen del problema al final de este post). Supongamos que tenemos un conjunto de bloques de madera:

No nos preocuparemos de su altura. Para el problema nos intersa su ancho horizontal. Usaremos los bloques en esa posición. Para simplificar, supondremos que tienen un ancho entero respecto de una unidad.

Tenemos una serie de baldosas contiguas, tambien de ancho entero, de tal manera que la suma del ancho de esas baldosas es igual a la suma del ancho de nuestros bloques. Podemos, entonces, cubrir las baldosas con nuestros bloques:

El problema es: cubrir las baldosas, tratando de minimizar la cantidad de bloques que "pisan" dos baldosas a la vez. Somos Monk: quisiéramos no pisar los bordes de las baldosas. No importa el tamaño de los bloques que infringen la regla de Monk: sólo nos interesa minimizar las infracciones. En la figura de arribla, el bloque amarillo está sobre dos baldosas verde oscuro.

Es fácil ver que no siempre podemos cumplir con Monk: tres baldosas de 10 unidades, y 10 bloques de 3 unidades, implican dos "pisajes múltiples".

Uno podría imaginar que hay un algoritmo sencillo para, dado un conjunto de bloques y baldosas, uno pueda llevar a la mejor solución. Pero nones. Todo indica que es un problema tipo NP.

Alguna notación: un conjunto de bloques le diremos que es 1-baldosa si cubre exactamente una baldosa. Y 2-baldosa si cubre exactamente dos baldosas. Y así.

Puedo sugerir un algoritmo tentativo, pero que no siempre da la mejor solución:

- Maximizar la cantidad de conjuntos 1-baldosa
- Con el resto de los bloques, maximizar la cantidad de conjuntos 2-baldosa
- Y así, proseguir, hasta que las baldosas que queden, digamos 3 baldosas, sólo puedan cubrirse con un conjunto 3-baldosa

El problema es que, al maximizar la cantidad de conjuntos 1-baldosa, luego puede suceder que nos convenga "deshacer" uno de esos conjuntos, para aumentar la cantidad de conjuntos 2-baldosa, y aún con la pérdida de un conjunto 1-baldosa, puede que tengamos menos cortes que antes.

Un ejemplo hipotético: habiendo desarrollo los conjuntos 1- y 2-baldosa, nos encontramos que tenemos 3 de los primeros, y 3 de los segundos, y bloques que sobran. Hasta el momento, tenemos 3 bordes de baldosas pisados (los del medio de los conjuntos 2-baldosa). Podemos encontrar que desaciendo uno de los conjuntos 1-baldosa, conseguimos armar 3 conjuntos 2-baldosas adicionales, con lo que podríamos disminuir las infracciones finales.

Si llenáramos las baldosas utilizando primero los bloques más grandes, de tal forma que siempre tratamos de encajarlos en un conjunto 1-baldosa, sino los desechamos para colocarlos despues, pues bien, no obtenemos siempre la mejor solución.

Un ejemplo concreto:

- 4 baldosas de 10 unidades
- 1 bloque de 8 unidades
- 2 bloques de 1 unidad
- 10 bloques de 3 unidades

Si tratamos de cubrir una baldosa con el mayor bloque, llegamos a la disposición (no importa el orden dentro de la baldosa):

8.1.1

Luego, al tratar de llenar las 3 baldosas restantes con los 10 bloques de 3 unidades, siempre pisamos los bordes:

8.1.1 3.3.2- -1.3.3.2- -1.3.3.3

(la notación 2- -1 indica que "partimos" el bloque en dos baldosas).

Pero hay una mejor solución: "deshacer" el mejor conjunto 1-baldosa, para poder armar otros del mismo orden:

3.3.3.1 3.3.3.1 8.2- -1.3.3.3

Y ahora, Monk, si bien no estará completamente calmado, verá que es mejor que la anterior solución.

Hay varios conjuntos de bloques que hacen que el algoritmo "el más grande primero" falle. Basta tener

B = ancho de baldosa
N = cantidad de baldosas
B primo con M
R = B mod M
(N-2) bloques de longitud R
(N-1)*B divisible por M
(N-1)*B/M bloques de longitud M
1 bloque de B-R*(N-2) unidades

En nuestro caso, B=10, N=4, M=3, entonces R=1 (todo esto a revisar)

El problema original fue planteado en una lista privada, y es distinto que éste que planteo. Pero fue mi inspiración. Como está planteado en una lista privada, no puedo describirlo acá sin permiso. Se sugirió que su solución tiene relación con el problema llamado Knapsack.

De ahí, encontré estos enlaces interesantes, algo relacionados con este problema:

Knapsack Problem
http://en.wikipedia.org/wiki/Knapsack_problem

Packing Problema
http://en.wikipedia.org/wiki/Packing_problem

Partition Problem
http://en.wikipedia.org/wiki/Partition_problem

Cutting Stock Problem
http://en.wikipedia.org/wiki/Cutting_stock_problem

Cutting Stock Problem
http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/cutting/formulation.html

Subset Problem (tiene relación con obtener una n-baldosa)
http://en.wikipedia.org/wiki/Subset_sum_problem

EURO Special Interest Group on Cutting and Packing
http://paginas.fe.up.pt/~esicup/tiki-index.php

Si hasta hay ahí:

 Call for Papers

The purpose of this special issue is to encourage research dealing with cutting, packing and related problems. Case studies describing successful applications in practice are particularly welcome. Topics for this special issue include (but are not limited to) the following:

• Cutting and packing problems;
• Bin packing;
• Knapsack problems;
• Pallet and container loading;
• Nesting;
• Pattern sequencing;
• Layout problems;
• Multi-processor scheduling; and
• Integrated problems such as cutting and sequencing, lot sizing and cutting, routing and packing, etc.
 

Si hasta hay software para solucionar problemas similares:

AutoLoad Pro-Container Loading Software 2007 review and download. load planner, cargo load planning, cargo loading, 
http://rbytes.net/software/autoload-pro-container-loading-software--review/

Más sobre búsqueda de soluciones enteras:

Advanced Integer Programming
http://opim.wharton.upenn.edu/~guignard/916_2007/916.html

Sobre complejidad de algoritmos:

NP Complexity
http://en.wikipedia.org/wiki/NP_%28complexity%29

NP-complete
http://en.wikipedia.org/wiki/NP-complete

Karp s 21 NP-complete problems
http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems

He dejado esos enlaces en

http://del.icio.us/ajlopez/algorithm

Más sobre Adrian Monk en

http://www.usanetwork.com/series/monk/
http://en.wikipedia.org/wiki/Adrian_Monk

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com/