Rutina para optimizar cortes. Estrategia

He estado probando corte certo. Y sólo por seguir jugando se me ha ocurrido hacer una rutina para optimizar los cortes de barras (elementos de una dimensión). Le he estado dando vueltas y ya tengo pensadas las primeras versiones.

No sé cuanto tardaré, supongo que mucho, porque lo hago por jugar, en mi tiempo libre, que es escaso. Pero lo acabaré algún día.

La idea es intentar huir de la fuerza bruta. Ni una sola mosca más muerta a cañonazos. No voy a programar un script que haga todas las permutaciones y escoja la que menos piezas usa, es un camino que no me interesa mucho. Disfrutaré más intentando inventar un programa que use un poquito de inteligencia…

Patrones de prueba

Para poner a prueba los diferentes prototipos hay que inventar una serie de patrones, de despieces que sean los problemas que debe intentar resolver cada rutina.

Se me han ocurrido dos patrones. Uno con solución sin retales, y otro sin garantía de solución sin retales.

El patrón con solución sin retales sería partir cada una de las piezas con diferentes denominadores. Avanzando de uno en uno para cada pieza de partida. Y dentro de cada pieza, seguiría una sucesión en los numeradores, mientras sea posible. Cuando ya no se puedan hacer más cortes, se hace otro con el resto. Mejor lo escribo con fracciones:

  1. 1 = 1
  2. 1/2 + 1/2 = 1
  3. 1/3 + 2/3 = 1
  4. 1/4 + 2/4 + 1/4 = 1
  5. 1/5 + 2/5 + 2/5 = 1
  6. 1/6 + 2/6 + 3/6 = 1

El patrón sin garantía de solución sin retales sería similar, pero llegando siempre hasta la fracción (n – 1)/n, independientemente de que forme pieza completa o no la forme. Por éso digo que podría ocurrir que no tenga una solución redonda, y tenga resto…

  1. 1 = 1
  2. 1/2 = 1/2
  3. 1/3 + 2/3 = 1
  4. 1/4 + 2/4 + 3/4 = 6/4
  5. 1/5 + 2/5 + 3/5 + 4/5 = 2
  6. 1/6 + 2/6 + 3/6 + 4/6 + 5/6 = 5/2

Empezando con pocas piezas, se puede ir subiendo la complejidad con más y más piezas, o limitando los denominadores a números primos, que lo van a hacer más complejo…

Es un problema de números enteros

Creo que el meollo de la cuestión para evitar un cálculo por fuerza bruta es que se trata de un problema de números enteros. Me explico con un ejemplo:

Supongamos que tenemos que comprar un montón de barras de 6m, para cortarlas y obtener un número de piezas de diferentes longitudes.

Supongamos que todas las piezas que necesito cortar suman un total de 595 m. Por muy bien que lo haga y por mucho que me esfuerce, tendré que comprar 100 barras de 6m. Puedo hacer tropecientasmil combinaciones, que la primera que consiga consumir sólo 100 barras no será ni mejor ni peor que cualquier otra combinación que no consuma más barras.

Y esa va a ser la estrategia para huir de la fuerza bruta y hacer un programa rápido y liviano: Si con un cálculo sencillo se consigue el mínimo número de barras que se puede esperar, se para el proceso. Si hay muchos retales y obligan a comprar una sola barra más de las necesarias, entonces se calcula de una forma más concienzuda, evaluando más posibilidades. Y buscando ahorro donde se puede encontrar.

Tecnología

Quizás lo haga en Python (por aprender), en una hoja de cálculo con macros o, muy probablemente, una versión web, con Javascript. Por hacer crecer al frontend developer que ha nacido dentro de mí.

Es lo de menos. Probablemente lo haga en verios formatos. Probablemente intente engatusar a Álvaro (el aprendiz que se convirtió en maestro) para que lo haga en Java, como app nativa de Android.

Proximamente, la descripción de las diferentes versiones…

Anuncios

Acerca de Pablo Nieto Cabezas

Arquitecto

Publicado el 5 diciembre, 2016 en Informática, Tecnología y etiquetado en , . Guarda el enlace permanente. Deja un comentario.

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: