Matemáticas de la Hechicería - la Fórmula para la selección de los mejores hechizos

Question

Imaginemos que tenemos un asistente que sabe un par de hechizos. Cada hechizo tiene 3 atributos: Daño, tiempo de reutilización de tiempo, y un tiempo de lanzamiento.

Tiempo de reutilización: la cantidad de tiempo (t) que tarda antes de ser capaz de lanzar ese hechizo de nuevo. Un hechizo pasa de "enfriamiento" en el momento en que comienza a lanzar.

Tiempo de lanzamiento: la cantidad de tiempo (t) que se necesita para usar un hechizo. Mientras que el asistente está echando algo de otro hechizo puede ser lanzado y no puede ser cancelado.

La pregunta es: ¿Cómo maximizar el daño dado diferentes conjuntos de hechizos?

Es fácil calcular el mayor daño por el tiempo de lanzamiento. Pero, ¿qué ocurre en situaciones en las que es mejor esperar entonces para conseguir la "pegada" de fundición de baja hechizo de daño cuando un mucho mayor que uno está disponible:

Por ejemplo,

1) 100 de daño, de lanzamiento de 1 segundo tiempo, a los 10 segundos de enfriamiento.

2) 10 daños, 4 en la segunda el tiempo de lanzamiento, 0 de segunda enfriar.

Así que, en este caso, usted tendría elenco de #1, #2, esperar. Cast #1

Answer 1

Vale la pena señalar que, en situaciones extremas de casos especiales, este problema se redujera a la Mochila Problema, que es NP-completo para resolver exactamente. Para ver esto, suponga que hay un hechizo, en adelante denominado el Megaspell, que hace un muy, muy gran cantidad de daño, tiene cero el tiempo de lanzamiento, y tiene algo de positivo el tiempo de reutilización de $n$. Si todos los otros hechizos de hacer mucho menos daño que el Megaspell, es evidente que será óptimo para lanzar el Megaspell cada $n$ segundos y, a continuación, optimizar el tiempo de reutilización con el más débil de los hechizos.

Ahora, suponga que todos los otros hechizos también tiene tiempo de reutilización de $n$. Si uno se optimiza un determinado $n$-segundo tiempo de inactividad con estos hechizos, entonces el mismo hechizo-secuencia también será posible en los próximos $n$-segundo tiempo de inactividad, por lo que podemos suponer que la solución es de $n$-periódico.

El problema se reduce entonces a la optimización de la $n$ disponible segundos con el menor de los hechizos, cada uno de los cuales sólo pueden ser emitidos una vez. Si se reemplaza el tiempo de lanzamiento con el 'peso' y los daños con 'valor', uno recupera la Mochila Problema para el peso máximo n.

Answer 2

No tengo una respuesta, pero sólo quiero señalar que el algoritmo voraz falla. Es decir, si elegimos a emitir, en cualquier momento, el hechizo que maximiza $\frac{ \text{daños} }{ \text{tiempo de lanzamiento} }$, que en realidad no maximizar nuestro daño de salida porque de tiempo de reutilización. Considere la posibilidad de que el par de hechizos $(300, 5, 12)$ y $(50, 3, 0)$ (donde los tres números son los daños, el tiempo de lanzamiento en el segundo de los tiempos, y el tiempo de reutilización de tiempo en segundos): el algoritmo voraz sugiere la fundición de horario

• Hechizo 1 ($300$ daño $5$ segundos),
• Hechizo 2 ($50$ daño $3$ segundos),
• Hechizo 2 ($50$ daño $3$ segundos),
• Hechizo 2 ($50$ daño $3$ segundos),
• Repita

lo que da alrededor de $32.1$ daño por segundo. Sin embargo, la fundición de horario

• Hechizo 1 ($300$ daño $5$ segundos),
• Hechizo 2 ($50$ daño $3$ segundos),
• Hechizo 2 ($50$ daño $3$ segundos),
• Esperar $1$ segundo,
• Repita

da alrededor de $33.3$ daño por segundo. Así, una correcta algoritmo debe tomar en cuenta que los hechizos están a punto de finalizar el enfriamiento.

Answer 3

