Variación del Problema del Viajante de Comercio con visitas repetidas y visitas fuera de las ciudades.
Problema. Dado un grafo dirigido ponderado G(V, E), no necesariamente completo, encuentra el camino más corto pasando por cada ciudad en el conjunto de ciudades dado (un subconjunto de vértices de V), podemos repetir cada ciudad más de una vez y se nos permite visitar ciudades que no están en el conjunto de ciudades pero que están en el grafo.
Ahora, sé que hay una versión del problema del vendedor viajero (TSP) en la que se nos permite repetir la visita a los vértices internos, sin embargo, en este problema, podemos visitar los vértices de los visitantes externos.
Por ejemplo:
V = {0,1,2,...10} y E es desconocido, tenemos el conjunto de ciudades {0,1,3,8,9}
Entonces, el siguiente camino:
8 -> 9 -> 0 -> 3 -> 9 -> 7 -> 6 -> 5 -> 1
es válido y debe tenerse en cuenta en el algoritmo.
Ahora, tengo que ser capaz de hacer funcionar el algoritmo con un gran número de vértices, como 1000000, así que sé que el algoritmo debería ser avaro, pero no sé cómo abordarlo con una forma eficiente de cumplir con estos requisitos.
davy.ai
Travesía del camino más corto de un grafo dirigido ponderado con un subconjunto de ciudades
Descripción del problema
Dado un grafo dirigido ponderado G(V, E), que no necesariamente está completo. Encuentra el camino más corto que visita cada ciudad en el conjunto de ciudades dado (un subconjunto de vértices de V). La solución puede incluir visitar ciudades fuera del subconjunto de ciudades múltiples veces y no estamos limitados a la distancia cubierta en el subconjunto de ciudades.
Ejemplo
Supongamos que tenemos un Grafo dirigido ponderado G con vértices V{0, 1, 2, 3, 4, 5} y Aristas E{01, 13, 05, 14, 35, 34, 24, 45},
y tenemos un conjunto de ciudades {0, 2, 4, 5}.
Ahora queremos encontrar el camino más corto que visite todas las ciudades en el subconjunto de ciudades.
Una posible solución es {0, 1, 3, 4, 5, 2, 5, 4, 0} con una ponderación de 42.
Enfoque
Este problema es una variación del conocido problema del Viajante de Comercio (TSP). El TSP es NP-duro, lo que significa que no existe un algoritmo conocido que lo resuelva en tiempo polinomial, excepto para algunos casos especiales. Por lo tanto, no nos centraremos en la solución exacta al problema del TSP. En cambio, necesitamos desarrollar un algoritmo que nos dé una solución cercana a óptima en un tiempo razonable.
Un enfoque en particular es el algoritmo voraz, donde seguimos una heurística simple que siempre selecciona el mejor siguiente paso según algún criterio basado en el estado actual de la solución.
El algoritmo voraz
a. Seleccionar la ciudad no visitada más cercana a la ciudad actual en el subconjunto
b. Marcarla como visitada
c. Agregar su distancia a la posición actual
a. Seleccionar la ciudad no visitada más cercana a la ciudad actual en el grafo
b. Agregar su distancia a la posición actual
El algoritmo anterior funciona bien si tenemos un número pequeño de vértices. Sin embargo, a medida que aumenta el número de vértices, el rendimiento del algoritmo degrada debido a la carga computacional de calcular la matriz de distancias.
Optimizando el algoritmo
Para optimizar el algoritmo voraz, podemos aplicar las siguientes mejoras:
– Utilizar una cola de prioridad para almacenar y recuperar la ciudad más cercana en cada iteración.
– Preprocesar el grafo utilizando un algoritmo de Árbol de Expansión Mínima (MST) para filtrar los vértices inalcanzables que no están en el subconjunto pero no están conectados a ningún vértice en el subconjunto.
– Utilizar un enfoque de programación dinámica para almacenar resultados intermedios que se pueden reutilizar en iteraciones posteriores.
Con las optimizaciones anteriores, podemos recorrer grafos con conjuntos de vértices grandes de manera eficiente y, al mismo tiempo, encontrar una solución cercana a óptima para el problema.
Conclusión
Hemos descrito un enfoque para resolver el problema de travesía de grafos dirigidos ponderados. El algoritmo se basa en el método voraz y se pueden emplear varias técnicas para optimizar el rendimiento al reducir la carga computacional. La solución exacta al problema del TSP puede ser poco práctica de resolver, pero podemos lograr una solución aceptable que capture la mayoría de las características esenciales del problema.