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
Other articles related to "canadian traveller problem, problem":
... Despite the age of the problem and its many potential applications, many natural questions still remain open ... Is there a constant-factor approximation or is the problem APX-hard? Is i-SSPPR #P-complete? An even more fundamental question has been left unanswered ...
Famous quotes containing the words problem, canadian and/or traveller:
“If a problem is insoluble, it is Necessity. Leave it alone.”
—Mason Cooley (b. 1927)
“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)
“The traveller on the prarie is naturally a hunter, on the head waters of the Missouri and Columbia a trapper, and at the Falls of St. Mary a fisherman.”
—Henry David Thoreau (1817–1862)