lunes, 4 de julio de 2011

Fundamentos de la complejidad Computacional: Problema de Bin Packing

Problema
El problema de Bin Packing es un problema NP Complejo (Polinomial No Determinista), El problema consiste en intentar acomodar en un recipiente la mayor cantidad posible de objetos de diferente valor y volumen, ocupando el mayor espacio posible.

En este problema lo que se busca es tratar de aprovechar la mayor cantidad de espacio posible que este disponible en el contenedor o recipiente y acomodar todo de una mejor manera para que pueda caber mas y se pueda optimizar el espacio como se muestra en la imagen siguiente.

Como podemos observar en la imagen no hay ningun espacio en blanco. Todo ese espacio fue bien aprovechado debido a que los objetos dentro del contenedor se colocaron adecuadamente.
Este problema se puede plantear de diferentes maneras, dependiendo del algoritmo que tengamos para resolverlo. Podria plantearse como un problema de definicion en el siguiente caso:
Imaginemos que tenemos varios objetos de diferentes volumenes y valores:

Para poder obtener el valor total maximo de los objetos que podrian caber en el recipiente necesitamos preguntar si existe N valor de objetos adentro (De preferencia tenemos que utilizar uno grande).

Por ejemplo, podemos preguntar si dentro del recipiente se podria obtener un valor total de 500. Si la respuesta a esta decision es si, entonces vamos disminuyendo el numero hasta que nos diga que el valor proporcionado no es el mayor. Despues de que nos diga que no debemos aumentar los valores hasta llegar al valor maximo correcto.
En cuanto al algoritmo de optimizacion, se iran desechando solos los objetos que no sean indispensables o que no tengan mucho valor y se ira acomodando todo de una manera automatica asi como podemos ver en el siguiente video


Justificacion
Este problema me llamo mucho la atención porque tiene una inmensa variedad de aplicaciones y usos. Se puede aplicar por ejemplo en los contenedores de basura, en los trailes que tienen que mantener cierto peso estable, para conservar la ecologia y hacer menos desperdicio de recursos y espacio de los que normalmente se utilizan.
Es indispensable saber administrar bien el espacio y hacerlo rendir. Es por esto que considero este problema muy común en el mundo actual y se puede aplicar en muchos aspectos.


Complejidad
Como dije anteriormente, este problema es Combinatorio NP(Polinomial No Determinista) Complejo. 


Algoritmos
Aqui les muestro el video de un algoritmo que encontre en internet sobre este problema. Me gusto porque viene informacion detallada del algoritmo.




Este es un codigo que encontre en internet solucionando el mismo problema



float[] used = new float[n + 1];
   //used[j] is the amount of space in bin j already used up.
   int i, j;
   Initialize all used entries to 0.0
   Sort S into descending(nonincreasing)order, giving the sequence S1 >= S2 >= ... >= Sn.
   for(i = 1; i <= n; i++)
     //Look for a bin in which s[i] fits.
     for(j = 1; j <= n; j++)
      if (used[j]+si<+1.0)
        bin[i] = j;
        used[j] += si;
        break;  //exit for(j)
     //continue for(i).




Referencias



3 comentarios:

  1. Ahora no confundas bin packing con knapsack. En bin packing debes poner a TODOS los objetos y lo que optimizas es la cantidad de contenedores ocupados. Una definición matemática de lo que se hace, un ejemplo que hayas trabajado tú y la discusión de la complejidad computacional, incluyendo una explicación de una reducción de un problema cuyo complejidad está establecida a tu problema hubieran sido bienvenidos. Te pongo 9 puntos.

    ResponderEliminar