説明

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

【課題】出発地から目的地までの最適経路を見つける方法。
【解決手段】出発地から目的地までの取り得る経路は、辺によって接続されるノードからなる確率的グラフとして表される。各辺は、その辺のコストに関する独立確率分布を有する。目的地に到達するための制約が定義される。そのグラフは、比較的小さな1組の決定論的最小コスト問題に変形され、それを解いて、その制約の中で目的地に到達する確率を最大にする最適経路を求めることができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、包括的には最小コスト経路を見つけることに関し、より詳細には確率的ネットワークでモデル化される最適経路を見つけることに関する。
【背景技術】
【0002】
最小コストまたは「最短」経路、一般的には最適経路または「最も成功する可能性が高い」経路を見つけることは、数多くの実用的な輸送の応用形態および通信の応用形態において重要である。その問題は、ある特定の制約がある中で、出発地から目的地までのルートを見つけることである。たとえば、その問題は、出発時刻前の空港までの最良の地理的なルート、燃料を使い果たす前に車で家に帰るための最良のルート、またはパケットを最小限の遅延で送信するためのネットワーク内の最良のルートを見つけることである。
【0003】
本発明は、確率的ネットワーク(グラフ)としてモデル化することができる経路に関する。確率的ネットワークは、辺によって接続されるノードを含む。辺は、最適になりうるルートを形成することができる個々の経路を表しており、ノードは、中継点であり、ノードにおいて、特定のルートのために代替の経路を選択することができる。確率的ネットワークでは、辺(経路)を横断するコストは、その辺に関連付けられる確率分布に従ってランダムに生じる。通常、コスト分布は、辺の「長さ」、または辺を横断するのにかかる進行時間を表す。っこのようにして実際に機能している。
【0004】
確率的な最短経路の意味を定義することは難しいので、この問題を形式化するのも難しい。経路をモデル化する辺が、確率分布によってモデル化されるとき、最短経路は、平均値を決定することができるか、平均および分散を最小にすることができるか、または他の指定された判定基準を最小にすることができる。さらに、それらの最短経路は、適応的に、または非適応的に決定することができる。予想される経路長の非適応的な最小化は、決定論的な最短経路問題に帰着するのは明らかであり、適応的な方法が最も一般的である。
【0005】
大部分の従来技術の方法は、出発地から目的地までの予想される経路長を最小にするか、または二基準問題のように、予想される経路長および予想されるコストの組み合わせを最小にする。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)を参照願いたい。
【0006】
いくつかの方法は、経路長の非線形関数を最適化する。他の方法は、決定理論的枠組みを定義する。R. P. Loui著「Optimal paths in graphs with stochastic or multi-dimensional weights」(Communications of the ACM, 26:670-676, 1983)を参照願いたい。そこでは、最適経路は、ある種の単調増加する効用関数に対して予想される効用を最大にする。
【0007】
期限前に到着する確率を最大にする最短経路を見つけるための適応的な方法が、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)によって記述される。非線形目的関数によるこのタイプの定式化は、実用上おそらく最も有用であるにもかかわらず、多数のレベルから(たとえばいくつかの例を挙げると、組み合わせ、分布、解析および機能のレベルから)その問題の難しさが生じて積み重なるので、ほとんど存在しない。たとえば、ランダム性がない場合には、その問題の組み合わせ特性は、近似するのが難しいことがある。グラフ構造が存在しない場合には、その目的関数は、最適化するのが難しいことがある。
【0008】
確率的最短経路モデルは、実効的に、上記の難しさを低減することができる。
【0009】
確率論的最短経路を取り扱う大部分の従来技術の方法は、適応的な過程を用いる。そこでは、最良の次の経路の選択は、そこまでに実現された辺長についての情報に基づく。適応的な方法の大部分は、予想される長さを最小にすることに焦点を当てている。長さの非線形関数を最小化することを考慮するものはほとんどなく、近似的な発見的過程を与えるだけである。
【0010】
最も関連する方法は、Louiの方法である。Louiは、単調で、かつ減少しない経路長の一般的な効用関数を検討し、その効用関数が線形関数であるか、または指数関数であるときにだけ、予想される効用が辺長に分離可能になることを証明する。その場合に、従来の最短経路過程によって、予想される効用を最大にする経路を求めることができる。一般的な効用関数の場合に、Louiは、経路を確実に列挙することに基づく過程を記述する。
【0011】
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)を参照願いたい。
【発明の開示】
【発明が解決しようとする課題】
【0012】
本発明の実施の形態は、ある所定の制約、たとえば、期限がある中で、出発地から目的地までの最小コスト(最短)経路を見つけるための方法を提供する。
【課題を解決するための手段】
【0013】
それらの経路は、ノードおよび辺からなる確率的ネットワーク(グラフ)としてモデル化される。本発明は、辺長(コスト)が独立に、かつランダムに分布しているグラフにおいて、最適経路を見つける問題を考える。
【0014】
その目標は、経路長が、期限時刻のような所与の閾値(制約)を超えない確率を最大にすることである。本発明は、正規分布の辺長の場合に驚くほど厳密な過程を提供し、それは準凸最大化に基づく。
【発明の効果】
【0015】
本発明は、独立したランダムな辺長で確率的最短経路を見つけるための方法を提供する。その方法を用いて、あるコスト制約の下で、出発地から目的地までの最短(最小コスト)経路を見つけることができる。その経路として、期限に間に合うように、または期限前に空港まで行くルート、サービス品質保証またはコスト制御保証を有するネットワークの中でメッセージをルーティングするための経路、または船舶、トラックおよび航空機による商品の運送中継を用いることができる。また、その方法を用いて、モニタリング、保護の応用形態の場合に最も信頼性のあるルート、回線または中継を特定することもできる。また、その方法は、待ち時間保証が望まれる取引処理パイプライン、たとえば、インターネットを利用する販売にも適用することができる。
【0016】
その方法は、動的計画法に基づかない点で独特であることに留意願いたい。その問題は、本質的に離散的であるが、その核心において、連続した最適化からの特性である。
【0017】
注目すべきことに、辺長分布を変更することによって、問題の性質が大きく変更される。加法的な確率優位分布、指数関数分布およびベルヌーイ分布の場合についても、本発明の種々の実施の形態が提供される。
【発明を実施するための最良の形態】
【0018】
確率的最短経路定義
図1は、本発明による、出発地(S)101から目的地(T)102までの経路を表すグラフ100を示す。そのグラフは、ノード110と、ノードを接続する辺120とを含む。形式的には、グラフ100は、G=(V,E)である。ただし、|V|=n個のノードであり、|E|=m個の辺である。それらの辺は、経路を表す。実際の応用形態の場合、辺の数は、何千個にもなることは理解されたい。
【0019】
本発明は、ある制約がある中で、出発地から目的地までの最適経路を見つけるための方法を提供する。本明細書において用いられるときに、最適は、個々の応用形態に応じて、種々の意味を有することができる。最適は、最小コスト、最小時間、制約の中で目的地に到着する最大の確率、または成功する可能性が最も高い経路等を意味することができる。
【0020】
各辺E120は、確率分布として表される、関連する独立確率変数コスト、たとえば、長さ、または進行時間X121を有する。コストの厳密な意味は、特定の応用形態による。コストの確率は、正規分布、加法的に分布、指数関数的に分布、またはベルヌーイ関数に従って分布することができる。コストの正規確率分布は、その平均μおよびその分散σに関して表すことができる。
【0021】
本発明は、制約tを有する。その制約は、出発時刻t131から期限時刻t132までの時間間隔t、すなわちt=t−tとして表すことができる。他の応用形態では、時間以外の制約を用いることができることを理解願いたい。たとえば、その制約として、ある目標を達成するための実際の全予算を用いることができる。
【0022】
本発明は、制約がある中で、たとえば、時間間隔t以内に目的地に到着する確率を最大にする、SからTへの最適経路πを見つけたいこととなる。
【0023】
したがって、出発地から目的地までの全ての取り得る経路πの場合に、下式(1)を解く。
【0024】
【数1】

【0025】
本発明は、同じグラフ上で等価なパラメトリック最短経路問題を構成し、解くことによって最適経路を見つける。そのグラフGは、出発地S101および目的地T102を区別する。各経路π120は、コストパラメータに依存する重みu+λwを与えられる。ただし、uおよびwは、負の値でない重みであり、パラメータλは、範囲[0,∞]の中で変化する。パラメトリック最短経路問題は、最短経路が変化するパラメータ値(区切点)λを見つける。
【0026】
本発明では、区切点の数をパラメトリック最短経路複雑度と呼ぶ。この場合、複雑度は、同じパラメトリック重みの経路を1つとして数えて、空でない開区間[0,∞]の場合に最短である経路の数に等しいことに留意願いたい。本発明では、これらを最適経路と呼ぶ。
【0027】
本発明は、正規分布を用いる確率的最短経路と、パラメトリック最短経路問題との間の関連性を明らかにする。これにより、本発明は、前者のための平均および平滑化された結果を、パラメトリック最短経路環境にも適用できるようになる。
【0028】
図2は、本発明の1つの実施の形態による、グラフ100を通過する最適経路を見つけるための包括的な方法のステップを示す。本発明では、出発地から目的地までの全ての取り得る経路を、辺によって接続されるノードの確率的グラフ100として表す(210)。各辺が、経路のコストに関する独立確率分布と関連付けられる(220)。本発明では、目的地に到着するための制約を定義する(230)。その後、本発明では、そのグラフを、比較的少ない数の決定論的最小コスト問題に変形する。
【0029】
本発明において、「比較的少ない」とは、問題の数が一定であるか、または悪くても辺の数に対して線形であることを意味する。従来技術の解法は、良くても指数関数的であるか、それよりも複雑である。通常、従来技術の方法は、誤差および処理時間に関する既知の限界を用いることなく、近似的な発見的方法を使用する。それに対して、本発明の方法は、立証可能な限界および計算可能な処理時間を与える。ある制約の中で目的地に到着する確率を最大にする最適経路を求めるために、比較的少ない数の決定論的問題が解かれる(250)。決定論的最小コスト過程を用いて、比較的少ない数の候補経路の評価を行うことができる。
【0030】
準凸最大化
本発明では、凸関数、およびその準凸関数への一般化を定義し、それらの大域的な最大値の主な特性を提示している。Cを凸集合とする。
【0031】
定義2.1:集合C内の全てのx、yおよびα[0,1]の場合に、f(αx+(1−α)y)≦αf(x)+(1−α)f(y)である場合には、関数f(C)→(−∞,∞)は、凸関数である。全てのその下位集合が凸である場合には、その関数fは、準凸関数である。
【0032】
非公式には、準凸関数は、任意のレベルにおいて凸断面を有する。
【0033】
定義2.2:本発明では、xが集合C内の2つの他の点の凸結合、すなわち、C内のy、z、範囲(0,1)内のαの場合に、x=αy+(1−α)z⇒y=z=xとして表すことができない場合には、xは、集合Cの極値点であると言う。
【0034】
定理2.3:C⊂Rをコンパクト凸集合とする。集合Cに関して最大値を達成する準凸関数f:C→Rは、Cの極値点において、その最大値に達する。
【0035】
本発明では、いくつかのさらに多くの定義を与える。R内の凸集合の2次元平面200への影は、その平面への凸集合の正投影である。R内の集合Cのドミナントは、C内のある点よりも大きい全ての点の集合、すなわち、集合C内のいくつかのyの場合に{x∈R|x≧yと定義する。
【0036】
正規分布を有する確率的最短経路
それゆえ、図3に示されるように、本発明は、最初にグラフ100を投影する。そのグラフは、幾何学的には複数のノードからなるハイパーキューブ301であり、経路頂点303と経路閉包304とを含む、平均−分散(μ,σ)平面へのハイパーキューブ閉包302を有し、その閉包は、多角形である。その投影における経路頂点303は、経路のコスト121、たとえば、長さまたは時間に対応する。
【0037】
その投影は、以下のように実行される。グラフの中のいずれかの経路の場合に、その経路によってどの辺が用いられるかを指示する、0および1からなるベクトルを構成する。このベクトルは、R|E|内のハイパーキューブの角を指す。ただし、|E|は、辺の数である。有効な経路に対応する、全ての角の凸包は、経路ポリトープと呼ばれる。ポリトープの各頂点は、有効な経路に対応する。
【0038】
また、本発明は、全ての平均パラメータからなり各辺に関連付けられるベクトルと、全ての分散パラメータからなり各辺に関連付けられる別のベクトルとを構成する。これらの2つのベクトルは、R|E|内の平面を張る。本発明は、ポリトープをその平面上に投影して、影、すなわち、凸経路閉包304を得る。影経路閉包の頂点303は、元のグラフの中の経路に対応し、それは、上記の本発明の元のコスト関数に関連するパラメトリックコスト関数を極値化する。最適経路は、多角形の左下にある頂点、すなわち、小さな分散および小さな平均を有する頂点からなる小さな部分集合だけを精査することによって特定される。多角形304内の辺は、意味を持たない。
【0039】
本発明は、正規分布している辺長を有するグラフに準凸最大化を適用する。本発明は、所与の期限時刻tまでに、またはその前に、出発地から目的地まで到着するための最良のルートを選択する。その問題は、時間どおりに空港に到着することのような、不確定の交通条件を有する輸送ネットワークへの現実的な用途を有する。
【0040】
図4は、コストが正規分布するときの変形するステップを示す。本発明は、平均−分散平面上にグラフ100を投影し(410)、最小分散頂点を特定する(440)。また、本発明は、最小平均頂点も特定し(420)、ルートが時間どおりである確率が0.5未満であるか否かを判定する(430)。0.5未満でない場合には、本発明は、分散頂点を昇順に列挙し(450)、0.5未満である場合には、最初に最小分散頂点を特定し(440)、その後、列挙する(450)。これは、最適である可能性があり、その問題が解かれる必要がある、少数の取り得る候補経路を与える。その後、本発明は、各経路が時間どおりである確率を求め、最適経路を選択する。
【0041】
各辺iが独立正規分布の長さX〜N(μ,σ)121を有するものと仮定する。ただし、μは、平均であり、σは、分散である。本発明の目標は、以下の値を最大にすることである。
【0042】
【数2】

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

【0045】
ただし、Φ( )は、標準正規確率変数N(0,1)の累積分布関数である。Φは、単調増加するので、その問題は、その引数を最大にするST経路を見つけることと同じである。
【0046】
【数4】

【0047】
式(3)の目的は、辺のコストに分離することはできず、準最適性を満たさない。それゆえ、下部構造に基づく動的計画法は、失敗する。目的関数の特性をさらに十分に理解するために、本発明は、その目的関数を、R内の経路ポリトープにわたる連続最適化問題として定式化する。ただし、mは、辺の数である。
【0048】
本発明では、全ての辺120を1、2、・・・、mによって添え字を付けて、その入射ベクトルxによって各辺部分集合を表し、辺iがその部分集合内に存在する場合には、x=1であり、そうでない場合には、x=0である。辺の全ての2個の部分集合は、R内の単位ハイパーキューブの頂点に対応する。ST経路ポリトープ、略して経路ポリトープは、単純なST経路の入射ベクトルの凸包である。ポリトープは、R内の単位ハイパーキューブの部分集合であり、ポリトープの頂点は、ハイパーキューブの頂点の部分集合である。したがって、最適なST経路は、下式(4)を最大にするための解である。
【0049】
【数5】

【0050】
ただし、本発明では、{0,1}によって長さmの0−1ベクトルの集合を表す。
【0051】
経路ポリトープをベクトルμ=(μ,・・・,μ)およびσ=(σ,・・・,σ)の張られた空間上に投影することによって、凸経路閉包304が定義され、本発明では、それを経路ポリトープ影と呼ぶ。
【0052】
式(4)の目的は、分離不可能であり、決して一次および二次ではなく、凸ですらない。これは、その目的を計画法および組み合わせ最適化問題の範疇に入れるので、一般的な効率的解法は存在しない。通常、整数制約が主な問題を引き起こすが、この場合には、部分的に見たとしても、この問題を如何にして解くかは明らかではない。
【0053】
結局、本発明の目的は、特別な構造を有し、その構造によれば、その最大値は、実現可能な集合の境界上に位置せざるを得ないということがわかる。詳細には、その構造は、経路ポリトープの集合において準凸であり、そのポリトープの残りの部分集合においては、μxおよびσxに関して単調である。本発明は、経路ポリトープ、さらにはその影の境界の多項式記述を持たないので、これは都合が良いとは言えない。
【0054】
たとえば、経路ポリトープ影の最も右側で、かつ最も上側の頂点を計算することは、それぞれ辺平均および辺分散に関して最長経路を見つけることに対応する。それゆえ、経路凸包の計算は、一般的には、強くNP−hardである。一方、極値点は、線形目的λμ+(1−λ)σ(ただしλ[0;1])を最適化するので、本発明は、影閉包のドミナントにおいて極値点を効率的に見つけることができる。
【0055】
以下に記述される本発明の主要な定理3.3は、最長経路問題が発生しないようにする十分に早い出発時刻の場合に、本発明の目的が準凸であることを示す。本発明では、最初に、確率的およびパラメトリック最短経路問題の対応についての補助定理を述べる。
【0056】
補助定理3.1:ベクトルu=(u,・・・,u)、w=(w,・・・,w)によって張られる平面上の経路ポリトープドミナントの影上の極値点と、辺重みu+λwを用いるパラメトリック最短経路問題の区切点との間には、1対1対応がある。
【0057】
補助定理3.1によれば、パラメトリック最短経路問題の複雑度に応じて、影ドミナントにおける極値点の数にも、それに相当する限界があることを意味する。
【0058】
定理3.3.期限tが最小平均経路の平均以上であるとき、式(4)に対する解は、経路ポリトープ影のドミナントの極値点である。
【0059】
証明
本発明は、最初に、式(4)の変形された形を考える。x=μおよびx=σxと表す。この系は、以下の条件と等価になる。
【0060】
【数6】

【0061】
下式で示される誘導された目的は、実現可能な集合S( ̄)の部分集合において準凸である(ここで、表記( ̄)は、その前の符号の上部に ̄が付くことを意味する)。
【0062】
【数7】

【0063】
その集合S( ̄)は、t未満の平均を有する経路が存在するものと仮定すると空ではない。x=μx<tであるので、この実現可能な部分集合におけるf(x,x)の値は正であり、最大値を含まなければならない。それゆえ、目的関数f(x,x)は、実現可能な集合S( ̄)、すなわち、x=tの左にある経路ポリトープ影において準凸である。定理2.3によれば、最大値は、集合S( ̄)の極値点にある。それゆえ、f(x,x)は、xおよびxの両方において単調に減少するので、その解は、x=tの左にある、影のドミナントの極値点である。
【0064】
ところで、影の任意の極値点は、元の経路ポリトープmの極値点の投影であり、mは、整数座標を有する。それゆえ、式(4)の緩和された問題の最適な解は、式(5)の整数問題への解でもある。影ドミナントにおける各極値点は、以下の線形計画minへの解である。
c≧0の場合に、x∈影経路ポリトープを条件として、
min cx
【0065】
同じように、各極値点は、c+cを最小にする経路に対応する。ただし、xは、その経路の全平均であり、xは、全分散であるので、c、c≧0の場合に、それは任意の最短経路過程を介して見つけることができる。
【0066】
影ドミナントにおける全ての極値点を見つけるために、本発明は、2つの端点、すなわち、最小平均を有する経路に対応する最も左側の点、および最小分散の経路である最も下側の点で開始する。
【0067】
それらの点を見つけるとき、本発明では、それらの点を、π=(m,s)、π=(m,s)∈Rと表す。ただし、mは、経路πの平均であり、sは、分散である。その後、本発明では、m≠0である場合には、(c,c)=(−(s=s)/(m−m))で、そうでない場合には、(c,c)=(1,0)で式(6)を解く。新たな解をπ=(m,s)と仮定する。πおよびπのいずれとも異なる場合には、本発明は、経路πとπとの間、πとπとの間等の頂点を見つけるために、その手順を繰り返す。このようにして、本発明が影上の全ての頂点を見つけることは明らかであろう。
【0068】
出発時刻が期限に近く、任意の最短経路がtよりも大きな平均を有するときに、その計画の最適値は、負になり、目的関数は、経路の平均に関して減少していき、分散に関して増加していく。この場合、緩和された計画に対する解は、最も低い平均の最も左にある極値点と、最も高い分散の最も上にある極値点との間にある、影の左上境界上にある。最も高い分散を有する簡単な経路を見つけることは、強くNP−hardだからである。
【0069】
本発明は、良好な多項式−時間近似を見つけることは期待しない。さらに、式(5)の目的関数は、{x|x>t}で横切られる実現可能な集合において、もはや準凸ではない。本発明が分数解を見つけることができる場合であっても、式(4)に対する整数解と一致することは保証されない。
【0070】
本発明では、おそらく単純でない経路を含む場合がある擬似多項式過程を記述し、それは、ノードの数nおよび最大辺分散σに関する多項式である。この過程は、以下のように、動的な計画表を構成する。
【0071】
経路分散の取り得る値s=0,1,・・・,σ毎に、かつノードv毎に、出発地Sから分散sおよび最小平均のノードvまでの経路上にある、ノードvの先行ノードを求める。最後には、本発明は、取り得る分散sと、その分散値のための最小平均毎に1つずつの、出発地から目的地までのσ個の経路を有する。
【0072】
より厳密には、ノードvおよび分散s毎に、本発明は、準最適な方程式を解く。
【0073】
【数8】

【0074】
ただし、Φ(v,s)は、出発地から、厳密にsである分散のノードvまでの最小平均経路の平均である。経路π(v,s)は、その経路上にあるノードvの先行ノードであり、ノードvの隣接するノードvである。辺長が独立しているという仮定は、経路分散を、辺分散の和として分離できることを確保することに留意願いたい。
【0075】
その後、本発明は、分散sの部分的に最適化された値毎に、目的関数値(t−経路平均)/(√(経路分散))を計算することによって、最適なST経路を見つけ、最小目的値を有する経路を選択する。
【0076】
平均および平滑化された複雑度
辺重みベクトルu、wが、わずかに摂動する、一様にランダムな単位ベクトルまたは束縛ベクトルである場合には、経路ポリトープ影上の極値点の予想される数は、線形であり、結果として、上記の本発明の過程の予想される多項式実行時間は、小さい。本明細書において記述される技法は、線形計画法のための多項式シンプレックス過程のための技法を基にしている。
【0077】
経路ポリトープPの頂点は、単位ハイパーキューブの頂点の部分集合であり、詳細には、
事実1:ポリトープPの各辺は、少なくとも1の長さを有し、
事実2:ポリトープPは、単位ハイパーキューブに含まれ、そのハイパーキューブは、√(半径m)/2の球内に含まれることに留意願いたい。
【0078】
平均限界
定理4.1:u、w∈R2を一様にランダムな単位ベクトルとし、Vをその張られた空間とする。そのとき、V上へのPの投影の辺の数の期待値は、大きくても2×√(2)×mである。
【0079】
証明:事実2によって、V上へのPの影の周囲は、π×√(m)によって画定される。次に、ポリトープPの辺I毎に、その影内に辺Iが現われる事象をS(V)によって表し、l(I)を、その影内の辺の長さとする。その影内の予想される辺長の和は、大きくても、最も大きな取り得る周囲に等しい。
【0080】
【数9】

【0081】
以下の補助定理4.2によれば、以下の式が成り立つ。
【0082】
【数10】

【0083】
それゆえ、以下の式が成り立つ。
【0084】
【数11】

【0085】
ただし、mは、ポリトープPの次元であり、本発明の場合には、確率的ネットワークの辺の数である。
【0086】
補助定理4.2:ポリトープPの全ての辺Iの場合に、以下の式が成り立つ。
【0087】
【数12】

【0088】
証明:ポリトープの辺Iが影の中に現われる場合には、その辺は、投影面Vと小さな角度をなす。
【0089】
【数13】

【0090】
ポリトープP内の任意の辺は、少なくとも1の長さを有するので(上記の事実1による)、影の中の辺の長さは、少なくともcos(θ(V))であり、その影内に辺が現われる期待値は、以下のようになる。
【0091】
【数14】

【0092】
平滑化された限界
本発明では、本発明の平均ケース限界を厳密にして、平滑化された解析を得る。すなわち、一様にランダムな2D−平面上に投影するのではなく、本発明では、任意の、そしておそらく最悪ケースの2D平面で開始し、その平面をわずかに摂動させる。その後、本発明では、本発明の2D平面上へのPの投影の辺の予想される数が、mに関する多項式であり、摂動の大きさに関して逆多項式であることを立証する。
【0093】
2D平面上の本発明の分布は、指数関数的な確率変数を含む。期待値λで指数関数的に分布する変数xは、全てのt≧0の場合に、以下の累積密度関数を有することとなる。
【0094】
【数15】

【0095】
そして、下式の確率密度を有することとなる。
【0096】
【数16】

【0097】
これにより、本発明では、ベクトルの摂動を定義できるようになる。
【0098】
定義4.3:任意のρ>0、および任意の単位ベクトルuの場合に、本発明では、uのρ−摂動を、以下のように選択されたランダムな単位ベクトルvであると定義する:
範囲[0,π]に限定して、期待値ρの指数関数分布から角度θ∈[0,π]をランダムに選択する。uとθの角度をなすベクトルの集合から一様にランダムにvを選択する。結果は、以下の通りである。
【0099】
定理4.4:U=span(u,u)を任意の2D平面とする。vおよびvをそれぞれuおよびuのρ−摂動とし、V=span(v,v)とする。ρ<1/(√(m))の場合に、V上へのPの投影の辺の予想される数は、多くても、4π×√(2m/ρ)である。セクション4.1において用いられたのと同じ引数によって、これは、以下の補助定理に従う。
【0100】
補助定理4.5:上記で定義された確率変数の場合に、以下の式が成り立つ。
【0101】
【数17】

【0102】
この補助定理によれば、それらの値のうちの一方が一様にランダムである必要があるのとは対照的に、vおよびvは、いずれも、ρ−摂動分布から引き出すことができるようになる。
【0103】
当然、摂動が小さくなると、その定理における限界も弱くなる。補助定理3.1によれば、これらの限界は、グラフの辺の数、平均および同様のパラメトリック最短経路問題における最適経路の数に対する平滑化された限界に関して線形であることを暗示することに留意願いたい。
【0104】
加法的分布、指数関数分布およびベルヌーイ分布
本発明では、本発明のモデルを、正規分布以外の分布に拡張する。一定の第2のパラメータを有するポアソン分布またはガンマ分布、またはさらに包括的には、加法的であり、かつ確率優位を満たす分布に由来する辺長の場合、本発明は、その問題が、対応する分布のパラメータに等しい辺重みを有する決定的最短経路問題に帰着することを立証する。指数関数およびベルヌーイ確率変数の場合、その和は、厳密に計算することが難しいので、本発明では、多項式時間近似方式および準多項式時間近似方式、それぞれPTASおよびQPTASを用いる。
【0105】
ポアソン分布およびガンマ分布
レート(平均)μおよびμを有する2つの独立したポアソン確率変数の和は、その和に等しい平均を有する別のポアソン確率変数である。さらに、ポアソン分布は、確率優位を満たす。すなわち、低い方のレートμの場合のその累積分布関数は、高い方のレートμの場合の累積分布関数よりも完全に大きい。
【0106】
図5は、コストの確率分布が加法的であるときに最短経路を見つけるための方法を示す。各辺が、重みLを付される(510)。決定論的最小コスト過程が、重み付けされた辺に適用され(520)、最適経路を出力することができる(530)。
【0107】
具体的には、D(λ)を任意の単一のパラメータ加法的分布とする。すなわち、分布D(λ)およびD(λ)を有する2つの独立確率変数の和は、同じ分布と、和D(λ+λ)に等しいパラメータとを有する別の確率変数である。
【0108】
また、本発明では、D(λ)を用いて、この分布を有する確率変数も表す。さらに、分布Dが確率優位、すなわち、Pr(D(λ)≦t)≧Pr(D(λ)≦t)、ただし、λ≦λを満たすものと仮定する。
【0109】
そのような分布の別の現実的な例は、一定の形状パラメータbを有するガンマ分布gamma(a,b)である。これは、任意の平均(分散)を有するが、平均対分散比が一定である一群の確率変数を定義する。
【0110】
辺iのランダム長がX〜D(λ)であると仮定する。ここで、分離不可能な目的関数であるにもかかわらず、確率優位とともに、分布の加法性が、その問題を分離可能にする。
【0111】
【数18】

【0112】
ただし、最後の不等式は、分布の確率優位特性から得られる。こうして、経路は、その分布パラメータが小さい場合に限って、閾値tを超えない高い確率を有する。この場合、最適経路は、そのリンクに沿って、分布パラメータの和が最も小さな経路であり、決定論的最短経路過程を適用すること(520)によって厳密に見つけることができる。
【0113】
指数関数PTASおよびベルヌーイQPTAS
ポアソン分布とは異なり、指数関数分布およびベルヌーイ分布は、加法的ではない。それゆえ、目的確率関数のための単純な閉じた形の式を立てることはできない。本発明では、確率分布の量子化を介する動的計画法に基づく、多項式−時間近似方式を記述する。
【0114】
図6は、確率分布が指数関数またはベルヌーイ関数であるときに最短経路を見つけるための方法を示す。本発明は、上記のようなグラフ、制約で開始し、近似パラメータも供給する(610)。本発明は、辺を2つの集合、すなわち、大きなパラメータの1つの集合および小さな辺の1つの集合に分割する(620)。大きな辺が量子化される(630)。グラフ内の大きな辺および小さな辺と、特定のノードvとの取り得る組み合わせ毎に、出発地からノードvまでの辺の組み合わせと一致するあらゆる経路を特定する(640)。特定された経路は、ある決定論的最小コスト過程で評価し、上記のように最大確率を有する経路を選択するための少数の経路である(650)。
【0115】
より厳密には、本発明は、二基準近似を与え、それは、遅延許容値pを与えられ、ε>0の場合に、以下の式を満たす経路πを見つける。
【0116】
【数19】

【0117】
定理5.1:近似的な最適経路は以下の式によって与えられる。
【0118】
【数20】

【0119】
ベルヌーイ分布の場合に、類似の量子化によって、準多項式時間近似方式がもたらされる。
【0120】
本発明の具体的な実施の形態は、最小コスト経路の応用形態を用いて記述されてきたが、同じ基本的な技法を他の応用形態の場合にも用いることができることを理解願いたい。たとえば、そのグラフは、初期条件(出発地)から目標(目的地)を達成するために取り得る方法を表すことができる。この場合、確率分布は、その目標を達成する各ステップに関連付けられる不確定のコストを表し、制約は、コストを割り当てられた全コストの範囲内に抑えることである。
【0121】
別法では、出発地は、ある過程または機械の初期状態にすることができ、目的地は最終状態にすることができる。この場合、辺は、状態遷移およびその関連するコストを表す。ここでは、その方法は、最終状態に達するための最適な1組の遷移を見つける。
【図面の簡単な説明】
【0122】
【図1】本発明の1つの実施の形態における出発地から目的地までの経路を表すグラフである。
【図2】本発明の1つの実施の形態における最適経路を見つけるための方法の流れ図である。
【図3】平均−分散平面上への図1のグラフの投影図である。
【図4】本発明の1つの実施の形態における確率分布が正規分布である場合の最適経路を見つけるための方法の流れ図である。
【図5】本発明の1つの実施の形態における確率分布が加法的である場合の最適経路を見つけるための方法の流れ図である。
【図6】本発明の1つの実施の形態における確率分布がベルヌーイ関数である場合の最適経路を見つけるための方法の流れ図である。

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

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate


【公開番号】特開2008−77636(P2008−77636A)
【公開日】平成20年4月3日(2008.4.3)
【国際特許分類】
【外国語出願】
【出願番号】特願2007−199040(P2007−199040)
【出願日】平成19年7月31日(2007.7.31)
【出願人】(597067574)ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】201 BROADWAY, CAMBRIDGE, MASSACHUSETTS 02139, U.S.A.
【Fターム(参考)】