En informática y teoría de grafos , el problema del viajero canadiense ( CTP ) es una generalización del problema de la ruta más corta a grafos que son parcialmente observables . En otras palabras, el gráfico se revela mientras se explora y los bordes exploratorios se cargan incluso si no contribuyen a la ruta final.
Este problema de optimización fue introducido por Christos Papadimitriou y Mihalis Yannakakis en 1989 y desde entonces se han estudiado varias variantes del problema. El nombre supuestamente se origina en conversaciones de los autores que se enteraron de una dificultad que tenían los conductores canadienses : viajar por una red de ciudades con nevadas que bloqueaban carreteras al azar. La versión estocástica, donde cada borde se asocia con una probabilidad de estar independientemente en el gráfico, ha recibido una atención considerable en la investigación de operaciones bajo el nombre "Problema de la ruta más corta estocástica con recurso" (SSPPR).
Descripción del problema
Para un caso dado, hay una serie de posibilidades, o realizaciones , de cómo se verá el gráfico oculto. Dada una instancia, una descripción de cómo seguir la instancia de la mejor manera se llama política . La tarea de CTP es calcular el costo esperado de las políticas óptimas. Calcular una descripción real de una política óptima puede ser un problema más complicado.
Dada una instancia y una política para la instancia, cada realización produce su propio recorrido (determinista) en el gráfico. Tenga en cuenta que la caminata no es necesariamente un camino, ya que la mejor estrategia puede ser, por ejemplo, visitar cada vértice de un ciclo y regresar al inicio. Esto se diferencia del problema del camino más corto (con pesos estrictamente positivos), donde las repeticiones en una caminata implican que existe una mejor solución.
Variantes
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 paseo producido por una política para una instancia y realización determinadas. En el problema del camino más corto estocástico con recurso, el objetivo es simplemente minimizar el costo de la caminata (definido como la suma de todos los bordes del costo del borde multiplicado por el número de veces que se tomó ese borde). Para el problema del viajero canadiense, la tarea es minimizar la relación competitiva de la caminata; es decir, para minimizar el número de veces que el recorrido producido es hasta el camino más corto de la realización.
El segundo parámetro es cómo evaluar una política con respecto a diferentes realizaciones consistentes con la instancia bajo consideración. En el problema del viajero canadiense, se desea estudiar el peor de los casos y en la SSPPR, el caso medio . Para el análisis de casos promedio, además se debe especificar una distribución a priori sobre las realizaciones.
El tercer parámetro está restringido a las versiones estocásticas y trata sobre qué suposiciones 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 los bordes (i-SSPPR), cada borde incierto (o costo) tiene una probabilidad asociada de estar en la realización y el evento de que haya un borde en el gráfico es independiente de las cuales otras aristas están en la realización. Aunque se trata de una simplificación considerable, el problema sigue siendo #P -hard. Otra variante es no hacer ninguna suposición sobre la distribución, pero requiere que cada realización con probabilidad distinta de cero se establezca explícitamente (como “Probabilidad 0.1 del conjunto de aristas {{3,4}, {1,2}}, probabilidad 0.2 de. .. ”). Esto se denomina Problema de la ruta más corta estocástica de distribución (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 gráfico con el tiempo. En CTP y SSPPR, la realización es fija pero no conocida. En el problema de la ruta más corta estocástica con recurso y restablecimientos o en el problema de la ruta más corta esperada, se elige una nueva realización de la distribución después de cada paso dado por 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, en la que la realización del gráfico puede influir en la siguiente realización, es mucho más difícil.
Un parámetro adicional es cómo se descubren nuevos conocimientos en la realización. En las variantes tradicionales de CTP, el agente descubre el peso (o estado) exacto de un borde al llegar a un vértice adyacente. Recientemente se sugirió una nueva variante en la que un agente también tiene la capacidad de realizar sensores remotos desde cualquier lugar en la realización. En esta variante, la tarea es minimizar el costo de viaje más el costo de las operaciones de detección.
Definicion formal
Definimos la variante estudiada en el trabajo de 1989. Es decir, el objetivo es minimizar el ratio competitivo en el peor de los casos. Es necesario que comencemos por introducir ciertos términos.
Considere un gráfico dado y la familia de gráficos no dirigidos que se pueden construir agregando una o más aristas de un conjunto dado. Formalmente, dejadonde pensamos en E como los bordes que deben estar en el gráfico y en F como los bordes que pueden estar en el gráfico. Nosotros decimos esoes una realización de la familia de gráficos. Además, sea W una matriz de costos asociada dondees el costo de pasar del vértice i al vértice j , asumiendo que esta arista está en la realización.
Para cualquier vértice v en V , llamamossu incidente bordes con respecto al conjunto de borde B en V . Además, para una realización, dejar el coste de la ruta más corta en el gráfico de s a t . Esto se denomina problema fuera de línea porque un algoritmo para tal problema tendría información completa del gráfico.
Decimos que una estrategia navegar por un gráfico de este tipo es un mapeo de a , dónde denota el powerset de X . Definimos el costo de una estrategia con respecto a una realización particular como sigue.
- Dejar y .
- Para , definir
- ,
- , y
- .
- Si existe una T tal que, luego ; de lo contrario deja.
En otras palabras, evaluamos la política en función de los bordes que actualmente sabemos que están en el gráfico () y los bordes que sabemos que podrían estar en el gráfico (). Cuando damos un paso en el gráfico, conocemos los bordes incidentes a nuestra nueva ubicación. Los bordes que están en el gráfico se agregan ae independientemente de si los bordes están en el gráfico o no, se eliminan del conjunto de bordes desconocidos, . Si la meta nunca se alcanza, decimos que tenemos un costo infinito. Si se alcanza la meta, definimos el costo de la caminata como la suma de los costos de todos los bordes recorridos, con cardinalidad.
Finalmente, definimos el problema del viajero canadiense.
- Dada una instancia de CTP , decide si existe una política tal que por cada realización , el costo de la póliza no es más de r veces el óptimo fuera de línea, .
Papadimitriou y Yannakakis señalaron que esto define un juego de dos jugadores , en el que los jugadores compiten por el costo de sus respectivos caminos y el segundo jugador (la naturaleza) elige la ventaja.
Complejidad
El artículo original analizó la complejidad del problema e informó que estaba completo en PSPACE . También se demostró que encontrar una ruta óptima en el caso en el que cada borde tiene una probabilidad asociada de estar en el gráfico (i-SSPPR) es un problema PSPACE fácil pero ♯P difícil. [1] Era un problema abierto cerrar esta brecha, pero desde entonces se demostró que tanto la versión dirigida como la no dirigida eran difíciles de PSPACE. [2]
La versión dirigida del problema estocástico se conoce en la investigación de operaciones como el problema del camino más corto estocástico con recurso.
Aplicaciones
Se dice que el problema tiene aplicaciones en la investigación de operaciones , la planificación del transporte, la inteligencia artificial , el aprendizaje automático , las redes de comunicación y el enrutamiento. Se ha estudiado una variante del problema para la navegación robótica con reconocimiento probabilístico de puntos de referencia. [3]
Problemas abiertos
A pesar de la antigüedad del problema y sus muchas aplicaciones potenciales, muchas preguntas naturales siguen abiertas. ¿Existe una aproximación de factor constante o el problema APX es 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 la descripción? [4]
Ver también
Notas
- ^ Papadimitriou y Yannakakis, 1989, p. 148
- ^ Fried, Shimony, Benbassat y Wenner 2013
- ^ Briggs, Amy J .; Detweiler, Carrick; Scharstein, Daniel (2004). "Rutas más cortas esperadas para la navegación de robots basada en puntos de referencia". "Revista Internacional de Investigación en Robótica" . 23 (7–8): 717–718. CiteSeerX 10.1.1.648.3358 . doi : 10.1177 / 0278364904045467 .
- ^ Karger y Nikolova, 2008, p. 1
Referencias
- CH Papadimitriou; M. Yannakakis (1989). "Caminos más cortos sin mapa". Apuntes de conferencias en Ciencias de la Computación . Proc. 16º ICALP. 372 . Springer-Verlag . págs. 610–620.
- Dror Fried; Solomon Eyal Shimony; Amit Benbassat; Cenny Wenner (2013). "Complejidad de las variantes del problema del viajero canadiense". Informática Teórica . 487 : 1-16. doi : 10.1016 / j.tcs.2013.03.016 .
- David Karger; Evdokia Nikolova (2008). "Algoritmos exactos para el problema del viajero canadiense en caminos y árboles". Cite journal requiere
|journal=
( ayuda ) - Zahy Bnaya; Ariel Felner; Solomon Eyal Shimony (2009). "Problema del viajero canadiense con la teledetección". Parámetro desconocido
|conference=
ignorado ( ayuda );Cite journal requiere|journal=
( ayuda )