Problema del viajero canadiense

En informática y teoría de grafos , el problema del viajero canadiense ( CTP ) es una generalización del problema del camino más corto a grafos parcialmente observables . En otras palabras, un "viajero" en un punto dado del grafo no puede ver el grafo completo, sino solo los nodos adyacentes o una determinada "restricción de realización".

Este problema de optimización fue introducido por Christos Papadimitriou y Mihalis Yannakakis en 1989, y desde entonces se han estudiado diversas variantes. Su nombre, al parecer, proviene de conversaciones entre los autores que se percataron de una dificultad que enfrentaban los conductores canadienses: transitar por una red de ciudades con nevadas que bloqueaban aleatoriamente las carreteras. La versión estocástica , donde cada arista se asocia con una probabilidad de pertenecer al grafo de forma independiente, ha recibido considerable atención en la investigación operativa bajo el nombre de "Problema de la Ruta Más Corta Estocástica con Recurso" (SSPPR, por sus siglas en inglés).

Una instancia del problema especifica el grafo y el conjunto de aristas propensas a bloquearse. Dada una instancia, la descripción del camino a seguir, en función de las aristas bloqueadas encontradas en el trayecto, se denomina política . La tarea del CTP consiste en encontrar una política competitiva, es decir, una que no se desvíe demasiado del óptimo. Calcular una descripción precisa de una política óptima puede resultar un problema más complejo.

Dada una instancia y una política para dicha instancia, cada realización (es decir, un conjunto de aristas bloqueadas) produce su propio recorrido (determinista) en el grafo. Cabe destacar que el recorrido no es necesariamente un camino , ya que la mejor estrategia podría ser, por ejemplo, visitar todos los vértices de un ciclo y regresar al punto de partida. Esto difiere del problema del camino más corto (con pesos estrictamente positivos), donde las repeticiones en un recorrido implican que existe una mejor solución.

Existen principalmente cinco parámetros que distinguen el número de variantes del Problema del Viajero Canadiense. El primer parámetro es cómo valorar el recorrido generado por una política para una instancia y realización dadas. En el Problema Estocástico del Camino Más Corto con Recurso, el objetivo es simplemente minimizar el costo del recorrido (definido como la suma, sobre todas las aristas, del costo de la arista multiplicado por el número de veces que se tomó dicha arista). Para el Problema del Viajero Canadiense, la tarea consiste en minimizar la razón de competitividad del recorrido; es decir, minimizar el número de veces que el recorrido generado es más largo que el camino más corto en la realización.

El segundo parámetro es cómo evaluar una política con respecto a diferentes realizaciones consistentes con la instancia en consideración. En el Problema del Viajero Canadiense, se desea estudiar el peor caso y en SSPPR, el caso promedio . Para el análisis del caso promedio, se debe especificar además una distribución a priori sobre las realizaciones.

El tercer parámetro está restringido a las versiones estocásticas y se refiere a las suposiciones que podemos hacer sobre la distribución de las realizaciones y cómo se representa la distribución en la entrada. En el Problema del Viajero Canadiense Estocástico y en el Problema del Camino Más Corto Estocástico Independiente de Aristas (i-SSPPR), cada arista incierta (o costo) tiene una probabilidad asociada de estar en la realización y el evento de que una arista esté en el grafo es independiente de qué otras aristas estén en la realización. Aunque esto es una simplificación considerable, el problema sigue siendo #P -difícil. Otra variante es no hacer ninguna suposición sobre la distribución, pero requerir que cada realización con probabilidad distinta de cero se indique explícitamente (como “Probabilidad 0.1 del conjunto de aristas { {3,4},{1,2} }, probabilidad 0.2 de...”). Esto se llama Problema del Camino Más Corto Estocástico Distribuido (d-SSPPR o R-SSPPR) y es NP-completo . La primera variante es más difícil que la segunda porque la primera puede representar en el espacio logarítmico algunas distribuciones que la segunda representa en el espacio lineal.

El cuarto y último parámetro es cómo cambia el grafo con el tiempo. En CTP y SSPPR, la realización es fija pero desconocida. En el Problema de la Ruta Más Corta Estocástica con Recurso y Reinicios o el Problema de la Ruta Más Corta Esperada, se elige una nueva realización de la distribución después de cada paso de la política. Este problema se puede resolver en tiempo polinomial reduciéndolo a un proceso de decisión de Markov con horizonte polinomial. Se sabe que la generalización de Markov, donde la realización del grafo puede influir en la siguiente realización, es mucho más difícil.

Un parámetro adicional es cómo se descubre nuevo conocimiento durante la realización. En las variantes tradicionales de CTP, el agente descubre el peso exacto (o estado) de una arista al llegar a un vértice adyacente. Recientemente se propuso una nueva variante en la que el agente también tiene la capacidad de realizar teledetección desde cualquier ubicación en la realización. En esta variante, la tarea consiste en minimizar el costo de desplazamiento más el costo de las operaciones de detección.

Definimos la variante estudiada en el artículo de 1989. Es decir, el objetivo es minimizar la relación de competitividad en el peor de los casos. Es necesario comenzar introduciendo ciertos términos.

