経路探索方法、プログラム及びシステム
【課題】 A*探索技法において、上限値と下限値の精度を向上させることにより、探索速度を向上させること。
【解決手段】 経路探索される、もととなる重み付きグラフに対して、複数のランドマークを選択し、ランドマーク間の最短経路長、及び各頂点から、近くのランドマークへの最短経路長を計算し、後で参照できるように、記憶装置に記録する。
また、2つの頂点v,wとそれにそれぞれ近接する2つのランドマークの2つの頂点からなる四角不等式から導かれる式に基づき、v,wに対応する最短経路長の上下限値を計算するルーチンが用意される。これらのルーチンは、A*探索プログラムからの呼び出しに応じて、予め記憶装置に記録されている、ランドマーク間の最短経路長及び、各頂点から近くのランドマークへの最短経路長のデータを参照して、v,wに対応する最短経路長の上限値または下限値を返す。
【解決手段】 経路探索される、もととなる重み付きグラフに対して、複数のランドマークを選択し、ランドマーク間の最短経路長、及び各頂点から、近くのランドマークへの最短経路長を計算し、後で参照できるように、記憶装置に記録する。
また、2つの頂点v,wとそれにそれぞれ近接する2つのランドマークの2つの頂点からなる四角不等式から導かれる式に基づき、v,wに対応する最短経路長の上下限値を計算するルーチンが用意される。これらのルーチンは、A*探索プログラムからの呼び出しに応じて、予め記憶装置に記録されている、ランドマーク間の最短経路長及び、各頂点から近くのランドマークへの最短経路長のデータを参照して、v,wに対応する最短経路長の上限値または下限値を返す。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は、カーナビゲーション・システムなどで利用される経路探索技法に関し、より詳しくは、経路探索を高速化するための方法、プログラム及びシステムに関するものである。
【背景技術】
【0002】
近年、カーナビゲーション・システムや、ウェブサイトにおける最適交通路探索サービスの増加により、コンピュータにより経路を探索する、より高速化された技法への要望が高まっている。このことは、コンピュータ・サイエンス的には、重み付きグラフにおける、最短経路の決定アルゴリズムに帰着される。
【0003】
ところで、重み付きグラフにおける、最短経路の決定アルゴリズムの、古典的とも言える技法として、ダイクストラ法と呼ばれるものが知られている。これは要するに、重み付きグラフGにおいて、頂点aから頂点zへの最短経路を決定するにあたって、aからある他の頂点への最短経路を決定し、次に、そうして見つかった他の頂点を対象から外して、残りの頂点に対して同様のことを行い、残りの頂点がなくなったとき、手続を完了する、というものである。このアルゴリズムは、必ず解が存在することを保証するが、グラフGの頂点の数が増えてくると、計算量の点で、現実的なものでなくなる。
そこで、計算量の点でより改善された、さまざまな技法が提案されてきた。そのようなものの1つとして、A*探索と呼ばれる技法がある。これは、予め計算された任意の2頂点間の最短経路長の上下限値を利用して、最短経路の計算を高速化するものであり、具体的には、下記のような技法である。
【0004】
以下で、頂点 v, w について d(v,w) は、vからwへの最短経路長を表すものとする。また、w(v,w)を、vとwを結ぶ枝の長さとする。
先ず、初期設定として、始点sから終点tまでの最短経路を求めたい場合、各頂点vについて以下のように定める。
k(v): v=s のとき k(s):=π(s)、v≠sのときk(v):=∞;
d(v): v=s のとき d(v):=0、v≠sのときd(v):=∞;
prev(v) = NULL;
頂点集合 S = {s};
そうして、次のようにして探索処理を行う。
while( Sが空でない ) {
S から k(v)の値が最も小さい頂点vを除去;
for(vから出ている全ての枝(v,w) について以下の操作を行う) {
if( k(w) > k(v) + w(v,w) - π(v) + π(w)) {
k(w) := k(v) + w(v,w) -π(v)+π(w);
d(w) := d(v) + w(v,w);
prev(w) := v;
if (d(w)+π(w) <= min(d(s,t) の上限値, d(t)))
{ S ← S ∪{w}; }
}
}
}
最後に、d(t) に入っている値が最短経路長になる。
また、prev(t) に入っている頂点を t'、prev(t')に入っている頂点を t'' ・・・とすると、 t←t'←t''←・・・←s が最短経路になる。
【0005】
任意の2頂点 v, w について、d(v,w) の上限値と下限値が正しく与えられるとき、上記のA*探索が正しく最短経路を求めることが知られている。また、A*探索に与える上下限値の精度が良ければ良いほど終点まで速く到達できることが知られている。直感的には、アルゴリズム中のk(v) には、始点sからvを経由して終点tに到達する経路の最短経路長の下限値、d(v)には始点 s からvまでの最短経路長が格納される。
【0006】
そこで、上記のA*探索アルゴリズムでブラックボックスになっている部分(d(v,w)の上下限値を計算する方法)が、従来より課題になっている。
【0007】
これに関連して先ず、Computing the Shortest Path: A* Search Meets Graph Theory by A. V. Goldberg and C. Harrelson, in Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005.という文献に記載された手法がある。
この手法では、グラフ上の少数(十数個)の頂点を「ランドマーク」として選択し、ランドマークから各頂点への最短経路長を記憶しておく。そして、記憶しておいた最短経路長を利用して任意の2頂点間の最短経路長の下限値を算出し、A*探索による探索を高速化する手法である。
【0008】
また、Goal Directed Shortest Path Queries Using Precomputed Cluster Distances by Jens Maue, Peter Sanders, Domagoj Matijevic, in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA-06), LNCS 4007, 316-327, Springer, 2006.も知られている。
この手法では、グラフを多数のクラスターに分割し、各クラスター間の最短経路長を定義し、記憶しておく。そして、記憶しておいた最短経路長を利用して、任意の2頂点間の最短経路長の上限値と下限値を算出し、最短経路長の上限値による枝刈りとA*探索を組み合わせて高速化する手法である。
【0009】
いずれの手法も、A*探索で利用する「任意の2頂点間の最短経路長の上下限値」の精度がアルゴリズムの高速化に大きく寄与している。[1]の手法では、下限値計算時に複数のランドマーク情報を利用するが、ランドマーク自体の数が少ないことが欠点である。[2]の手法では、クラスターの数自体は沢山あるが、上下限値計算時に利用するクラスター情報の数が少ないことが欠点である。
【0010】
この他にも、従来技術として特開2006−201174という特許公開公報に開示されている技術があるが、その発明者の一人は、上記文献[1]にも著者としてリストされており、その開示内容も、上記文献[1]とほぼ重なるものである。
【非特許文献1】[1] Computing the Shortest Path: A* Search Meets Graph Theory by A. V. Goldberg and C. Harrelson, in Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005.
【非特許文献2】[2] Goal Directed Shortest Path Queries Using Precomputed Cluster Distances by Jens Maue, Peter Sanders, Domagoj Matijevic, in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA-06), LNCS 4007, 316-327, Springer, 2006.
【特許文献1】特開2006−201174
【発明の開示】
【発明が解決しようとする課題】
【0011】
この発明の目的は、経路探索を高速化するための技法を提供することにある。
より詳しくは、この発明の目的は、A*探索を用いた経路探索において、任意の2頂点間の最短経路長の上下限値の精度を向上させることによって、経路探索を高速化することにある。
【課題を解決するための手段】
【0012】
本願発明者は、研究を重ねた結果、下記のような手法により、経路探索が高速化されることに想到した。
すなわち、先ず、経路探索される、もととなる重み付きグラフに対して、ランドマークを生成し、上下限値の計算に必要な情報が予め、計算される。
次に、最短経路長の上下限値が計算される。特に、本発明は、この計算のために、頂点vの近くのランドマークLvと、頂点wの近くのランドマークLwの4点で構成される四角不等式に着目するものであり、下記のような式が、上下限値の計算に利用される。
d(v,w)の下限値:d(v,w)>=d(Lv,Lw)-d(Lv,v)-d(w,Lw)
d(v,w)の上限値:d(v,w)<=d(v,Lv)+d(Lv,Lw)+d(Lw,w)
これらの不等式の右辺の値は全て、上記のランドマークの生成に関連して、予め計算され保存されていることに留意されたい。
この上限値と、下限値の計算ルーチンは、後のA*探索に適宜呼び出されて利用される。
【発明の効果】
【0013】
この発明によれば、最短経路長の上下限値の精度の向上が達成され、この結果、経路探索の時間が短縮される。発明者の実験によれば、特定のグラフの探索に関して、上記文献[2]の手法よりも、4倍以上の探索性能の向上が確認された。
【発明を実施するための最良の形態】
【0014】
以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
【0015】
図1は、本発明の手法を実施するためのハードウェア構成のブロック図である。図1において、コンピュータ100は、CPU102と、メイン・メモリ104をもち、これらは、バス106に接続されている。メイン・メモリ104は、少なくとも512MB、好適には、1GB以上の記憶容量をもつものである。後述するグラフの全頂点データなどをロードするためには、メイン・メモリ104の容量は、大きい程好ましい。CPUは、好適には、32ビットまたは64ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium(R) 4、AMD社のAthlon(R)などを使用することができる。バス106には、ディスプレイ・コントローラ108を介して、LCDモニタなどのディスプレイ110が接続される。ディスプレイ110は、本発明に係る、処理用に書かれたプログラムを眺めたり、編集したりするために使用される。また、本発明に従い、探索した経路を表示するためにも使用される。バス106にはまた、IDEコントローラ112を介して、ハードディスク114と、CD−ROMドライブ116が接続される。ハードディスク114には、オペレーティング・システム、コンパイラその他のプログラムが、メインメモリ104にロード可能に記憶されている。ハードディスク114は、少なくとも40GB、好適には、160GB以上の記憶容量をもつものである。CD−ROMドライブ116は、必要に応じて、CD−ROMからプログラムをハードディスク114に追加導入するために使用される。バス106には更に、キーボード・マウスコントローラ118を介して、キーボード120と、マウス122が接続されている。キーボード120及びマウス122は、コンパイラを使用して、本発明に係る処理を実行させるプログラムを書いたり、実行させたりするために使用される。
【0016】
コンピュータ100のソフトウェア的な環境について更に説明すると、上記オペレーティング・システムとしては、Linux(R)、マイクロソフト社のWindows XP(R)、Windows(R)2000、アップルコンピュータのMac OS(R)などを使用することができるが、ここに掲げたオペレーティング・システムには限定されない。本発明の処理用のプログラムを作成するためのコンパイラは、使用するオペレーティング・システムの上で、動作し得る、マイクロソフト社のVisual Basic(R)、Visual C++(R)、Visual Studio(R)、ボーランド社のBorland(R)C++ Compiler 5.5、Delphi(商標)、C++ Builder(商標)、IBM社のVisualAge for Java(商標)などがあり、これらの任意のものを使うことができる。コンパイラは、GUIをサポートしておらず、CUIベースだけのものでも、本発明の機能を実現することができる。
【0017】
図2は、この実施例の高レベル機能ブロック図である。図2において、グラフ全頂点データ202は、重み付きグラフを、コンピュータ可読な形式で、ハードディスク114に保存したものであり、各頂点に対応するデータを保持する。経路探索アプリケーションの場合、重み付きグラフの各頂点は、各々が、各地点に対応する。また、この実施例では、グラフは、無向グラフである。
【0018】
グラフの各頂点には、好ましくは、1から連番で番号が付与され、そのデータ形式は、図3に示すように、各頂点毎に、隣接する頂点の番号のリストへのリンクと、隣接する頂点への距離のリストへのリンクとを含む。尚、このようなデータ形式は、可能ないくつかの選択肢のうちの1つであり、本発明が想定するグラフ表現のデータ形式は、これに限定されるものではないことを、当業者なら理解するはずである。
【0019】
図4には、具体的なグラフの頂点の配置の例が示されている。すなわち、図4では、n番目の頂点は、nを丸で囲って表示されている。図4で、頂点1は、隣接する頂点として、頂点2、5及び8をもち、それぞれへの距離は、4.0, 5.0, 2.5である。頂点2は、隣接する頂点として、頂点1、4及び5をもち、それぞれへの距離は、4.0, 3.5, 3.0である。図3には、ハードディスク114から、メイン・メモリ104上に、前処理部212が処理可能にロードされた、頂点1及び頂点2のデータ構造が示されている。
これを、例えば、C言語の構造体で記述すると、下記のようになる。
struct Node {
int NodeID; // 頂点番号
int *adjNodeList[]; // 隣接する頂点の頂点番号を配列として記憶
double *adjDistanceList[]; // 隣接する頂点までの距離を配列として記憶
};
図4の頂点1に、この構造体を適用すると、NodeID = 1, *adjNodeList = {2,5,8}, *adjDistanceList = {4.0, 5.0, 2.5} となる。
【0020】
図2に戻って、前処理部212、上限値計算部214、下限値計算部216、探索方向決定部218、及びクエリー処理部220は、この実施例に処理を行うように、好適には、CまたはC++で書かれ、ハードディスク114に記憶されているプログラムであり、キーボード120またはマウス122の操作により、オペレーティング・システムの動作で、ハードディスク114から、メイン・メモリ104にロードされる際に、CPU102の働きで、実行されるものである。
【0021】
また、好適には、前処理部212、上限値計算部214、下限値計算部216、探索方向決定部218、及びクエリー処理部220がメイン・メモリ104に際に、または、後のユーザーの操作に応答して、グラフ全頂点データ202が、ハードディスク114から、図3に示すようなグラフ全頂点データ202'として、例えば、C言語のmalloc()のような関数を呼び出してメモリ領域を確保しながら、メイン・メモリ104にロードされる。このとき、後の処理の高速化のために、グラフ全頂点データ202の全体をメイン・メモリ104にロードすることが望ましい。
【0022】
しかし、メイン・メモリ104の容量が十分でない場合、あるいは、グラフ全頂点データ202がの頂点の数が非常に多い場合は、このようにグラフ全頂点データ202の全体をメイン・メモリ104にロードできないことがある。そのような場合、例えば、次のような方法が考えられる。すなわち、許される限りのメイン・メモリ104の領域を確保しておき、そこに可能な限りのグラフ全頂点データ202の頂点のデータをロードしておく。そうして、前処理部212が、ある頂点vのデータを、メイン・メモリ104にロードされた頂点データ202'中で探し、もし見つかれば、そのデータを前処理部212は利用する。もし見つからなければ、例えば、見つからなかった頂点のデータを含むあるまとまりの頂点データを、ハードディスク114に記録されているグラフ全頂点データ202からメイン・メモリ104にロードし、頂点データ202'の領域の一部に置換することにより、前処理部212が参照可能となるようにすることができる。
【0023】
このようなグラフ全頂点データ202をメイン・メモリ104にロードするためのメモリ管理ルーチンは、必要に応じて予め用意されるものであるが、オペレーティング・システムが提供するAPI関数やC言語の標準ライブラリ関数等を用いて慣用の技術で実現できるものであるため、ここでは、これ以上詳述しない。
【0024】
後で詳しく説明するが、前処理部212は、好適には、メイン・メモリ104にロードされたグラフ全頂点データ202'から個々の頂点データを読み取って、全ランドマーク間の最短経路長のデータ204と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206を生成し、後で読み出し可能に、ハードディスク114に記憶する機能をもつ。なお、全ランドマーク間の最短経路長のデータ204と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206は、好適には、上限値計算部214及び下限値計算部216が高速でアクセスできるように、データ204'及びデータ206'として、メイン・メモリ104にロードされる。
【0025】
上限値計算部214は、メイン・メモリ104にロードされた、全ランドマーク間の最短経路長のデータ204'と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206'を参照して、後述する手順により、頂点の上限値を計算して提供する機能をもつ。上限値計算部214は、他のプログラムまたはモジュールから呼び出され、好適には倍精度浮動小数点数として上限値の値を返す、サブルーチンまたは関数として実装される。
【0026】
下限値計算部216は、メイン・メモリ104にロードされた、全ランドマーク間の最短経路長のデータ204'と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206'を参照して、後述する手順により、頂点の下限値を計算して提供する機能をもつ。下限値計算部216は、他のプログラムまたはモジュールから呼び出され、好適には倍精度浮動小数点数として下限値の値を返す、サブルーチンまたは関数として実装される。
【0027】
クエリー処理部220は、実際の出発頂点と、宛先頂点の指定を受けて、それらの頂点間の最短経路を探索し、その結果を返す機能をもつ。クエリー処理部220は、A*探索に基づき、必要に応じて上限値計算部214と、下限値計算部214を呼び出して上限値と下限値を利用するとともに、探索方向決定部218を利用して、探索方向を決定することにより、経路探索を行う機能をもつ。
【0028】
以下、前記各処理モジュールの動作を、フローチャートを参照して、説明する。図5を参照すると、前処理部212の動作フローチャートが示されている。図5のステップ502では、グラフGの頂点から、L個の頂点がランドマークとして選ばれる。L個のランドマークは、グラフGにおいて、なるべく均一に分布するように配置すのが望ましい。本発明者の実験によれば、ランドマークの個数Lは、グラフGの頂点の数をNとすると、L=N1/2個程度、あるいはそれ以上にすればよいことが分かった。
【0029】
ランドマークを選択する1つの方法は、下記のようなものである。
・グラフに配置された頂点を全て含む最小の矩形を取る。
・矩形を縦横それぞれの辺に平行な、矩形の中心を通る2本の直線で田の字に4等分する。
・分割されたそれぞれの領域が規定数以上の頂点を含んでいれば、再度4等分する。
・以後これを繰り返す。
・以上の手続きが終了後、各小領域の中心部に最も近い頂点をランドマークとして選択する。
【0030】
あるいは、より粗い方法ではあるが、ランドマークは、C言語でライブラリとして装備されている乱数関数を用いて、選んでもよい。例えば、random関数を用いて、異なるL個の頂点が選ばれるように、random(N)を少なくともL回繰り返して、その結果の整数の番号の頂点をランドマークとしてもよい。
【0031】
こうしてステップ502で、L個のランドマークが選ばれると、次に、ステップ504では、選ばれた全L個のランドマーク間の最短経路長が計算される。この最短経路長の計算は、例えば、公知のダイクストラ法などの方法を用いて、行ってもよい。全L個のランドマーク間の最短経路長だと、実質的に、L2回の計算となる。以下では、ランドマークLvと、ランドマークLwにつき、こうして計算された最短経路長を、d(Lv,Lw)であらわすものとする。このようにして計算されたd(Lv,Lw)の値は、一旦、適当な配列変数に格納される。ステップ504の完了時点で、その配列変数に入れられ、メイン・メモリ104に展開されているデータの集まりが、全ランドマーク間の最短経路長のデータ204'となる。
【0032】
ステップ506では、グラフの各頂点vについて、vの近くのk個のランドマークを選択し、頂点vと、そのk個の各ランドマークへの最短経路長が計算される。この、近傍のk個のランドマークの選択は、例えば、vから全てのランドマークへの最短経路長を計算し、そのうちの最短経路長が小さいものから順にk個選ぶという方法で行う。ここでも、最短経路長の計算は、ダイクストラ法などの周知の経路探索方法を用いることができる。本発明者の実験によれば、k=4程度が望ましいことが分かった。以下では、頂点vと、ランドマークLwにつき、こうして計算された最短経路長を、d(v,Lw)であらわすものとする。各頂点に対して、このようにしてkv個のランドマークが対応づけられる。このようにして計算されたd(Lv,Lw)の値は、一旦、適当な配列変数に格納される。ステップ506の完了時点で、その配列変数に入れられ、メイン・メモリ104に展開されているデータの集まりが、全頂点vの近くのランドマークとの最短距離長のデータ206'となる。
尚、ここでグラフの各頂点vというとき、ランドマークとして選ばれた頂点自体も除外されないことに留意されたい。
【0033】
図6は、ランドマークと、他の頂点との関係を模式的に示す図である。分かりやすくするために、実際のグラフよりも、ずっと頂点の数を少なく示してある。図6では、白丸がランドマークであり、ここでは、ランドマークの数L=4である。また、他の頂点を黒丸で示し、図示するように、1つの黒丸の頂点には、2個のランドマークが対応付けられているので、この図の例では、k=2である。
【0034】
ステップ508では、ステップ504とステップ506で計算され、メイン・メモリ104上に、データ204'及びデータ206'として存在している計算結果が、例えば、C言語のread()、write()のようなライブラリ関数を用いて、ハードディスク114に、それぞれ、データ204及びデータ206として記録される。より具体的に説明すると、ステップ504での計算結果として、2つのランドマークLv,Lwの全ての組み合わせに対する最短経路長d(Lv,Lw)が、全ランドマーク間の最短経路長データ204として、ハードディスク114に記録され、このデータは、データ204'として、ハードディスク114からメイン・メモリ104にロードされたとき、上限値計算部214または下限値計算部216が、任意の2つのランドマークLv,Lwに対して、その最短経路長d(Lv,Lw)を取り出すことができるようになっている。
【0035】
同様に、ステップ506での計算結果として、グラフの任意の頂点vに対応づけられたk個のランドマークLvkに対する、最短経路長d(v,Lvk)が、全頂点vの近くのk個のランドマークとの距離データ206として、ハードディスク114に記録され、このデータは、データ206'として、ハードディスク114からメイン・メモリ104にロードされたとき、任意の頂点vに対して、データ206から、上限値計算部214または下限値計算部216が、その頂点に近傍のランドマークとして関連付けられたk個のランドマークへの最短経路長d(v,Lvk)の各々を取り出すことができるようになっている。
【0036】
尚、図5のフローチャートでは、ステップ504とステップ506の終了後、ステップ508で、ステップ504とステップ506での計算結果を一気にハードディスク114に記録するように示されているが、ステップ504での計算の終了後直ちに、ステップ504での計算結果をハードディスク114に記録し、ステップ506での計算の終了後直ちに、ステップ506での計算結果をハードディスク114に記録するようにしてもよく、そのようにしても、図5のフローチャートの処理と、本質的な差異はないことを当業者なら、理解するであろう。
【0037】
さて、図7と図8を参照して、上限値計算部216と、下限値計算部218の計算処理について説明する前提として、本発明の特徴である四角不等式に基づく計算の原理について、図9を参照して説明する。図9には、頂点vと、それに近接するランドマークLvと、頂点wと、それに近接するランドマークLwの4つの頂点が描かれている。その4つの頂点を線で結ぶと、必ずしも長方形ではないにしても、何らかの四角形を形成することは確かである。もしこの四角形の頂点が全て同一平面上にあれば、任意の四角形において、一辺は、必ず残りの三辺の長さの和よりも小さい、という命題は無条件で成立する。しかし、四角形の頂点が同一平面上にないと、一辺は、残りの三辺の長さの和よりも小さいとは、必ずしも言えなくなる。ところが、辺の間の距離を測る指標を、最短経路長にすることによって、四角形の頂点が同一平面上になくても、一辺は、必ず残りの三辺の長さの和よりも小さい、という命題が復活する。そこで、まず、頂点vと頂点wを結ぶ線をその一辺と考えると、次の関係式が成立する。
d(Lv,v) + d(Lv,Lw) + d(w,Lw) >= d(v,w)
この式から、d(Lv,v) + d(Lv,Lw) + d(w,Lw)は、常にd(v,w)より大きいと言えるので、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限を以って、d(v,w)の上限とすることができる。図7のフローチャートでは、この式を用いて、d(v,w)の上限値が計算される。
【0038】
次に、ランドマークLvとランドマークLwを結ぶ線をその一辺と考えると、
d(Lv,v) + d(v,w) + d(w,Lw) >= d(Lv,Lw)
これから、d(v,w) >= d(Lv,Lw) - d(Lv,v) - d(w,Lw)
この式から、d(Lv,Lw) - d(Lv,v) - d(w,Lw)は常にd(v,w)より小さいと言えるので、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限を以って、d(v,w)の下限とすることができる。図8のフローチャートでは、この式を用いて、d(v,w)の下限値が計算される。
【0039】
ここで、図7のフローチャートを参照して、上限値計算部214の処理について、説明する。
図7のステップ702では、MaxValという変数が、初期的に0にセットされる。この変数は、例えば、C言語だと、倍精度浮動小数点のdoubleとして宣言されるものである。
【0040】
ステップ704では、頂点vにつき、その近くとして関連付けられたランドマークLvのうちのkv個が選ばれる。このような対応付けは、図2に示す、全頂点vの近くのk個のランドマークとの距離データ206'として、既に前処理部212の処理によって予め用意されており、頂点vに対応するものとして、データ206'から取り出される。
【0041】
ステップ706では、同様に、頂点wにつき、その近くとして関連付けられたランドマークLwのうちのkw個が選ばれる。1つの実施例では、kv = kw = 4である。
【0042】
さて、ステップ708では、頂点vからランドマークLvへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D1に格納される。ステップ710では、LvからLwへの最短経路長が、データ204'から取り出されて、その値が、倍精度浮動小数点の変数D2に格納される。ステップ712では、ランドマークLwから頂点wへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D3に格納される。
【0043】
ステップ714では、D1 + D2 + D3が計算されて、それが、MaxValという値と比較され、その大きい方が、MaxValにセットされる。
【0044】
このようにして、データ206'から、頂点vに対応して取り出されたkv個のランドマークLvと、wに対応して取り出されたkw個のランドマークLwにつき、ステップ708〜714を巡らせ、その結果MaxValに与えられた値が、d(v,w)の上限値ということになる。すなわち、ステップ706から716までが、Lwについての内側のループで、ステップ704からステップ718の外側のループである。kv = kw = 4だと、4 * 4 = 16で、ステップ708〜714は、16回実行される。
【0045】
但し、頂点v,wに対して、k2回の計算を行うと計算量が大きくなりすぎる場合があるので、頂点vの近くのk'v個のランドマークと、頂点wの近くのk'w個のランドマークだけ抜き出して、計算のループの回数をk'v * k'wに削減する、という工夫を行うことができる。
このとき、k'v<=kv, k'w<=kwである。
本発明者のさまざまな試行により、k'v = k, k'w = 1の設定が良好な結果をもたらすことが分かった。
【0046】
このようにして計算された値は、頂点v,wに対応するd(v,w)の上限値として、上限値計算部214を呼び出すプログラムに返される。上限値計算部214を呼び出すプログラムとは、典型的には、クエリー処理部220である。
【0047】
次に、図8のフローチャートを参照して、下限値計算部216の処理について、説明する。
図8のステップ802では、MinValという変数が、初期的に∞にセットされる。この変数は、例えば、C言語だと、倍精度浮動小数点のdoubleとして宣言されるものである。コンピュータの変数の値で、∞ということは現実的にはあり得ないが、ここでは、グラフの経路長としてとり得る値よりも十分大きい値を予めセットしておくものとする。
【0048】
ステップ804では、頂点vにつき、その近くとして関連付けられたランドマークLvのうちのkv個が選ばれる。このような対応付けは、図2に示す、全頂点vの近くのk個のランドマークとの距離データ206'として、既に前処理部212の処理によって予め用意されており、頂点vに対応するものとして、データ206'から取り出される。
【0049】
ステップ806では、同様に、頂点wにつき、その近くとして関連付けられたランドマークLwのうちのkw個が選ばれる。好適な実施例では、kv = kw = 4である。
【0050】
ステップ808では、ランドマークLvからランドマークLwへの最短経路長が、データ204'から取り出されて、その値が、倍精度浮動小数点の変数D1に格納される。ステップ810では、Lvからvへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D2に格納される。ステップ812では、頂点wからランドマークLwへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D3に格納される。
【0051】
ステップ814では、D1 - D2 - D3が計算されて、それが、MinValという値と比較され、その小さい方が、MinValにセットされる。
【0052】
このようにして、データ206'から、頂点vに対応して取り出されたkv個のランドマークLvと、wに対応して取り出されたkw個のランドマークLwにつき、ステップ808〜814を巡らせ、その結果MinValに与えられた値が、d(v,w)の下限値ということになる。すなわち、ステップ806から816までが、Lwについての内側のループで、ステップ804からステップ818の外側のループである。kv = kw = 4だと、4 * 4 = 16で、ステップ808〜814は、16回実行される。
【0053】
上限値の計算の場合と同様に、頂点v,wに対して、k2回の計算を行うと計算量が大きくなりすぎることがあるので、頂点vの近くのk'v個のランドマークと、頂点wの近くのk'w個のランドマークだけ抜き出して、計算のループの回数をk'v * k'wに削減する、という工夫を行うことができる。このとき、k'v<=kv, k'w<=kwである。k'v = k, k'w = 1の設定が良好な結果をもたらすことも同様である。
【0054】
このようにして計算された値が、頂点v,wに対応するd(v,w)の下限値として、下限値計算部216を呼び出すプログラムに返される。下限値計算部216を呼び出すプログラムとは、典型的には、探索方法決定部218及びクエリー処理部220である。
【0055】
尚、上限値、下限値の計算ループで、k'v = k, k'w = 1のような工夫を行うことができることを上記で説明したが、このような設定を行うならば、上限値、下限値の計算を行う前に予め、固定的に設定し、後は変更しないようにすることに留意されたい。例えば、頂点p,q,r について、d(p,q) の上下限を計算するときは、pの近くの k'v 個のランドマークと q の近くのk'w個のランドマークを用いて計算し、d(q,r) の上下限を計算するときは、q の近くの k'v 個のランドマークと r の近くのk'w個のランドマークを用いて計算する。
【0056】
また、図7と図8の計算ルーチンを、グラフの頂点v,wのすべてに亘って予め計算して、v,wの上限値と下限値をハードディスク114に記録しておいて、実行時にメイン・メモリ114にロードし、A*探索においては、図7と図8の計算ルーチンを呼び出す代わりに、v,wの値で、メイン・メモリ114にある値をルックアップすることにより、データの計算が高速化されると思われるかもしれない。実際、多くの場合、ルックアップは、その場で計算するよりは短い時間で済む。しかし、このような方法は、ごく少ない頂点のグラフにしか適用できない。すなわち、一般的に、あまり精細でない地図でも、グラフの頂点としてあらわされる地点の数は、少なくともN = 3 × 105程度である。このようなデータをv,wの組について用意するには、組み合わせの数は少なくとも、N2 = 9 × 1010で、それに上記kを掛け、また、倍精度浮動小数点数が8バイトであらわされることを考慮すると、あまり精細でない地図でも、上限値と下限値を記録するには、数テラバイトを下らない記憶容量を要することが理解されよう。
【0057】
次に、図10のフローチャートを参照して、探索方向決定部218の処理を説明する。探索方向決定部218に与えられるのは、グラフの2つの頂点、sとtである。探索方向決定部218は、クエリー処理部220から呼び出されるものであり、典型的には、sとtは、探索すべき始点と終点である。
【0058】
さて、図10のステップ1002では、頂点sから頂点tへの最短経路長の下限値が、下限値計算部216を呼び出すことによって、求められる。同様に、ステップ1004では、頂点tから頂点sへの最短経路長の下限値が、下限値計算部216を呼び出すことによって、求められる。
【0059】
ステップ1006では、このようにして計算された、頂点sから頂点tへの最短経路長の下限値と、頂点tから頂点sへの最短経路長の下限値とが比較され、頂点sから頂点tへの最短経路長の下限値が、頂点tから頂点sへの最短経路長の下限値より大きいと、ステップ1008で、sとtが入れ替えられる。このように、最短経路長の下限値の大きさに応じて、sとtを入れ替える理由は、頂点sから頂点tへの最短経路長の下限値が、頂点tから頂点sへの最短経路長の下限値より大きいと、sからtへ向かう経路の上下限値の精度よりも、tからsへ向かう経路の上下限値の精度の方がよいことが多い、という発明者の経験則によるものである。すなわち、より高い精度の上下限値を用いることで、A*探索の探索速度の向上がはかられる。
【0060】
図11は、ここまでで用意された結果を以って、最終的に経路探索するためのクエリー処理部220の処理を示すフローチャートである。
【0061】
クエリー処理部220に与えられる入力は、始点としてのグラフの頂点sと、終点としてのグラフの頂点tであり、クエリー処理部220は、これらの頂点の間の最短経路を探索して出力として与えるものである。
【0062】
クエリー処理部220を実行するに際して、グラフ全頂点データ202、全ランドマーク間の最短経路長のデータ204、及び全頂点vの近くのランドマークとの最短距離長のデータ206は、予め、データ202'と、データ204'と、データ206'として、ハードディスク114からメイン・メモリ104にロードされているものとする。
【0063】
ステップ1102では、頂点s及びtのデータを以って、図10に関連して説明した、探索方向決定部10が呼ばれる。この結果、頂点s及びtの条件に応じて、sとtの入れ替わりが行われ、その頂点s及びtが、ステップ1104のA*探索ルーチンに引き渡される。
【0064】
次に、ステップ1104のA*探索ルーチンを、C言語的な擬似コードを用いて説明いる。
下記の擬似コードで、頂点 v, w について d(v,w) は、vからwへの最短経路長を表すものとする。また、w(v,w)を、vとwを結ぶ枝の長さとする。
先ず、始点sから終点tまでの最短経路を求めるとして、各頂点vについて以下のように定める。
ここで、π(v)をd(v,t) の下限値とする。その下限値は、図11のフローチャートにおいて、ステップ1108で、v,tに関して下限値計算部216を呼び出すことにより、求められる。
更に、初期設定として、始点sから終点tまでの最短経路を求めたい場合、各頂点vについて以下のように定める。
k(v): v=s のとき k(s):=π(s)、v≠sのときk(v):=∞;
d(v): v=s のとき d(v):=0、v≠sのときd(v):=∞;
prev(v) = NULL;
頂点集合 S = {s};
そうして、次のようにして探索処理を行う。
while( Sが空でない ) {
S から k(v)の値が最も小さい頂点vを除去;
for(vから出ている全ての枝(v,w) について以下の操作を行う) {
if( k(w) > k(v) + w(v,w) - π(v) + π(w)) {
k(w) := k(v) + w(v,w) -π(v)+π(w);
d(w) := d(v) + w(v,w);
prev(w) := v;
if(d(w)+π(w) <= min(d(s,t) の上限値, d(t)))
{ S ← S ∪{w}; }
}
}
}
最後に、d(t) に入っている値が最短経路長になる。また、この擬似コードで示す処理において、d(s,t) の上限値を求める際に、図11のステップ1106に示すように、s,tに関して上限値計算部214が呼び出される。
このとき、prev(t) に入っている頂点を t'、prev(t')に入っている頂点を t'' ・・・とすると、 t←t'←t''←・・・←s が最短経路になる。
【0065】
本発明者は、本発明の効果を確認するために、次のような実験を行った。先ず、下記の表に示すような、7つの重み付きグラフを用意した。また、パラメータは、k=4, kw=4, kv=1を用いた。また、ランドマークは、既に説明したが、下記のような方法で、配置した。
・グラフに配置された頂点を全て含む最小の矩形を取る。
・矩形を縦横それぞれの辺に平行な、矩形の中心を通る2本の直線で田の字に4等分する。
・分割されたそれぞれの領域が規定数以上の頂点を含んでいれば、再度4等分する。
・以後これを繰り返す。
・以上の手続きが終了後、各小領域の中心部に最も近い頂点をランドマークとして選択する。
【表1】
【0066】
グラフ1に対して、文献[1]の方法と、本実施例の方法を、下記の表のような条件で、それぞれ適用した。特に、文献[1]の方法と本実施例の方法にあっては、クラスタは用いないので、「ランドマークまたはクラスタ数」の欄は、ランドマーク数と解釈されたい。すると、探索時間と探索頂点数に関して、本実施例の方法は、明らかに優れた効果を奏したことが見て取れる。尚、この表及び以下の表で、「探索時間」の欄は、ダイクストラ法の性能を1とした場合の性能の程度を表している。すなわち、実際にかかった時間は、ここの「探索時間」に示した数値の逆数に比例する。同様に、「探索頂点数」の欄も、ダイクストラ法で探索される頂点数の1とした場合の、探索される頂点数の少なさの度合いを示すものである。よって、実際に探索された頂点数という意味では、ここの「探索頂点数」に示した数値の逆数に比例する。さらに、前処理後の必要記憶量という意味でも、この実施例が、文献[1]の方法より優れていることが示されている。
【表2】
【0067】
グラフ2及び3に対しても、下記のように、本実施例の方法が、文献[1]よりも、探索性能において優れていることが示されている。
【表3】
【表4】
【0068】
次に、以下では、文献[2]の方法と、本実施例の方法を比較する実験を行った。なお、本発明の方法は、クラスタは用いないので、「ランドマークまたはクラスタ数」の欄は、ランドマークの数と解釈する。一方、文献[2]の方法では、ランドマークは用いず、その代わりにクラスタを用いるので、「ランドマークまたはクラスタ数」の欄は、クラスタの数と解釈する。
下記のようにグラフ4に、文献[2]の方法と、本実施例の方法を適用した結果は、やはり、本実施例の方法が実質的に優れた効果を奏することを示している。この実施例は、前処理後の必要記憶量という意味でも、文献[2]の方法より優れていることが示されている。
【表5】
【0069】
グラフ5〜7に、文献[2]の方法と、本実施例の方法を適用した比較結果は、下記のとおりである。これらの実験例でも、本実施例の方法が、文献[2]の方法よりも顕著な効果を奏することが見て取れる。
【表6】
【表7】
【表8】
【0070】
尚、上記の実施例では、無向グラフとして説明してきたが、本発明は、有向グラフにも適用できる。その場合、探索しようとする経路が、有向グラフの枝の向きと逆であると、その枝は避けて、別の枝を探索する、というような処理を行う。
【0071】
また、上記実施例では、スタンドアロンの環境で、グラフのデータを探索する処理を説明したが、Webサーバ上で、上記で説明した処理を実行して、探索可能な環境を用意し、図2に示すクエリー処理部220の入力のところで、クライアント・コンピュータからの探索問い合わせを受け付け、クエリー処理部220の出力のところで、探索問い合わせを受け付けたクライアント・コンピュータに、探索結果を送信するようにすることもできる。
【0072】
また、最近の携帯電話の性能の向上により、1GB以上のディスク容量と、高速のCPUをもつ携帯電話もあらわれてきている。このような携帯電話には、図2に示すグラフ全頂点データ202、全ランドマーク間の最短経路長のデータ204、全頂点vのその近傍のランドマークとの最短経路長のデータ206、上限値計算部214、下限値計算部216、探索方向決定部218及びクエリー処理部220の全体をそのディスクに格納して、携帯電話だけでスタンドアロンに探索を行い、その結果を携帯電話の画面に表示するようにすることができる。
【0073】
さらに、本発明に係るグラフの探索技法は、カーナビ、地図探索、鉄道路線探索など、頂点が重み付きグラフとして表現される対象における、任意の対象物上での経路探索に適用し得るものであることを理解されたい。
【図面の簡単な説明】
【0074】
【図1】本発明を実施するためのハードウェアのブロック図である。
【図2】本発明を実施するための、データと処理モジュールのブロック図である。
【図3】保存されているグラフ頂点データの論理構造を示す図である。
【図4】重み付きグラフの一部を示す図である。
【図5】グラフの頂点データの前処理部の処理のフローチャートを示す図である。
【図6】ランドマークと他の点の関連付けを示す図である。
【図7】上限値計算部の処理のフローチャートを示す図である。
【図8】下限値計算部の処理のフローチャートを示す図である。
【図9】四角不等式におけるランドマークとその他の点の位置関係を示す図である。
【図10】探索方向決定部の処理のフローチャートを示す図である。
【図11】クエリー処理部の処理のフローチャートを示す図である。
【技術分野】
【0001】
この発明は、カーナビゲーション・システムなどで利用される経路探索技法に関し、より詳しくは、経路探索を高速化するための方法、プログラム及びシステムに関するものである。
【背景技術】
【0002】
近年、カーナビゲーション・システムや、ウェブサイトにおける最適交通路探索サービスの増加により、コンピュータにより経路を探索する、より高速化された技法への要望が高まっている。このことは、コンピュータ・サイエンス的には、重み付きグラフにおける、最短経路の決定アルゴリズムに帰着される。
【0003】
ところで、重み付きグラフにおける、最短経路の決定アルゴリズムの、古典的とも言える技法として、ダイクストラ法と呼ばれるものが知られている。これは要するに、重み付きグラフGにおいて、頂点aから頂点zへの最短経路を決定するにあたって、aからある他の頂点への最短経路を決定し、次に、そうして見つかった他の頂点を対象から外して、残りの頂点に対して同様のことを行い、残りの頂点がなくなったとき、手続を完了する、というものである。このアルゴリズムは、必ず解が存在することを保証するが、グラフGの頂点の数が増えてくると、計算量の点で、現実的なものでなくなる。
そこで、計算量の点でより改善された、さまざまな技法が提案されてきた。そのようなものの1つとして、A*探索と呼ばれる技法がある。これは、予め計算された任意の2頂点間の最短経路長の上下限値を利用して、最短経路の計算を高速化するものであり、具体的には、下記のような技法である。
【0004】
以下で、頂点 v, w について d(v,w) は、vからwへの最短経路長を表すものとする。また、w(v,w)を、vとwを結ぶ枝の長さとする。
先ず、初期設定として、始点sから終点tまでの最短経路を求めたい場合、各頂点vについて以下のように定める。
k(v): v=s のとき k(s):=π(s)、v≠sのときk(v):=∞;
d(v): v=s のとき d(v):=0、v≠sのときd(v):=∞;
prev(v) = NULL;
頂点集合 S = {s};
そうして、次のようにして探索処理を行う。
while( Sが空でない ) {
S から k(v)の値が最も小さい頂点vを除去;
for(vから出ている全ての枝(v,w) について以下の操作を行う) {
if( k(w) > k(v) + w(v,w) - π(v) + π(w)) {
k(w) := k(v) + w(v,w) -π(v)+π(w);
d(w) := d(v) + w(v,w);
prev(w) := v;
if (d(w)+π(w) <= min(d(s,t) の上限値, d(t)))
{ S ← S ∪{w}; }
}
}
}
最後に、d(t) に入っている値が最短経路長になる。
また、prev(t) に入っている頂点を t'、prev(t')に入っている頂点を t'' ・・・とすると、 t←t'←t''←・・・←s が最短経路になる。
【0005】
任意の2頂点 v, w について、d(v,w) の上限値と下限値が正しく与えられるとき、上記のA*探索が正しく最短経路を求めることが知られている。また、A*探索に与える上下限値の精度が良ければ良いほど終点まで速く到達できることが知られている。直感的には、アルゴリズム中のk(v) には、始点sからvを経由して終点tに到達する経路の最短経路長の下限値、d(v)には始点 s からvまでの最短経路長が格納される。
【0006】
そこで、上記のA*探索アルゴリズムでブラックボックスになっている部分(d(v,w)の上下限値を計算する方法)が、従来より課題になっている。
【0007】
これに関連して先ず、Computing the Shortest Path: A* Search Meets Graph Theory by A. V. Goldberg and C. Harrelson, in Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005.という文献に記載された手法がある。
この手法では、グラフ上の少数(十数個)の頂点を「ランドマーク」として選択し、ランドマークから各頂点への最短経路長を記憶しておく。そして、記憶しておいた最短経路長を利用して任意の2頂点間の最短経路長の下限値を算出し、A*探索による探索を高速化する手法である。
【0008】
また、Goal Directed Shortest Path Queries Using Precomputed Cluster Distances by Jens Maue, Peter Sanders, Domagoj Matijevic, in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA-06), LNCS 4007, 316-327, Springer, 2006.も知られている。
この手法では、グラフを多数のクラスターに分割し、各クラスター間の最短経路長を定義し、記憶しておく。そして、記憶しておいた最短経路長を利用して、任意の2頂点間の最短経路長の上限値と下限値を算出し、最短経路長の上限値による枝刈りとA*探索を組み合わせて高速化する手法である。
【0009】
いずれの手法も、A*探索で利用する「任意の2頂点間の最短経路長の上下限値」の精度がアルゴリズムの高速化に大きく寄与している。[1]の手法では、下限値計算時に複数のランドマーク情報を利用するが、ランドマーク自体の数が少ないことが欠点である。[2]の手法では、クラスターの数自体は沢山あるが、上下限値計算時に利用するクラスター情報の数が少ないことが欠点である。
【0010】
この他にも、従来技術として特開2006−201174という特許公開公報に開示されている技術があるが、その発明者の一人は、上記文献[1]にも著者としてリストされており、その開示内容も、上記文献[1]とほぼ重なるものである。
【非特許文献1】[1] Computing the Shortest Path: A* Search Meets Graph Theory by A. V. Goldberg and C. Harrelson, in Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, 2005.
【非特許文献2】[2] Goal Directed Shortest Path Queries Using Precomputed Cluster Distances by Jens Maue, Peter Sanders, Domagoj Matijevic, in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA-06), LNCS 4007, 316-327, Springer, 2006.
【特許文献1】特開2006−201174
【発明の開示】
【発明が解決しようとする課題】
【0011】
この発明の目的は、経路探索を高速化するための技法を提供することにある。
より詳しくは、この発明の目的は、A*探索を用いた経路探索において、任意の2頂点間の最短経路長の上下限値の精度を向上させることによって、経路探索を高速化することにある。
【課題を解決するための手段】
【0012】
本願発明者は、研究を重ねた結果、下記のような手法により、経路探索が高速化されることに想到した。
すなわち、先ず、経路探索される、もととなる重み付きグラフに対して、ランドマークを生成し、上下限値の計算に必要な情報が予め、計算される。
次に、最短経路長の上下限値が計算される。特に、本発明は、この計算のために、頂点vの近くのランドマークLvと、頂点wの近くのランドマークLwの4点で構成される四角不等式に着目するものであり、下記のような式が、上下限値の計算に利用される。
d(v,w)の下限値:d(v,w)>=d(Lv,Lw)-d(Lv,v)-d(w,Lw)
d(v,w)の上限値:d(v,w)<=d(v,Lv)+d(Lv,Lw)+d(Lw,w)
これらの不等式の右辺の値は全て、上記のランドマークの生成に関連して、予め計算され保存されていることに留意されたい。
この上限値と、下限値の計算ルーチンは、後のA*探索に適宜呼び出されて利用される。
【発明の効果】
【0013】
この発明によれば、最短経路長の上下限値の精度の向上が達成され、この結果、経路探索の時間が短縮される。発明者の実験によれば、特定のグラフの探索に関して、上記文献[2]の手法よりも、4倍以上の探索性能の向上が確認された。
【発明を実施するための最良の形態】
【0014】
以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
【0015】
図1は、本発明の手法を実施するためのハードウェア構成のブロック図である。図1において、コンピュータ100は、CPU102と、メイン・メモリ104をもち、これらは、バス106に接続されている。メイン・メモリ104は、少なくとも512MB、好適には、1GB以上の記憶容量をもつものである。後述するグラフの全頂点データなどをロードするためには、メイン・メモリ104の容量は、大きい程好ましい。CPUは、好適には、32ビットまたは64ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium(R) 4、AMD社のAthlon(R)などを使用することができる。バス106には、ディスプレイ・コントローラ108を介して、LCDモニタなどのディスプレイ110が接続される。ディスプレイ110は、本発明に係る、処理用に書かれたプログラムを眺めたり、編集したりするために使用される。また、本発明に従い、探索した経路を表示するためにも使用される。バス106にはまた、IDEコントローラ112を介して、ハードディスク114と、CD−ROMドライブ116が接続される。ハードディスク114には、オペレーティング・システム、コンパイラその他のプログラムが、メインメモリ104にロード可能に記憶されている。ハードディスク114は、少なくとも40GB、好適には、160GB以上の記憶容量をもつものである。CD−ROMドライブ116は、必要に応じて、CD−ROMからプログラムをハードディスク114に追加導入するために使用される。バス106には更に、キーボード・マウスコントローラ118を介して、キーボード120と、マウス122が接続されている。キーボード120及びマウス122は、コンパイラを使用して、本発明に係る処理を実行させるプログラムを書いたり、実行させたりするために使用される。
【0016】
コンピュータ100のソフトウェア的な環境について更に説明すると、上記オペレーティング・システムとしては、Linux(R)、マイクロソフト社のWindows XP(R)、Windows(R)2000、アップルコンピュータのMac OS(R)などを使用することができるが、ここに掲げたオペレーティング・システムには限定されない。本発明の処理用のプログラムを作成するためのコンパイラは、使用するオペレーティング・システムの上で、動作し得る、マイクロソフト社のVisual Basic(R)、Visual C++(R)、Visual Studio(R)、ボーランド社のBorland(R)C++ Compiler 5.5、Delphi(商標)、C++ Builder(商標)、IBM社のVisualAge for Java(商標)などがあり、これらの任意のものを使うことができる。コンパイラは、GUIをサポートしておらず、CUIベースだけのものでも、本発明の機能を実現することができる。
【0017】
図2は、この実施例の高レベル機能ブロック図である。図2において、グラフ全頂点データ202は、重み付きグラフを、コンピュータ可読な形式で、ハードディスク114に保存したものであり、各頂点に対応するデータを保持する。経路探索アプリケーションの場合、重み付きグラフの各頂点は、各々が、各地点に対応する。また、この実施例では、グラフは、無向グラフである。
【0018】
グラフの各頂点には、好ましくは、1から連番で番号が付与され、そのデータ形式は、図3に示すように、各頂点毎に、隣接する頂点の番号のリストへのリンクと、隣接する頂点への距離のリストへのリンクとを含む。尚、このようなデータ形式は、可能ないくつかの選択肢のうちの1つであり、本発明が想定するグラフ表現のデータ形式は、これに限定されるものではないことを、当業者なら理解するはずである。
【0019】
図4には、具体的なグラフの頂点の配置の例が示されている。すなわち、図4では、n番目の頂点は、nを丸で囲って表示されている。図4で、頂点1は、隣接する頂点として、頂点2、5及び8をもち、それぞれへの距離は、4.0, 5.0, 2.5である。頂点2は、隣接する頂点として、頂点1、4及び5をもち、それぞれへの距離は、4.0, 3.5, 3.0である。図3には、ハードディスク114から、メイン・メモリ104上に、前処理部212が処理可能にロードされた、頂点1及び頂点2のデータ構造が示されている。
これを、例えば、C言語の構造体で記述すると、下記のようになる。
struct Node {
int NodeID; // 頂点番号
int *adjNodeList[]; // 隣接する頂点の頂点番号を配列として記憶
double *adjDistanceList[]; // 隣接する頂点までの距離を配列として記憶
};
図4の頂点1に、この構造体を適用すると、NodeID = 1, *adjNodeList = {2,5,8}, *adjDistanceList = {4.0, 5.0, 2.5} となる。
【0020】
図2に戻って、前処理部212、上限値計算部214、下限値計算部216、探索方向決定部218、及びクエリー処理部220は、この実施例に処理を行うように、好適には、CまたはC++で書かれ、ハードディスク114に記憶されているプログラムであり、キーボード120またはマウス122の操作により、オペレーティング・システムの動作で、ハードディスク114から、メイン・メモリ104にロードされる際に、CPU102の働きで、実行されるものである。
【0021】
また、好適には、前処理部212、上限値計算部214、下限値計算部216、探索方向決定部218、及びクエリー処理部220がメイン・メモリ104に際に、または、後のユーザーの操作に応答して、グラフ全頂点データ202が、ハードディスク114から、図3に示すようなグラフ全頂点データ202'として、例えば、C言語のmalloc()のような関数を呼び出してメモリ領域を確保しながら、メイン・メモリ104にロードされる。このとき、後の処理の高速化のために、グラフ全頂点データ202の全体をメイン・メモリ104にロードすることが望ましい。
【0022】
しかし、メイン・メモリ104の容量が十分でない場合、あるいは、グラフ全頂点データ202がの頂点の数が非常に多い場合は、このようにグラフ全頂点データ202の全体をメイン・メモリ104にロードできないことがある。そのような場合、例えば、次のような方法が考えられる。すなわち、許される限りのメイン・メモリ104の領域を確保しておき、そこに可能な限りのグラフ全頂点データ202の頂点のデータをロードしておく。そうして、前処理部212が、ある頂点vのデータを、メイン・メモリ104にロードされた頂点データ202'中で探し、もし見つかれば、そのデータを前処理部212は利用する。もし見つからなければ、例えば、見つからなかった頂点のデータを含むあるまとまりの頂点データを、ハードディスク114に記録されているグラフ全頂点データ202からメイン・メモリ104にロードし、頂点データ202'の領域の一部に置換することにより、前処理部212が参照可能となるようにすることができる。
【0023】
このようなグラフ全頂点データ202をメイン・メモリ104にロードするためのメモリ管理ルーチンは、必要に応じて予め用意されるものであるが、オペレーティング・システムが提供するAPI関数やC言語の標準ライブラリ関数等を用いて慣用の技術で実現できるものであるため、ここでは、これ以上詳述しない。
【0024】
後で詳しく説明するが、前処理部212は、好適には、メイン・メモリ104にロードされたグラフ全頂点データ202'から個々の頂点データを読み取って、全ランドマーク間の最短経路長のデータ204と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206を生成し、後で読み出し可能に、ハードディスク114に記憶する機能をもつ。なお、全ランドマーク間の最短経路長のデータ204と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206は、好適には、上限値計算部214及び下限値計算部216が高速でアクセスできるように、データ204'及びデータ206'として、メイン・メモリ104にロードされる。
【0025】
上限値計算部214は、メイン・メモリ104にロードされた、全ランドマーク間の最短経路長のデータ204'と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206'を参照して、後述する手順により、頂点の上限値を計算して提供する機能をもつ。上限値計算部214は、他のプログラムまたはモジュールから呼び出され、好適には倍精度浮動小数点数として上限値の値を返す、サブルーチンまたは関数として実装される。
【0026】
下限値計算部216は、メイン・メモリ104にロードされた、全ランドマーク間の最短経路長のデータ204'と、全頂点vの近くのk個のランドマークとの最短経路長のデータ206'を参照して、後述する手順により、頂点の下限値を計算して提供する機能をもつ。下限値計算部216は、他のプログラムまたはモジュールから呼び出され、好適には倍精度浮動小数点数として下限値の値を返す、サブルーチンまたは関数として実装される。
【0027】
クエリー処理部220は、実際の出発頂点と、宛先頂点の指定を受けて、それらの頂点間の最短経路を探索し、その結果を返す機能をもつ。クエリー処理部220は、A*探索に基づき、必要に応じて上限値計算部214と、下限値計算部214を呼び出して上限値と下限値を利用するとともに、探索方向決定部218を利用して、探索方向を決定することにより、経路探索を行う機能をもつ。
【0028】
以下、前記各処理モジュールの動作を、フローチャートを参照して、説明する。図5を参照すると、前処理部212の動作フローチャートが示されている。図5のステップ502では、グラフGの頂点から、L個の頂点がランドマークとして選ばれる。L個のランドマークは、グラフGにおいて、なるべく均一に分布するように配置すのが望ましい。本発明者の実験によれば、ランドマークの個数Lは、グラフGの頂点の数をNとすると、L=N1/2個程度、あるいはそれ以上にすればよいことが分かった。
【0029】
ランドマークを選択する1つの方法は、下記のようなものである。
・グラフに配置された頂点を全て含む最小の矩形を取る。
・矩形を縦横それぞれの辺に平行な、矩形の中心を通る2本の直線で田の字に4等分する。
・分割されたそれぞれの領域が規定数以上の頂点を含んでいれば、再度4等分する。
・以後これを繰り返す。
・以上の手続きが終了後、各小領域の中心部に最も近い頂点をランドマークとして選択する。
【0030】
あるいは、より粗い方法ではあるが、ランドマークは、C言語でライブラリとして装備されている乱数関数を用いて、選んでもよい。例えば、random関数を用いて、異なるL個の頂点が選ばれるように、random(N)を少なくともL回繰り返して、その結果の整数の番号の頂点をランドマークとしてもよい。
【0031】
こうしてステップ502で、L個のランドマークが選ばれると、次に、ステップ504では、選ばれた全L個のランドマーク間の最短経路長が計算される。この最短経路長の計算は、例えば、公知のダイクストラ法などの方法を用いて、行ってもよい。全L個のランドマーク間の最短経路長だと、実質的に、L2回の計算となる。以下では、ランドマークLvと、ランドマークLwにつき、こうして計算された最短経路長を、d(Lv,Lw)であらわすものとする。このようにして計算されたd(Lv,Lw)の値は、一旦、適当な配列変数に格納される。ステップ504の完了時点で、その配列変数に入れられ、メイン・メモリ104に展開されているデータの集まりが、全ランドマーク間の最短経路長のデータ204'となる。
【0032】
ステップ506では、グラフの各頂点vについて、vの近くのk個のランドマークを選択し、頂点vと、そのk個の各ランドマークへの最短経路長が計算される。この、近傍のk個のランドマークの選択は、例えば、vから全てのランドマークへの最短経路長を計算し、そのうちの最短経路長が小さいものから順にk個選ぶという方法で行う。ここでも、最短経路長の計算は、ダイクストラ法などの周知の経路探索方法を用いることができる。本発明者の実験によれば、k=4程度が望ましいことが分かった。以下では、頂点vと、ランドマークLwにつき、こうして計算された最短経路長を、d(v,Lw)であらわすものとする。各頂点に対して、このようにしてkv個のランドマークが対応づけられる。このようにして計算されたd(Lv,Lw)の値は、一旦、適当な配列変数に格納される。ステップ506の完了時点で、その配列変数に入れられ、メイン・メモリ104に展開されているデータの集まりが、全頂点vの近くのランドマークとの最短距離長のデータ206'となる。
尚、ここでグラフの各頂点vというとき、ランドマークとして選ばれた頂点自体も除外されないことに留意されたい。
【0033】
図6は、ランドマークと、他の頂点との関係を模式的に示す図である。分かりやすくするために、実際のグラフよりも、ずっと頂点の数を少なく示してある。図6では、白丸がランドマークであり、ここでは、ランドマークの数L=4である。また、他の頂点を黒丸で示し、図示するように、1つの黒丸の頂点には、2個のランドマークが対応付けられているので、この図の例では、k=2である。
【0034】
ステップ508では、ステップ504とステップ506で計算され、メイン・メモリ104上に、データ204'及びデータ206'として存在している計算結果が、例えば、C言語のread()、write()のようなライブラリ関数を用いて、ハードディスク114に、それぞれ、データ204及びデータ206として記録される。より具体的に説明すると、ステップ504での計算結果として、2つのランドマークLv,Lwの全ての組み合わせに対する最短経路長d(Lv,Lw)が、全ランドマーク間の最短経路長データ204として、ハードディスク114に記録され、このデータは、データ204'として、ハードディスク114からメイン・メモリ104にロードされたとき、上限値計算部214または下限値計算部216が、任意の2つのランドマークLv,Lwに対して、その最短経路長d(Lv,Lw)を取り出すことができるようになっている。
【0035】
同様に、ステップ506での計算結果として、グラフの任意の頂点vに対応づけられたk個のランドマークLvkに対する、最短経路長d(v,Lvk)が、全頂点vの近くのk個のランドマークとの距離データ206として、ハードディスク114に記録され、このデータは、データ206'として、ハードディスク114からメイン・メモリ104にロードされたとき、任意の頂点vに対して、データ206から、上限値計算部214または下限値計算部216が、その頂点に近傍のランドマークとして関連付けられたk個のランドマークへの最短経路長d(v,Lvk)の各々を取り出すことができるようになっている。
【0036】
尚、図5のフローチャートでは、ステップ504とステップ506の終了後、ステップ508で、ステップ504とステップ506での計算結果を一気にハードディスク114に記録するように示されているが、ステップ504での計算の終了後直ちに、ステップ504での計算結果をハードディスク114に記録し、ステップ506での計算の終了後直ちに、ステップ506での計算結果をハードディスク114に記録するようにしてもよく、そのようにしても、図5のフローチャートの処理と、本質的な差異はないことを当業者なら、理解するであろう。
【0037】
さて、図7と図8を参照して、上限値計算部216と、下限値計算部218の計算処理について説明する前提として、本発明の特徴である四角不等式に基づく計算の原理について、図9を参照して説明する。図9には、頂点vと、それに近接するランドマークLvと、頂点wと、それに近接するランドマークLwの4つの頂点が描かれている。その4つの頂点を線で結ぶと、必ずしも長方形ではないにしても、何らかの四角形を形成することは確かである。もしこの四角形の頂点が全て同一平面上にあれば、任意の四角形において、一辺は、必ず残りの三辺の長さの和よりも小さい、という命題は無条件で成立する。しかし、四角形の頂点が同一平面上にないと、一辺は、残りの三辺の長さの和よりも小さいとは、必ずしも言えなくなる。ところが、辺の間の距離を測る指標を、最短経路長にすることによって、四角形の頂点が同一平面上になくても、一辺は、必ず残りの三辺の長さの和よりも小さい、という命題が復活する。そこで、まず、頂点vと頂点wを結ぶ線をその一辺と考えると、次の関係式が成立する。
d(Lv,v) + d(Lv,Lw) + d(w,Lw) >= d(v,w)
この式から、d(Lv,v) + d(Lv,Lw) + d(w,Lw)は、常にd(v,w)より大きいと言えるので、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限を以って、d(v,w)の上限とすることができる。図7のフローチャートでは、この式を用いて、d(v,w)の上限値が計算される。
【0038】
次に、ランドマークLvとランドマークLwを結ぶ線をその一辺と考えると、
d(Lv,v) + d(v,w) + d(w,Lw) >= d(Lv,Lw)
これから、d(v,w) >= d(Lv,Lw) - d(Lv,v) - d(w,Lw)
この式から、d(Lv,Lw) - d(Lv,v) - d(w,Lw)は常にd(v,w)より小さいと言えるので、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限を以って、d(v,w)の下限とすることができる。図8のフローチャートでは、この式を用いて、d(v,w)の下限値が計算される。
【0039】
ここで、図7のフローチャートを参照して、上限値計算部214の処理について、説明する。
図7のステップ702では、MaxValという変数が、初期的に0にセットされる。この変数は、例えば、C言語だと、倍精度浮動小数点のdoubleとして宣言されるものである。
【0040】
ステップ704では、頂点vにつき、その近くとして関連付けられたランドマークLvのうちのkv個が選ばれる。このような対応付けは、図2に示す、全頂点vの近くのk個のランドマークとの距離データ206'として、既に前処理部212の処理によって予め用意されており、頂点vに対応するものとして、データ206'から取り出される。
【0041】
ステップ706では、同様に、頂点wにつき、その近くとして関連付けられたランドマークLwのうちのkw個が選ばれる。1つの実施例では、kv = kw = 4である。
【0042】
さて、ステップ708では、頂点vからランドマークLvへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D1に格納される。ステップ710では、LvからLwへの最短経路長が、データ204'から取り出されて、その値が、倍精度浮動小数点の変数D2に格納される。ステップ712では、ランドマークLwから頂点wへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D3に格納される。
【0043】
ステップ714では、D1 + D2 + D3が計算されて、それが、MaxValという値と比較され、その大きい方が、MaxValにセットされる。
【0044】
このようにして、データ206'から、頂点vに対応して取り出されたkv個のランドマークLvと、wに対応して取り出されたkw個のランドマークLwにつき、ステップ708〜714を巡らせ、その結果MaxValに与えられた値が、d(v,w)の上限値ということになる。すなわち、ステップ706から716までが、Lwについての内側のループで、ステップ704からステップ718の外側のループである。kv = kw = 4だと、4 * 4 = 16で、ステップ708〜714は、16回実行される。
【0045】
但し、頂点v,wに対して、k2回の計算を行うと計算量が大きくなりすぎる場合があるので、頂点vの近くのk'v個のランドマークと、頂点wの近くのk'w個のランドマークだけ抜き出して、計算のループの回数をk'v * k'wに削減する、という工夫を行うことができる。
このとき、k'v<=kv, k'w<=kwである。
本発明者のさまざまな試行により、k'v = k, k'w = 1の設定が良好な結果をもたらすことが分かった。
【0046】
このようにして計算された値は、頂点v,wに対応するd(v,w)の上限値として、上限値計算部214を呼び出すプログラムに返される。上限値計算部214を呼び出すプログラムとは、典型的には、クエリー処理部220である。
【0047】
次に、図8のフローチャートを参照して、下限値計算部216の処理について、説明する。
図8のステップ802では、MinValという変数が、初期的に∞にセットされる。この変数は、例えば、C言語だと、倍精度浮動小数点のdoubleとして宣言されるものである。コンピュータの変数の値で、∞ということは現実的にはあり得ないが、ここでは、グラフの経路長としてとり得る値よりも十分大きい値を予めセットしておくものとする。
【0048】
ステップ804では、頂点vにつき、その近くとして関連付けられたランドマークLvのうちのkv個が選ばれる。このような対応付けは、図2に示す、全頂点vの近くのk個のランドマークとの距離データ206'として、既に前処理部212の処理によって予め用意されており、頂点vに対応するものとして、データ206'から取り出される。
【0049】
ステップ806では、同様に、頂点wにつき、その近くとして関連付けられたランドマークLwのうちのkw個が選ばれる。好適な実施例では、kv = kw = 4である。
【0050】
ステップ808では、ランドマークLvからランドマークLwへの最短経路長が、データ204'から取り出されて、その値が、倍精度浮動小数点の変数D1に格納される。ステップ810では、Lvからvへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D2に格納される。ステップ812では、頂点wからランドマークLwへの最短経路長が、データ206'から取り出されて、その値が、倍精度浮動小数点の変数D3に格納される。
【0051】
ステップ814では、D1 - D2 - D3が計算されて、それが、MinValという値と比較され、その小さい方が、MinValにセットされる。
【0052】
このようにして、データ206'から、頂点vに対応して取り出されたkv個のランドマークLvと、wに対応して取り出されたkw個のランドマークLwにつき、ステップ808〜814を巡らせ、その結果MinValに与えられた値が、d(v,w)の下限値ということになる。すなわち、ステップ806から816までが、Lwについての内側のループで、ステップ804からステップ818の外側のループである。kv = kw = 4だと、4 * 4 = 16で、ステップ808〜814は、16回実行される。
【0053】
上限値の計算の場合と同様に、頂点v,wに対して、k2回の計算を行うと計算量が大きくなりすぎることがあるので、頂点vの近くのk'v個のランドマークと、頂点wの近くのk'w個のランドマークだけ抜き出して、計算のループの回数をk'v * k'wに削減する、という工夫を行うことができる。このとき、k'v<=kv, k'w<=kwである。k'v = k, k'w = 1の設定が良好な結果をもたらすことも同様である。
【0054】
このようにして計算された値が、頂点v,wに対応するd(v,w)の下限値として、下限値計算部216を呼び出すプログラムに返される。下限値計算部216を呼び出すプログラムとは、典型的には、探索方法決定部218及びクエリー処理部220である。
【0055】
尚、上限値、下限値の計算ループで、k'v = k, k'w = 1のような工夫を行うことができることを上記で説明したが、このような設定を行うならば、上限値、下限値の計算を行う前に予め、固定的に設定し、後は変更しないようにすることに留意されたい。例えば、頂点p,q,r について、d(p,q) の上下限を計算するときは、pの近くの k'v 個のランドマークと q の近くのk'w個のランドマークを用いて計算し、d(q,r) の上下限を計算するときは、q の近くの k'v 個のランドマークと r の近くのk'w個のランドマークを用いて計算する。
【0056】
また、図7と図8の計算ルーチンを、グラフの頂点v,wのすべてに亘って予め計算して、v,wの上限値と下限値をハードディスク114に記録しておいて、実行時にメイン・メモリ114にロードし、A*探索においては、図7と図8の計算ルーチンを呼び出す代わりに、v,wの値で、メイン・メモリ114にある値をルックアップすることにより、データの計算が高速化されると思われるかもしれない。実際、多くの場合、ルックアップは、その場で計算するよりは短い時間で済む。しかし、このような方法は、ごく少ない頂点のグラフにしか適用できない。すなわち、一般的に、あまり精細でない地図でも、グラフの頂点としてあらわされる地点の数は、少なくともN = 3 × 105程度である。このようなデータをv,wの組について用意するには、組み合わせの数は少なくとも、N2 = 9 × 1010で、それに上記kを掛け、また、倍精度浮動小数点数が8バイトであらわされることを考慮すると、あまり精細でない地図でも、上限値と下限値を記録するには、数テラバイトを下らない記憶容量を要することが理解されよう。
【0057】
次に、図10のフローチャートを参照して、探索方向決定部218の処理を説明する。探索方向決定部218に与えられるのは、グラフの2つの頂点、sとtである。探索方向決定部218は、クエリー処理部220から呼び出されるものであり、典型的には、sとtは、探索すべき始点と終点である。
【0058】
さて、図10のステップ1002では、頂点sから頂点tへの最短経路長の下限値が、下限値計算部216を呼び出すことによって、求められる。同様に、ステップ1004では、頂点tから頂点sへの最短経路長の下限値が、下限値計算部216を呼び出すことによって、求められる。
【0059】
ステップ1006では、このようにして計算された、頂点sから頂点tへの最短経路長の下限値と、頂点tから頂点sへの最短経路長の下限値とが比較され、頂点sから頂点tへの最短経路長の下限値が、頂点tから頂点sへの最短経路長の下限値より大きいと、ステップ1008で、sとtが入れ替えられる。このように、最短経路長の下限値の大きさに応じて、sとtを入れ替える理由は、頂点sから頂点tへの最短経路長の下限値が、頂点tから頂点sへの最短経路長の下限値より大きいと、sからtへ向かう経路の上下限値の精度よりも、tからsへ向かう経路の上下限値の精度の方がよいことが多い、という発明者の経験則によるものである。すなわち、より高い精度の上下限値を用いることで、A*探索の探索速度の向上がはかられる。
【0060】
図11は、ここまでで用意された結果を以って、最終的に経路探索するためのクエリー処理部220の処理を示すフローチャートである。
【0061】
クエリー処理部220に与えられる入力は、始点としてのグラフの頂点sと、終点としてのグラフの頂点tであり、クエリー処理部220は、これらの頂点の間の最短経路を探索して出力として与えるものである。
【0062】
クエリー処理部220を実行するに際して、グラフ全頂点データ202、全ランドマーク間の最短経路長のデータ204、及び全頂点vの近くのランドマークとの最短距離長のデータ206は、予め、データ202'と、データ204'と、データ206'として、ハードディスク114からメイン・メモリ104にロードされているものとする。
【0063】
ステップ1102では、頂点s及びtのデータを以って、図10に関連して説明した、探索方向決定部10が呼ばれる。この結果、頂点s及びtの条件に応じて、sとtの入れ替わりが行われ、その頂点s及びtが、ステップ1104のA*探索ルーチンに引き渡される。
【0064】
次に、ステップ1104のA*探索ルーチンを、C言語的な擬似コードを用いて説明いる。
下記の擬似コードで、頂点 v, w について d(v,w) は、vからwへの最短経路長を表すものとする。また、w(v,w)を、vとwを結ぶ枝の長さとする。
先ず、始点sから終点tまでの最短経路を求めるとして、各頂点vについて以下のように定める。
ここで、π(v)をd(v,t) の下限値とする。その下限値は、図11のフローチャートにおいて、ステップ1108で、v,tに関して下限値計算部216を呼び出すことにより、求められる。
更に、初期設定として、始点sから終点tまでの最短経路を求めたい場合、各頂点vについて以下のように定める。
k(v): v=s のとき k(s):=π(s)、v≠sのときk(v):=∞;
d(v): v=s のとき d(v):=0、v≠sのときd(v):=∞;
prev(v) = NULL;
頂点集合 S = {s};
そうして、次のようにして探索処理を行う。
while( Sが空でない ) {
S から k(v)の値が最も小さい頂点vを除去;
for(vから出ている全ての枝(v,w) について以下の操作を行う) {
if( k(w) > k(v) + w(v,w) - π(v) + π(w)) {
k(w) := k(v) + w(v,w) -π(v)+π(w);
d(w) := d(v) + w(v,w);
prev(w) := v;
if(d(w)+π(w) <= min(d(s,t) の上限値, d(t)))
{ S ← S ∪{w}; }
}
}
}
最後に、d(t) に入っている値が最短経路長になる。また、この擬似コードで示す処理において、d(s,t) の上限値を求める際に、図11のステップ1106に示すように、s,tに関して上限値計算部214が呼び出される。
このとき、prev(t) に入っている頂点を t'、prev(t')に入っている頂点を t'' ・・・とすると、 t←t'←t''←・・・←s が最短経路になる。
【0065】
本発明者は、本発明の効果を確認するために、次のような実験を行った。先ず、下記の表に示すような、7つの重み付きグラフを用意した。また、パラメータは、k=4, kw=4, kv=1を用いた。また、ランドマークは、既に説明したが、下記のような方法で、配置した。
・グラフに配置された頂点を全て含む最小の矩形を取る。
・矩形を縦横それぞれの辺に平行な、矩形の中心を通る2本の直線で田の字に4等分する。
・分割されたそれぞれの領域が規定数以上の頂点を含んでいれば、再度4等分する。
・以後これを繰り返す。
・以上の手続きが終了後、各小領域の中心部に最も近い頂点をランドマークとして選択する。
【表1】
【0066】
グラフ1に対して、文献[1]の方法と、本実施例の方法を、下記の表のような条件で、それぞれ適用した。特に、文献[1]の方法と本実施例の方法にあっては、クラスタは用いないので、「ランドマークまたはクラスタ数」の欄は、ランドマーク数と解釈されたい。すると、探索時間と探索頂点数に関して、本実施例の方法は、明らかに優れた効果を奏したことが見て取れる。尚、この表及び以下の表で、「探索時間」の欄は、ダイクストラ法の性能を1とした場合の性能の程度を表している。すなわち、実際にかかった時間は、ここの「探索時間」に示した数値の逆数に比例する。同様に、「探索頂点数」の欄も、ダイクストラ法で探索される頂点数の1とした場合の、探索される頂点数の少なさの度合いを示すものである。よって、実際に探索された頂点数という意味では、ここの「探索頂点数」に示した数値の逆数に比例する。さらに、前処理後の必要記憶量という意味でも、この実施例が、文献[1]の方法より優れていることが示されている。
【表2】
【0067】
グラフ2及び3に対しても、下記のように、本実施例の方法が、文献[1]よりも、探索性能において優れていることが示されている。
【表3】
【表4】
【0068】
次に、以下では、文献[2]の方法と、本実施例の方法を比較する実験を行った。なお、本発明の方法は、クラスタは用いないので、「ランドマークまたはクラスタ数」の欄は、ランドマークの数と解釈する。一方、文献[2]の方法では、ランドマークは用いず、その代わりにクラスタを用いるので、「ランドマークまたはクラスタ数」の欄は、クラスタの数と解釈する。
下記のようにグラフ4に、文献[2]の方法と、本実施例の方法を適用した結果は、やはり、本実施例の方法が実質的に優れた効果を奏することを示している。この実施例は、前処理後の必要記憶量という意味でも、文献[2]の方法より優れていることが示されている。
【表5】
【0069】
グラフ5〜7に、文献[2]の方法と、本実施例の方法を適用した比較結果は、下記のとおりである。これらの実験例でも、本実施例の方法が、文献[2]の方法よりも顕著な効果を奏することが見て取れる。
【表6】
【表7】
【表8】
【0070】
尚、上記の実施例では、無向グラフとして説明してきたが、本発明は、有向グラフにも適用できる。その場合、探索しようとする経路が、有向グラフの枝の向きと逆であると、その枝は避けて、別の枝を探索する、というような処理を行う。
【0071】
また、上記実施例では、スタンドアロンの環境で、グラフのデータを探索する処理を説明したが、Webサーバ上で、上記で説明した処理を実行して、探索可能な環境を用意し、図2に示すクエリー処理部220の入力のところで、クライアント・コンピュータからの探索問い合わせを受け付け、クエリー処理部220の出力のところで、探索問い合わせを受け付けたクライアント・コンピュータに、探索結果を送信するようにすることもできる。
【0072】
また、最近の携帯電話の性能の向上により、1GB以上のディスク容量と、高速のCPUをもつ携帯電話もあらわれてきている。このような携帯電話には、図2に示すグラフ全頂点データ202、全ランドマーク間の最短経路長のデータ204、全頂点vのその近傍のランドマークとの最短経路長のデータ206、上限値計算部214、下限値計算部216、探索方向決定部218及びクエリー処理部220の全体をそのディスクに格納して、携帯電話だけでスタンドアロンに探索を行い、その結果を携帯電話の画面に表示するようにすることができる。
【0073】
さらに、本発明に係るグラフの探索技法は、カーナビ、地図探索、鉄道路線探索など、頂点が重み付きグラフとして表現される対象における、任意の対象物上での経路探索に適用し得るものであることを理解されたい。
【図面の簡単な説明】
【0074】
【図1】本発明を実施するためのハードウェアのブロック図である。
【図2】本発明を実施するための、データと処理モジュールのブロック図である。
【図3】保存されているグラフ頂点データの論理構造を示す図である。
【図4】重み付きグラフの一部を示す図である。
【図5】グラフの頂点データの前処理部の処理のフローチャートを示す図である。
【図6】ランドマークと他の点の関連付けを示す図である。
【図7】上限値計算部の処理のフローチャートを示す図である。
【図8】下限値計算部の処理のフローチャートを示す図である。
【図9】四角不等式におけるランドマークとその他の点の位置関係を示す図である。
【図10】探索方向決定部の処理のフローチャートを示す図である。
【図11】クエリー処理部の処理のフローチャートを示す図である。
【特許請求の範囲】
【請求項1】
記憶手段をもつコンピュータにより、複数の頂点をもつ重み付きグラフ上で、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用して経路探索するための、グラフ上でのデータ処理プログラムであって、
コンピュータにより、
前記グラフの頂点のうちの複数の頂点をランドマークとして選択する機能と、
前記ランドマークとして選択された頂点Lv, Lw間の最短経路長d(Lv, Lw)の値を計算して、前記記憶手段に記録する機能と、
前記グラフの頂点vの、最短経路長に関して近くの1つまたは複数のランドマークLvを選択して、前記頂点vから前記ランドマークLvへ最短経路長d(v, Lv)の値を計算して、前記記憶手段に記録する機能と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算し、d(v,w)の上限値として提供する機能と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算し、d(v,w)の下限値として提供する機能を実現する、
プログラム。
【請求項2】
前記グラフの頂点の総数をNとしたとき、前記ランドマークの個数が、N1/2個以上選ばれる、請求項1のプログラム。
【請求項3】
前記グラフの頂点vの、最短経路長に関して近くのランドマークとして、4個のランドマークが選ばれる、請求項1のプログラム。
【請求項4】
前記上限値または下限値の計算ステップにおいて、前記グラフの頂点v,wに関して、該頂点vに関連して4個のランドマークが選ばれ、該頂点wに関連して1個のランドマークが選ばれる、請求項1のプログラム。
【請求項5】
コンピュータにより、重み付きグラフ上で、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用して経路探索するための、グラフのデータ処理システムであって、
データを読み出し可能に記録可能な記憶手段と、
グラフの全頂点データを読み出し可能に保持する頂点データ保持手段と、
前記頂点データ保持手段から頂点データを読み取り、前記グラフの頂点のうちの複数の頂点をランドマークとして選択する手段と、
前記選択されたランドマークの情報に基づき、前記ランドマークとして選択された頂点Lv, Lw間の最短経路長d(Lv, Lw)の値を計算し、前記記憶手段に記録する手段と、
前記全頂点データと、前記選択されたランドマークの情報に基づき、前記グラフの頂点vの、最短経路長に関して近くの1つまたは複数のランドマークLvを選択して、前記頂点vから前記ランドマークLvへ最短経路長d(v, Lv)の値を計算し、前記記憶手段に記録するする手段と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算する手段と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算する手段とを有する、
データ処理システム。
【請求項6】
前記グラフの頂点の総数をNとしたとき、前記ランドマークの個数が、N1/2個以上選ばれる、請求項5のデータ処理システム。
【請求項7】
前記グラフの頂点vの、最短経路長に関して近くのランドマークとして、4個のランドマークが選ばれる、請求項5のデータ処理システム。
【請求項8】
前記上限値または下限値の計算ステップにおいて、前記グラフの頂点v,wに関して、該頂点vに関連して4個のランドマークが選ばれ、該頂点wに関連して1個のランドマークが選ばれる、請求項5のデータ処理システム。
【請求項9】
記憶手段をもつコンピュータにより、重み付きグラフ上で、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用して経路探索するための、グラフ上でのデータ処理方法であって、
前記コンピュータの処理により、前記グラフの頂点のうちの複数の頂点をランドマークとして選択するステップと、
前記コンピュータの処理により、前記ランドマークとして選択された頂点Lv, Lw間の最短経路d(Lv, Lw)を計算して、前記記憶手段に記録するステップと、
前記コンピュータの処理により、前記グラフの頂点vの、最短経路長に関して近くの1つまたは複数のランドマークLvを選択して、前記頂点vから前記ランドマークLvへ最短経路d(v, Lv)を計算して、前記記憶手段に記録するステップと、
前記コンピュータの処理により、前記グラフの頂点v,wにつき、前記頂点v関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算し、d(v,w)の上限値として提供するステップと、
前記コンピュータの処理により、前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された、1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算し、d(v,w)の下限値として提供するステップとを有する、
データ処理方法。
【請求項10】
前記グラフの頂点の総数をNとしたとき、前記ランドマークの個数が、N1/2個以上選ばれる、請求項9の方法。
【請求項11】
前記グラフの頂点vの、最短経路長に関して近くのランドマークとして、4個のランドマークが選ばれる、請求項9の方法。
【請求項12】
前記上限値または下限値の計算ステップにおいて、前記グラフの頂点v,wに関して、該頂点vに関連して4個のランドマークが選ばれ、該頂点wに関連して1個のランドマークが選ばれる、請求項9の方法。
【請求項13】
前記複数の頂点をランドマークとして選択するステップが、
グラフに配置された頂点を全て含む最小の矩形を取るステップと、
矩形を縦横それぞれの辺に平行な、矩形の中心を通る2本の直線で田の字に4等分するステップと、
分割されたそれぞれの領域が規定数以上の頂点を含んでいれば、再度4等分するステップを繰り返し、前記ステップの手続きが終了後、各小領域の中心部に最も近い頂点をランドマークとして選択するステップを有する、請求項9の方法。
【請求項14】
コンピュータにより、重み付きグラフ上で、経路探索するためのシステムにおいて、
前記グラフの全頂点のデータを読み出し可能に記録するグラフ頂点記憶手段と、
前記グラフの全頂点のうち、ランドマークとして選択された頂点Lv, Lw間の最短経路長d(Lv, Lw)の値を読み出し可能に記録するランドマーク記憶手段と、
前記グラフの頂点vと、該頂点vの、1つまたは複数の近傍のランドマークLwの間の最短経路長d(v, Lw)の値を読み出し可能に記録する近傍ランドマーク記憶手段と、
前記グラフの頂点v,wにつき、前記頂点v関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記ランドマーク記憶手段と前記近傍ランドマーク記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算しその値を返す上限値計算手段と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記ランドマーク記憶手段と前記近傍ランドマーク記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算しその値を返す下限値計算手段と、
グラフの始点と終点を受け取り、前記上限値計算手段と前記下限値計算手段を呼び出すことにより、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用してA*探索を行い、該始点と終点の間の最短経路を含む探索結果を出力する経路探索手段とを有する、
システム。
【請求項15】
前記グラフの始点と終点を受け取り、前記下限値計算手段を呼び出すことにより、前記グラフの始点から終点への下限値と、前記グラフの終点から始点への下限値を計算して比較し、前記グラフの始点から終点への下限値が、前記グラフの終点から始点への下限値より大きいことに応答して、前記始点と終点とを入れ替えて前記経路探索手段に渡す探索方向決定手段をさらに有する、請求項14のシステム。
【請求項16】
複数のランドマークを選択された重み付きグラフ上で、頂点と前記ランドマークの間の最短経路長を記録する記憶手段をもつコンピュータにより、経路探索するためのプログラムであって、
コンピュータにより、
グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算しその値を返す機能と、
前記グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算しその値を返す機能と、
グラフの始点と終点を受け取り、前記上限値を計算しその値を返す機能と、前記下限値を計算しその値を返す機能を呼び出すことにより、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用してA*探索を行い、該始点と終点の間の最短経路を含む探索結果を出力する経路探索機能とを実現する、
プログラム。
【請求項17】
前記コンピュータにより、
前記グラフの始点と終点を受け取り、前記下限値計算手段を呼び出すことにより、前記グラフの始点から終点への下限値と、前記グラフの終点から始点への下限値を計算して比較し、前記グラフの始点から終点への下限値が、前記グラフの終点から始点への下限値より大きいことに応答して、前記始点と終点とを入れ替えて前記経路探索機能に渡す探索方向決定機能をさらに実現する、請求項16のプログラム。
【請求項18】
複数のランドマークを選択された重み付きグラフ上で、頂点と前記ランドマークの間の最短経路長を記録する記憶手段をもつコンピュータにより、経路探索するための経路探索方法であって、
コンピュータの処理により、グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算しその値を返す上限値計算ステップと、
コンピュータの処理により、前記グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算しその値を返す下限値計算ステップと、
コンピュータの処理により、グラフの始点と終点を受け取り、前記上限値計算ステップと前記下限値計算ステップにより、頂点v,w間の最短経路長d(v,w)の上限値と下限値を計算してA*探索を行い、該始点と終点の間の最短経路を含む探索結果を出力するステップとを有する、
方法。
【請求項19】
前記グラフの始点と終点を受け取り、前記下限値計算手段を呼び出すことにより、前記グラフの始点から終点への下限値と、前記グラフの終点から始点への下限値を計算して比較し、前記グラフの始点から終点への下限値が、前記グラフの終点から始点への下限値より大きいことに応答して、前記始点と終点とを入れ替えて前記経路探索を出力するステップに渡すステップをさらに有する、請求項18の方法。
【請求項1】
記憶手段をもつコンピュータにより、複数の頂点をもつ重み付きグラフ上で、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用して経路探索するための、グラフ上でのデータ処理プログラムであって、
コンピュータにより、
前記グラフの頂点のうちの複数の頂点をランドマークとして選択する機能と、
前記ランドマークとして選択された頂点Lv, Lw間の最短経路長d(Lv, Lw)の値を計算して、前記記憶手段に記録する機能と、
前記グラフの頂点vの、最短経路長に関して近くの1つまたは複数のランドマークLvを選択して、前記頂点vから前記ランドマークLvへ最短経路長d(v, Lv)の値を計算して、前記記憶手段に記録する機能と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算し、d(v,w)の上限値として提供する機能と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算し、d(v,w)の下限値として提供する機能を実現する、
プログラム。
【請求項2】
前記グラフの頂点の総数をNとしたとき、前記ランドマークの個数が、N1/2個以上選ばれる、請求項1のプログラム。
【請求項3】
前記グラフの頂点vの、最短経路長に関して近くのランドマークとして、4個のランドマークが選ばれる、請求項1のプログラム。
【請求項4】
前記上限値または下限値の計算ステップにおいて、前記グラフの頂点v,wに関して、該頂点vに関連して4個のランドマークが選ばれ、該頂点wに関連して1個のランドマークが選ばれる、請求項1のプログラム。
【請求項5】
コンピュータにより、重み付きグラフ上で、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用して経路探索するための、グラフのデータ処理システムであって、
データを読み出し可能に記録可能な記憶手段と、
グラフの全頂点データを読み出し可能に保持する頂点データ保持手段と、
前記頂点データ保持手段から頂点データを読み取り、前記グラフの頂点のうちの複数の頂点をランドマークとして選択する手段と、
前記選択されたランドマークの情報に基づき、前記ランドマークとして選択された頂点Lv, Lw間の最短経路長d(Lv, Lw)の値を計算し、前記記憶手段に記録する手段と、
前記全頂点データと、前記選択されたランドマークの情報に基づき、前記グラフの頂点vの、最短経路長に関して近くの1つまたは複数のランドマークLvを選択して、前記頂点vから前記ランドマークLvへ最短経路長d(v, Lv)の値を計算し、前記記憶手段に記録するする手段と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算する手段と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算する手段とを有する、
データ処理システム。
【請求項6】
前記グラフの頂点の総数をNとしたとき、前記ランドマークの個数が、N1/2個以上選ばれる、請求項5のデータ処理システム。
【請求項7】
前記グラフの頂点vの、最短経路長に関して近くのランドマークとして、4個のランドマークが選ばれる、請求項5のデータ処理システム。
【請求項8】
前記上限値または下限値の計算ステップにおいて、前記グラフの頂点v,wに関して、該頂点vに関連して4個のランドマークが選ばれ、該頂点wに関連して1個のランドマークが選ばれる、請求項5のデータ処理システム。
【請求項9】
記憶手段をもつコンピュータにより、重み付きグラフ上で、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用して経路探索するための、グラフ上でのデータ処理方法であって、
前記コンピュータの処理により、前記グラフの頂点のうちの複数の頂点をランドマークとして選択するステップと、
前記コンピュータの処理により、前記ランドマークとして選択された頂点Lv, Lw間の最短経路d(Lv, Lw)を計算して、前記記憶手段に記録するステップと、
前記コンピュータの処理により、前記グラフの頂点vの、最短経路長に関して近くの1つまたは複数のランドマークLvを選択して、前記頂点vから前記ランドマークLvへ最短経路d(v, Lv)を計算して、前記記憶手段に記録するステップと、
前記コンピュータの処理により、前記グラフの頂点v,wにつき、前記頂点v関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算し、d(v,w)の上限値として提供するステップと、
前記コンピュータの処理により、前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された、1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算し、d(v,w)の下限値として提供するステップとを有する、
データ処理方法。
【請求項10】
前記グラフの頂点の総数をNとしたとき、前記ランドマークの個数が、N1/2個以上選ばれる、請求項9の方法。
【請求項11】
前記グラフの頂点vの、最短経路長に関して近くのランドマークとして、4個のランドマークが選ばれる、請求項9の方法。
【請求項12】
前記上限値または下限値の計算ステップにおいて、前記グラフの頂点v,wに関して、該頂点vに関連して4個のランドマークが選ばれ、該頂点wに関連して1個のランドマークが選ばれる、請求項9の方法。
【請求項13】
前記複数の頂点をランドマークとして選択するステップが、
グラフに配置された頂点を全て含む最小の矩形を取るステップと、
矩形を縦横それぞれの辺に平行な、矩形の中心を通る2本の直線で田の字に4等分するステップと、
分割されたそれぞれの領域が規定数以上の頂点を含んでいれば、再度4等分するステップを繰り返し、前記ステップの手続きが終了後、各小領域の中心部に最も近い頂点をランドマークとして選択するステップを有する、請求項9の方法。
【請求項14】
コンピュータにより、重み付きグラフ上で、経路探索するためのシステムにおいて、
前記グラフの全頂点のデータを読み出し可能に記録するグラフ頂点記憶手段と、
前記グラフの全頂点のうち、ランドマークとして選択された頂点Lv, Lw間の最短経路長d(Lv, Lw)の値を読み出し可能に記録するランドマーク記憶手段と、
前記グラフの頂点vと、該頂点vの、1つまたは複数の近傍のランドマークLwの間の最短経路長d(v, Lw)の値を読み出し可能に記録する近傍ランドマーク記憶手段と、
前記グラフの頂点v,wにつき、前記頂点v関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記ランドマーク記憶手段と前記近傍ランドマーク記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算しその値を返す上限値計算手段と、
前記グラフの頂点v,wにつき、前記頂点vに関して選択された1つまたは複数のランドマークLvと、前記頂点wに関して選択された1つまたは複数のランドマークLwに関して、前記ランドマーク記憶手段と前記近傍ランドマーク記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算しその値を返す下限値計算手段と、
グラフの始点と終点を受け取り、前記上限値計算手段と前記下限値計算手段を呼び出すことにより、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用してA*探索を行い、該始点と終点の間の最短経路を含む探索結果を出力する経路探索手段とを有する、
システム。
【請求項15】
前記グラフの始点と終点を受け取り、前記下限値計算手段を呼び出すことにより、前記グラフの始点から終点への下限値と、前記グラフの終点から始点への下限値を計算して比較し、前記グラフの始点から終点への下限値が、前記グラフの終点から始点への下限値より大きいことに応答して、前記始点と終点とを入れ替えて前記経路探索手段に渡す探索方向決定手段をさらに有する、請求項14のシステム。
【請求項16】
複数のランドマークを選択された重み付きグラフ上で、頂点と前記ランドマークの間の最短経路長を記録する記憶手段をもつコンピュータにより、経路探索するためのプログラムであって、
コンピュータにより、
グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算しその値を返す機能と、
前記グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算しその値を返す機能と、
グラフの始点と終点を受け取り、前記上限値を計算しその値を返す機能と、前記下限値を計算しその値を返す機能を呼び出すことにより、頂点v,w間の最短経路長d(v,w)の上限値と下限値を利用してA*探索を行い、該始点と終点の間の最短経路を含む探索結果を出力する経路探索機能とを実現する、
プログラム。
【請求項17】
前記コンピュータにより、
前記グラフの始点と終点を受け取り、前記下限値計算手段を呼び出すことにより、前記グラフの始点から終点への下限値と、前記グラフの終点から始点への下限値を計算して比較し、前記グラフの始点から終点への下限値が、前記グラフの終点から始点への下限値より大きいことに応答して、前記始点と終点とを入れ替えて前記経路探索機能に渡す探索方向決定機能をさらに実現する、請求項16のプログラム。
【請求項18】
複数のランドマークを選択された重み付きグラフ上で、頂点と前記ランドマークの間の最短経路長を記録する記憶手段をもつコンピュータにより、経路探索するための経路探索方法であって、
コンピュータの処理により、グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,v) + d(Lv,Lw) + d(w,Lw)の上限値を計算しその値を返す上限値計算ステップと、
コンピュータの処理により、前記グラフの頂点v,wにつき、前記頂点vの近傍として選択された1つまたは複数のランドマークLvと、前記頂点wの近傍として選択された1つまたは複数のランドマークLwに関して、前記記憶手段から値を読み出すことにより、d(Lv,Lw) - d(Lv,v) - d(w,Lw)の下限値を計算しその値を返す下限値計算ステップと、
コンピュータの処理により、グラフの始点と終点を受け取り、前記上限値計算ステップと前記下限値計算ステップにより、頂点v,w間の最短経路長d(v,w)の上限値と下限値を計算してA*探索を行い、該始点と終点の間の最短経路を含む探索結果を出力するステップとを有する、
方法。
【請求項19】
前記グラフの始点と終点を受け取り、前記下限値計算手段を呼び出すことにより、前記グラフの始点から終点への下限値と、前記グラフの終点から始点への下限値を計算して比較し、前記グラフの始点から終点への下限値が、前記グラフの終点から始点への下限値より大きいことに応答して、前記始点と終点とを入れ替えて前記経路探索を出力するステップに渡すステップをさらに有する、請求項18の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2008−157698(P2008−157698A)
【公開日】平成20年7月10日(2008.7.10)
【国際特許分類】
【出願番号】特願2006−345224(P2006−345224)
【出願日】平成18年12月22日(2006.12.22)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【Fターム(参考)】
【公開日】平成20年7月10日(2008.7.10)
【国際特許分類】
【出願日】平成18年12月22日(2006.12.22)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【Fターム(参考)】
[ Back to top ]