10 votos

Supervivencia Zombie: ¿Cuál es la forma óptima para colocar siete entidades en una red infinita para reducir el número de pares adyacentes?

Estoy diseñando un zombie supervivencia tipo de escenario en una mesa de juego de rol. Mi sistema es el que va a trabajar de tal manera que los jugadores toman el daño en el inicio de su gira en base a cuántas plazas adyacentes en la batalla de la cuadrícula están llenos de zombies. Quiero a determinar la mejor formación para un grupo de 7 jugadores que se perfilan para ocupar la menor cantidad de daños.

Suponiendo que no hay paredes u otros terrenos en el mapa, por lo que una infinita red de zombies (Z), ¿cuál es la forma óptima a la posición 7 jugadores (numeradas) para reducir el número de pares adyacentes con respecto a cada jugador? Tenga en cuenta que la diagonal de plazas se consideran adyacentes.

Ejemplo:

zombie grid

En la anterior formación, podemos observar lo siguiente:

Player 1:  5 Adjacent zombies
Player 2:  4 Adjacent zombies
Player 3:  5 Adjacent zombies
Player 4:  4 Adjacent zombies
Player 5:  6 Adjacent zombies
Player 6:  6 Adjacent zombies
Player 7:  6 Adjacent zombies

Total   : 36 Adjacent zombies

¿Cuál es el mínimo número posible de total adyacentes zombies, y lo que es una formación que logra este número? Existen múltiples configuraciones óptimas?

Los Puntos de bonificación: ¿hay un genérico para resolver este problema para un número variable de jugadores en caso de que alguien no se presenta?

6voto

Vincent Puntos 5027

Para un pequeño número de jugadores, podemos encontrar un mínimo de configuraciones de la mano. Aquí están algunos ($n$ es el número de jugadores, $z$ es el total de zombie contar, y los números en los diagramas que se muestran de cada jugador individual zombie count):

n=1, z=8: 8

n=2, z=14: 7 7

n=3, z=18: 6
           6 6

n=4, z=20: 5 5
           5 5

             5
n=5, z=24: 5 4 5  or  5 4 
             5        5 4 6

n=6, z=26: 5 3 5
           5 3 5

           5 4        5 4
n=7, z=28: 3 2 5  or  4 2 4
           5 4          4 5

Creo que estas son las únicas configuraciones mínimas de seguridad para la reflexión y la rotación.

En el otro extremo de la escala, podemos ver lo que sucede cuando las $n$ se hace muy grande. En el límite, podemos ignorar la esquina efectos, lo que simplifica el análisis. Supongamos que organizar a los jugadores en un cuadrado de $a \times a$ red, por lo que el $n = a^2$ $-$ ignorar los efectos de la esquina $-$ $z = 12a$ (porque cada borde jugador tiene un individuo zombie conteo de $3$). Así tenemos, por un cuadrado de la cuadrícula en el límite: $$n=\frac{z^2}{144}$$

Now let's try to round off the corners, by constructing an octagon like this:

      x x x x x x
    x x x x x x x x
  x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
  x x x x x x x x x x
    x x x x x x x x
      x x x x x x

where the horizontal and vertical edges contain $un$ players, and the diagonal edges contain $b$ players. In the diagram, $=6$ and $b=4$ (this double-counts the corners, but we don't care about corner effects here because we are interested in the limiting behaviour as $n$ becomes large). All players on an edge have individual zombie counts of $3$, but players in the second rank of a diagonal edge have a zombie count of $1$. Así, obtenemos: $$z = 12a+16b$$ $$n = a^2 + 4ab + 2b^2$$ Supongamos $z$ fijo. Entonces la primera ecuación nos da $b$ en términos de $a$, que se sustituye en la segunda ecuación para dar una ecuación de segundo grado en $a$. A continuación, podemos encontrar el máximo valor de $n$ mediante el establecimiento de la derivada a $0$. Si usted hace el álgebra, consigue, sorprendentemente: $$a = b = \frac{z}{28}$$

(Me sorprendió, de todos modos.) Así tenemos, para una óptima octágono en el límite: $$n=\frac{z^2}{112}$$

This is significantly better than a square.

Note that, although $un$ and $b$ are equal, this is not a regular octagon $-$ for that, we would need $a=b\sqrt 2$. The reason that a regular octagon is not best is that diagonals cost fewer zombies per Euclidean unit distance ($2\sqrt 2$) than horizontals and verticals ($3$). So it seems clear that the limiting shape is not a circle.

Edited to add: The zombie cost per unit distance along the edge depends on the slope $\delta$ de la siguiente manera: $$\frac{3|\delta|+1}{\sqrt{1+\delta^2}} \text{ if } |\delta| \ge 1$$ $$\frac{|\delta|+3}{\sqrt{1+\delta^2}} \text{ if } |\delta| \le 1$$

Quizás mejor cerebros que yo pueda trabajar fuera de la limitación óptima forma de este.

1voto

Martin Gordon Puntos 19587

Si deseamos maximizar la zona dado el perímetro de la figura óptima es un círculo.

En el caso discreto que tienes que hacer una enumeración completa de todas las posiciones posibles, pero la forma óptima será cerca de un "círculo".

Supongo que en el caso de 7 jugadores sería algo como

ooooo
ooxoo
oxxxo
oxxxo
ooooo

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X