Puzzle de optimización

Question

Se le da un gran número de bloques de LEGO de tamaño 1. Usted puede construir bloques de otros tamaños, utilizando bloques más pequeños. Por ejemplo, usted puede construir un bloque de tamaño 2 con dos de tamaño de los bloques 1 y, a continuación, construir un bloque de tamaño 6, con tres de tamaño de 2 cuadras. Sin embargo, no se puede mezclar bloques de diferentes tamaños para construir un bloque, ni puede utilizar una fracción de un bloque. Por ejemplo, para construir un bloque de tamaño 3, usted no puede usar un bloque de tamaño 2 y un bloque de tamaño 1, ni puede utilizar una cuadra y media de tamaño 2. Debe utilizar tres bloques de tamaño 1.

Se le pide a construir n bloques, cada uno de los cuales tiene diferente tamaño mayor que 1. Un bloque de tamaño 1 costos de \$1. Once you build a block of a larger size, using one costs only \$1, independientemente de su tamaño. Por ejemplo, los costos de los 1 * 5 = \$5 to build a block of size 5 using five blocks of size 1. Now that you have a block of size 5, you can use them to build even a larger block, say a block of size 10, using two of these for a cost of 2 * 1 = \$2.

La cuestión es encontrar un algorithem la construcción de todos estos n bloques con la menor cantidad de dinero.

Ejemplo 1: Usted le pide a construir un bloque de tamaño 7 y un bloque de tamaño 10.

Solución: Construir un bloque de tamaño 7 el uso de siete bloques de tamaño 1 \$7. Build a block of size 5 using five of size-1 blocks for \$5 y construir un tamaño de 10 bloque con dos de estos para \$2. The total cost will be 7 + 5 + 2 = \$14.

Ejemplo 2: Usted le pide a construir un bloque de tamaño 10 y un bloque de tamaño 20.

Solución: Primero, construir un bloque de tamaño 5 con cinco bloques de tamaño 1 \$5. Then use two of size 5 blocks to build a block of size 10 for \$2 y el uso de dos de tamaño 10 bloques para construir un bloque de tamaño 20 por un costo total de 5 + 2 + 2 = \$9, which is much cheaper than building each with size-1 blocks that would cost 10 + 20 = \$30.

Ejemplo 3: a Usted se le pide a construir un bloque de tamaño 6, a una cuadra de la talla 40, un bloque de tamaño 60.

Solución: Construir un tamaño de 3 bloque con tres bloques de tamaño 1 para un costo de \$3 and build a block of size 6 with two of these for \$2. Construir un bloque de tamaño 4 \$4 and use five of these to build a size-20 block for \$5. Por último, el uso de dos de un tamaño de 20 bloque para construir un tamaño de 40 bloque y tres para construir un tamaño de 60 bloque de \$2 and \$3, respectivamente. El costo total será de 3 + 2 + 4 + 5 + 2 + 3 = \$19.

Answer 1

Como Patrick87 señala, $\forall m,n\ge 2 : mn \ge m+n$, por lo que siempre se desea construir el uso de factores primos.

Indicar el destino de los tamaños de bloque como $\{t_i\}$. Podemos expresar los costos de construcción como un grafo dirigido con vértices correspondientes a $\mathbb{Z}^+$ y los bordes $n\to pn$ peso $p$ todos los $n$ y todos prime $p$. La tarea es encontrar el conectado subgrafo que contiene $\{t_i\} \cup \{1\}$ que tiene menos peso total.

Podemos hacer las siguientes observaciones:

1. Si sólo hay un objetivo, $n$, la solución óptima es $\text{sopfr}(n)$ donde sopfr (A001414) es la suma de los factores primos con la repetición. De hecho, podemos reclamar un mayor propiedad: cualquier camino de $1$ $n$tienen peso total $\text{sopfr}(n)$, que sólo difieren en el orden de los números primos.

2. Si los objetivos se pueden dividir en $\{a_j\}, \{b_k\}$ tal que $\forall j,k : \gcd(a_j, b_k) = 1$, entonces el problema puede dividirse en subproblemas independientes para la $\{a_j\}$$\{b_k\}$. Prueba: si un vértice distinto de $1$ está incluido en el óptimo subgrafo de la $\{a_j\}$, entonces no es un factor de cualquiera de las $\{b_k\}$, y por tanto, se encontraban en el óptimo subgrafo de la $\{b_k\}$ podría ser eliminado, contradiciendo la optimalidad.

