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 gráficos 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 presentado 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 las carreteras al azar. La versión estocástica, donde cada borde está asociado 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 de "Problema del camino más corto estocástico con recurso" (SSPPR).
Para un caso dado, hay una serie de posibilidades, o realizaciones , de cómo puede verse el gráfico oculto. Dada una instancia, una descripción de cómo seguir la instancia de la mejor manera se denomina 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 difícil.
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 todos los vértices de un ciclo y volver al inicio. Esto difiere del problema del camino más corto (con pesos estrictamente positivos), donde las repeticiones en una caminata implican que existe una mejor solución.
Hay principalmente cinco parámetros que distinguen el número de variantes del problema del viajero canadiense. El primer parámetro es cómo se valora el paseo que produce una política para una determinada instancia y realización. En el Problema estocástico de la ruta más corta con recurso, el objetivo es simplemente minimizar el costo de la caminata (definido como la suma sobre 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 más largo que el paseo producido es 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 bajo consideración. En el Problema del Viajero Canadiense, se desea estudiar el peor de los casos y en SSPPR, el caso promedio . Para el análisis de casos promedio, se debe especificar además una distribución a priori sobre las realizaciones.