Publicado el 4 de Mayo, 2008, 16:21
|
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 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 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 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 Packing Problema Partition Problem Cutting Stock Problem Cutting Stock Problem Subset Problem (tiene relación con obtener una n-baldosa) EURO Special Interest Group on Cutting and Packing Si hasta hay ahí:
Si hasta hay software para solucionar problemas similares: Más sobre búsqueda de soluciones enteras: Advanced Integer Programming Sobre complejidad de algoritmos: NP Complexity NP-complete Karp s 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/ Nos leemos! Angel "Java" Lopez |
Soy un "fan" de 