3. Si hay un común divisor $d$ de todas las $\{t_i\}$, entonces podemos reducir el problema con los objetivos de $\left\{\frac{t_i}{d}\right\}$ y añadir $\text{sopfr}(d)$ para obtener una solución óptima. Como Ross Millikan observa, esto es obvio; es fácil demostrar, cuando sólo hay dos objetivos, y cuando hay más yo creo que una prueba por contradicción es posible, aunque no muy elegante.

Esto ya es una solución completa para $|\{t_i\}| \le 2$.

En la no-trivial caso con tres objetivos deben ser descomponible como $axy, bxz, cyz$ donde$x,y,z>1$$\gcd(ay,bz) = \gcd(ax,cz) = \gcd(bx, cy) = 1$. A continuación, supongamos que wlog que construimos el primer MCD de a pares, $x$. Esto conduce a un costo total $$\begin{eqnarray}C & = & \text{sopfr}(x) + \text{sopfr}(ay) + \text{sopfr}(bz) + \text{sopfr}(cyz) \\ & = & \text{sopfr}(x) + 2\text{sopfr}(y) + 2\text{sopfr}(z) + \text{sopfr}(a) + \text{sopfr}(b) + \text{sopfr}(c) \end{eqnarray}$$ Por lo tanto es óptimo para la construcción de los pares de MCD con la mayor sopfr en este caso. (NB no necesariamente los más grandes pares MCD - considerar la posibilidad de $\text{sopfr}(8) = 6 < \text{sopfr}(7)$).

Si sólo necesita un mejor de lo trivial de la aproximación de la siguiente codiciosos estrategia es mejor que nada:

1. Aplicar las tres observaciones anteriores, si procede.
2. De lo contrario, encontrar el par de dianas $t_j$ $t_k$ con el MCD de a pares con mayor sopfr, $d$; resolver los objetivos de $\{t_i | i\ne j \wedge i\ne k\} \cup \{d\}$; y agregar $\text{sopfr}\left(\frac{t_j}{d}\right) + \text{sopfr}\left(\frac{t_k}{d}\right)$.

Pero hay una reducción desde el vértice de la cubierta, lo que demuestra que el problema es NP-completo, así que no se mantenga mucho la esperanza de un manejable solución general.

---

Con el crédito para user946850 para la idea clave:

Esbozamos el argumento de que el problema es NP-completo por la reducción de desde el vértice de la cubierta problema. Dado que la NP es formalmente una clase de problemas de decisión, debemos repetir el problema en una decisión de la forma:

Objetivo determinado tamaños de bloque de $\{t_i\}$ y un objetivo de costos $T$, es posible construir todos los tamaños de destino con los costes totales no exceda el $T$?

El vértice de la cubierta problema se expresa como:

Dado un no-grafo dirigido $G = (V, E)$ y un objetivo de cubrir el tamaño de la $k$ ¿existe un subconjunto $S \subseteq V$ tal que $|S| \le k$$\forall (v_i, v_j)\in E : v_i \in C \vee v_j \in C$?

Podemos suponer wlog que la gráfica está conectado, por lo que (abusando de la notación, permitiendo que la pone en un contexto escalar a ser interpretado como sus tamaños) $E = \Omega(V)$$E = O(V^2)$.

La estrategia de reducción de la tomamos es el mapa cada una de las $v_i \in V$ a distintas prime $p_i$ y cada arista $(v_i, v_j) \in E$ a un objetivo de tamaño de bloque de $p_i p_j$. Entonces cualquier vértice de la cubierta $C'$ puede ser representado como la construcción de los números primos correspondientes a los vértices en $C'$ y de estos la construcción de los objetivos. El costo de la misma será la suma de $|C'| + |E|$ no distintos de los números primos extraídas de $\{p_i\}$. Si llamamos a la más pequeña de los números primos utilizado $p_{min}$ y la mayor de las $p_{max}$, se puede establecer un objetivo costo de $(k + E)p_{max}$ y es suficiente con que $(k+E+1)p_{min}$ es mayor para la respuesta dada por la reducción del problema a ser la respuesta al problema original.

