カナダ人旅行者問題

コンピュータサイエンスとグラフ理論において、カナダトラベラー問題（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 番目の変種が線形空間で表す分布の一部を前者が対数空間で表すことができるため、2 番目の変種よりも困難です。

4つ目、そして最後のパラメータは、グラフが時間とともにどのように変化するかです。CTPとSSPPRでは、実現値は固定されていますが、未知です。リコースとリセットを伴う確率的最短経路問題、あるいは期待最短経路問題では、方策が各ステップを実行するたびに分布から新たな実現値が選択されます。この問題は、多項式時間区間を持つマルコフ決定過程に簡約することで、多項式時間で解くことができます。グラフの実現値が次の実現値に影響を与える可能性があるマルコフ一般化は、はるかに困難であることが知られています。

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

正式な定義

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

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

Vの任意の頂点vについて、そのV上の辺集合Bに対する接続辺をと呼ぶ。さらに、実現 において、グラフsからtへの最短経路のコストを とする。この問題は、この問題のアルゴリズムがグラフの完全情報を持つことになるため、オフライン問題と呼ばれる。 ${\displaystyle E_{B}(v,V)}$ ${\displaystyle G=(V,B)\in {\mathcal {G}}(V,E,F)}$ ${\displaystyle d_{B}(s,t)}$

このようなグラフをナビゲートする戦略は、 からへの写像であると言えます。ここで、 はXの冪集合を表します。特定の実現に関する戦略のコストは以下のように定義されます。 ${\displaystyle \pi }$ ${\displaystyle ({\mathcal {P}}(E),{\mathcal {P}}(F),V)}$ ${\displaystyle V}$ ${\displaystyle {\mathcal {P}}(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 インスタンス が与えられた場合、すべての実現に対して、ポリシーのコストがオフライン最適値のr倍以下になるようなポリシーが存在するかどうかを判断します。${\displaystyle (V,E,F,s,t,r)}$ ${\displaystyle \pi }$ ${\displaystyle (V,B)\in {\mathcal {G}}(V,E,F)}$ ${\displaystyle c(\pi,B)}$ ${\displaystyle d_{B}(s,t)}$

パパディミトリウとヤナカキスは、これが2 人用ゲームを定義し、各プレイヤーがそれぞれのパスのコストを競い合い、エッジ セットが 2 番目のプレイヤー (自然) によって選択されることを指摘しました。

複雑

原論文では、この問題の複雑さを分析し、PSPACE完全であると報告しました。また、各辺がグラフ内に存在する確率を持つ場合（i-SSPPR）の最適経路を見つける問題は、PSPACE容易だが、#P困難であることも示されました。^{[ 1 ]}このギャップを埋めることは未解決問題でしたが、その後、有向版と無向版の両方がPSPACE困難であることが示されました。^{[ 2 ]}

確率的問題の有向バージョンは、オペレーションズ リサーチでは、リコース付き確率的最短経路問題として知られています。

アプリケーション

この問題は、オペレーションズ・リサーチ、交通計画、人工知能、機械学習、通信ネットワーク、経路探索といった分野に応用できると言われています。この問題の変種として、確率的ランドマーク認識を用いたロボットナビゲーションの研究が行われています。^{[ 3 ]}

未解決の問題

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

参照

• グラフトラバーサル
• 打撃時間
• 最短経路問題

注記

1. パパディミトリウとヤナカキス、1989年、p. 148
2. フリード、シモニー、ベンバサット、ウェナー 2013
3. Briggs, Amy J.; Detweiler, Carrick; Scharstein, Daniel (2004). 「ランドマークベースのロボットナビゲーションにおける期待最短経路」. International Journal of Robotics Research . 23 ( 7–8 ): 717– 718. CiteSeerX  10.1.1.648.3358 . doi : 10.1177/0278364904045467 . S2CID  15681481 .
4. Karger と Nikolova、2008、p. 1

参考文献

• CH Papadimitriou; M. Yannakakis (1989). 「地図なしの最短経路」.コンピュータサイエンス講義ノート. 第16回ICALP会議論文集. 第372巻. Springer-Verlag . pp.  610– 620.
• Dror Fried、Solomon Eyal Shimony、Amit Benbassat、Cenny Wenner (2013). 「カナダ人旅行者問題の変種の複雑性」 .理論計算機科学. 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).