Cortar palos iguales de palos diferentes

10

Tienes palos de longitudes arbitrarias, no necesariamente integrales.n

Al cortar algunos palos (un corte corta un palo, pero podemos cortar con la frecuencia que queramos), desea obtener palos de manera que:k<n

  • Todos estos palos tienen la misma longitud;k
  • Todos los palos son al menos tan largos como todos los demás palos.k

Tenga en cuenta que obtenemos palos después de realizar cortes enCn+CC

¿Qué algoritmo usarías para que el número de cortes necesarios sea mínimo? ¿Y cuál es ese número?

Como ejemplo, tome y cualquier . Se puede usar el siguiente algoritmo:n 2k=2n2

  • Ordene los palos por orden descendente de longitud tal que .L1L2Ln
  • Si , corte el palo # 1 en dos piezas iguales. Ahora hay dos palos de longitud , que son al menos tan largos como los palos restantes .L 1 / 2 2 ... nL12L2L1/22n
  • De lo contrario ( ), corte palo # 1 a dos piezas desiguales de tamaños y . Ahora hay dos palos de longitud , que es más larga que y los otros palos .L 2 L 1 - L 2 L 2 L 1 - L 2 3 nL1<2L2L2L1L2L2L1L23n

En ambos casos, un solo corte es suficiente.

Traté de generalizar esto a más grande , pero parece que hay muchos casos a considerar. ¿Puedes encontrar una solución elegante?k

Erel Segal-Halevi
fuente

Respuestas:

6

La primera observación central para resolver este problema es que la viabilidad de una longitud de corte ,l

,Feasible(l)=[i=1nLilk]

es constante a trozos, continuo a la izquierda y no aumenta en . Dado que el número de cortes necesarios se comporta de manera similar, encontrar la longitud óptima es solol

l=max{lFeasible(l)}

Además, como las otras respuestas han propuesto, todas las discontinuidades de salto tienen la forma . Esto nos deja con un problema discreto de búsqueda unidimensional susceptible de búsqueda binaria (después de clasificar un conjunto finito de candidatos).Li/j

Tenga en cuenta además que solo tenemos que considerar los que son más cortos que el grande, ya que ese siempre es factible. kLyok

Entonces, diferentes límites en conducen a algoritmos de diferente eficiencia.j

  • k1jk da como resultado un espacio de búsqueda de tamaño cuadrático (en ),k
  • L i1jk/ /yo en (suponiendo que se ordenan por tamaño decreciente), yLyo
  • límites ligeramente más involucrados en uno lineal.

Con esto, podemos resolver el problema propuesto en tiempo y espacio .Θ ( n + k )Θ(norte+kIniciar sesiónk)Θ(norte+k)

Una observación adicional es que la suma en crece en por para cada candidato "aprobado", contando los duplicados. Con esto, podemos usar la selección de rango en lugar de la búsqueda binaria y obtener un algoritmo que se ejecuta en tiempo y espacio , que es óptimo. l 1 L i / j Θ ( n )Fmiunsyosilmil1Lyo/ /jΘ(norte)

Encuentre los detalles en nuestro artículo Algoritmos eficientes para la división de bastones sin envidia con cortes de Fewest (por Reitzig y Wild, 2015).

Rafael
fuente
Como resultado, las ideas de nuestro enfoque para cortar palos se trasladan al problema más general o al reparto (proporcional) , un problema de relevancia práctica; Vea nuestro breve artículo sobre eso .
Raphael
4

Como sugirió @randomA, procederemos en dos fases: primero encontramos el conjunto de palos que se cortarán y luego minimizamos el número de cortes.

Como en el caso especial de la pregunta, clasificamos / nombramos los palos para que . Esto lleva tiempo O ( n log n ) .L1L2LnorteO(norteIniciar sesiónnorte)

Como señaló @ user1990169, nunca tenemos que cortar una pieza .yok

En la primera fase, empleamos una búsqueda binaria para encontrar el número , 1 s k , de modo que los palos 1 , ... , s puedan cortarse en al menos k piezas de tamaño L s (más algunas piezas más pequeñas), pero los palos 1 , ... , s - 1 no se pueden cortar en k piezas de tamaño L s - 1 . Esto llevará tiempo O ( k log k ) .s1sk1,...,skLs1,...,s-1kLs-1O(kIniciar sesiónk)

Si , este valor es el tamaño óptimo y podemos omitir la fase dos.Ls-1=Ls

De lo contrario, sabemos que el tamaño óptimo satisface L s - 1 > o L s y si o > L s entonces o resulta de cortar al menos uno de los palos en piezas de igual tamaño. La fase dos determinará o :oLs-1>oLso>Lsoo

Para cada palo , 1 i s , determinar un conjunto de tamaños candidatos como sigue: Si el corte en trozos de tamaño L s vueltas el palo en r i piezas (incluyendo el más corto, en su caso), entonces el candidatos para este palo son todos los valores L iyo1yosLsryo , dondejriyLiLyojjryo. (Consultela respuesta de @ user1990169 para saberpor qué estos son los únicos tamaños candidatos).Lyoj<Ls-1

