algorithm - problems - Mochila parabólica

p np

Question

Digamos que tengo una parábola. Ahora también tengo un montón de palos que tienen todos el mismo ancho (¡sí, mis habilidades para dibujar son increíbles!). ¿Cómo puedo apilar estas barras dentro de la parábola de manera que estoy minimizando el espacio que usa tanto como sea posible? Creo que esto cae dentro de la categoría de problemas de mochila , pero esta página de Wikipedia no parece acercarme más a una solución del mundo real. ¿Es este un problema NP-Hard?

En este problema, estamos tratando de minimizar la cantidad de área consumida (p. Ej .: Integral), que incluye el área vertical.

Answer 1

¿Cómo puedo apilar estas barras dentro de la parábola de manera que estoy minimizando el espacio (vertical) que utiliza tanto como sea posible?

Solo trátelo como cualquier otro problema de Bin Packing . Me gustaría lanzar meta-heurística en él (como la búsqueda tabú , recocido simulado , ...) ya que esos algoritmos no son específicos del problema.

Por ejemplo, si comenzara desde mi problema de equilibrio de la nube (= una forma de embalaje de la papelera) en Drools Planner . Si todos los palos tienen la misma altura y no hay espacio vertical entre 2 palos uno encima del otro, no hay mucho que deba cambiar:

• Cambiar el nombre de la Computer a ParabolicRow . Eliminar sus propiedades (CPU, memoria, ancho de banda). Dale un level único (donde 0 es la fila más baja). Crea un número de ParabolicRows .
• Renombrar Process para Stick
• Cambiar el nombre de ProcessAssignement a StickAssignment
• Reescribe las restricciones difíciles para que compruebe si hay espacio suficiente para la suma de todos los Sticks asignados a una ParabolicRow .
• Reescribe las restricciones suaves para minimizar el level más level de todos los ParabolicRows .

Answer 2

Simplificando

Primero quiero simplificar el problema, para hacer eso:

• Cambio los ejes y los sumo unos a otros, esto da como resultado un crecimiento x2
• Supongo que es una parábola en un intervalo cerrado [a, b], where a = 0 y para este ejemplo b = 3

Digamos que le dan b (segunda parte del intervalo) w (ancho de un segmento), luego puede encontrar el número total de segmentos en n=Floor[b/w] . En este caso, existe un caso trivial para maximizar la suma y la función de Riemann para obtener la altura del segmento is: f(b-(b*i)/(n+1))) . En realidad, es una suposición y no estoy 100% seguro.

Ejemplo maximo para 17 segmentos en intervalo cerrado [0, 3] para valores reales de función Sqrt[x] :

Y la función de alturas de segmento en este caso es Re[Sqrt[3-3*Range[1,17]/18]] , y los valores son:

• Forma exacta:

{Sqrt [17/6], 2 Sqrt [2/3], Sqrt [5/2], Sqrt [7/3], Sqrt [13/6], Sqrt [2], Sqrt [11/6], Sqrt [5/3], Sqrt [3/2], 2 / Sqrt [3], Sqrt [7/6], 1, Sqrt [5/6], Sqrt [2/3], 1 / Sqrt [2], 1 / Sqrt [3], 1 / Sqrt [6]}

• Forma aproximada:

{1,6832508230603465, 1,632993161855452, 1,5811388300841898, 1,5275252316519468, 1,4719601443879744, 1,4142135623730951, 1,35400640077266, 1,2909944487358056, 1,224744871391589, 1,1547005383792517, 1,0801234497346435, 1, ,9128709291752769, ,816496580927726, ,7071067811865475, ,5773502691896258, ,4082482904638631}

Lo que ha archivado es un problema de empaquetamiento de bandejas , con un contenedor parcialmente lleno.

Encontrar b

Si b se desconoce o nuestra tarea es encontrar el menor posible b debajo de lo que todos los palos forman el ajuste inicial del grupo. Entonces podemos limitar al menos b valores a:

1. límite inferior: si suma de alturas de segmento = suma de alturas de barra
2. límite superior: número de segmentos = número de palos palo más largo <altura del segmento más larga

Una de las formas más sencillas de encontrar b es tomar un pivote en (higher limit-lower limit)/2 buscar si existe una solución. Luego se convierte en un límite superior o inferior y se repite el proceso hasta que se alcanza la precisión requerida.