Cómo acerca de este algoritmo? En cada momento de su decisión es que hechizo para lanzar siguiente. Habiendo decidido, si el tiempo de enfriamiento para que uno ha caducado, a continuación, seguir adelante y lo echó. Si no, espere hasta que haya expirado, luego lanzarlo. Para tomar la decisión, el rango de los hechizos de daño/tiempo donde el tiempo es a partir de ahora hasta su finalización (incluyendo cualquier tiempo de enfriamiento de la izquierda). Y luego ver si puede encajar en una de las otras hechizo sin retrasar el mejor. Tomando Qiochu ejemplo, en el inicio de hechizo 1 es 300/5=60 presa/seg y la ortografía de los 2 es 50/3=16.7 presa/seg. Teniendo hechizo 1, es ahora 300/17=17.6 presa/seg, todavía mejor que la 2. Pero podemos obtener 2 realiza dos veces antes de 1 está disponible, así que se debería hacer. La cuestión sería si se puede cambiar los parámetros de modo que debe utilizar el más débil hechizo aunque se demora el fuerte por sólo un poco.

Answer 4

Vamos a plantearlo de otra forma: ¿cuál es el máximo daño que puedo causar, por ejemplo, en 100 segundos? Las limitaciones que luego se convierte en:

1. No se puede gastar más de 100 segundos de fundición
2. No pueden lanzar un único hechizo más de $\frac{100}{mon\ + cool\ hora}$ veces

Deje de $n_i$ ser el número de veces que me hechizo yo. Quiero maximizar $\sum_i n_i damage_i$ sujetos $\sum_i n_i cast_i < 100$ y cada $n_i(cast_i + cool_i) < 100$.

Este puede ser reescrito para un problema de programación lineal de la siguiente manera:

1. La primera restricción es de $[cast_0 \dots cast_m] [n_0 \dots n_m]^T<100$
2. Las demás restricciones son $[0 \dots (cast_i + cool_i) \dots 0] [n_0 \dots n_m]^T < 100$

EDIT: Mi hipótesis

1. Usted no puede lanzar dos hechizos al mismo tiempo. Restricción #1 asegura que esto es verdad.
2. Usted sólo puede lanzar un hechizo una vez cada $elenco + cool$ período. Restricción #2 asegura que esto es verdad. (Nota que esto no digo que usted no puede emitir un diferente hechizo en este período; sólo que no se puede lanzar el mismo hechizo en este período.)

Answer 5

Yo era capaz de solucionar el problema con un algoritmo de computadora, pero todavía no estoy seguro de cómo se puede hacer matemáticamente. Se señaló por @Greg Muller que el problema de la mochila es aplicable, pero no tengo la matemática destreza para aplicarlo. Si alguien pudiera mostrar cómo se puede hacer por favor.

Compartiré mi lógica aquí, espero que le sea útil a alguien por ahí.

El primer paso es determinar el hechizo con la mayoría de los daños por el tiempo de lanzamiento.

Este hechizo se convierte en la "línea de base" hechizo ya que le garantizan el más alto de daño por segundo. Lo que significa, que siempre debe lanzar este hechizo si las 2 condiciones siguientes se cumplen: 1) La línea de base del hechizo está disponible (no en tiempo de reutilización). 2) Usted no es actualmente un hechizo.

Por lo que se convierte en una materia de relleno en otros hechizos, mientras que la línea de base del hechizo es el tiempo de reutilización. Entre (el tiempo de lanzamiento) y (tiempo de reutilización - tiempo de lanzamiento). Sin embargo, algún grado de superposición, puede ocurrir (regla 2 anterior es falso).

Entonces se convierte en una cuestión de recursing a través de todos los no-línea de base de los hechizos para encontrar todas las secuencias de los hechizos que no violan las 2 reglas.

Para los hechizos que se sobreponen debe sancionar a los posibles daños de la línea de base del hechizo podría haber hecho (hasta su daño máximo).

Tomemos, por ejemplo, 2 hechizos

1: 300 de daño, 3s tiempo de lanzamiento, 10s de tiempo de reutilización

2: 290 daño, 3s tiempo de lanzamiento, 3s tiempo de reutilización

El mayor daño proviene de la secuencia 1 - 2 - 2 - 2. Lo que provoca una superposición de 2 segundos en un potencial #1 de fundición. Sin embargo, esto es beneficioso, ya que si no emitir el tercer hechizo (es decir. 1 - 2 - 2) que va a hacer 880 daño con 1 segundo de sobra. Si lanzas el extra #2 hechizo que va a hacer 1170 - 2 segundo #1, que es de 200. Así 970 daño es su pariente daño.

Este algoritmo es significativamente más rápido que otros algoritmos que buscar secuencias que coinciden con un objetivo final: es decir. límite de tiempo o daño.