Mantenga para cada tamaño de candidato, con qué frecuencia ocurrió. Usando un árbol de búsqueda equilibrado, esto se puede hacer en , ya que el número total de tamaños candidatos está limitado por i r i2 k .O(kIniciar sesiónk)yoryo2k

Ahora, el tamaño del candidato que se produjo con mayor frecuencia y conduce a un corte válido es el que nos da la solución óptima. Además, si cualquier tamaño candidato conduce a un corte válido, cualquier tamaño más pequeño también conducirá a un corte válido.

Entonces podemos emplear nuevamente la búsqueda binaria para encontrar la longitud de candidato más grande que conduzca a un corte válido en . Luego iteramos sobre el conjunto de longitudes de candidatos hasta este umbral y encontramos el que tiene la mayor multitud entre ellos en O ( k ) .O(kIniciar sesiónk)O(k)

En total, obtenemos un tiempo de ejecución en , u O ( k log k ) , si ignoramos (o no tenemos que hacer) la ordenación inicial.O(norteIniciar sesiónnorte)O(kIniciar sesiónk)

FrankW
fuente
En el paso de búsqueda binaria, ¿cómo se verifica exactamente si "los palos se pueden cortar en al menos k piezas de tamaño L s "? 1,...,skLs
Erel Segal-Halevi
Para calcule L i / L s . La suma de estos valores es la cantidad de piezas que puede obtener. 1yosLyo/ /Ls
FrankW
"El tamaño del candidato que ocurrió con mayor frecuencia ... es el que nos da la solución óptima" - ¿por qué?
Erel Segal-Halevi
Cada vez que ocurre, tenemos un palo que da piezas con t - 1 cortes. tt-1
FrankW
1
El número total de cortes es en el mejor de los casos (kk2 palos de igual longitud, todos los demás palos como máximo la mitad de estos y, por lo que puedo ver, nunca serán más quek-1. (Definitivamente nunca será más dek, ya que cada corte produce un palo de la longitud correcta y un resto. Pero parece que siempre podemos elegir un tamaño para que al menos un corte deje un resto de la longitud correcta. Sin embargo, no tengo una prueba para eso.)k2k-1k
FrankW
1

Después de haber ordenado a los palos con el fin de sus longitudes descendente, a continuación, un palo será cortada solamente si todos los palos L 1 , L 2 , . . . L i - 1 han sido cortados.LyoL1,L2,...Lyo-1

Ahora, dado que , no haremos ningún corte en los palos L k en adelante, ya que siempre podemos tener k palos con una longitud L k .k<norteLkkLk

Entonces, en lugar de , estamos tratando con solo k - 1 palos (posiblemente agregando el k -th palo como un todo), y el número máximo de cortes que se requerirán en el peor de los casos = k - 1 .nortek-1k=k-1

Además, si el número óptimo de cortes es , entonces habrá al menos un juego de palos entre esos palos k - 1 que se tomarán como un todo de 1 palo original<k-1k-1 (ya sea en partes o en 1 pieza) , es decir, ninguna parte de ese palo original se dejará 'sin tomar'. Esto se debe a que, según el principio del agujero de paloma , habrá al menos 1 corte que deberá producir más de 1 palo válido.

Luego puede realizar dos bucles anidados (ambos hasta ). El bucle externo indicará el número de palo i cuyas partes deben tomarse y el bucle interno indicará el número de partes j hechas de ese palo. Para cada talla L ikyoj
verifique si puede obtener palos k factibles cortando palosL1 enadelante secuencialmente y, si puede, actualice los cortes mínimos requeridos hasta ahora si el número requerido actual es menor.LyojL1

La complejidad total del algoritmo anterior es O(nortelosol(norte)+k3)

Abhishek Bansal
fuente
1

La idea de alto nivel sería la búsqueda binaria.

El tamaño de cada uno de los k sticks solicitados será al menos el más pequeño y, como máximo, el más grande. Debido a esto, procedemos mediante la búsqueda binaria en el tamaño del stick central, veamos qué número podemos obtener, si este k es mayor que el k dado, entonces sabemos que necesitamos elegir un nuevo tamaño de candidato de referencia. Entonces nos movemos al más grande o más pequeño usando un nuevo stick de referencia. Nos detenemos cuando k es menor que kkkkkk

Una vez que hayamos encontrado el palo de referencia apropiado, hay un caso de esquina donde necesitaríamos refinar aún más el tamaño. Podemos ordenar todos los palos cortados por el número de cortes en ellos y el tamaño del palo. Elija el que tenga el menor número de cortes y el menor tamaño. Reduzca el número de cortes en este palo en 1 y haga todos los subgrupos de este tamaño. Este será el nuevo tamaño de referencia, verifique si este nuevo tamaño puede conducir a una aceptable . Lo admito, no sé cómo limitar el tiempo de ejecución en este caso.k

Con suerte, puedo ver algo útil de otras respuestas.

InformadoA
fuente
2
Creo que la idea básica de su enfoque funcionará. Pero su descripción del algoritmo no es lo suficientemente clara como para estar seguro. ¿Podría agregar un pseudocódigo más detallado?
FrankW
@FrankW Sin embargo, no estoy muy seguro sobre el tiempo de ejecución. Veré lo que otras personas tienen, esta es una pregunta bastante interesante.
InformadoA