Por lo tanto, tenemos que encontrar un primer $p_{min}$ tal de que no se $V$ de los números primos en el medio abierto intervalo de $[\;p_{min},\;(1+\epsilon)p_{min})$ donde $\epsilon^{-1} = k + E$. También tenemos que identificar a todas las $V$ números primos. Aquí vamos a mantener las cosas simples (de ahí el "boceto de un argumento" en lugar de "probar") por la mera utilización de la forma más simple del teorema de los números primos. Vamos a comprobar $\Theta(\epsilon\; p_{min})$ números de primalidad, y tenemos la necesidad de $V$ de aciertos, por lo que queremos $\frac{p_{min}}{\log p_{min}} = \Theta(\epsilon^{-1} V )$. Esto le dará $p_{min} = O(E^2 V^2)$ (que puede ser fortalecido a $p_{min} = O((EV)^{1+\alpha})$ cualquier $\alpha > 0$), que es polinomial en el tamaño de la entrada para el vértice de la cubierta problema, que de entrada tamaño de $\Theta(E \log V)$. El número de candidatos de los números que se debe comprobar es también exponencialmente acotado, y puesto que sus tamaños son exponencialmente delimitada y pruebas de primalidad es en P el costo total de la realización de la reducción es el polinomio.

Answer 2

Aquí es lo que creo que es un algoritmo que se debe trabajar; no es muy buena en el sentido de la complejidad computacional, pero (si es correcto) al menos tiene un punto de partida para optimizar (tal vez a través de la programación dinámica?) o hacer algo más inteligente.

El algoritmo se basa en la siguiente observación: una solución óptima es uno para el cual el costo de la construcción de la más grande de la cuadra, más el costo de todos los bloques necesarios para construir el mayor bloque y el resto de los bloques, es mínima. Además, el costo de un bloque de tamaño de 1 es 1; el costo de un bloque de tamaño $n$ si $n$ es un número primo; y el costo de un bloque de tamaño $n$ puede ser el costo de la construcción de un bloque de tamaño $a$ y replicar $b$ a veces, por cualquier $a$ $b$ tal que $ab = n$. Tenga en cuenta que, para el compuesto de números, que nunca tiene sentido para construir de todos los 1-bloques; esto es porque si $n = ab$ $n >= 4$ ni $a = 1$ ni $b = 1$, $a + b <= n$, una declaración de que yo deje sin pruebas, pero en la que me siento bastante confiado.

Dicho esto, he aquí un algoritmo candidato:

1. Si no hay ningún número que necesita ser construido, la respuesta es que los costos de cero y que no hay más trabajo necesita ser hecho, de manera que el algoritmo devuelve.
2. De lo contrario, comienza con el mayor número de $n_{0}$ usted necesita para construir. Determinar el conjunto $S_{0}$ de todos los pares ordenados $(a, b)$ tal que $n = ab$.
3. Si $|S_{0}| = 1$, $n_{0}$ es uno, y la manera más barata de construir $n_{0}$ es para uso en un solo bloque de tamaño 1; resolver el problema con este mayor número quitado, y la solución general es la solución a la subproblem además de la construcción de un solo 1 cuadra.
4. De lo contrario, si $|S_{0}| = 2$, $n_{0}$ es primo, y la manera más barata de construir $n_{0}$ es el uso de $n_{0}$ bloques de tamaño 1; resolver el problema con este mayor número quitado, y la solución general es la solución a la subproblem además de la construcción de una $n_{0}$ bloque de 1-bloques.
5. De lo contrario, si $|S_{0}| > 2$, $n_{0}$ es compuesto, y podemos construir mediante la construcción de un más barato bloque y replicarlo. Específicamente, uno de los pares ordenados en el $S_{0}$ le dará el método apropiado: la construcción de un bloque de tamaño $a$ y replicar $b$ veces. Así que, para cada par ordenado en $S_{0}$, calcula el $b$ más el costo mínimo de la resolución de la subproblem donde ya no tiene que construir $n_{0}$ pero usted debe construir $a$ lugar. Una vez que hayas hecho esto por todos los pares ordenados, simplemente seleccione un par para que un costo mínimo fue devuelto; la solución al problema es este costo (si desea que el método de construcción, tanto de la tienda como está la solución de subproblemas correspondiente a cada par ordenado, o una vez a un costo mínimo es determinado, volver a resolver el subproblem correspondiente a un par de costo mínimo, e imprimir los seris de decisiones).