Canadian traveller problem

From Wiktionary, the free dictionary
Jump to navigation Jump to search

English

[edit]

Etymology

[edit]

Introduced by Christos Papadimitriou and Mihalis Yannakakis in 1989. Supposed to allude to the difficulties experienced by Canadian drivers with snowfall randomly blocking roads.

Noun

[edit]

Canadian traveller problem

  1. (computing theory) A generalization of the shortest path problem to graphs that are only partially observable (i.e. the graph is revealed while it is being explored).