In computer science and graph theory, the Canadian Traveller Problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable. In other words, the graph is revealed while it is being explored, and explorative edges are charged even if they do not contribute to the final path.
This optimization problem was introduced by Christos Papadimitriou and Mihalis Yannakakis in 1989 and a number of variants of the problem have been studied since. The name supposedly originates from conversations of the authors who learned of the difficulty Canadian drivers had with snowfall randomly blocking roads. The stochastic version, where each edge is associated with a probability of independently being in the graph, has been given considerable attention in operations research under the name "the Stochastic Shortest Path Problem with Recourse" (SSPPR).
Read more about Canadian Traveller Problem: Problem Description, Variants, Formal Definition, Complexity, Applications, Open Problems
Famous quotes containing the words canadian, traveller and/or problem:
“We’re definite in Nova Scotia—’bout things like ships ... and fish, the best in the world.”
—John Rhodes Sturdy, Canadian screenwriter. Richard Rossen. Joyce Cartwright (Ella Raines)
“I have learned that the swiftest traveller is he that goes afoot.”
—Henry David Thoreau (1817–1862)
“Every reform was once a private opinion, and when it shall be a private opinion again, it will solve the problem of the age.”
—Ralph Waldo Emerson (1803–1882)