Teleporting viajeros, Ganancia óptima durante el tiempo Problema

Question

Soy nuevo en todo el problema del vendedor ambulante, así como stackoverflow por lo que me haga saber si digo algo que no está del todo bien.

Intro:

Estoy tratando de codificar un algoritmo de múltiples intercambios de beneficio / tiempo óptimo para un juego que consiste en varias ciudades (nodos) en varios países (zonas), donde:

• El tiempo físico que se necesita para viajar entre dos ciudades conectadas es siempre la misma;
• Las ciudades no están conectados de forma lineal (que puede teletransportarse entre algunas ciudades en el mismo tiempo);
• Algunos países (áreas) tienen rutas de teletransporte que hacen que el camino más corto a través de otros países.
• El viajero (o comerciante) tiene un límite en su bolso con monedas, el peso de sus bienes, y la cantidad negociable en una determinada ruta comercial. La ruta comercial puede abarcar varias ciudades.

---

Parámetros pregunta:

Ya existe una base de datos en la memoria (Python: sqlite) que posee operaciones en función de su ciudad de origen y la ciudad de destino, las ciudades la ruta más corta entre medio como una matriz y cantidad, y el factor limitante con su% de retorno sobre el total el capital (o en el caso de que ninguno de los factores que están limitando, a continuación, sólo el método que proporciona el más alto rendimiento del capital total).

• Estoy tratando de encontrar la ganancia óptima para un determinado trozo de tiempo (es decir, 30 minutos)
• El acto de cruzar a una nueva ciudad es en realidad simultánea
• Por lo general toma la misma cantidad de tiempo definido a viajar por todo el mapa de la ciudad (es decir, 2 minutos)
• El acto de iniciar la primera o cualquier nuevo comercio lleva el mismo tiempo como cruzar una mapa de la ciudad (es decir, 2 minutos)
• Mi punto de partida no en realidad podría tener un comercio válida (I tendría que viajar a la primera / mejor / más cercano)

---

pseudo solución hasta ahora

Optimización

En primer lugar, entiendo que porque tengo un límite en el tiempo que se tarda, y sé cuánto tiempo toma cada salto (incluyendo -1 para intiating el comercio), puedo limitar la gráfica para todos los oficios cuyos saltos son menores o igual a max_hops=int(max_time/route_time) -1. Corté elementos de la base de datos comerciales que no entran dentro de este plazo, la poda de las ciudades que tienen la ruta más corta longitudes mayores de max_hops.

hago otra entrada en la base de datos incluye las operaciones que más corta caminos entre mi ciudad actual y las ciudades de partida de todas las operaciones existentes que no son de mi ciudad actual, y darles un retorno de 0%. Me gustaría limitar estos a los que el número de la ciudad de lúpulo es menor que max_hops, y también me calcular si la ciudad actual a la ciudad de partida, más que comercia la ruta más corta lúpulo se excederse max_hops y eliminar aquellas que superaron este límite.

Entonces tomo las operaciones restantes que no están (current_city->starting_city) y añadir las rutas comerciales con el retorno del 0% entre todos los destinos y ciudades de partida wheres el lúpulo no excederse max_hops

A continuación hago una última ciruela para todas las ciudades que no están en la base de datos oficios, ya sea como una ciudad de partida, ciudad de destino, o parte de las matrices de la ruta más corta de la ciudad.

Gráfico de búsqueda Me quedo con un gráfico (mucho) más pequeño de operaciones factibles dentro del límite de tiempo (es decir, 30 minutos).

Debido a que todos los nodos que están conectados son adyacentes, las conexiones son de forma predeterminada todo ponderada 1. divido el retorno% en el número de saltos en el comercio luego tomar la inversa y se suman + 1 (esto significaría un peso de 1,01 para una ruta de retorno de 100%). En el caso en que el retorno es 0%, agrego ... 2?

A continuación, debería devolver la ruta más rentable ...

---

La Pregunta:

En su mayoría,

1. ¿Cómo agrego la capacidad de tomar varias rutas cuando me queda más dinero o espacio y mantener la búsqueda de rutas a través del camino discrete a las rutas comerciales individuales? Debido a la naturaleza de los productos que se venden en múltiples precios y cantidades dentro de la ciudad, habría una gran cantidad de rutas superpuestas.

2. ¿Cómo se penalizan iniciar una nueva ruta comercial?