Cuando busca b , no necesita un resultado exacto, pero no es óptimo y sería mucho más rápido si utiliza un algoritmo eficiente para encontrar un punto de pivote relativamente cercano al b real.

Por ejemplo:

• clasifique el palo por longitud: de mayor a menor
• comience a "poner los artículos más grandes" en el primer recipiente que se ajuste

Answer 3

Apoyos para aquellos que mencionaron el hecho de que los niveles podrían estar a diferentes alturas (por ejemplo, suponiendo que los palos son 1 ''de espesor'' nivel 1 va de 0.1 unidades a 1.1 unidades, o podría ir de 0.2 a 1.2 unidades en su lugar)

Por supuesto, puede ampliar la metodología de "empaquetado múltiple" y probar incrementos arbitrariamente pequeños . (Ejemplo: ejecute la metodología de binpacking múltiple con niveles que comienzan en 0.0, 0.1, 0.2, ... 0.9) y luego elija el mejor resultado, pero parece que se quedaría atrapado calulando por una cantidad infinita de tiempo a menos que tuviera alguna metodología. para verificar que lo hiciste "bien" (o más precisamente, que tenías todas las "filas" correctas en cuanto a lo que contenían, en ese punto podrías cambiarlas hasta que toparan con el borde de la parábola)

Además, el OP no especificó que los palos debían colocarse horizontalmente, aunque tal vez el OP lo implicó con esos dibujos dulces.

No tengo idea de cómo resolver este problema de manera óptima, pero apuesto a que hay ciertos casos en los que puedes colocar palos aleatoriamente y luego probar si están "dentro" de la parábola, y superaría a cualquiera de las metodologías que dependen solo de la tecnología horizontal. filas (Considere el caso de una parábola estrecha que intentamos llenar con 1 palo largo).

Yo digo que simplemente los tire a todos allí y sacúdalos;)

Answer 4

Esto es equivalente a tener varias mochilas (suponiendo que estos bloques tengan la misma "altura", esto significa que hay una mochila para cada "línea"), y es, por lo tanto, una instancia del problema de embalaje de la papelera.

Ver http://en.wikipedia.org/wiki/Bin_packing

Answer 5

Estoy muy seguro de que es equivalente al bin-packing:

reducción informal

Sea x el ancho de la fila más ancha, haga los contenedores 2 veces grandes y cree para cada fila un elemento marcador de posición que tenga 2x-rowWidth big. Por lo tanto, dos elementos de marcador de posición no se pueden empaquetar en un solo contenedor.

Para reducir el bin-packing en la mochila parabólica solo debes crear elementos de marcador de posición para todas las filas que sean más grandes que el binsize necesario con ancho-binsize de tamaño. Además, agregue marcadores de posición para todas las filas que sean más pequeñas que Binsize, que llenan toda la fila.

Esto obviamente significaría que su problema es NP-difícil.

Para otras ideas, mira aquí tal vez: http://en.wikipedia.org/wiki/Cutting_stock_problem

Answer 6

Lo más probable es que este sea el problema 1-0 Knapsack o un problema con el bin-packing. Este es un problema difícil de NP y muy probablemente este problema no lo entiendo y no puedo explicarte pero puedes optimizar con algoritmos codiciosos. Aquí hay un artículo útil al respecto http://www.developerfusion.com/article/5540/bin-packing que utilizo para hacer mi paquete de bin de php class en phpclasses.org.

Answer 7

Preparé una solución en JavaScript usando processing.js y canvas HTML5.

Este proyecto debería ser un buen punto de partida si desea crear su propia solución. Agregué dos algoritmos. Uno que clasifica los bloques de entrada de mayor a menor y otro que mezcla aleatoriamente la lista. Luego se intenta colocar cada elemento en el cucharón comenzando desde la parte inferior (el cubo más pequeño) y moviéndolo hacia arriba hasta que tenga espacio suficiente para caber.

Dependiendo del tipo de entrada, el algoritmo de clasificación puede dar buenos resultados en O (n ^ 2). Aquí hay un ejemplo de la salida ordenada.

Aquí está el algoritmo de insertar en orden.

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

Proyecto en github - https://github.com/gradbot/Parabolic-Knapsack

Es un repositorio público así que siéntase libre de ramificar y agregar otros algoritmos. Probablemente agregue más en el futuro, ya que es un problema interesante.