¿Astackr cajas en la menor cantidad de stacks eficientemente?

Tengo esta pregunta en un desafío de encoding en línea.

Dada una lista de cuadros con longitud y ancho (l, h), genere el número mínimo de stacks necesarias para contener todos los cuadros, ya que puede astackr un cuadro sobre otro si su largo y ancho son menores que los del otro cuadro.

No puedo averiguar cómo encontrar una solución de tiempo polinomial. Construí una solución de fuerza bruta que crea todos los arreglos de stack posibles de forma recursiva (comience con las stacks de N. Luego, para cada stack, intente colocarla encima de cada stack de otras. A continuación, genere de forma recursiva todas las posibilidades de stack dada la nueva disposición de stack). y luego devuelve el menor número de stacks necesarias.

Lo he acelerado con algunas optimizaciones:

  • Si puede astackr la caja A encima de la caja B y la caja C, y puede astackr la caja B encima de la caja C, entonces no considere astackr la caja A en la caja C.
  • Memorice los arreglos de stack, solo teniendo en cuenta los niveles inferior y superior de las stacks

Aquí está el código de Python para esta solución:

from time import time def all_stacks(bottom, top, d={}): memo_key = (tuple(bottom), tuple(top)) if memo_key in d: # print "Using MEMO" return d[memo_key] res = len(bottom) found = False stack_possibilities = {} # try to stack the smallest boxes in all the other boxes for j, box1 in enumerate(bottom): stack_possibilities[j] = [] for i, box2 in enumerate(top[j:]): # box1 fits in box2 if fits(box2, box1): stack_possibilities[j].append(i + j) found = True for fr, to_list in stack_possibilities.iteritems(): indices_to_keep = [] for box_ind in to_list: keep = True for box_ind_2 in to_list: if fits(top[box_ind], top[box_ind_2]): keep = False if keep: indices_to_keep.append(box_ind) stack_possibilities[fr] = indices_to_keep if found: lens = [] for fr, to_list in stack_possibilities.iteritems(): # print fr for to in to_list: b = list(bottom) t = list(top) t[to] = t[fr] del b[fr] del t[fr] lens.append(all_stacks(b, t, d)) res = min(lens) d[memo_key] = res return res def stack_boxes_recursive(boxes): boxes = sorted(boxes, key=lambda x: x[0] * x[1], reverse=False) stacks = all_stacks(boxes, boxes) return stacks def fits(bigbox, smallbox): b1 = smallbox[0] < bigbox[0] b2 = smallbox[1] < bigbox[1] return b1 and b2 def main(): n = int(raw_input()) boxes = [] for i in range(0,n): l, w = raw_input().split() boxes.append((long(l), long(w))) start = time() stacks = stack_boxes_recursive(boxes) print time() - start print stacks if __name__ == '__main__': main() 

Entrada

 17 9 15 64 20 26 46 30 51 74 76 53 20 66 92 90 71 31 93 75 59 24 39 99 40 13 56 95 50 3 82 43 68 2 50 

Salida:

 33.7288980484 6 

El algoritmo resuelve un problema de 16 cajas en unos pocos segundos (1-3), un problema de 17 cajas en ~ 30 segundos. Estoy bastante seguro de que este es un tiempo exponencial. (Ya que hay un número exponencial de arreglos de stack).

Estoy bastante seguro de que hay una solución de tiempo polinomial, pero no sé qué es. Uno de los problemas es que la memoria depende de los arreglos de stack actuales, lo que significa que tiene que hacer más cálculos.

Construyamos un gráfico, donde haya un vértice para cada recuadro y un borde desde un recuadro A a un recuadro B si A puede astackrse encima de B. Este gráfico es acíclico (porque “se puede astackr encima” es una relación transitiva y una caja no puede astackrse encima de sí misma.

Ahora necesitamos encontrar la cobertura de ruta mínima de este gráfico. Es un problema estándar y se resuelve de esta manera:

  1. Construyamos un gráfico bipartito (cada vértice en el gráfico original obtiene dos “copias” en la parte izquierda y en la parte derecha). Para cada borde A->B en el gráfico original, hay un borde entre la copia izquierda de A y la copia derecha de B

  2. La respuesta es el número de cajas menos el tamaño de la coincidencia máxima en el gráfico bipartito.

El gráfico bipartito como O(n) vértices y O(n^2) bordes. Si usamos, por ejemplo, el algoritmo de Kuhn para encontrar una coincidencia, la complejidad del tiempo total es O(n^3) , donde n es el número de casillas.

Me encontré con esta pregunta recientemente también. Propongo la siguiente solución O (NlogN):

1) Mantenga una lista AllStkTops de la casilla superior de todas las stacks de cajas actuales que se están utilizando. Se inicializaría a una lista vacía.

2) Ordenar los cuadros en orden decreciente de sus longitudes. (Si las longitudes son iguales, clasifíquelas en orden creciente de amplitud (sí, no en disminución) ).

