búsqueda del camino: cálculo del camino óptimo, entendiendo por "óptimo" la distancia máxima en un tiempo determinado

Question

No estoy seguro de si este es el lugar adecuado para preguntar esto, pero aquí está mi problema:

Tengo un gran conjunto de puntos, donde cada punto representa una coordenada. Necesito desarrollar un algoritmo que calcule qué puntos visitar para maximizar la distancia total recorrida en un determinado lapso de tiempo (por ejemplo, 24 horas). Para cada camino entre dos puntos conozco la distancia y la velocidad máxima.

Además, hay una restricción. Cada camino sólo puede recorrerse dos veces (así, arriba y abajo es posible, pero entonces ambos puntos no pueden volver a utilizarse).

Mi problema es que no sé por dónde empezar. He mirado algunos algoritmos de búsqueda de rutas (por ejemplo, el de Dijkstra), pero todos ellos buscan la menor distancia, ¡mientras que yo necesito encontrar la máxima distancia!

Gracias de antemano.

Answer 1

Creo que el siguiente enfoque debería llevarte a alguna parte: (Se parece al algoritmo de Kruskal)

1. Para cada arista, calcula la velocidad.
2. Ordena los bordes por velocidad.
3. Sigue añadiendo la arista más rápida al gráfico.
4. Cuando el tiempo total de todos los bordes añadidos alcanza la mitad del límite, $\frac T2$ Para.
5. Si el gráfico resultante es conexo, esto es lo mejor que se puede conseguir. Como puedes recorrer cada arista dos veces, es fácil visitar todas las aristas dos veces. Simplemente empieza en algún sitio y camina como un patrón de "búsqueda profunda", es decir, avanza sobre las aristas no visitadas cuando puedas, y retrocede en caso contrario.
   Si hay una arista (o varias aristas) conectada a tu grafo que aún pueda ser visitada dentro de la restricción de tiempo, empieza por ahí.
6. Si el grafo resultante no está conectado, continúe añadiendo aristas hasta que uno de los componentes tenga un tiempo total de $\frac T2$ . Esto puede no ser óptimo cuando es mejor pasar de un componente a otro por un pequeño borde ineficiente, pero no tengo una solución para eso.