カナダ人旅行者の問題

コンピュータサイエンスとグラフ理論において、カナダ旅行者問題（CTP）は、最短経路問題を部分的に観測可能なグラフに一般化したものである。言い換えれば、グラフ上の特定の地点にいる「旅行者」は、グラフ全体を見ることはできず、隣接するノード、あるいは特定の「実現制約」しか見ることができない。

この最適化問題は、 1989年にクリストス・パパディミトリウとミハリス・ヤナカキスによって提唱され、以来、この問題の様々な変種が研究されてきた。その名称は、カナダのドライバーが雪によって道路がランダムに遮断される都市ネットワークを走行する際に直面する困難を知った著者らの会話に由来するとされている。各エッジがグラフ内に存在する確率と独立して関連付けられる確率的バージョンは、「リコース付き確率的最短経路問題」（SSPPR）という名称でオペレーションズリサーチにおいて大きな注目を集めている。

問題のインスタンスは、グラフとブロックされやすいエッジの集合を指定します。インスタンスが与えられたとき、途中で遭遇するブロックされたエッジの関数として、たどるべきパスを記述したものをポリシーと呼びます。CTPタスクは、最適解から大きく逸脱しない、競争力のあるポリシーを見つけることです。最適なポリシーの実際の記述を計算することは、より難しい問題となる可能性があります。

インスタンスとそのインスタンスに対するポリシーが与えられると、各実現（つまり、ブロックされたエッジの集合）は、グラフ内で独自の（決定論的な）ウォークを生成します。ウォークは必ずしもパスになるとは限らないことに注意してください。例えば、サイクルのすべての頂点を訪れて開始点に戻ることが最善の戦略となる場合があるからです。これは、ウォークにおける繰り返しがより良い解の存在を意味する最短経路問題（厳密に正の重みを持つ場合）とは異なります。

カナダ旅行者問題のバリエーションの数を区別する主なパラメータは 5 つあります。最初のパラメータは、特定のインスタンスと実現に対してポリシーによって生成されるウォークをどのように評価するかです。リコース付き確率的最短経路問題では、ウォークのコスト (すべてのエッジについて、エッジのコストにそのエッジが通った回数を掛けたものの合計として定義される) を最小化することが目標です。カナダ旅行者問題では、ウォークの競争比を最小化することが課題です。つまり、生成されたウォークが実現における最短経路よりも何倍長いかを最小化することです。

2つ目のパラメータは、検討対象の事例に合致する様々な実現値に関して、政策をどのように評価するかという点です。カナダ旅行者問題では最悪のケースを、SSPPRでは平均的なケースを研究することが望まれます。平均的なケースを分析するためには、実現値に関する事前分布をさらに指定する必要があります。

3 番目のパラメータは確率的バージョンに限定され、実現の分布についてどのような仮定を置くことができるか、またその分布が入力でどのように表現されるかに関するものです。確率的カナダ旅行者問題とエッジ独立確率的最短経路問題 (i-SSPPR) では、各不確実なエッジ (またはコスト) には、実現に含まれる確率が関連付けられており、エッジがグラフに含まれるという事象は、実現に含まれる他のエッジとは独立しています。これはかなり単純化されていますが、この問題は依然として#P困難です。別のバリアントは、分布について仮定を置かず、非ゼロ確率の各実現を明示的に指定することを要求するものです (たとえば、「エッジセット { {3,4},{1,2} } の確率 0.1、... の確率 0.2」)。これは分布確率的最短経路問題 (d-SSPPR または R-SSPPR) と呼ばれ、NP 完全です。最初のバリアントは2番目のバリアントよりも難しい。なぜなら、前者は後者が線形空間で表現する分布の一部を対数空間で表現できるからである。

4番目にして最後のパラメータは、グラフが時間とともにどのように変化するかです。CTPとSSPPRでは、実現値は固定されていますが、既知ではありません。リコースとリセット付き確率的最短経路問題、または期待最短経路問題では、ポリシーが実行される各ステップの後、分布から新しい実現値が選択されます。この問題は、多項式時間ホライズンを持つマルコフ決定過程に還元することで、多項式時間で解くことができます。グラフの実現値が次の実現値に影響を与える可能性があるマルコフ一般化は、はるかに難しいことが知られています。

もう一つのパラメータは、実現図上で新たな知識がどのように発見されるかという点です。従来のCTPのバリアントでは、エージェントは隣接する頂点に到達すると、エッジの正確な重み（または状態）を明らかにします。最近、エージェントが実現図上の任意の場所からリモートセンシングを実行できる新しいバリアントが提案されました。このバリアントでは、移動コストとセンシング操作のコストの合計を最小化することが課題となります。

1989年の論文で研究された変種を定義する。すなわち、最悪の場合における競争比率を最小化することが目標である。まず、いくつかの用語を導入する必要がある。