Consideremos un grafo dado y la familia de grafos no dirigidos que se pueden construir añadiendo una o más aristas de un conjunto dado. Formalmente, sea${\displaystyle {\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset }$donde pensamos en E como las aristas que deben estar en el grafo y en F como las aristas que pueden estar en el grafo. Decimos que${\displaystyle G\in {\mathcal {G}}(V,E,F)}$es una realización de la familia de grafos. Además, sea W una matriz de costos asociada donde${\displaystyle w_{ij}}$es el costo de ir del vértice i al vértice j , suponiendo que esta arista está en la realización.

Para cualquier vértice v en V , llamamos${\displaystyle E_{B}(v,V)}$sus aristas incidentes con respecto al conjunto de aristas B en V. Además, para una realización${\displaystyle G=(V,B)\in {\mathcal {G}}(V,E,F)}$, dejar${\displaystyle d_{B}(s,t)}$Sea el costo del camino más corto en el grafo desde s hasta t . Esto se denomina problema fuera de línea porque un algoritmo para tal problema tendría información completa del grafo.

Decimos que una estrategia${\displaystyle \pi }$navegar por dicho gráfico es un mapeo desde${\displaystyle ({\mathcal {P}}(E),{\mathcal {P}}(F),V)}$a${\displaystyle V}$, dónde${\displaystyle {\mathcal {P}}(X)}$denota el conjunto potencia de X. Definimos el costo${\displaystyle c(\pi ,B)}$de una estrategia${\displaystyle \pi }$con respecto a una realización particular${\displaystyle G=(V,B)}$como sigue.

• Dejar${\displaystyle v_{0}=s,E_{0}=E}$y${\displaystyle F_{0}=F}$.
• Para${\displaystyle i=0,1,2,...}$, definir
  • ${\displaystyle E_{i+1}=E_{i}\cup E_{B}(v_{i},V)}$,
  • ${\displaystyle F_{i+1}=F_{i}-E_{F}(v_{i},V)}$, y
  • ${\displaystyle v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})}$.
• Si existe un T tal que${\displaystyle v_{T}=t}$, entonces${\displaystyle c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}}$; de lo contrario, deja${\displaystyle c(\pi ,B)=\infty }$.

En otras palabras, evaluamos la política basándonos en las aristas que actualmente sabemos que están en el grafo (${\displaystyle E_{i}}$) y las aristas que sabemos que podrían estar en el grafo (${\displaystyle F_{i}}$). Cuando damos un paso en el grafo, las aristas incidentes a nuestra nueva ubicación se hacen conocidas para nosotros. Esas aristas que están en el grafo se agregan a${\displaystyle E_{i}}$y, independientemente de si las aristas están en el grafo o no, se eliminan del conjunto de aristas desconocidas,${\displaystyle F_{i}}$Si nunca se alcanza el objetivo, decimos que el coste es infinito. Si se alcanza el objetivo, definimos el coste del recorrido como la suma de los costes de todas las aristas recorridas.

Finalmente, definimos el problema del viajero canadiense.

Dada una instancia de CTP${\displaystyle (V,E,F,s,t,r)}$decidir si existe una política${\displaystyle \pi }$de tal manera que para cada realización${\displaystyle (V,B)\in {\mathcal {G}}(V,E,F)}$el costo${\displaystyle c(\pi ,B)}$de la política no es más que r veces el óptimo fuera de línea,${\displaystyle d_{B}(s,t)}$.

Papadimitriou y Yannakakis señalaron que esto define un juego de dos jugadores , donde los jugadores compiten por el costo de sus respectivos caminos y el conjunto de aristas es elegido por el segundo jugador (la naturaleza).

El artículo original analizó la complejidad del problema y lo clasificó como PSPACE-completo . También se demostró que encontrar un camino óptimo en el caso donde cada arista tiene una probabilidad asociada de estar en el grafo (i-SSPPR) es un problema PSPACE-fácil pero ♯P -difícil. ^{[ 1 ]} Era un problema abierto para superar esta brecha, pero desde entonces se ha demostrado que tanto las versiones dirigidas como las no dirigidas son PSPACE-difíciles. ^{[ 2 ]}

La versión dirigida del problema estocástico se conoce en investigación operativa como el Problema de la Ruta Más Corta Estocástica con Recurso.

Se dice que el problema tiene aplicaciones en investigación operativa , planificación del transporte, inteligencia artificial , aprendizaje automático , redes de comunicación y enrutamiento. Se ha estudiado una variante del problema para la navegación de robots con reconocimiento probabilístico de puntos de referencia. ^{[ 3 ]}

A pesar de la antigüedad del problema y sus numerosas aplicaciones potenciales, aún quedan muchas preguntas sin respuesta. ¿Existe una aproximación con factor constante o el problema es APX -difícil? ¿Es i-SSPPR #P-completo? Una pregunta aún más fundamental ha quedado sin respuesta: ¿existe una descripción de tamaño polinomial de una política óptima, dejando de lado por un momento el tiempo necesario para calcular dicha descripción? ^{[ 4 ]}

• Recorrido de grafos
• Llegar a tiempo
• problema del camino más corto

• CH Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture Notes in Computer Science . Proc. 16th ICALP. Vol.  372. Springer-Verlag . pp. 610–620 . 
• Dror Fried; Solomon Eyal Shimony; Amit Benbassat; Cenny Wenner (2013). "Complejidad de variantes del problema del viajero canadiense" . Theoretical Computer Science . 487 : 1–16 . arXiv : 1207.4710 . doi : 10.1016/j.tcs.2013.03.016 . S2CID 17810202 . 
• David Karger; Evdokia Nikolova (28 de enero de 2008). Algoritmos exactos para el problema del viajero canadiense en caminos y árboles (PDF) (Informe). Instituto Tecnológico de Massachusetts.
• Zahy Bnaya; Ariel Felner; Solomon Eyal Shimony (2009). Problema del viajero canadiense con la teledetección . Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI).