JP5241163B2 - 出発地から目的地までの最適経路を見つけるためにコンピュータによって実施される方法 - Google Patents

Description

本発明は、包括的には最小コスト経路を見つけることに関し、より詳細には確率的ネットワークでモデル化される最適経路を見つけることに関する。

最小コストまたは「最短」経路、一般的には最適経路または「最も成功する可能性が高い」経路を見つけることは、数多くの実用的な輸送の応用形態および通信の応用形態において重要である。その問題は、ある特定の制約がある中で、出発地から目的地までのルートを見つけることである。たとえば、その問題は、出発時刻前の空港までの最良の地理的なルート、燃料を使い果たす前に車で家に帰るための最良のルート、またはパケットを最小限の遅延で送信するためのネットワーク内の最良のルートを見つけることである。

本発明は、確率的ネットワーク（グラフ）としてモデル化することができる経路に関する。確率的ネットワークは、辺によって接続されるノードを含む。辺は、最適になりうるルートを形成することができる個々の経路を表しており、ノードは、中継点であり、ノードにおいて、特定のルートのために代替の経路を選択することができる。確率的ネットワークでは、辺（経路）を横断するコストは、その辺に関連付けられる確率分布に従ってランダムに生じる。通常、コスト分布は、辺の「長さ」、または辺を横断するのにかかる進行時間を表す。っこのようにして実際に機能している。

確率的な最短経路の意味を定義することは難しいので、この問題を形式化するのも難しい。経路をモデル化する辺が、確率分布によってモデル化されるとき、最短経路は、平均値を決定することができるか、平均および分散を最小にすることができるか、または他の指定された判定基準を最小にすることができる。さらに、それらの最短経路は、適応的に、または非適応的に決定することができる。予想される経路長の非適応的な最小化は、決定論的な最短経路問題に帰着するのは明らかであり、適応的な方法が最も一般的である。

大部分の従来技術の方法は、出発地から目的地までの予想される経路長を最小にするか、または二基準問題のように、予想される経路長および予想されるコストの組み合わせを最小にする。J. Mote、I. MurthyおよびD. Olson著「A parametric approach to solving bicriterion shortest path problems」（European Journal of Operational Research, 53:81-92, 1991）およびS. PallottinoおよびM. G. Scutella著「Shortest path processes in transportation models: Classical and innovative aspects」（Technical Report TR-97-06, Universita di Pisa Dipartimento di Informatica, 1997）を参照願いたい。

いくつかの方法は、経路長の非線形関数を最適化する。他の方法は、決定理論的枠組みを定義する。R. P. Loui著「Optimal paths in graphs with stochastic or multi-dimensional weights」（Communications of the ACM, 26:670-676, 1983）を参照願いたい。そこでは、最適経路は、ある種の単調増加する効用関数に対して予想される効用を最大にする。

期限前に到着する確率を最大にする最短経路を見つけるための適応的な方法が、Y. Fan、R. KalabaおよびI. J. E. Moore著「Arriving on time」（Journal of Optimization Theory and Applications, Vol. 127, No. 3, pp. 485-496, December 2005）によって記述される。非線形目的関数によるこのタイプの定式化は、実用上おそらく最も有用であるにもかかわらず、多数のレベルから（たとえばいくつかの例を挙げると、組み合わせ、分布、解析および機能のレベルから）その問題の難しさが生じて積み重なるので、ほとんど存在しない。たとえば、ランダム性がない場合には、その問題の組み合わせ特性は、近似するのが難しいことがある。グラフ構造が存在しない場合には、その目的関数は、最適化するのが難しいことがある。

確率的最短経路モデルは、実効的に、上記の難しさを低減することができる。

確率論的最短経路を取り扱う大部分の従来技術の方法は、適応的な過程を用いる。そこでは、最良の次の経路の選択は、そこまでに実現された辺長についての情報に基づく。適応的な方法の大部分は、予想される長さを最小にすることに焦点を当てている。長さの非線形関数を最小化することを考慮するものはほとんどなく、近似的な発見的過程を与えるだけである。

最も関連する方法は、Louiの方法である。Louiは、単調で、かつ減少しない経路長の一般的な効用関数を検討し、その効用関数が線形関数であるか、または指数関数であるときにだけ、予想される効用が辺長に分離可能になることを証明する。その場合に、従来の最短経路過程によって、予想される効用を最大にする経路を求めることができる。一般的な効用関数の場合に、Louiは、経路を確実に列挙することに基づく過程を記述する。

MirchandaniおよびSoroushは、二次効用関数の場合の指数関数的過程および発見的方法を与える。P. MirchandaniおよびH. Soroush著「Optimal paths in probabilistic networks: a case with temporary preferences」（Computers and Operations Research, 12(4):365-381, 1985）を参照願いたい。損失を用いる非単調効用関数の場合に、Nikolova等は、困難性および擬似多項式過程を与える。E. Nikolova、M. BrandおよびD. R. Karger著「Optimal route planning under uncertainty」（Proceedings of International Conference on Automated Planning and Scheduling, 2006）を参照願いたい。

本発明の実施の形態は、ある所定の制約、たとえば、期限がある中で、出発地から目的地までの最小コスト（最短）経路を見つけるための方法を提供する。

それらの経路は、ノードおよび辺からなる確率的ネットワーク（グラフ）としてモデル化される。本発明は、辺長（コスト）が独立に、かつランダムに分布しているグラフにおいて、最適経路を見つける問題を考える。

その目標は、経路長が、期限時刻のような所与の閾値（制約）を超えない確率を最大にすることである。本発明は、正規分布の辺長の場合に驚くほど厳密な過程を提供し、それは準凸最大化に基づく。

本発明は、独立したランダムな辺長で確率的最短経路を見つけるための方法を提供する。その方法を用いて、あるコスト制約の下で、出発地から目的地までの最短（最小コスト）経路を見つけることができる。その経路として、期限に間に合うように、または期限前に空港まで行くルート、サービス品質保証またはコスト制御保証を有するネットワークの中でメッセージをルーティングするための経路、または船舶、トラックおよび航空機による商品の運送中継を用いることができる。また、その方法を用いて、モニタリング、保護の応用形態の場合に最も信頼性のあるルート、回線または中継を特定することもできる。また、その方法は、待ち時間保証が望まれる取引処理パイプライン、たとえば、インターネットを利用する販売にも適用することができる。

その方法は、動的計画法に基づかない点で独特であることに留意願いたい。その問題は、本質的に離散的であるが、その核心において、連続した最適化からの特性である。

注目すべきことに、辺長分布を変更することによって、問題の性質が大きく変更される。加法的な確率優位分布、指数関数分布およびベルヌーイ分布の場合についても、本発明の種々の実施の形態が提供される。

確率的最短経路定義
図１は、本発明による、出発地（Ｓ）１０１から目的地（Ｔ）１０２までの経路を表すグラフ１００を示す。そのグラフは、ノード１１０と、ノードを接続する辺１２０とを含む。形式的には、グラフ１００は、Ｇ＝（Ｖ，Ｅ）である。ただし、｜Ｖ｜＝ｎ個のノードであり、｜Ｅ｜＝ｍ個の辺である。それらの辺は、経路を表す。実際の応用形態の場合、辺の数は、何千個にもなることは理解されたい。

本発明は、ある制約がある中で、出発地から目的地までの最適経路を見つけるための方法を提供する。本明細書において用いられるときに、最適は、個々の応用形態に応じて、種々の意味を有することができる。最適は、最小コスト、最小時間、制約の中で目的地に到着する最大の確率、または成功する可能性が最も高い経路等を意味することができる。

各辺Ｅ_ｉ１２０は、確率分布として表される、関連する独立確率変数コスト、たとえば、長さ、または進行時間Ｘ_ｉ１２１を有する。コストの厳密な意味は、特定の応用形態による。コストの確率は、正規分布、加法的に分布、指数関数的に分布、またはベルヌーイ関数に従って分布することができる。コストの正規確率分布は、その平均μおよびその分散σ^２に関して表すことができる。

本発明は、制約ｔを有する。その制約は、出発時刻ｔ_０１３１から期限時刻ｔ_１１３２までの時間間隔ｔ、すなわちｔ＝ｔ_１−ｔ_０として表すことができる。他の応用形態では、時間以外の制約を用いることができることを理解願いたい。たとえば、その制約として、ある目標を達成するための実際の全予算を用いることができる。

本発明は、制約がある中で、たとえば、時間間隔ｔ以内に目的地に到着する確率を最大にする、ＳからＴへの最適経路πを見つけたいこととなる。

したがって、出発地から目的地までの全ての取り得る経路π_ｉの場合に、下式（１）を解く。

本発明は、同じグラフ上で等価なパラメトリック最短経路問題を構成し、解くことによって最適経路を見つける。そのグラフＧは、出発地Ｓ１０１および目的地Ｔ１０２を区別する。各経路π_ｉ１２０は、コストパラメータに依存する重みｕ_ｉ＋λｗ_ｉを与えられる。ただし、ｕ_ｉおよびｗ_ｉは、負の値でない重みであり、パラメータλは、範囲［０，∞］の中で変化する。パラメトリック最短経路問題は、最短経路が変化するパラメータ値（区切点）λを見つける。

本発明では、区切点の数をパラメトリック最短経路複雑度と呼ぶ。この場合、複雑度は、同じパラメトリック重みの経路を１つとして数えて、空でない開区間［０，∞］の場合に最短である経路の数に等しいことに留意願いたい。本発明では、これらを最適経路と呼ぶ。

本発明は、正規分布を用いる確率的最短経路と、パラメトリック最短経路問題との間の関連性を明らかにする。これにより、本発明は、前者のための平均および平滑化された結果を、パラメトリック最短経路環境にも適用できるようになる。

図２は、本発明の１つの実施の形態による、グラフ１００を通過する最適経路を見つけるための包括的な方法のステップを示す。本発明では、出発地から目的地までの全ての取り得る経路を、辺によって接続されるノードの確率的グラフ１００として表す（２１０）。各辺が、経路のコストに関する独立確率分布と関連付けられる（２２０）。本発明では、目的地に到着するための制約を定義する（２３０）。その後、本発明では、そのグラフを、比較的少ない数の決定論的最小コスト問題に変形する。

本発明において、「比較的少ない」とは、問題の数が一定であるか、または悪くても辺の数に対して線形であることを意味する。従来技術の解法は、良くても指数関数的であるか、それよりも複雑である。通常、従来技術の方法は、誤差および処理時間に関する既知の限界を用いることなく、近似的な発見的方法を使用する。それに対して、本発明の方法は、立証可能な限界および計算可能な処理時間を与える。ある制約の中で目的地に到着する確率を最大にする最適経路を求めるために、比較的少ない数の決定論的問題が解かれる（２５０）。決定論的最小コスト過程を用いて、比較的少ない数の候補経路の評価を行うことができる。

準凸最大化
本発明では、凸関数、およびその準凸関数への一般化を定義し、それらの大域的な最大値の主な特性を提示している。Ｃを凸集合とする。

定義２．１：集合Ｃ内の全てのｘ、ｙおよびα［０，１］の場合に、ｆ（αｘ＋（１−α）ｙ）≦αｆ（ｘ）＋（１−α）ｆ（ｙ）である場合には、関数ｆ（Ｃ）→（−∞，∞）は、凸関数である。全てのその下位集合が凸である場合には、その関数ｆは、準凸関数である。

非公式には、準凸関数は、任意のレベルにおいて凸断面を有する。

定義２．２：本発明では、ｘが集合Ｃ内の２つの他の点の凸結合、すなわち、Ｃ内のｙ、ｚ、範囲（０，１）内のαの場合に、ｘ＝αｙ＋（１−α）ｚ⇒ｙ＝ｚ＝ｘとして表すことができない場合には、ｘは、集合Ｃの極値点であると言う。

定理２．３：Ｃ⊂Ｒ^ｍをコンパクト凸集合とする。集合Ｃに関して最大値を達成する準凸関数ｆ：Ｃ→Ｒは、Ｃの極値点において、その最大値に達する。

本発明では、いくつかのさらに多くの定義を与える。Ｒ^ｍ内の凸集合の２次元平面２００への影は、その平面への凸集合の正投影である。Ｒ^ｍ内の集合Ｃのドミナントは、Ｃ内のある点よりも大きい全ての点の集合、すなわち、集合Ｃ内のいくつかのｙの場合に｛ｘ∈Ｒ^ｍ｜ｘ≧ｙと定義する。

正規分布を有する確率的最短経路
それゆえ、図３に示されるように、本発明は、最初にグラフ１００を投影する。そのグラフは、幾何学的には複数のノードからなるハイパーキューブ３０１であり、経路頂点３０３と経路閉包３０４とを含む、平均−分散（μ，σ^２）平面へのハイパーキューブ閉包３０２を有し、その閉包は、多角形である。その投影における経路頂点３０３は、経路のコスト１２１、たとえば、長さまたは時間に対応する。

その投影は、以下のように実行される。グラフの中のいずれかの経路の場合に、その経路によってどの辺が用いられるかを指示する、０および１からなるベクトルを構成する。このベクトルは、Ｒ^｜Ｅ｜内のハイパーキューブの角を指す。ただし、｜Ｅ｜は、辺の数である。有効な経路に対応する、全ての角の凸包は、経路ポリトープと呼ばれる。ポリトープの各頂点は、有効な経路に対応する。

また、本発明は、全ての平均パラメータからなり各辺に関連付けられるベクトルと、全ての分散パラメータからなり各辺に関連付けられる別のベクトルとを構成する。これらの２つのベクトルは、Ｒ^｜Ｅ｜内の平面を張る。本発明は、ポリトープをその平面上に投影して、影、すなわち、凸経路閉包３０４を得る。影経路閉包の頂点３０３は、元のグラフの中の経路に対応し、それは、上記の本発明の元のコスト関数に関連するパラメトリックコスト関数を極値化する。最適経路は、多角形の左下にある頂点、すなわち、小さな分散および小さな平均を有する頂点からなる小さな部分集合だけを精査することによって特定される。多角形３０４内の辺は、意味を持たない。

本発明は、正規分布している辺長を有するグラフに準凸最大化を適用する。本発明は、所与の期限時刻ｔまでに、またはその前に、出発地から目的地まで到着するための最良のルートを選択する。その問題は、時間どおりに空港に到着することのような、不確定の交通条件を有する輸送ネットワークへの現実的な用途を有する。

図４は、コストが正規分布するときの変形するステップを示す。本発明は、平均−分散平面上にグラフ１００を投影し（４１０）、最小分散頂点を特定する（４４０）。また、本発明は、最小平均頂点も特定し（４２０）、ルートが時間どおりである確率が０．５未満であるか否かを判定する（４３０）。０．５未満でない場合には、本発明は、分散頂点を昇順に列挙し（４５０）、０．５未満である場合には、最初に最小分散頂点を特定し（４４０）、その後、列挙する（４５０）。これは、最適である可能性があり、その問題が解かれる必要がある、少数の取り得る候補経路を与える。その後、本発明は、各経路が時間どおりである確率を求め、最適経路を選択する。

各辺ｉが独立正規分布の長さＸ_ｉ〜Ｎ（μ_Ｉ，σ_ｉ）１２１を有するものと仮定する。ただし、μは、平均であり、σは、分散である。本発明の目標は、以下の値を最大にすることである。

任意の経路πに対して、この確率は、以下の式によって与えられる。

ただし、Φ（ ）は、標準正規確率変数Ｎ（０，１）の累積分布関数である。Φは、単調増加するので、その問題は、その引数を最大にするＳＴ経路を見つけることと同じである。

式（３）の目的は、辺のコストに分離することはできず、準最適性を満たさない。それゆえ、下部構造に基づく動的計画法は、失敗する。目的関数の特性をさらに十分に理解するために、本発明は、その目的関数を、Ｒ^ｍ内の経路ポリトープにわたる連続最適化問題として定式化する。ただし、ｍは、辺の数である。

本発明では、全ての辺１２０を１、２、・・・、ｍによって添え字を付けて、その入射ベクトルｘによって各辺部分集合を表し、辺ｉがその部分集合内に存在する場合には、ｘ_ｉ＝１であり、そうでない場合には、ｘ_ｉ＝０である。辺の全ての２^ｍ個の部分集合は、Ｒ^ｍ内の単位ハイパーキューブの頂点に対応する。ＳＴ経路ポリトープ、略して経路ポリトープは、単純なＳＴ経路の入射ベクトルの凸包である。ポリトープは、Ｒ^ｍ内の単位ハイパーキューブの部分集合であり、ポリトープの頂点は、ハイパーキューブの頂点の部分集合である。したがって、最適なＳＴ経路は、下式（４）を最大にするための解である。

ただし、本発明では、｛０，１｝^ｍによって長さｍの０−１ベクトルの集合を表す。

経路ポリトープをベクトルμ＝（μ_１，・・・，μ_ｍ）およびσ＝（σ_１ ^２，・・・，σ_ｍ ^２）の張られた空間上に投影することによって、凸経路閉包３０４が定義され、本発明では、それを経路ポリトープ影と呼ぶ。

式（４）の目的は、分離不可能であり、決して一次および二次ではなく、凸ですらない。これは、その目的を計画法および組み合わせ最適化問題の範疇に入れるので、一般的な効率的解法は存在しない。通常、整数制約が主な問題を引き起こすが、この場合には、部分的に見たとしても、この問題を如何にして解くかは明らかではない。

結局、本発明の目的は、特別な構造を有し、その構造によれば、その最大値は、実現可能な集合の境界上に位置せざるを得ないということがわかる。詳細には、その構造は、経路ポリトープの集合において準凸であり、そのポリトープの残りの部分集合においては、μｘおよびσ^２ｘに関して単調である。本発明は、経路ポリトープ、さらにはその影の境界の多項式記述を持たないので、これは都合が良いとは言えない。

たとえば、経路ポリトープ影の最も右側で、かつ最も上側の頂点を計算することは、それぞれ辺平均および辺分散に関して最長経路を見つけることに対応する。それゆえ、経路凸包の計算は、一般的には、強くＮＰ−ｈａｒｄである。一方、極値点は、線形目的λμ＋（１−λ）σ^２（ただしλ［０；１］）を最適化するので、本発明は、影閉包のドミナントにおいて極値点を効率的に見つけることができる。

以下に記述される本発明の主要な定理３．３は、最長経路問題が発生しないようにする十分に早い出発時刻の場合に、本発明の目的が準凸であることを示す。本発明では、最初に、確率的およびパラメトリック最短経路問題の対応についての補助定理を述べる。

