¿Cuál es la ruta óptima para visitar Pokéstops en Pokémon ir?

Question

Bueno, tengo un divertido problema para usted, que no era adecuado para el juego stackexchange:

Pokéstops son ubicaciones de GPS con un radio determinado. Cuando usted está en la radio, usted puede obtener cierto juego de golosinas como Pokéballs. Pokéstops tienen una tasa de actualización de ca. cinco minutos, lo que significa que se puede acampar en un lugar y obtener nuevos artículos cada cinco minutos (1 por cada 5 min). Tal vez hay una segunda Pokéstop cerca, así que usted puede alternar entre los dos, caminando y obtener el doble de los elementos (2 por 5 min), pero usted todavía tiene que esperar algunos minutos. Por lo tanto, ahora que usted está corriendo o montando en bicicleta y, posiblemente, podría llegar a más Pokéstops en el tiempo. Pero ¿cómo va tu dependiente de la velocidad de la ruta para maximizar su Pokéstops golpeado por la proporción de tiempo?

Ha habido un reciente artículo (http://www.popularmechanics.com/culture/gaming/a21843/traveling-salesman-problem-pokemon-go/) en el que los matemáticos calcula una solución para el problema del viajante de comercio con Pokéstops en la ciudad. Pero esta no es la óptima en el sentido de maximizar su Pokéstops visitas por hora.

¿Cómo modelar y resolver este problema? Los puntos de bonificación si usted incorpora un parámetro de velocidad en su solución, por lo que podrían encontrar soluciones para la velocidad de marcha, la velocidad de carrera o carreras de velocidad.

Answer 1

El artículo que se refieren, no está recibiendo el máximo por minuto, que es el cálculo de la ruta más eficiente de pasar por todos los pokestops sin repetir pokestop(euler rutas o caminos hamiltonianos no recuerdo)

Para tu pregunta, quiero seleccionar la parte del mapa con la mayoría de los pokestops y dibujar un círculo en el cual la circunferencia de la ruta es de 5 min de caminar o montar a caballo. así que usted tiene una enorme área cubierta. Así que empieza y cuando llegan a un mismo punto todos los pokestops se pone y vuelve a empezar

Answer 2

Digamos que usted tiene este gráfico como el conjunto de nodos de $PS_{i}$ accesible Pokestops:

Cada arista tiene un factor de costo $\alpha_{j}$ en minutos o segundos. $\alpha_{j}$ es dependiendo de tus personajes de velocidad. Por simplicidad, la auto-conexión de los bordes de $PS_{i}$ tiene un $\alpha_{j}$ de 5. Porque de 5 minutos el tiempo de espera y el resto de los valores son elegidos al azar para fines de demostración.

Crear una matriz de adyacencia para la gráfica asociada con el $\alpha_{j}$.

Después de que usted puede modelar el problema (el problema del transporte) como un modelo de programación lineal y utilizar el algoritmo del simplex para resolver. En este caso, $x_{1}$ se refiere a la primera entrada en la tabla y $x_{9}$ a la última. También es importante que $x_{i}$ es un número entero.

$$Minimize\ 5x_{1}+2x_{2}+x_{3}+2x_{4}+5x_{5}+3x_{6}+x_{7}+3x_{8}+5x_{9} $$ $$subject\ to\\ x_{1}+x_{2}+x_{3}=1$$ $$x_{4}+x_{5}+x_{6}=1$$ $$x_{7}+x_{8}+x_{9}=1$$ $$x_{1}+x_{4}+x_{7}=1$$ $$x_{2}+x_{5}+x_{8}=1$$ $$x_{3}+x_{6}+x_{9}=1$$

Usted puede refinar este modelo, pero esta un método básico para resolver tal problema. Si usted necesita alternativas como correr o caminar, se puede agregar mediante la ampliación de la función objetivo y las restricciones adicionales.

En general, este enfoque es el de visitar todas las tiendas en un período de tiempo determinado con el mínimo coste y esfuerzo.