Canadian traveller problem とは

コンピュータ科学とグラフ理論では、カナダ旅行者問題(CTP)は、部分的に観測可能なグラフに対する最短経路問題の一般化です。言い換えれば、グラフは探索されている間に明らかにされ、最終的な経路に寄与しない場合でも探索的な辺は充電される。
この最適化問題は、1989年にChristos PapadimitriouとMihalis Yannakakisによって導入され、以来、この問題の多くの変形が研究されてきた。この名前は、カナダ人の運転手が抱えていた困難を学んだ著者の会話から生じたものと思われます。各エッジがグラフ内に独立して存在する可能性がある確率的バージョンは、オペレーションズリサーチで「確率論的最短経路問題(SSPPR)」という名前で注目されています。