補助定理３．１：ベクトルｕ＝（ｕ_１，・・・，ｕ_ｍ）、ｗ＝（ｗ_１，・・・，ｗ_ｍ）によって張られる平面上の経路ポリトープドミナントの影上の極値点と、辺重みｕ_ｉ＋λｗ_ｉを用いるパラメトリック最短経路問題の区切点との間には、１対１対応がある。

補助定理３．１によれば、パラメトリック最短経路問題の複雑度に応じて、影ドミナントにおける極値点の数にも、それに相当する限界があることを意味する。

定理３．３．期限ｔが最小平均経路の平均以上であるとき、式（４）に対する解は、経路ポリトープ影のドミナントの極値点である。

証明
本発明は、最初に、式（４）の変形された形を考える。ｘ_１＝μ_ｘおよびｘ^２＝σ^２ｘと表す。この系は、以下の条件と等価になる。

下式で示される誘導された目的は、実現可能な集合Ｓ（￣）の部分集合において準凸である（ここで、表記（￣）は、その前の符号の上部に￣が付くことを意味する）。

その集合Ｓ（￣）は、ｔ未満の平均を有する経路が存在するものと仮定すると空ではない。ｘ_１＝μｘ＜ｔであるので、この実現可能な部分集合におけるｆ（ｘ_１，ｘ_２）の値は正であり、最大値を含まなければならない。それゆえ、目的関数ｆ（ｘ_１，ｘ_２）は、実現可能な集合Ｓ（￣）、すなわち、ｘ_１＝ｔの左にある経路ポリトープ影において準凸である。定理２．３によれば、最大値は、集合Ｓ（￣）の極値点にある。それゆえ、ｆ（ｘ_１，ｘ_２）は、ｘ_１およびｘ_２の両方において単調に減少するので、その解は、ｘ_１＝ｔの左にある、影のドミナントの極値点である。

ところで、影の任意の極値点は、元の経路ポリトープｍの極値点の投影であり、ｍは、整数座標を有する。それゆえ、式（４）の緩和された問題の最適な解は、式（５）の整数問題への解でもある。影ドミナントにおける各極値点は、以下の線形計画ｍｉｎへの解である。
ｃ≧０の場合に、ｘ∈影経路ポリトープを条件として、
ｍｉｎ ｃｘ

同じように、各極値点は、ｃ_１ｘ_１＋ｃ_２ｘ_２を最小にする経路に対応する。ただし、ｘ_１は、その経路の全平均であり、ｘ_２は、全分散であるので、ｃ_１、ｃ_２≧０の場合に、それは任意の最短経路過程を介して見つけることができる。

影ドミナントにおける全ての極値点を見つけるために、本発明は、２つの端点、すなわち、最小平均を有する経路に対応する最も左側の点、および最小分散の経路である最も下側の点で開始する。

それらの点を見つけるとき、本発明では、それらの点を、π_１＝（ｍ_１，ｓ_１）、π_２＝（ｍ_２，ｓ_２）∈Ｒ^２と表す。ただし、ｍ_ｉは、経路π_ｉの平均であり、ｓ_ｉは、分散である。その後、本発明では、ｍ_２≠０である場合には、（ｃ_１，ｃ_２）＝（−（ｓ_２＝ｓ_１）／（ｍ_２−ｍ_１））で、そうでない場合には、（ｃ_１，ｃ_２）＝（１，０）で式（６）を解く。新たな解をπ_３＝（ｍ_３，ｓ_３）と仮定する。π_１およびπ_２のいずれとも異なる場合には、本発明は、経路π_１とπ_３との間、π_２とπ_３との間等の頂点を見つけるために、その手順を繰り返す。このようにして、本発明が影上の全ての頂点を見つけることは明らかであろう。

出発時刻が期限に近く、任意の最短経路がｔよりも大きな平均を有するときに、その計画の最適値は、負になり、目的関数は、経路の平均に関して減少していき、分散に関して増加していく。この場合、緩和された計画に対する解は、最も低い平均の最も左にある極値点と、最も高い分散の最も上にある極値点との間にある、影の左上境界上にある。最も高い分散を有する簡単な経路を見つけることは、強くＮＰ−ｈａｒｄだからである。

本発明は、良好な多項式−時間近似を見つけることは期待しない。さらに、式（５）の目的関数は、｛ｘ_１｜ｘ_１＞ｔ｝で横切られる実現可能な集合において、もはや準凸ではない。本発明が分数解を見つけることができる場合であっても、式（４）に対する整数解と一致することは保証されない。

本発明では、おそらく単純でない経路を含む場合がある擬似多項式過程を記述し、それは、ノードの数ｎおよび最大辺分散σ^２に関する多項式である。この過程は、以下のように、動的な計画表を構成する。

