Algoritmo de aproximación para la variante TSP, inicio y finalización fijos en cualquier lugar pero punto de partida + visitas múltiples en cada vértice PERMITIDO

Question

NOTA: Debido a que el viaje no termina en el mismo lugar donde comenzó y también el hecho de que cada punto puede ser visitado más de una vez, siempre y cuando aún los visite a todos, esta no es realmente una variante de TSP, pero lo expreso debido a la falta de una mejor definición del problema.

Así que ..

Supongamos que yo voy en un viaje de senderismo con n puntos de interés. Todos estos puntos están conectados por rutas de senderismo. Tengo un mapa que muestra todos los caminos con sus distancias, dándome un gráfico dirigido.

Mi problema es cómo aproximar una gira que comienza en un punto A y visita todos los n puntos de interés, mientras termina la gira en cualquier lugar excepto el punto donde comencé y quiero que la gira sea lo más corta posible.

Debido a la naturaleza de las caminatas, pensé que lamentablemente esto no sería un problema simétrico (¿o puedo convertir mi gráfico asimétrico en uno simétrico?), Ya que pasar de una altitud alta a baja es obviamente más fácil que de otra manera alrededor.

También creo que tiene que ser un algoritmo que funcione para gráficos no métricos, donde la desigualdad del triángulo no se cumple, ya que pasar de a a byc podría ser más rápido que tomar un camino muy largo y extraño que va de aa c directamente. Consideré si la desigualdad del triángulo aún se mantiene, ya que no hay restricciones con respecto a cuántas veces visito cada punto, siempre y cuando los visite todos, lo que significa que siempre elegiría el camino más corto de dos a cero y nunca Takr el camino largo y extraño.

Creo que mi problema es más fácil que TSP, por lo que esos algoritmos no se ajustan a este problema. Pensé en usar un árbol de expansión mínimo, pero me cuesta convencerme de que se pueden aplicar a un gráfico dirigido no asimétrico asimétrico.

Lo que realmente quiero son algunas sugerencias en cuanto a cómo puedo llegar a un algoritmo de aproximación que buscar un recorrido óptimo próximo a través de todos los puntos de n

Answer 1

Se puede simplificar este problema a un problema TSP normal con n + 1 vértice Para hacer esto, tome el nodo 'A' y todos los puntos de interés y calcule una ruta más corta entre cada par de estos puntos. Puede usar el algoritmo de ruta más corta para todos los pares en el gráfico original. O bien, si n es significativamente más pequeño que el tamaño del gráfico original, utilice el algoritmo de ruta más corta de fuente única para estos n + 1 vértices. También puede establecer la longitud de todas las rutas, que terminan en 'A', a alguna constante, más grande que cualquier otra ruta, lo que permite finalizar el viaje en cualquier lugar (esto puede ser necesario solo para algoritmos TSP, encontrar una ruta de ida y vuelta) .

Como resultado, obtiene un gráfico completo, que es métrico, pero sigue siendo asimétrico. Todo lo que necesita ahora es resolver un problema TSP normal en este gráfico. Si desea convertir este gráfico asimétrico en uno simétrico, Wikipedia explica cómo hacerlo.

Answer 2

Para reducir su problema a TSP asimétrico, introduzca un nuevo nodo uy arme arcos de longitud L desde u a A y desde todos los nodos excepto A a u, donde L es muy grande (lo suficientemente grande para que ninguna solución óptima vuelva a visitarlo) Eliminar u de la gira para obtener una ruta de A a otro nodo a través de todos los demás. Desafortunadamente, esta reducción preserva el objetivo solo de manera aditiva, lo que hace que las garantías de aproximación empeoren por un factor constante.

El objetivo de la reducción que Evgeny señaló es no métrico TSP simétrico, por lo que la reducción no es útil para usted, porque las aproximaciones conocidas todas requieren instancias de métrica.Suponiendo que la colección de caminos forma un gráfico plano (o está cerca de él), existe una aproximación de factor constante debido a Gharan and Saberi, que desafortunadamente puede ser bastante difícil de implementar y puede no dar resultados razonables en la práctica. Frieze, Galbiati, and Maffioli da una aproximación de factor de registro simple para gráficos generales.

Si hay un número razonable de rutas, las bifurcaciones y los enlaces pueden ofrecerle una solución óptima. Tanto G & S como bifurcación y encuadernación requieren resolver el programa lineal Held-Karp para ATSP, que puede ser útil en sí mismo para evaluar otros enfoques. Para muchas instancias de TSP simétricas que surgen en la práctica, da un límite inferior en el costo de una solución óptima dentro del 10% del valor verdadero.