与えられたグラフと、与えられた集合から 1 つ以上の辺を追加することによって構築できる無向グラフの族を考えます。形式的には、${\displaystyle {\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset }$ここで、 E はグラフに必ず含まれなければならない辺、Fはグラフに含まれる可能性がある辺と考える。${\displaystyle G\in {\mathcal {G}}(V,E,F)}$はグラフ族の実現である。さらに、W を関連するコスト行列とする。${\displaystyle w_{ij}}$これは、頂点iから頂点jへ移動するコストであり、この辺が実現に含まれていると仮定します。

V内の任意の頂点vに対して、${\displaystyle E_{B}(v,V)}$V上のエッジ集合Bに関するその入射エッジ。さらに、実現のために${\displaystyle G=(V,B)\in {\mathcal {G}}(V,E,F)}$、 させて$d_B(s,t)$は、グラフ内のsからtまでの最短経路のコストとする。このような問題に対するアルゴリズムはグラフに関する完全な情報を持っているため、これはオフライン問題と呼ばれる。

戦略とは${\displaystyle \pi }$このようなグラフをナビゲートするには、${\displaystyle ({\mathcal {P}}(E),{\mathcal {P}}(F),V)}$に${\displaystyle V}$、 どこ$\displaystyle {\mathcal {P}}(X)}$はXの冪集合を表す。コストを定義する。${\displaystyle c(\pi ,B)}$戦略の${\displaystyle \pi }$特定の実現に関して${\displaystyle G=(V,B)}$次のように。

• させて${\displaystyle v_{0}=s,E_{0}=E}$そして${\displaystyle F_{0}=F}$。
• のために${\displaystyle i=0,1,2,...}$、 定義する
  • ${\displaystyle E_{i+1}=E_{i}\cup E_{B}(v_{i},V)}$、
  • ${\displaystyle F_{i+1}=F_{i}-E_{F}(v_{i},V)}$、 そして
  • ${\displaystyle v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})}$。
• Tが存在して、${\displaystyle v_{T}=t}$、 それから${\displaystyle c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}}$; そうでなければ${\displaystyle c(\pi ,B)=\infty }$。

言い換えれば、我々は現在グラフ内に存在することがわかっているエッジに基づいてポリシーを評価する（${\displaystyle E_{i}}$）そして、グラフ内に存在することがわかっているエッジ（${\displaystyle F_{i}}$) グラフ内でステップを踏むと、新しい位置に接続するエッジがわかります。グラフ内のエッジは、${\displaystyle E_{i}}$、また、エッジがグラフに含まれているかどうかに関係なく、未知のエッジの集合から削除されます。${\displaystyle F_{i}}$目標地点に到達しない場合、コストは無限大であると言います。目標地点に到達する場合、経路のコストは、通過したすべての辺のコストの合計として定義されます。

最後に、カナダ人旅行者の問題を定義する。

CTPインスタンスが与えられた場合${\displaystyle (V,E,F,s,t,r)}$政策が存在するかどうかを判断する${\displaystyle \pi }$すべての実現に対して${\displaystyle (V,B)\in {\mathcal {G}}(V,E,F)}$費用${\displaystyle c(\pi ,B)}$この政策のコストはオフライン最適値のr倍以下であり、$d_B(s,t)$。

パパディミトリウとヤナカキスは、これは2人対戦ゲームを定義するものであり、プレイヤーはそれぞれの経路のコストを競い合い、エッジセットは2番目のプレイヤー（自然）によって選択されると指摘した。

元の論文では、問題の複雑さを分析し、PSPACE完全であると報告した。また、各エッジがグラフ内に存在する確率に関連付けられている場合（i-SSPPR）の最適パスを見つけることは、PSPACE簡単だが♯P難しい問題であることも示された。^{[ 1 ]}このギャップを埋めることは未解決の問題であったが、その後、有向バージョンと無向バージョンの両方がPSPACE難しいことが示された。^{[ 2 ]}

確率問題の方向性のあるバージョンは、オペレーションズリサーチにおいて、リカース付き確率最短経路問題として知られている。

この問題は、オペレーションズリサーチ、輸送計画、人工知能、機械学習、通信ネットワーク、ルーティングなどの分野に応用できると言われています。この問題の変種は、確率的ランドマーク認識を用いたロボットナビゲーションのために研究されています。^{[ 3 ]}

この問題の歴史の長さと多くの潜在的な応用にもかかわらず、多くの自然な疑問が未解決のまま残されています。定数係数近似は存在するのか、それともこの問題はAPX困難なのか？ i-SSPPR #P 完全なのか？ さらに根本的な疑問も未解決のままです。最適方策の多項式サイズの記述は存在するのか、記述を計算するのに必要な時間は一旦置いておくとして？^{[ 4 ]}

• グラフ走査
• 打撃時間
• 最短経路問題

• CH Papadimitriou; M. Yannakakis (1989). 「地図なしの最短経路」. Lecture Notes in Computer Science . Proc. 16th ICALP. Vol.  372. Springer-Verlag . pp. 610–620 . 
• Dror Fried 、 Solomon Eyal Shimony、Amit Benbassat 、Cenny Wenner ( 2013) 「カナダ旅行者問題の変種の複雑性」 Theoretical Computer Science.487 : 1–16.arXiv : 1207.4710.doi : 10.1016 / j.tcs.2013.03.016.S2CID 17810202 . 
• David Karger; Evdokia Nikolova (2008年1月28日).パスとツリー上のカナダ旅行者問題に対する厳密なアルゴリズム(PDF) (レポート). マサチューセッツ工科大学.
• Zahy Bnaya; Ariel Felner; Solomon Eyal Shimony (2009).リモートセンシングにおけるカナダ旅行者の問題. 国際人工知能合同会議 (IJCAI).