経路分散の取り得る値ｓ＝０，１，・・・，σ^２毎に、かつノードｖ毎に、出発地Ｓから分散ｓおよび最小平均のノードｖまでの経路上にある、ノードｖの先行ノードを求める。最後には、本発明は、取り得る分散ｓと、その分散値のための最小平均毎に１つずつの、出発地から目的地までのσ^２個の経路を有する。

より厳密には、ノードｖおよび分散ｓ毎に、本発明は、準最適な方程式を解く。

ただし、Φ（ｖ，ｓ）は、出発地から、厳密にｓである分散のノードｖまでの最小平均経路の平均である。経路π（ｖ，ｓ）は、その経路上にあるノードｖの先行ノードであり、ノードｖの隣接するノードｖ_０である。辺長が独立しているという仮定は、経路分散を、辺分散の和として分離できることを確保することに留意願いたい。

その後、本発明は、分散ｓの部分的に最適化された値毎に、目的関数値（ｔ−経路平均）／（√（経路分散））を計算することによって、最適なＳＴ経路を見つけ、最小目的値を有する経路を選択する。

平均および平滑化された複雑度
辺重みベクトルｕ、ｗが、わずかに摂動する、一様にランダムな単位ベクトルまたは束縛ベクトルである場合には、経路ポリトープ影上の極値点の予想される数は、線形であり、結果として、上記の本発明の過程の予想される多項式実行時間は、小さい。本明細書において記述される技法は、線形計画法のための多項式シンプレックス過程のための技法を基にしている。

経路ポリトープＰの頂点は、単位ハイパーキューブの頂点の部分集合であり、詳細には、
事実１：ポリトープＰの各辺は、少なくとも１の長さを有し、
事実２：ポリトープＰは、単位ハイパーキューブに含まれ、そのハイパーキューブは、√（半径ｍ）／２の球内に含まれることに留意願いたい。

平均限界
定理４．１：ｕ、ｗ∈Ｒ^ｍ２を一様にランダムな単位ベクトルとし、Ｖをその張られた空間とする。そのとき、Ｖ上へのＰの投影の辺の数の期待値は、大きくても２×√（２）×ｍである。

証明：事実２によって、Ｖ上へのＰの影の周囲は、π×√（ｍ）によって画定される。次に、ポリトープＰの辺Ｉ毎に、その影内に辺Ｉが現われる事象をＳ_Ｉ（Ｖ）によって表し、ｌ（Ｉ）を、その影内の辺の長さとする。その影内の予想される辺長の和は、大きくても、最も大きな取り得る周囲に等しい。

以下の補助定理４．２によれば、以下の式が成り立つ。

それゆえ、以下の式が成り立つ。

ただし、ｍは、ポリトープＰの次元であり、本発明の場合には、確率的ネットワークの辺の数である。

補助定理４．２：ポリトープＰの全ての辺Ｉの場合に、以下の式が成り立つ。

証明：ポリトープの辺Ｉが影の中に現われる場合には、その辺は、投影面Ｖと小さな角度をなす。

ポリトープＰ内の任意の辺は、少なくとも１の長さを有するので（上記の事実１による）、影の中の辺の長さは、少なくともｃｏｓ（θ_Ｉ（Ｖ））であり、その影内に辺が現われる期待値は、以下のようになる。

平滑化された限界
本発明では、本発明の平均ケース限界を厳密にして、平滑化された解析を得る。すなわち、一様にランダムな２Ｄ−平面上に投影するのではなく、本発明では、任意の、そしておそらく最悪ケースの２Ｄ平面で開始し、その平面をわずかに摂動させる。その後、本発明では、本発明の２Ｄ平面上へのＰの投影の辺の予想される数が、ｍに関する多項式であり、摂動の大きさに関して逆多項式であることを立証する。

２Ｄ平面上の本発明の分布は、指数関数的な確率変数を含む。期待値λで指数関数的に分布する変数ｘは、全てのｔ≧０の場合に、以下の累積密度関数を有することとなる。

そして、下式の確率密度を有することとなる。

これにより、本発明では、ベクトルの摂動を定義できるようになる。

定義４．３：任意のρ＞０、および任意の単位ベクトルｕの場合に、本発明では、ｕのρ−摂動を、以下のように選択されたランダムな単位ベクトルｖであると定義する：
範囲［０，π］に限定して、期待値ρの指数関数分布から角度θ∈［０，π］をランダムに選択する。ｕとθの角度をなすベクトルの集合から一様にランダムにｖを選択する。結果は、以下の通りである。

定理４．４：Ｕ＝ｓｐａｎ（ｕ_１，ｕ_２）を任意の２Ｄ平面とする。ｖ_１およびｖ_２をそれぞれｕ_１およびｕ_２のρ−摂動とし、Ｖ＝ｓｐａｎ（ｖ_１，ｖ_２）とする。ρ＜１／（√（ｍ））の場合に、Ｖ上へのＰの投影の辺の予想される数は、多くても、４π×√（２ｍ／ρ）である。セクション４．１において用いられたのと同じ引数によって、これは、以下の補助定理に従う。

補助定理４．５：上記で定義された確率変数の場合に、以下の式が成り立つ。

この補助定理によれば、それらの値のうちの一方が一様にランダムである必要があるのとは対照的に、ｖ_１およびｖ_２は、いずれも、ρ−摂動分布から引き出すことができるようになる。

当然、摂動が小さくなると、その定理における限界も弱くなる。補助定理３．１によれば、これらの限界は、グラフの辺の数、平均および同様のパラメトリック最短経路問題における最適経路の数に対する平滑化された限界に関して線形であることを暗示することに留意願いたい。

加法的分布、指数関数分布およびベルヌーイ分布
本発明では、本発明のモデルを、正規分布以外の分布に拡張する。一定の第２のパラメータを有するポアソン分布またはガンマ分布、またはさらに包括的には、加法的であり、かつ確率優位を満たす分布に由来する辺長の場合、本発明は、その問題が、対応する分布のパラメータに等しい辺重みを有する決定的最短経路問題に帰着することを立証する。指数関数およびベルヌーイ確率変数の場合、その和は、厳密に計算することが難しいので、本発明では、多項式時間近似方式および準多項式時間近似方式、それぞれＰＴＡＳおよびＱＰＴＡＳを用いる。

ポアソン分布およびガンマ分布
レート（平均）μ_１およびμ_２を有する２つの独立したポアソン確率変数の和は、その和に等しい平均を有する別のポアソン確率変数である。さらに、ポアソン分布は、確率優位を満たす。すなわち、低い方のレートμ_１の場合のその累積分布関数は、高い方のレートμ_２の場合の累積分布関数よりも完全に大きい。

図５は、コストの確率分布が加法的であるときに最短経路を見つけるための方法を示す。各辺が、重みＬを付される（５１０）。決定論的最小コスト過程が、重み付けされた辺に適用され（５２０）、最適経路を出力することができる（５３０）。

具体的には、Ｄ（λ）を任意の単一のパラメータ加法的分布とする。すなわち、分布Ｄ（λ_１）およびＤ（λ_２）を有する２つの独立確率変数の和は、同じ分布と、和Ｄ（λ_１＋λ_２）に等しいパラメータとを有する別の確率変数である。

また、本発明では、Ｄ（λ）を用いて、この分布を有する確率変数も表す。さらに、分布Ｄが確率優位、すなわち、Ｐｒ（Ｄ（λ）≦ｔ）≧Ｐｒ（Ｄ（λ_２）≦ｔ）、ただし、λ_１≦λ_２を満たすものと仮定する。

そのような分布の別の現実的な例は、一定の形状パラメータｂを有するガンマ分布ｇａｍｍａ（ａ，ｂ）である。これは、任意の平均（分散）を有するが、平均対分散比が一定である一群の確率変数を定義する。

辺ｉのランダム長がＸ_ｉ〜Ｄ（λ_ｉ）であると仮定する。ここで、分離不可能な目的関数であるにもかかわらず、確率優位とともに、分布の加法性が、その問題を分離可能にする。

ただし、最後の不等式は、分布の確率優位特性から得られる。こうして、経路は、その分布パラメータが小さい場合に限って、閾値ｔを超えない高い確率を有する。この場合、最適経路は、そのリンクに沿って、分布パラメータの和が最も小さな経路であり、決定論的最短経路過程を適用すること（５２０）によって厳密に見つけることができる。

指数関数ＰＴＡＳおよびベルヌーイＱＰＴＡＳ
ポアソン分布とは異なり、指数関数分布およびベルヌーイ分布は、加法的ではない。それゆえ、目的確率関数のための単純な閉じた形の式を立てることはできない。本発明では、確率分布の量子化を介する動的計画法に基づく、多項式−時間近似方式を記述する。

図６は、確率分布が指数関数またはベルヌーイ関数であるときに最短経路を見つけるための方法を示す。本発明は、上記のようなグラフ、制約で開始し、近似パラメータも供給する（６１０）。本発明は、辺を２つの集合、すなわち、大きなパラメータの１つの集合および小さな辺の１つの集合に分割する（６２０）。大きな辺が量子化される（６３０）。グラフ内の大きな辺および小さな辺と、特定のノードｖとの取り得る組み合わせ毎に、出発地からノードｖまでの辺の組み合わせと一致するあらゆる経路を特定する（６４０）。特定された経路は、ある決定論的最小コスト過程で評価し、上記のように最大確率を有する経路を選択するための少数の経路である（６５０）。

