🚀 go-pugleaf

Hola, Tomey:

Tomey escribi� en es.comp.os.linux.programacion:

> Si, correcto.
> Se me olvido poner el ^ :P
> 
> Voy a probar el algoritmo que me has pasado a ver que tal.
> 
> Te explico exactamente el problema a ver si asi te sirve de algo mas de
> ayuda.
> Una empresa me ha pedido que haga un programa que es el siguiente.
> 
> Ellos tienen barras de aluminio de 30 metros (supongamos, medida
> standard). Y necesitan sacar de esas barras de aluminio 3 secciones de
> 10m, 5 de 43m y 4 de 27m.
> Hay que optimizar los cortes de las barras para que la perdida de material
> sea el minimo.
> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre
> sea reutililizable.

�De cu�ntas barras estamos hablando?

En principio, el problema parece NP-Dif�cil (t=>a^n), no obstante, con un
n�mero relativamente bajo de barras, y si el tiempo no es cr�tico, puedes
optar por la cosa m�s sencilla: hacer una b�squeda exhaustiva en el espacio
de soluciones (es decir, calcular *todas* las soluciones posibles y
quedarte con la mejor).  Es problable que si el stock es menor que,
digamos, 100 barras, eso te sea suficiente si puedes obtener la soluci�n
en, digamos, menos de una o dos horas (el hecho de que una soluci�n sea
"fea" en t�rminos absolutos, no quiere decir que no pueda ser perfectamente
viable en tu entorno real).

Si ves que el proceso es demasiado largo para tus necesidades, puedes
utilizar el m�todo de bipartici�n, que deber�a ser lineal: simplemente coge
la secci�n m�s larga, y luego la m�s larga que te quede (y que entre en el
resto), de entre las restantes, sucesivamente hasta que no te quepa ninguna
m�s.  No voy a echar n�meros ahora, pero tiene pinta de ser una
aproximaci�n "suficientemente buena".  La suposici�n que hago es que todas
las barras que utilizas son del mismo tama�o, ya que no dices otra cosa.

> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una
> barra es de 10m.
> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o
> superiro a 10m.

Con esta constricci�n, juega con dos barras, una "real" y otra "virtual"
diez metros m�s corta; si consigues que a la barra "virtual" le sobre menos
material que a la barra "real", �sa es tu soluci�n; en caso contrario, usa
la soluci�n obtenida para la barra "real".

Veamos un ejemplo pr�ctico con los datos que das:

Primera barra:
        27m (nos sobran tres metros, que es un tama�o mayor que la secci�n m�s
peque�a, por lo que ya no podemos seguir; veamos que pasa con la barra
"virtual" de 20m):
                10m+10m (no sobra nada, por lo tanto cogemos esta soluci�n y nos queda un
"resto" de 10m, que volvemos a partir):
                10m (no sobra nada, y ya hemos acabado con las secciones de 10m)
Segunda barra:
        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" de 20m;
voy a suponer que donde dices 5 secciones de 43m son 10 secciones de 5m, ya
que las de 43m no "caben" en la barra de 30m, y con 43 barras, el ejemplo
sale demasiado largo):
                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta soluci�n y nos queda
un "resto" de 10m, que volvemos a partir):
                5m+5m (no sobra nada)
Tercera barra:
        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" de
20m):
                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta soluci�n y ya no nos
quedan secciones de cinco metros; nos queda un "resto" de 10m, que
intentamos volver a partir, pero no podemos, porque no nos quedan ya
perfiles iguales o menores que 10m para encajar).
Cuarta, quinta, sexta y s�ptima barras: 27m, y nos sobran tres pedazos de 3m
de cada una (la soluci�n de la "barra virtual" la omito porque es evidente
que no va a ser mejor).

Ya hemos acabado.  En este caso, adem�s, se puede demostrar que hemos
encontrado la soluci�n �ptima*1: el reparto no pod�a hacerse de mejor
manera, porque la secci�n m�s larga (la de 27m) no dejaba sitio en la barra
para la secci�n m�s peque�a (la de 10m) 

Pueden existir optimizaciones locales "parientes" de los algoritmos de
ordenaci�n, pero no las busques a menos que realmente las necesites (ya
sabes, "early optimization is the root of all evils"): por ejemplo, puesto
que hemos ordenado las secciones de mayor a menor, una vez que la barra m�s
corta que nos queda no quepa en la "barra virtual", sabemos que ya no nos
hace falta intentar con ella en iteraciones posteriores; o, si en la barra
entran muchas secciones, o si tenemos muchos tama�os distintos a encajar,
podemos avanzar "a saltos" 2:1 o 3:1 para encontrar la secci�n adecuada
cuando las mayores ya no nos quepan, o puedes probar a colocar los perfiles
en lugar de mayor a menor, de forma alterna mayor-menor-mayor-menor...

*1 En general, puedes calcular heur�sticamente si esta aproximaci�n es
razonablemente buena utilizando un m�todo de montecarlo para generar
pedidos aleatorios (la generaci�n de pedidos la puedes sustituir, por
ejemplo, por el listado de pedidos del �ltimo a�o, si tienes acceso a �l),
y luego calculando el resto �ptimo si s�lo tuvieras una barra de longitud
m�ltiplo de la barra real, compar�ndolo con el que te da el procedimiento
que te he contado.
En el ejemplo: 3*10 + 10*5 + 4*27 = 188m
               7*30=210m
               210-188=22m sobrantes
As�, sabemos que en la soluci�n ideal nos van a sobrar por lo menos 22m
(justo lo que nos sobr� a nosotros, por eso sabemos que nuestra soluci�n
era ideal).  Puesto que no tenemos una barra de 210m, sino muchas de 30,
podr�a darse el caso de la soluci�n �ptima te�rica no existiese: por
ejemplo, supongamos que nos piden 12 perfiles de 25m; el �ptimo te�rico
ser�a (12*25=300; 300/30=10) utilizar diez barras sin que nos sobrase nada,
pero es obvio que en este caso necesitar�amos 12 barras y nos sobrar�an 12
trozos de cinco metros.  As�, aunque no sabemos realmente cu�n cerca
estamos del �ptimo real (para ello habr�a que calcular exhaustivamente los
�ptimos reales y compararlos con las soluciones obtenidas, o poder
demostrar matem�ticamente la aproximaci�n del algoritmo en el paso al
l�mite -existe toda una rama de la matem�tica que se dedica a estas cosas-)
s� tenemos una idea aproximada de lo bien que lo estamos haciendo.  Si,
adem�s, tienes acceso a los pedidos del �ltimo a�o, puedes establecer si el
m�todo es mejor que el que ten�a la empresa, tanto calcul�sticamente
(cu�ntas barras utilizaron realmente y cu�ntas hubieran utilizado caso de
usar tu programa), como en tiempo (cu�nto tiempo les llev� hacer los
c�lculos -si esa informaci�n existe- y cu�nto les hubiera costado de haber
utilizado tu programa).  Puede darse el caso de que incluso si tu programa
fuese peor que el m�todo que estuviesen utilizando hasta ahora, fuese
rentable si, por ejemplo, se pasase de usar dos horas diarias de operador
con l�piz y papel, a utilizar 10 minutos diarios de tiempo de ordenador. 
Si la diferencia es sustancial, incluso puedes plantear un aumento de
sueldo por una fracci�n del dinero que les est�s ahorrando.
-- 
SALUD,
Jes