3. ¿Es la búsqueda gráfica incluso útil en esta situación?

En una nota lateral,

3. ¿Qué tipo de ciruelas / optimizaciones a la gráfica debería (o no debería) hacer?
4. ¿Es correcta mi método de ponderación? Tengo la sensación de que me va a dar pesos desproporcionados. ¿Debo usar el rendimiento real en lugar de porcentaje de retorno?
5. Si estoy de codificación en Python son bibliotecas tales como python-gráfico adecuado para ¿mis necesidades? ¿O me ahorrar una gran cantidad de gastos generales (como yo lo entiendo, los algoritmos de búsqueda gráfica pueden ser computacionalmente intensivas) para escribir una función especializada?
6. ¿Soy el mejor fuera mediante una búsqueda *?
7. ¿Debo calcular previamente los puntos de la ruta más corta en la base de datos del comercio y el gasto excesivo optimizaciones o debería dejarlo todo al gráfico-búsqueda?
8. ¿Puede usted darse cuenta de nada que pudiera mejorar?

Answer 1

Creo que ha definido algo que encaja en una clase de problemas llamados de inventario - problemas de enrutamiento. Asumo ya que tiene tanto de mercancías como de la moneda, el viajero es tanto para la compra y venta a lo largo de la ruta elegida. Primero vamos a suponer que todo es determinista - todas las cantidades de los bienes de la demanda, la oferta disponible, la compra y los precios de venta, etc., son conocidos de antemano. La versión estocástica se vuelve más difícil (obviamente).

Uno de los objetivos sería la de maximizar las ganancias con una restricción en el bolso y los bienes. Si el viajero tiene que volver a casa de su aspecto como un tour, si no, se ve como un camino. Ya que no han requerido al viajero a visitar cada nodo, que no es un TSP. Eso es bueno - más cortos problemas de ruta son generalmente mucho más fácil que la TSP a resolver.

Debido a las limitaciones laterales y la elección limitada de los próximos pasos en cada nodo - me gustaría considerar el uso de programación dinámica primer intento de una técnica de solución. Le ayudará a enumerar lo que comprar y vender en cada etapa y hay un número limitado de etapas. También, ya que poner un límite temporal a la decisión, que limita el espacio de estados de opciones.

Para los que sugirió el algoritmo de Djikstra - Puede que tengas razón - las convenciones de etiquetado tendrían que incluir la hora, la moneda, y los bienes y las ganancias correspondientes. Puede ser que los supuestos de Djikstra de no funcionen para esto con la complejidad añadida de lucro. no han pensado en eso todavía.

Aquí hay enlace a un problema similar en la capital presupuesto.

Buena suerte!

Answer 2

Si se trata de un juego en el que está jugando contra los humanos que supongo que el tamaño total del espacio de datos es bastante limitada. Si es así me inclinaría a tirar toda la poda elegante como dudo que vale la pena.

En su lugar, ¿qué tal una sencilla búsqueda en amplitud?

Construir una lista de todas las ciudades, marcarlos no visitado

Tome su ciudad de salida, marcar el tiempo de viaje como cero

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O (): el bucle exterior ejecuta ciudades * máximo lúpulo veces. El bucle interior se ejecuta una vez por ciudad. No son necesarias las asignaciones de memoria.

Ahora, para cada aspecto de la ciudad en lo que puede comprar aquí y vender allí. Al calcular la tasa de retorno en un comercio recordar que el crecimiento es exponencial, no lineal. Dos veces el beneficio de un comercio que lleva el doble de tiempo es no una buena oferta! Busque la forma de calcular la tasa interna de retorno.

Si la ciudad actual no tiene el comercio no se moleste con el análisis completo, sólo tiene que mirar por encima de los vecinos y ejecutar el análisis sobre ellos en su lugar, sumando uno al tiempo para cada movimiento.

Si tiene ciclos de CPU de sobra (y que bien podría hacerlo, nada significaba para un ser humano para jugar tendrá un muy pequeño espacio de datos) puede ejecutar el análisis en cada ciudad la adición en el tiempo que tarda en llegar a la ciudad.

Editar: Basado en su comentario usted tiene toneladas de capacidad de CPU disponible como el juego no se está ejecutando en la CPU. Me atengo a mi solución: Comprobar todo. Tengo la firme sospecha se necesitará más tiempo para obtener la información de ruta y el comercio de lo que será para el cálculo de la solución óptima.