3) Comience a escoger las cajas (comenzando desde la más larga) y colóquelas en una de las stacks actuales. Para la primera caja, no habrá stacks, por lo que sería la base de la primera stack de cajas. La segunda casilla irá a la parte superior de la primera casilla o sería la base de la segunda stack. A medida que continuamos con este proceso, nos daremos cuenta de que para cualquier caja en mano, su longitud será menor o igual a la caja superior de todas las stacks. Por lo tanto, solo tenemos que preocuparnos por la amplitud. Verifique su amplitud con la parte superior de todas las stacks actuales a partir de la primera stack, y colóquela en la parte superior de la stack que tendrá i) la longitud y la anchura sean estrictamente mayores que las de la caja actual, y ii) la anchura mínima posible ( para optimalidad). Si ninguna de las stacks puede acomodar esta caja, cree una nueva stack con esta caja como base.

Tenga en cuenta que la amplitud de todas las partes superiores de la stack estaría en orden creciente, ya que solo creamos una nueva stack cuando la amplitud de la caja sea mayor que todas las tapas de la stack en ese momento. (Para el caso de cajas de igual longitud, ya las teníamos en orden creciente de amplitudes al clasificar). Por lo tanto, podemos usar un procedimiento de búsqueda binaria para encontrar un tope de stack más estrecho que tenga una amplitud suficientemente grande. Pero también deberíamos asegurarnos de que su longitud sea estrictamente más grande (y no solo igual) que la de la caja dada. Sin embargo, afirmo que la longitud de la parte superior nunca sería un problema porque
i) Las cajas se seleccionan en orden decreciente de longitudes, por lo que la longitud de la parte superior no puede ser estrictamente menor, y ii) También podría no ser igual porque ya clasificamos las cajas con longitudes iguales en orden creciente de sus anchuras, por lo que la stack que obtuvo el cuadro anterior tendría que estar hacia la izquierda de la parte superior de esta stack.

Por lo tanto, podemos usar un procedimiento de búsqueda binaria para encontrar la parte superior de la stack óptima para el cuadro actual.

Podemos repetir el procedimiento anterior hasta que coloquemos todas las cajas en las stacks. Al final, cuente el número de stacks en AllStkTops .

Esto es O (NlogN) en complejidad ya que la ordenación lleva tiempo O (NlogN), y la búsqueda binaria para cada casilla lleva tiempo O (logN).

Me encantaría responder a las preguntas y / o fallas que alguien encuentre en mi algoritmo.

¡Aclamaciones!

Esto parecía simple al principio, pero considerando las posibilidades, rápidamente resultó ser difícil. Sin embargo, he logrado implementar mi algoritmo en JS donde me siento muy seguro, además de que JS tiene especialidades, como los objetos como tipos de referencia que, en este caso en particular, me ayudaron enormemente.

Empiezo suponiendo que podemos girar las casillas para que tengan su lado más largo en el eje x. Luego, las 17 cajas proporcionadas se realizan entre 4 y 10 ms en Chrome y, como 15 a 25 ms en FF, lo que da como resultado que un total de 5 cajas en total puede contener las 17.

Además, he probado una caja de 50 cajas (cada una con dimensiones aleatorias entre 1-100). Por lo tanto, la caja de 50 cajas, dependiendo de cómo pueden caber, se resuelve entre unos increíbles 250 ~ 15000 ms tanto en Chrome como en FF. Supongo que 70 es el límite para este trabajo antes de que sea realmente aburrido.

El código aún puede ser mejorado en términos de velocidad, pero a partir de ahora esto es así. Intentaré hacer una descripción detallada del código en un día o dos una vez que tenga algo de tiempo libre.

 function insertBoxes(data){ if (data.length <= 1) return data[0] ? [data] : data; function flatMap(o){ return o.inside.length ? o.inside.reduce((p,b) => p.concat(flatMap(b).map(f => f.concat(o.id))),[]) : [[o.id]]; } function getBest(arr, r = []){ var i = arr.findIndex(a => a.every(i => !used[i])),len,tgt,bests,best; if (i === -1) return r; len = arr[i].length; tgt = arr.slice(i); bests = tgt.filter(a => a.length === len && a.every(x => !used[x])); best = bests.map((a,i) => [a.reduceRight((p,c) => p + boxes[c].x + boxes[c].y, 0), i]) .reduce((p,c) => c[0] < p[0] ? c : p,[Infinity,-1]); bests[best[1]].forEach(i => used[i] = true); r.push(bests[best[1]]); return getBest(tgt,r); } var boxes = data.map((e,i) => ({id:i, x:Math.max(e[0],e[1]), y:Math.min(e[0],e[1]), inside:[]})), used = Array(data.length).fill(false), interim = boxes.map((b,_,a) => { a.forEach(box => (bx > box.x && by > box.y) && b.inside.push(box)); return b; }) .map(b => flatMap(b)) .reduce((p,c) => p.concat(c)) .sort((a,b) => b.length-a.length); return getBest(interim).map(b => b.map(i => data[i])) .concat(insertBoxes(data.reduce((p,c,i) => used[i] ? p : (p.push(c),p) ,[]))); } var input = [[9, 15], [64, 20], [26, 46], [30, 51], [74, 76], [53, 20], [66, 92], [90, 71], [31, 93], [75, 59], [24, 39], [99, 40], [13, 56], [95, 50], [3, 82], [43, 68], [2, 50]]; result = [], ps = 0, pe = 0, ps = performance.now(); result = insertBoxes(input); pe = performance.now(); console.log("boxing", input.length, "boxes done in:", pe-ps,"msecs and all boxes fit in just", result.length,"boxes"); console.log(JSON.stringify(result));