より厳密には、本発明は、二基準近似を与え、それは、遅延許容値ｐを与えられ、ε＞０の場合に、以下の式を満たす経路πを見つける。

定理５．１：近似的な最適経路は以下の式によって与えられる。

ベルヌーイ分布の場合に、類似の量子化によって、準多項式時間近似方式がもたらされる。

本発明の具体的な実施の形態は、最小コスト経路の応用形態を用いて記述されてきたが、同じ基本的な技法を他の応用形態の場合にも用いることができることを理解願いたい。たとえば、そのグラフは、初期条件（出発地）から目標（目的地）を達成するために取り得る方法を表すことができる。この場合、確率分布は、その目標を達成する各ステップに関連付けられる不確定のコストを表し、制約は、コストを割り当てられた全コストの範囲内に抑えることである。

別法では、出発地は、ある過程または機械の初期状態にすることができ、目的地は最終状態にすることができる。この場合、辺は、状態遷移およびその関連するコストを表す。ここでは、その方法は、最終状態に達するための最適な１組の遷移を見つける。

本発明の１つの実施の形態における出発地から目的地までの経路を表すグラフである。 本発明の１つの実施の形態における最適経路を見つけるための方法の流れ図である。 平均−分散平面上への図１のグラフの投影図である。 本発明の１つの実施の形態における確率分布が正規分布である場合の最適経路を見つけるための方法の流れ図である。 本発明の１つの実施の形態における確率分布が加法的である場合の最適経路を見つけるための方法の流れ図である。 本発明の１つの実施の形態における確率分布がベルヌーイ関数である場合の最適経路を見つけるための方法の流れ図である。

Claims (10)

1. 出発地から目的地までの最適経路を見つけるためにコンピュータによって実施される方法であって、
   出発地から目的地までの全ての取り得る経路を、確率分布によってモデル化される辺によって接続されるノードの確率的グラフとしてモデル化し、モデル化した前記確率的グラフを前記コンピュータに入力するステップと、
   入力された前記確率的グラフに基づいて、各辺と、該辺のコストに関する確率分布を関連付けるステップと、
   前記目的地に到着するための制約を定義し、前記コンピュータにあらかじめ記憶させておくステップと、
   前記確率分布および前記制約に基づいて、前記確率的グラフを１組の最小コスト問題に変形するステップと、
   前記１組の最小コスト問題を解いて、あらかじめ記憶された前記制約の中で前記目的地に到着する確率を最大にする最適経路を求めるステップと
   を含み、
   前記１組の最小コスト問題は、辺の数および取り得る経路に関して一定であるか、または辺の数および取り得る経路に関して線形である
   出発地から目的地までの最適経路を見つけるためにコンピュータによって実施される方法。
2. 前記確率分布は、正規分布であり、各確率分布は、平均および分散を有し、前記変形するステップは、
   候補最適経路に対応する頂点の部分集合を有する凸多角形の形の経路ポリトープ影を生成するために、前記確率的グラフの経路ポリトープを平均および分散平面に投影するステップをさらに含む請求項１に記載の方法。
3. 前記辺の前記コストの前記確率分布は、加法的であるとともに、確率優位を満たし、かつ前記１組の最小コスト問題は、単一の要素を含み、
   ここで、前記確率優位とは、平均が高い分布と低い分布の２つの分布を考えた場合に、前記平均が高い分布の累積分布関数が、前記平均が低い分布の累積分布関数よりも完全に大きいことを意味する
   請求項１に記載の方法。
4. 前記確率分布は、指数関数的であり、前記変形するステップは、各確率分布を量子化するステップをさらに含み、前記求めるステップは、前記量子化された確率分布に動的プログラムを再帰的に適用する請求項１に記載の方法。
5. 前記確率分布は、ベルヌーイ関数であり、前記変形するステップは、近似パラメータに従って各確率分布を量子化するステップをさらに含み、前記求めるステップは、前記量子化された確率分布に動的プログラムを再帰的に適用する請求項１に記載の方法。
6. 前記グラフは、目標に到達するために取り得る方法を表し、前記確率分布は、前記目標に到達する各ステップに関連付けられる不確定のコストを表し、前記制約は、割り当てられている全コストを超えないことである請求項１に記載の方法。
7. 前記出発地は、初期状態を表し、前記目的地は、最終状態を表し、かつ前記辺は、状態遷移および関連するコストを表す請求項１に記載の方法。
8. 前記コストは、時間を表し、前記制約は、期限である請求項１に記載の方法。
9. 前記経路は、地理的なルートである請求項１に記載の方法。
10. 前記経路は、ネットワーク内のルートである請求項１に記載の方法。

Images