algorithm - programacion - Cortar el algoritmo de optimización
problema de cutting stock (3)
A mí y a algunos de mis amigos en la universidad se les asignó la tarea práctica de desarrollar una aplicación de red para la optimización del corte de piezas rectangulares de algún tipo de material. Algo así como aplicaciones en esta lista, pero más simple. Básicamente, me interesa saber si hay algún código fuente para este tipo de algoritmos de optimización disponibles en Internet. Estoy planeando desarrollar la aplicación usando el marco Adobe Flex. La parte de programación se realizará en Actionscript 3, ofc. Sin embargo, dudo que haya muestras de optimización para este idioma. Sin embargo, puede haber algunos para Java, C ++, C #, Ruby o Python y otros lenguajes más populares (entonces tendría que volver a escribirlo en AS). Por lo tanto, si alguien sabe alguna libre libs o muestras de código de algoritmo que me convienen, me gustaría escuchar sus sugerencias. :)
¡Esto suena exactamente como el problema de corte de stock que es extremadamente difícil! Las mejores soluciones usan programación lineal (típicamente basada en el método símplex) con generación de columnas (que, incluso después de años en un proyecto de investigación de resolución de restricciones, no me siento capacitado para dar una explicación medio decente). En resumen, no querrás probar este enfoque en Actionscript; en consecuencia, con lo que sea que implemente, no debe esperar grandes resultados en nada que no sean pequeños problemas.
El mejor consejo que puedo ofrecer, entonces, es ver si puedes cortar el rectángulo fuente en tiras (cada uno del ancho de los rectángulos más grandes que necesitas), luego subdividir el resto de cada tira después de que el rectángulo "cabeza" haya sido eliminado .
Recomendaría utilizar la función de rama y destino como su estrategia de optimización. BnB funciona haciendo una búsqueda exhaustiva de árboles que hace un seguimiento de la mejor solución vista hasta ahora. Cuando encuentre una solución, actualice el límite y retroceda buscando la siguiente solución. Cada vez que sepa que su búsqueda lo lleva a una sucursal que usted sabe que no puede conducir a una solución mejor que la mejor que ha encontrado, puede retroceder temprano en ese punto.
Dado que estos árboles de búsqueda serán muy grandes, es probable que desee colocar un límite de tiempo en la búsqueda y simplemente devolver su mejor esfuerzo.
Espero que esto ayude.
Esto puede ser excesivo para lo que necesita, pero el siguiente enlace describe un enfoque que da muy buenos resultados para este tipo de problema:
http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy
No hay código disponible, pero el algoritmo se describe con suficiente detalle como para que no sea demasiado difícil de implementar. Lo he implementado usando C # (lo siento, no puedo compartir ese código) y estaba muy contento con el resultado.
Tuve problemas para encontrar ejemplos cuando quería hacer lo mismo para la empresa maderera que trabajo. El problema en sí es NP-hard, por lo que debe usar un algoritmo de aproximación como primer algoritmo de ajuste o mejor ajuste. Haga una búsqueda de algoritmos de bin-packing 2d. El que encontré, clasificas los paneles más grandes a los más pequeños, luego agregas las hojas en orden, colocando el primer contenedor que encajará. Lo siento, no tengo el código conmigo y está en vb.net de todos modos.