El siguiente problema de optimización vino a mi atención como una idealización de los divertidos juegos de navegador, la Cookie Clicker, pero es representativa de una amplia gama de juegos de estrategia:
Tiene una una capacidad de producción inicial $p_0$ y un número de mejoras de $A, B, C, \ldots$ a construir en alguna secuencia que usted puede elegir. Cada mejora, $X$ tiene un costo $c_X$ y va a tomar tiempo para construir proporcional a su costo, e inversamente proporcional a su capacidad. Cuando termine va a aumentar su capacidad de producción por una determinada cantidad $p_X$. Sólo se puede construir a una mejora en un tiempo. La secuencia debe construir en el fin de conseguir todas las mejoras tan pronto como sea posible?
Para conseguir una manija en esto me puse a buscar en el caso de que sólo hay dos mejoras $A$$B$. El tiempo que nos llevará a construir $A$ primero y, a continuación,$B$$\frac{c_A}{p_0} + \frac{c_B}{p_0+p_A}$, y, mutatis mutandis, para $B$ primera. Así que usted debe elegir para construir $A$ primer fib $$ \frac{c_A}{p_0} + \frac{c_B}{p_0+p_A} < \frac{c_B}{p_0} + \frac{c_A}{p_0+p_B} $$ Después de un poco de álgebra (suponiendo que los diferentes parámetros son positivos, etc.) este resulta ser equivalente a $$ \tag{*} \frac{c_A}{p_0} + \frac{c_A}{p_A} < \frac{c_B}{p_0} + \frac{c_B}{p_B} $$ Esta condición tiene la propiedad de que todos los $A$s están en un lado de la desigualdad y de todos los $B$s están en el otro. Esto sugiere una solución para el caso de más de dos mejoras, al menos de forma heurística: Calcular $c_X/p_0 + c_X/p_X$ por cada mejora y empezar por la construcción de la $X$ con el valor más bajo. A continuación, repita el cálculo con un nuevo $p_0$.
Esta pregunta es acerca de que es la expresión $$\frac{c_X}{p_0} + \frac{c_X}{p_X} = c_X\Bigl(\frac1{p_0}+\frac1{p_X}\Bigr)$$ Es sospechosamente simple a la luz de el laberinto de álgebra que a mí. Mi pregunta es: ¿hay una forma intuitiva de entender que esta expresión es la cosa correcta para comparar?
El $c_X/p_X$ plazo es bastante fácil de entender: es el costo por unidad de productividad añadida tenemos que pagar por la construcción de $X$. Pero, ¿qué acerca de la $c_X/p_0$?
El efecto de la $c_X/p_0$ hace cualitativa sentido: En el límite de $p_0$ pequeñas, este término domina sobre el $c_X/p_X$ términos, y (*) se reduce a la comparación de $c_A<c_B$. En otras palabras, cuando tenemos muy poco de una capacidad de producción inicial lo importante es conseguir algo construido tan pronto como sea posible, y luego el otro tendrá comparativamente poco de tiempo. Por otro lado, en el límite de grandes $p_0$s, $c_X/p_0$ términos vanishe y nos quedamos con la comparación de $c_A/p_A$$c_B/p_B$. Debemos comprar la mejora que nos da la mayoría de la explosión para el buck primera. Que hace sentido intuitivo.
Pero entre esos dos límites, ¿por qué es $c_X/p_0$ el derecho de ajuste plazo? ¿Qué representa intuitivamente?
