外部メモリからのポイント−ポイントの最短パスの計算
【課題】地点の集合の中で最短パスを計算するための方法およびシステムを提供する。
【解決手段】２つの元のランドマークから開始し、ランドマーク選択を他のランドマークまでの距離に基づいて改善することによって、ランドマークの集合を動的に選択する。次いで、ランドマークをＡ*探索と共に使用して、ソースからディスティネーションまでの最短パスを見つける。必要な記憶容量を低減するために、追加の改良が提供される。ランドマークは、ツリーベースのヒューリスティックスや局所探索を用いるなど、１つまたは複数の選択ヒューリスティックスを使用して前処理中にランドマークのサブ集合から生成または選択することができる。
【解決手段】２つの元のランドマークから開始し、ランドマーク選択を他のランドマークまでの距離に基づいて改善することによって、ランドマークの集合を動的に選択する。次いで、ランドマークをＡ*探索と共に使用して、ソースからディスティネーションまでの最短パスを見つける。必要な記憶容量を低減するために、追加の改良が提供される。ランドマークは、ツリーベースのヒューリスティックスや局所探索を用いるなど、１つまたは複数の選択ヒューリスティックスを使用して前処理中にランドマークのサブ集合から生成または選択することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に経路指定の分野に関し、より詳しくはコンピュータ化された地図上の２点間の最良経路を判定することに関する。
【背景技術】
【０００２】
「道路地図」プログラムとして知られる既存のコンピュータプログラムは、デジタル地図を提供し、多くの場合、市街路レベルに至る詳細な道路網を完備している。通常、ユーザはある地点を入力することができ、道路地図プログラムが選択された地点のオンスクリーンの地図を表示する。幾つかの既存の道路地図プログラムは、典型的には２つの地点間の「最良経路」を計算する能力を含む。言い換えると、ユーザは２つの地点を入力することができ、道路地図プログラムがソース地点（ｓｏｕｒｃｅ ｌｏｃａｔｉｏｎ）からディスティネーション地点（ｄｅｓｉｔｎａｔｉｏｎ ｌｏｃａｔｉｏｎ）までの道案内を計算することになる。道案内は、典型的には距離、移動時間、およびユーザが好む運転速度や途中の景色の良さなどいくつかのユーザの好みに基づいている。地点間の最良経路の計算には、多くの計算時間と計算リソースが必要となり得る。
【０００３】
既存の道路地図プログラムは、最短パスを計算するためにＥ．Ｄｉｊｋｓｔｒａに帰属する方法の変形を用いている。Ｄｉｊｋｓｔｒａの方法は、非特許文献１に記載されており、それが教示する全てについて、いかなる部分も除外することなくその全体が参照により本明細書に組み込まれる。この文献では、「最短」は「最小コスト」を意味することに留意されたい。というのは、各道路セグメントには、その道路セグメントの長さに必ずしも直接関係しないコストまたは重みが割り当てられているからである。各道路についてコストの計算方法を変えることにより、最速、最短または好みの経路について最短パスを生成することができる。
【０００４】
【特許文献１】米国特許出願第１０／９２５７５１号明細書
【非特許文献１】Ｃｏｒｍｅｎ，Ｌｅｉｓｅｒｓｏｎ ａｎｄ Ｒｉｖｅｓｔ，Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ，ＭＩＴ Ｐｒｅｓｓ，１９９０，ｐｐ．５１４−５３１
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、Ｄｉｊｋｓｔｒａの当初の方法は、スキャンされる地点および可能なパスの数が多いので、実際には常に効率的であるとは限らない。その代わりに、現代の多くの道路地図プログラムは、最短パス計算をほぼ正しい方向に「誘導」するためにＡ*探索（ヒューリスティックなまたは目標指向型探索（ｇｏａｌ−ｏｒｉｅｎｔｅｄ ｓｅａｒｃｈ）とも呼ばれる）を含むＤｉｊｋｓｔｒａの方法のヒューリスティックな変形を使用している。このようなヒューリスティックな変形は、典型的に中間地点とディスティネーション地点との間のパスの重みを推定することを伴う。良好な推定は、道路地図プログラムによって考慮されるべき地点および道路セグメントの数を低減し、その結果最短パスがより速く計算されるが、悪い推定だと逆効果となり、最短パスを計算するのに必要な全体の時間が増加することがある。推定がいくつかの特定のプロパティで距離の下限（ｌｏｗｅｒ−ｂｏｕｎｄ）である場合、Ａ*探索は最適（最短）パスを計算する。これらの下限が実際のパスの重みに近いほど、推定およびアルゴリズムのパフォーマンスは良くなる。バウンドされている実際の値に非常に近い下限は、「良好」であると言われる。以前から知られているヒューリスティックな変形は、地点間のユークリッド距離（すなわち、「直線距離」）などの下限推定技法を使用するが、これらの技法はあまり良好なものではない。
【０００６】
その全体が参照により本明細書に組み込まれる２００４年８月２５日出願の「Ｅｆｆｉｃｉｅｎｔｌｙ Ｆｉｎｄｉｎｇ Ｓｈｏｒｔｅｓｔ Ｐａｔｈｓ Ｕｓｉｎｇ Ｌａｎｄｍａｒｋｓ Ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｌｏｗｅｒ−Ｂｏｕｎｄ Ｄｉｓｔａｎｃｅ Ｅｓｔｉｍａｔｅｓ」という名称の特許文献１には、三角不等式に基づく最短パスを決定するためのアルゴリズムが記載されている。アクティブなランドマークの動的な選択を提供し、パス計算技法やシステムなどでの使用についてメモリ効率を提供することが望ましいであろう。また、ツリーベースのビューリスティックスを使用し、ランドマークの生成において局所探索を使用することが望ましいであろう。
【課題を解決するための手段】
【０００７】
以下の概要は、本発明の様々な態様の概略を提供する。本発明の全ての重要な態様についての包括的な説明を提供したり、本発明の範囲を画定したりするものではない。むしろ、この要約は、これに続く詳細な説明および図面の導入部として意図されている。
【０００８】
本発明は、非負の孤長（ｎｏｎｎｅｇａｔｉｖｅ ａｒｃ ｌｅｎｇｈｔ）を有する有向グラフ（ｄｉｒｅｃｔｅｄ ｇｒａｐｈｓ）上のポイント−ポイントの最短パスの問題（Ｐ２Ｐ問題）を解くことを対象としている。正確な最短パスを見つけることが望ましい。問題を解くためにグラフのあらゆる頂点（ｖｅｒｔｅｘ）を検討しなければならない単一ソースの場合と異なり、Ｐ２Ｐ問題は小さなサブグラフを検討しながら解くことができる。グラフの小さな部分を検討することにより、プロセスの実行時間が改善されるだけでなく、外部メモリの実装が可能になる。一例の実施形態では、グラフと前処理データを二次ストレージ（たとえば、ディスクまたはフラッシュメモリ）に保持し、グラフの検討した部分について使用したデータをメインメモリ（たとえば、ＲＡＭ）に保持する。このアプローチが望ましいのは、いくつかのアプリケーションは大きなグラフ上で機能したり、小さなデバイス（たとえば、モバイルまたはハンドヘルドデバイス）上で稼働したり、あるいはその両方に該当したりするからである。
【０００９】
本発明のいくつかの態様によれば、ランドマークは、ツリーベースのヒューリスティックスや局所探索（ｌｏｃａｌ ｓｅａｒｃｈ）を用いるなど、１つまたは複数の選択ヒューリスティックスを使用して前処理中に生成または選択することができる。
【００１０】
本発明のさらなる特徴および利点は、添付の図面を参照しながら行われる例示的実施形態についての以下の詳細な説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１１】
前述の要約ならびに好ましい実施形態についての以下の詳細な説明は、添付の図面を参照と共に読むとよりよく理解されよう。本発明を例示する目的で図面には本発明の例示的な構成が示されているが、本発明は開示された具体的な方法および手段に限定されるものではない。
【００１２】
この内容は、法的要件を満たすために、詳細に説明されている。しかし、その説明自体は、本発明の範囲を限定するものではない。そうではなくて、本発明者らは、請求される内容が、本明細書に説明されたものと類似の異なるステップまたはステップの組合せを含むように、他の現在または将来の技術と共に、別のやり方で具体化できることを企図している。さらに、「ステップ」という言葉は、用いられる方法の様々な要素を意味するように本明細書では使用されることがあるが、この言葉は、個々のステップの順序が明示的に記載されていない限り、そしてその場合を除いて、本明細書で開示される様々なステップ中のまたはステップ間の特定の順序を示唆しているものと解釈されるべきではない。
【００１３】
本発明は、添付の図面と併せて読まれるべき以下の詳細な説明を通じてより完全に理解されるであろう。この説明において、同様の番号は、本発明の様々な実施形態内の同様の要素を参照している。本発明は、適切なコンピューティング環境で実施されているものとして示される。必須ではないが、本発明はパーソナルコンピュータによって実行される手順などのコンピュータ実行可能命令という一般的なコンテキストで説明されるであろう。一般に、手順には、特定のタスクの実行または特定の抽象データ型の実施を行うプログラムモジュール、ルーチン、関数、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。さらに、本発明がハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサに基づくあるいはプログラム可能な民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む他のコンピュータシステム構成と共に実施できることは、当業者には明らかであろう。本発明はまた、タスクが通信ネットワークでリンクされたリモート処理装置によって実行される分散コンピューティング環境で実施され得る。分散コンピューティングでは、プログラムモジュールを、ローカルおよびリモートの両方のメモリストレージデバイスにも置くことができる。コンピュータシステムという用語は、分散コンピューティング環境で見られ得るようなコンピュータのシステムを指すために使用することができる。
【００１４】
図１は、本発明を実施することができる、適切なコンピューティングシステム環境１００を示す。コンピューティングシステム環境１００は、適切なコンピューティング環境の一例に過ぎず、本発明の使用の範囲または機能に関するいかなる限定も示唆するものではない。また、コンピューティングシステム環境１００も、例示的動作環境１００中で示されるコンポーネントの１つまたはそれらの組合せに関する依存性または要件を有するものと解釈されるべきではない。本発明の一実施形態は、例示的動作環境１００に示される各コンポーネントを含むが、本発明のより典型的な別の実施形態は、たとえばネットワーク通信に必要なもの以外の入出力デバイスなど、本質的でないコンポーネントを含まない。
【００１５】
図１を参照すると、本発明を実施するための例示的システムは、コンピュータ１１０の形態の汎用コンピューティングデバイスを含む。コンピュータ１１０のコンポーネントには、処理装置１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステムコンポーネントを処理装置１２０に結合するシステムバス１２１が含まれ得るが、それだけには限定されない。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのいずれかを使用したローカルバスを含めて、いくつかのタイプのバス構造のずれでもよい。限定ではなく例として、このようなアーキテクチャとしては、ＩＳＡ（Ｉｎｄｕｓｔｒｙ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、およびメザニンバス（Ｍｅｚｚａｎｉｎｅ ｂｕｓ）とも呼ばれるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスなどがある。さらに、コンピュータ１１０のコンポーネントには、メモリキャッシュ１２２も含まれ得る。処理装置１２０は、メモリキャッシュからのデータに、システムメモリ１３０からのデータよりも速くアクセスすることができる。メモリキャッシュ１２２は典型的に、システムメモリ１３０からの直前にアクセスされたデータまたは処理装置１２０によって最近処理されたデータを格納する。処理装置１２０は、システムメモリ１３０からデータを取り出すのに先立って、そのデータがメモリキャッシュ１２２に現在格納されているかどうかをチェックすることができる。そうである場合、「キャッシュヒット」が生じることになり、データは一般により遅いシステムメモリ１３０からではなく、メモリキャッシュ１２２から取り出される。
【００１６】
コンピュータ１１０は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０によってアクセスできる利用可能な任意の媒体でよく、揮発性および不揮発性の媒体、リムーバブルおよび非リムーバブルの媒体を含む。限定ではなく例として、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を備えることができる。コンピュータ記憶媒体には、コンピュータ可読命令、デーダ構造、プログラムモジュールまたは他のデータなど、情報の格納のための任意の方法または技術で実施される揮発性および不揮発性の媒体、リムーバブルおよび非リムーバブルの媒体が含まれる。コンピュータ記憶媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤもしくは他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または所望の情報を格納するために使用し、コンピュータ１１０によってアクセスできる他の任意の媒体があるが、それだけには限定されない。通信媒体は、通常、コンピュータ可読命令、デーダ構造、プログラムモジュール、またはその他のデータを、搬送波や他のトランスポート機構などの変調データ信号に具現し、それには任意の情報送達媒体が含まれる。「変調データ信号」という用語は、信号に情報を符号化するようにその１つまたは複数の特徴を設定または変更した信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、ＲＦ、赤外線およびその他の無線媒体が含まれる。上記の任意の組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。
【００１７】
システムメモリ１３０は、たとえばリードオンリーメモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２など、揮発性および／または不揮発性のメモリの形態のコンピュータ記憶媒体を含む。たとえば起動の際にコンピュータ１１０内の要素間での情報の転送を助ける基本ルーチンを含む基本入出力システム（ＢＩＯＳ）１３３は通常、ＲＯＭ１３１に格納される。ＲＡＭ１３２は、通常、処理装置１２０から直ぐにアクセス可能であり、そして／または処理装置１２０によって現在操作されているデータおよび／またはプログラムモジュールを含む。限定ではなく例として、図１はオペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００１８】
コンピュータ１１０は、他の揮発性および／または不揮発性の媒体、リムーバブルおよび／または非リムーバブルの媒体を含むことができる。あくまで一例として、図１は、非リムーバブルで不揮発性の磁気媒体を読み書きするハードディスクドライブ１４１、リムーバブルで不揮発性の磁気ディスク１５２を読み書きする磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭや他の光媒体などのリムーバブルで不揮発性の光ディスク１５６を読み書きする光ディスクドライブ１５５を示す。この例示的動作環境で使用できる他の揮発性および／または不揮発性の媒体、リムーバブルおよび／または非リムーバブルの媒体としては、磁気テープカセット、フラッシュメモリカード、ＤＶＤ、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどがあるが、それだけには限定されない。ハードディスクドライブ１４１は、通常、インターフェース１４０などの非リムーバブルメモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常インターフェース１５０など、リムーバブルメモリインターフェースを介してシステムバス１２１に接続される。
【００１９】
上に説明し、図１に示したドライブおよびそれらに関連するコンピュータ記憶媒体は、コンピュータ１１０用のコンピュータ可読命令、デーダ構造、プログラムモジュールまたは他のデータのストレージを提供する。たとえば、図１では、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を格納しているものとして示してある。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じでもよく、異なっていてもよいことに留意されたい。ここでは、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７が少なくとも異なるコピーであることを示すために異なる参照番号が付されている。ユーザはタブレット、または電子式デジタイザ１６４、マイクロフォン１６３、キーボード１６２および一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティングデバイス１６１を介して、コンピュータ１１０にコマンドおよび情報を入力することができる。他の入力装置（図示せず）としては、ジョイスティック、ゲームパッド、衛星アンテナ、スキャナなどがある。これらおよび他の入力装置は、システムバスに結合されているユーザ入力インターフェース１６０を介して処理装置１２０に接続されることが多いが、パラレルポート、ゲームポートまたはユニバーサルシリアルバス（ＵＳＢ）など他のインターフェースおよびバス構造によって接続することもできる。モニタ１９１または他のタイプの表示装置も、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続されている。モニタ１９１は、タッチスクリーンパネルなどと統合することもできる。モニタおよび／またはタッチスクリーンパネルは、たとえばタブレットタイプのパーソナルコンピュータの場合など、コンピューティングデバイス１１０が組み込まれている筐体に物理的に結合することができることに留意されたい。加えて、コンピューティングデバイス１１０などのコンピュータは、出力周辺インターフェース１９５などを介して接続することができるスピーカ１９７やプリンタ１９６などの他の周辺出力装置を含んでもよい。
【００２０】
コンピュータ１１０は、リモートコンピュータ１８０など１つまたは複数のリモートコンピュータへの論理接続を用いてネットワーク化された環境で動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイスまたは他の共通ネットワークノードとすることができ、図１ではメモリストレージデバイス１８１のみが図示されているが、通常、コンピュータ１１０に関連して上述した要素の多くまたは全てを含む。図１に示された論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含むこともできる。このようなネットワーク環境は、オフィス、エンタープライズ規模のコンピュータネットワーク、イントラネットおよびインターネットにおいて一般的となっている。たとえば、本発明において、コンピュータ１１０はデータの移動元であるソースマシンを構成することができ、リモートコンピュータ１８０はディスティネーションマシンを構成することができる。しかし、ソースマシンおよびディスティネーションマシンはネットワークまたは他の手段によって接続されている必要はなく、代わりに、データはソースのプラットフォームによって書き込まれ、ディスティネーションの１つまたは複数のプラットフォームによって読み取ることができる任意の媒体を介して移動することができる。
【００２１】
ＬＡＮネットワーク環境で使用する場合、コンピュータ１１０はネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境で使用する場合、コンピュータ１１０は、通常、インターネットなど、ＷＡＮ１７３上での通信を確立するためのモデム１７２または他の手段を含む。モデム１７２は、内蔵でも外付けでもよく、ユーザ入力インターフェース１６０または他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク化された環境では、コンピュータ１１０に関連して図示されたプログラムモジュールあるいはその一部は、リモートメモリストレージデバイスに格納することができる。限定ではなく例として、図１はリモートアプリケーションプログラム１８５をメモリ装置１８１上にあるものとして示している。図示されたネットワーク接続は例示的であり、コンピュータ間の通信リンクを確立する他の手段を使用することもできることが理解できよう。
【００２２】
図２を参照すると、本発明が潜在的に活用されるコンピューティング環境の簡単な例が示されている。この例示の環境において、コンピューティングデバイス２００は、通信媒体を介した通信を容易にするネットワークインタフェースカード（具体的に図示せず）を含む。図２に示す特定の例では、コンピューティングデバイス２００は物理接続を介してローカルエリアネットワーク２０２と通信を行う。あるいは、コンピューティングデバイス２００はＷＷＡＮもしくはＷＬＡＮ媒体、または他の通信媒体を介してローカルエリアネットワーク２０２と通信を行ってもよい。サポートされるネットワーク媒体の結果として、コンピューティングデバイス２００のユーザは、典型的にコンピューティングデバイス２００上で実行されているブラウザアプリケーション２０４の使用を通じて、ネットワークリソースにアクセスすることができる。ブラウザアプリケーション２０４は、たとえばインターネット２０５を介したリモートネットワークとの通信を容易にする。１つの例示的なネットワークリソースが、地図経路サーバ２０８上で稼働する地図経路サービス２０６である。地図経路サーバ２０８は、物理的地点および所在地住所のデータベース２１０を、隣接物、距離、速度制限および格納された地点間のその他の関係などの経路情報と共にホストする。コンピューティングデバイス２００のユーザは、通常、ブラウザアプリケーション２０４を通じて、要求として開始地点およびディスティネーション地点を入力する。地図経路サーバ２０８は、要求を受け取り、開始地点からディスティネーション地点に到達するためにデータベース２１０に格納された地点から最適経路を生成する。次いで、地図経路サーバ２０８は、その最適経路を、要求元のコンピューティングデバイス２００に送り返す。あるいは、地図経路サーバ２０８は、コンピューティングデバイス２００上でホストされ、コンピューティングデバイス２００はローカルエリアネットワーク２０２と通信を行う必要はない。
【００２３】
しかし、最適経路の計算は、些細なタスクではない。ルーティング方法を視覚化し、実施するには、地点および接続するセグメントを、頂点および有向エッジを有する抽象グラフとして表すことが有用である。頂点は地点に対応し、エッジは地点間の道路セグメントに対応する。エッジは、好ましくは移動距離、速度制限および／または対応する道路セグメントについての他の基準に従って重み付けされる。一般的な用語である「長さ」および「距離」は、本文においてはエッジの重みまたはコストが測定されるメトリックを包含するように使用される。パスの長さまたは距離は、パスに含まれるエッジの重みの合計である。たとえば、図３のグラフにおいて、頂点ｓ３０４から頂点ｗ３０６に至るエッジ（ｓ，ｗ）３０２は長さ５を有する。ｓ３０４からｕ３０８へ、ｖ３１０へ、ｔ３１２へのパスの長さは１０＋１＋４＝１５である。ｓ３０２からｔ３１２へのより短いパスはｗ３０６経由であり、長さ７である。コンピューティングデバイスによる操作のために、グラフは、好ましくはレコードの集まりとしてコンピュータメモリの連続ブロックに格納することができ、各レコードは関連データと共に単一のグラフノードまたはエッジを表している。
【００２４】
最適経路を計算する１つのアプローチは、Ｄｉｊｋｓｔｒａの方法を使用することである。一般に、Ｄｉｊｋｓｔｒａの方法は、各頂点毎に距離ラベルおよびその頂点が既にスキャンされているかどうかを示すフラグを維持することにより、ある単一の「ソース（ｓｏｕｒｃｅ）」の頂点から他の全ての頂点までの最短パスを見つける。距離ラベルは最初に各頂点について無限大に設定され、既にスキャンされた頂点のみを使用してソースからその頂点までの最短パスの重みを表す。この方法では未スキャンの頂点を取り上げ、その頂点から出ている全ての（すなわち、隣接する頂点に至る）エッジが緩和される。Ｄｉｊｋｓｔｒａの方法の直接的な実装では、スキャンの対象に最も低い距離ラベルを有する未スキャンの頂点が選ばれる。エッジ（ｖ，ｗ）を緩和するために、この方法はｗのラベルされた距離が、ｖのラベルされた距離とエッジ（ｖ，ｗ）の実際の重みの合計よりも大きいかどうかをチェックする。そうである場合、この方法はその合計と等しくなるようにｗの距離ラベルを更新する。ある頂点がスキャンされると、その距離ラベルがその後に変わらないことを数学的に示すことができる。幾つかの実装では、さらに各スキャン済み頂点ｗ毎に親ラベルを維持し、それによって出エッジが最短パスでｗに至る頂点ｖが示される。この方法で頂点がスキャンされるとき、その頂点について親ポインタによって規定されたパスが最短パスである。
【００２５】
Ｄｉｊｋｓｔｒａの方法は、あるソースから他の全ての頂点までの最短パスを計算するために使用することができるが、あるソースから単一のディスティネーションの頂点までの最短パスを見つけるために使用することもでき、この方法はそのディスティネーションの頂点がスキャンされようとするときに終了する。直感的に、Ｄｉｊｋｓｔｒａの方法は、ソースの頂点を中心とする円内を探索し、頂点を選んでスキャンすることによりその円の半径を増大していく。特定のディスティネーションまでのパスが求められている場合、この方法は、円の境界上のディスティネーションと共に終了する。図４に示されるように、Ｄｉｊｋｓｔｒａの方法を介して頂点ｓ４０２から頂点ｔ４０４までの最短パスを探索すると、ｓ４０２からの距離の昇順において可能性のある頂点がスキャンされる結果になる。任意の頂点までの最短パスも、既にスキャンされた頂点を通過するだけである。頂点ｔ４０４までの距離および最短パスが決定されるとこの方法は停止し、ｓ４０２からの距離がｔ４０４よりも遠い頂点４０６が未スキャンのまま残される。この時点で、従来のＤｉｊｋｓｔｒａの方法では、ｓ４０２からの距離がｔ４０４よりも小さい全ての頂点４０８がスキャンされている。
【００２６】
先に述べたように、Ｄｉｊｋｓｔｒａの当初の方法は、スキャンされる地点および可能なパスの数が多いので、ソースから特定のディスティネーションまでの最短パスを見つけるのに実際には常に効率的であるとは限らない。その代わりに、最短パス計算をほぼ正しい方向に誘導するために、Ａ*探索を使用することができ、それによって途中でスキャンされる頂点の数を減らすことができる。Ａ*探索は、上述したＤｉｊｋｓｔｒａの方法と同様に動作するが、各頂点の推定をさらに維持する。推定は通常、その頂点からディスティネーションまでのパスの実際の重みの下限である。スキャンについてラベルされた頂点を選ぶために、Ａ*探索はラベルされた距離と推定との合計が最小である未スキャンの頂点を選ぶ。Ｄｉｊｋｓｔｒａの方法の残りは同じままである。頂点にわたる推定の集合は、ディスティネーションに対する「ポテンシャル」関数を形成し、頂点のポテンシャルはその頂点からディスティネーションまでの最短パスの重みの推定である。
【００２７】
正確な結果を数学的に保証するために、一般にヒューリスティックな変形は「実現可能な」推定を使用することがある（すなわち、ｖからｗまでのエッジについて、ｖの推定引くｗの推定はエッジの実際の重みを超えない）。これらの下限が実際のパスの重みに近いほど、推定が良くなる。一例を図５に示すが、ここでヒューリスティック探索をｓ５０２からｔ５０４に誘導するために推定が使われている。ヒューリスティック探索によってスキャンされる頂点の集合５０５は、ｔ５０４までの推定距離足すｓ５０４からの実際の距離が最小となる頂点である。この例示的ヒューリスティック探索により、Ｄｉｊｋｓｔｒａの方法の直接的な適用であればスキャンされていたであろう頂点ｖ５０６およびｗ５０８のスキャンが節約された。
【００２８】
以前の下限実装で用いられていた共通の技法は、ユークリッドグラフのユークリッド距離のように、その領域で含意された情報を使用して下限を計算している。本発明の実施形態は、その代わりに「ランドマーク」の小さな集合を選択し、全ての頂点について、あらゆるランドマークまでの、およびあらゆるランドマークからの距離を事前計算する。ここで、例示的な１つの技法を、図６を参照して説明する。前処理ステップ６０２において、集合中の各ランドマークまでの、および各ランドマークからの距離が、各地点（すなわち、対応するグラフ内の頂点）について計算される。ステップ６０４で、ユーザが開始地点およびディスティネーション地点を入力し、ステップ６０６で、そのクエリが地図サービスへ送られる。地図サービスはランドマークを使用して、ステップ６１０で、ソースからディスティネーションまでの最短パスを見つけるためにＡ*探索を行って、探索によって必要とされるときには下限を計算する。ステップ６１２で、地図サービスは最短パスをユーザに戻す。
【００２９】
ランドマークまでの、およびランドマークからの距離は、ディスティネーションまでの距離について下限推定を計算するのに使用することができる。距離は「三角不等式」（すなわち、任意の頂点ｕから他の頂点ｗまでの距離は、ｕから任意の中間頂点ｖまでの距離と、ｖからｗまでの距離との和を超えない）を満たし、次のようにランドマークと共に使用して良好な下限を生成することができる。ランドマークＬを考える。すると、三角不等式により、ｕからＬまでの距離引くｖからＬまでの距離は、ｕからｖまでの距離を超えない。同様に、Ｌからの距離を用いて、Ｌからｖまでの距離引くＬからｕまでの距離は、ｕからｖまでの距離を超えない。
【００３０】
図７を参照すると、本発明の実施形態に従って、ランドマークまでの、およびランドマークからの距離を用いて所定のディスティネーションｔについての緊密な下限推定値を計算するための方法が説明されている。この方法では、ステップ７０２で最初０に設定される最大値を維持することによってある所与の頂点ｕからｔまでの距離に関する緊密な下限が計算される。ステップ７０４で、ランドマークの集合からあるランドマークが選択される。ステップ７０６で、ｕからＬまでの距離とｔからＬまでの距離との差が計算され、ステップ７０８でこの差が最大値と比較される。最大値よりも大きい場合、ステップ７１０で最大値がこの値によって更新される。方法は、次いで、ステップ７１２でＬからｔまでの距離とＬからｕまでの距離との差が計算され、ステップ７１４でこの差が最大値と比較される。最大値よりも大きい場合、ステップ７１６で最大値がこの値によって更新される。方法は、ステップ７１８で、さらに考慮すべきランドマークがないかチェックされる。ある場合、ステップ７０４に戻ることで別のランドマークが選択される。それ以外の場合、方法は終了し、ｕからｔまでの推定距離として最大値が使用される。方法は、グラフ中の各頂点について繰り返し行うことができる。
【００３１】
Ｌまでの、およびＬからの距離が事前計算されるので、各差は一定時間に計算され（すなわち、入力のサイズに関わらず、一定量の計算）、一定の数のランドマークが使用される場合、各頂点ｕの最大差も一定時間内に見つけることもできる。
【００３２】
本発明の実施形態は、全てのランドマークを使用しないこともある。これは、必要な計算回数が少なくなるので、より効率的であることがある。ある所与のソースおよびディスティネーションについて、本発明の実施形態は、ソースからディスティネーションまでの距離に関して最も高い下限を与えるランドマークのサブ集合を選択する。最短パスの計算は、下限を計算するときにこのサブ集合に限定される。サブ集合は静的でも動的でもよく、すなわち計算中に更新されてもよい。
【００３３】
図８に注目すると、本発明の複数の実施形態によって実行されるＡ*探索と共にランドマークを使用することの有効性を示すために、頂点およびエッジの集合が図示されている。この例において、ソースｓ８０２およびディスティネーションｔ８０４は地図上で互いに離れており、ランドマークＬ８０６はｓから、ｔとおよそ同じ方向にある。ｓ８０２からＬ８０６までの最短経路は、ｓ８０２から高速道路までのセグメント８０８、高速道路のみを使用するセグメント８１２、および高速道路からＬまでのセグメント８１４から構成されていそうである。さらに、ｔ８０４までの最短経路は高速道路までの同じセグメント８０８を辿り、しばらく同じ高速道路のパス８１２を進むが、早く出て地方道路８１８を通ってｔ８０４に至る。言い換えると、Ｌ８０６の良好な選択では、ｓ８０２からＬ８０６およびｔ８０４までの最短パスは最初のセグメント８２０を共有する。このセグメント上の頂点ｖ８２４から頂点ｗ８２６までのエッジ８２２を考慮されたい。Ｌ８０６までの距離および三角不等式で与えられる下限関数は、ｖ８２４からＬ８０６までの距離の下限が、ｗ８２６からＬ８０６までの距離の下限とｖ８２４からｗ８２６までのエッジ８２２の実際の重みとの和に等しいという性質を有することが容易に分かる。ｓ８０２からｔ８０４までの最短パスの共有パスセグメント上の任意の２つの頂点についても同じことが言える。これにより、これらのエッジがスキャンされる最初のものとなるであろう。言い換えると、ｖ８２４からｗ８２６までのエッジの「低減されたコスト」が、そのエッジの実際の重みにｖ８２４でのポテンシャルを加え、ｗ８２６でのポテンシャルを減じたものであると定義され、実際の重みは低減されたコストによって置き換えられるならば、この問題は、推定が実現可能な場合、新しいグラフに関するＤｉｊｋｓｔｒａのアルゴリズムに数学的に等価となる。
【００３４】
ＡＬＴ（Ａ*探索、ランドマークおよび三角不等式）アルゴリズムは、ランドマークおよび三角不等式を使用して実現可能な下限を計算する。頂点の小さなサブ集合がランドマークとして選択され、グラフ中の各頂点について、あらゆるランドマークまでの、またはあらゆるランドマークからの距離が事前計算される。ランドマークＬを検討する。ｄ（ｘ，ｙ）がｘからｙまでの距離を表すとすると、三角不等式によりｄ（ｖ，Ｌ）−ｄ（ｗ，Ｌ）≦ｄ（ｖ，ｗ）であり、同様に、ｄ（Ｌ，ｗ）−ｄ（Ｌ，ｖ）≦ｄ（ｖ，ｗ）である。最も緊密な下限を得るには、これらのうち最大のバウンドを、全てのランドマークに対して取ることができる。ｄ（ｖ，ｗ）に関する最良の下限は、ｖの「前」またはｗの「後」に現れるランドマークによって与えられる。
【００３５】
ｓ〜ｔの最短パスの計算の中に、利用可能なランドマークのサブ集合だけを使用するよう推奨される。すなわち、ｓ〜ｔ距離に関して最も高い下限を与えるサブ集合である。これによってパフォーマンスが改善される傾向がある。というのは残りのほとんどのランドマークはこの計算に役立ちそうにないためである。さらなる改良が本明細書に記載されている。
【００３６】
ＡＬＴ技法は、主要段階および前処理段階を備えることができる。主要段階はアクティブなランドマークの動的選択を使用することによって改善することができ、前処理段階は様々なランドマーク選択技法を使用することによって改善することができる。ここにさらに説明したように、前処理中、ＡＬＴアルゴリズムはランドマークの集合を選択し、各ランドマークと全ての頂点との間の距離を事前計算する。次いで、これらの距離を使用して、Ａ*探索に基づく最短パスアルゴリズムのために下限を計算する。
【００３７】
本発明に従って、アクティブなランドマーク（現在の計算に実際に使用されているもの）を動的に選択することができる。例示的な１つの技法は、元の２つのランドマークで開始し、新しいランドマークが現在アクティブなランドマークに比べ、探索の境界について大幅により良い下限を与えるときにそのランドマークを選択することによって改善する。
【００３８】
ＡＬＴの一実装は、各最短パス計算について、ｓ〜ｔ距離に関する最良の下限を与えるｈ個のアクティブなランドマークのサブ集合のみを使用する。このアプローチでは、ランドマークの総数は、利用可能な二次ストレージデバイスの容量によって主に制限される。ｈの選択は、探索効率と、下限を計算するために検討しなければならないランドマークの数との間のトレードオフに依存する。
【００３９】
これは、アクティブなランドマークの集合を動的に更新することによって改善することができる。アクティブなランドマークを動的に選択する例示的な方法のフローチャートを図９に示す。例示的方法は、ステップ９００で２つのアクティブなランドマークのみで開始する。１つはランドマークまでの距離を用いて最良のバウンドを与え、もう１つはランドマークからの距離を用いて最良のバウンドを与える。次いで、規則的なあるいは不規則な間隔で定期的に、アルゴリズムを終了するか、あるいはアクティブなランドマークの総数が上限に達するまで新しいランドマークを追加することにより、アクティブな集合の更新が試行される。
【００４０】
更新の試行は、ステップ９１０で、探索（順方向または逆方向）が、現在の下限関数によって決められたディスティネーションまでの距離推定がある一定の値（チェックポイント）よりも小さい頂点ｖをスキャンするとき常に起こる。この時点で、アルゴリズムはステップ９２０で、（全てのランドマークを用いて）ｖからディスティネーション地までの距離の最良の下限が、（アクティブなランドマークのみを用いて）現在の下限より少なくともあるファクタ１＋∈（たとえば、∈＝０．０１）だけ良いかどうかを検証する。そうである場合、ステップ９３０で、改善されたバウンドをもたらすランドマークがアクティブ化される。そうでない場合、ステップ９４０で、そのランドマークは使用されない。
【００４１】
この計算は、ランドマークからの距離およびランドマークまでの距離をそれぞれ使用してｓ〜ｔ距離について最良のバウンドを与える、最初の最良のランドマークを用いて開始する。計算が進み、下限を必要とする頂点の地点が変化するに従って、他のランドマークがより良いバウンドを与えることがあり、これらはアクティブ集合にもたらされるべきである。あらゆるランドマークの更新の後、ステップ９５０で、ポテンシャル関数が変わり、優先キューが更新される。
【００４２】
チェックポイントは、計算が始まる前に計算されるｓとｔの間の距離についての元の下限ｂによって判定される。たとえば、各探索においてｉ番目のチェックポイントは値ｂ（１０−ｉ）／１０を有することができ、推定された下限が元の値の９０％に達するときにランドマークを更新することをまず試み、次に８０％に達するときに試みられ、以下同様である。この規則はｓとｔが十分離れている場合にうまく機能する。接近している場合、更新の試行が頻繁に起こり過ぎ、アルゴリズムの実行時間を独占してしまう。そのため、同じ方向の２つの連続した更新の試行の間に、アルゴリズムが少なくとも１００個の頂点をスキャンすることが望まれるであろう。
【００４３】
アクティブなランドマークの動的選択は効率を高め、アクティブなランドマークの最終的な数が普通、非常に小さい（たとえば、３に近い）ので、実行時間を短縮する。
【００４４】
前処理中、ランドマークの集合が選択され、各ランドマークと全ての頂点との間の距離が事前計算される。これらの距離は、Ａ*探索に基づく最短パスアルゴリズムについて下限を計算するために使用される。
【００４５】
下限方法の全体的なパフォーマンスを向上する良好なランドマークを見つける幾つかの技法がある。ランドマークを選択する簡単な方法は、ランダムに一定数のランドマーク頂点を選択することである。この「ランダム法」はそれなりにうまく機能する。別のアプローチは、最遠ランドマーク選択アルゴリズムがあるが、これは貪欲に機能する。開始の頂点が選ばれ、それから最も遠い頂点ｖ１が見つけられる。頂点ｖ１がランドマークの集合に加えられる。現在のランドマークの集合から最も遠い頂点（すなわち、集合中の最も近い頂点との距離が最大である頂点）として頂点ｖｉが見つけられる。次いで、頂点ｖｉがランドマークの集合に加えられる。このプロセスは、一定数のランドマークが見つけられるまで繰り返される。この方法は、「最遠ランドマーク選択方法」と呼ばれる。
【００４６】
良好なランドマークを見つけるための別の方法として、「平面ランドマーク選択方法」がある。平面ランドマーク選択方法は一般に、幾何的にディスティネーションの後に位置するランドマークを作り出し、これはグラフと幾何的距離が強く相関される道路グラフや他の幾何的グラフ（非平面グラフを含む）について、通常、良好なバウンドを与える。簡単な平面ランドマーク選択方法は、次のように機能する。まず、平面（または準平面）の埋め込みの中心に最も近い頂点ｃが見つけられる。埋め込みは、ｃを中心とする一定の数のパイ形状のセクタに分割され、それぞれがほぼ同数の頂点を含む。各セクタ毎に、中心から最も遠い頂点が選択される。２つのランドマークが互いに接近し過ぎるのを避けるために、セクタＡが既に処理され、ＡのランドマークがＡおよびＢの境界に近いようにセクタＢが処理されている場合、境界に近いＢの頂点が省かれる。
【００４７】
上記の選択規則は比較的速い。本発明の複数の実施形態によるさらなるランドマーク選択規則には、「回避」および「最大カバー」が含まれる。これらの選択技法はグラフレイアウト情報を使用しないが、従来の選択技法よりもうまく機能する。ランドマークの品質がどのように測定されるかにより、「最適」のランドマーク選択を何通りにも定義できることに留意されたい。たとえば、ｎがグラフ中の頂点の数とすると、全ての可能なＯ（ｎ2）個の最短パス計算について検討する頂点の総数を最小化することを目指すことができる。あるいは、検討した頂点の最大数を最小化することができる。
【００４８】
本発明による、例示的な１つのランドマーク選択方法は「回避」と呼ばれる。この技法は、既存のランドマークを回避することで「うまくカバーされていない」グラフの領域を特定するよう試みる。「回避」は、ランドマーク品質測定を使用して、別個に、あるいは「局所探索」のコンテキストで使用することができる候補の集合を生成する。「回避」では、頂点の重みｗ（ｖ）は、特定の頂点までの実際の最短パスと下限との差として決定される。次いで、頂点のサイズｓ（ｖ）が決定される。これは、「局所探索」により最適化することができる。
【００４９】
図１０は、本発明による例示的なランドマーク選択方法のフローチャートである。たとえば、ステップ１０００で、既に選択されたランドマークの集合Ｓがあり、追加のランドマークが望まれているものと仮定する。ステップ１００５で、ある頂点ｒをルートにもつ最短パスツリーＴｒを計算する。次に、ステップ１０１０で、あらゆる頂点ｖについて、ｄｉｓｔ（ｒ，ｖ）とＳによって与えられるｄｉｓｔ（ｒ，ｖ）の下限との差として定義される重みを計算する。これは、現在の距離推定がどれほど悪いかについての尺度となる。
【００５０】
ステップ１０１５で、あらゆる頂点ｖについて、ｖをルートにもつＴｒのサブツリーであるＴｖに依存するサイズｓ（ｖ）を計算する。ステップ１０２０で、Ｔｖがランドマークを含む場合、ステップ１０２５でｓ（ｖ）＝０に設定する。そうでない場合、ステップ１０３０で、ｓ（ｖ）はＴｖ中の全ての頂点の重みの和となる。ｗを最大サイズの頂点とする。ステップ１０４０で、ｗから開始し、葉に到達するまで常に最大サイズをもつ子を辿るようにＴｗをトラバースする。ステップ１０４５で、この葉を新しいランドマークとする。
【００５１】
このように、ｗから、そのサブツリー中のある頂点までのパスで、その「背後」ランドマークをもつパスはない。ランドマークの集合にこのサブツリーの葉を追加することにより、「回避」はカバレージを改善しようとする。
【００５２】
上で説明したもののように構成的ヒューリスティックスの弱点は、先に選択されたランドマークは、他のランドマークが選択されると、有用性が制限されることがあるということにある。それらをより良いもので置き換えようとすることが望まれる。「局所探索」は、この目的のために使用することができる。探索を実施するには、ある解（すなわち、ランドマークの集合）がどれほど良いかを測定することが望ましい。究極的には、全てのポイント−ポイント間探索の効率をより良くする解を見つけることが目標であるが、これはひどく高価なものである。実際的には、ランドマークの与えられた集合の品質が推定される。
【００５３】
推定には、低減されたコストを使用してもよい。このコンテキストにおいて、ランドマークＬに対する孤の低減されたコストをｌ（ｖ，ｗ）−ｄ（Ｌ，ｗ）＋ｄ（Ｌ，ｖ）と定義し、ここで、ｌ（ｖ，ｗ）は孤（ｖ，ｗ）の長さを表す。低減されたコストがゼロである場合、ランドマークは孤をカバーする。ポイント−ポイント間の最短パスアルゴリズムの最良のケースは、ランドマークがパス上のあらゆる孤をカバーするときに起きる。これを念頭に置いて、ある所与の解のコストを、少なくとも１つのランドマークに対してゼロの低減されたコストを有する孤の個数として定義する。よりコストがかからない解の方が良く、ある一定のｋについて、可能な限り多くの孤をカバーするｋ個のランドマークの集合を見つけることが望ましい。
【００５４】
所与の頂点がどの孤をカバーするかを判断するには、単一ソースの最短パス計算を実行する必要がある。大きいグラフの場合、これを全ての頂点について行うことは現実的ではない。それゆえ、「回避」を用いて選択された候補ランドマークの小さな集合を使用する。
【００５５】
より正確には、図１１に関して、ステップ１１００で、Ｃを最初は空である候補の集合とする。ステップ１１１０で、ｋ個のランドマークを有する解を見つけるために「回避」を実行して開始し、ステップ１１２０でランドマークの全てがＣに追加される。次いで、ステップ１１３０で、現在の解から確率１／２で各ランドマークを取り除く。取り除かれると、ステップ１１４０で、解が再びサイズｋとなるまで、さらにランドマークを（再び「回避」を用いて）生成する。ステップ１１５０で、Ｃにまだない新しい各ランドマークが追加される。ステップ１１６０で、たとえばＣがサイズ４ｋとなるか、あるいは「回避」が５ｋ回実行される（これらのいずれか先に発生するにしても）までこのプロセスを繰り返す。回避のあらゆる実行が必ずしも新しいランドマークを生成するとは限らないので、アルゴリズムの実行時間を制限することが望ましい。
【００５６】
最終的に、ｋ〜４ｋ個の候補ランドマークを有する集合Ｃがヒューリスティック的に得られることになる。各ランドマークをそれがカバーする孤の集合として解釈して、最大カバー問題の事例を解くことが望ましい。マルチスタートヒューリスティックを使用して近似解を見つけることができる。この問題はＮＰハードなので、厳密解を求めることは難しい。各繰り返しは、ｋ個のランドマークを有するＣのランダムなサブ集合Ｓで開始し、それに局所探索手順を適用する。集合の品質が決定される。最後に、全ての繰り返しを通じて得られた最良の解を選ぶ。たとえば、繰り返しの回数をｌｏｇ2ｋ＋１に設定する。
【００５７】
局所探索は、現在の解に属する１つのランドマークを、現在の解には属さないが候補の集合に属する別のもので置き換えようとする。これは、Ｏ（ｋ2）個の可能なスワップのそれぞれに関連付けられるプロフィットを計算することによって働く。プロフィットが負またはゼロのものは破棄される。残っているものの中で、利益に比例した確率でランダムにスワップを選ぶ。次いで、同じ手順が新しい解に適用される。局所探索は、局所的最適点に達するとき、すなわち改善をもたらすようなスワップがなされなくなるときに中止する。局所探索の各繰り返しは０（ｋｍ）時をとる。ランドマーク生成のこの方法は「最大カバー」と呼ばれる。この最適化フェーズはかなり速い。実行時間は、候補ランドマークの集合を生成するのに使用される「回避」の呼出しによって独占される。
【００５８】
ＡＬＴアルゴリズムのメモリ効率の良い実装を説明する。スペース効率の良いデータ構造がキャッシング、データ圧縮およびハッシングと組み合わせて使用される。このような技法は、フラッシュメモリにグラフおよびランドマークデータが格納されたポケットＰＣに使用することができ、約３０００万個の頂点を有する北米の道路ネットワークを含め、幾つかの道路ネットワークで使用されてきた。
【００５９】
例示的な一実装では、グラフおよびランドマークデータをフラッシュメモリカードに格納する。カードから読み出すことができる最低量（たとえば、５１２バイトセクタ）は、システム上の制約によって決まる。データはページ単位で読み出され、１つのページは１つまたは複数のセクタを収容する。
【００６０】
グラフは、次のフォーマットでフラッシュカードに格納することができる。弧は、弧のテールでソートされたレコードのアレイとして表される。各レコードは、１６ビットの弧長（たとえば、秒での移動時間）およびヘッド頂点の３２ビットＩＤを有する。別のアレイは、それぞれが最初の出弧を表すレコードの３２ビットインデックスを備える頂点レコードを表す。逆グラフも（同じフォーマットで）格納される。
【００６１】
探索によって検討された各頂点に必要な追加情報は、メインメモリ中にミュート可能ノード（ｍｕｔａｂｌｅ ｎｏｄｅ）と呼ばれるレコードに保持される。各頂点は２つのミュート可能ノードを必要とすることができる。１つは順方向探索のためのものであり、もう１つは逆方向探索のためのものである。ミュート可能ノードは４つの３２ビットフィールドを有する。すなわちＩＤ、距離ラベル、親ポインタおよびヒープ位置である。幾つかのフィールドは、道路ネットワークアプリケーションにおいて生じそうな最大グラフのためにさえ必要以上に大きいが、実装をクリーンかつ柔軟に保つためにレコードをワード整合することが望ましいことがある。ユーザは、ミュート可能ノードの許容される最大数Ｍを指定する。使用されるＲＡＭの総量はＭに比例する。
【００６２】
頂点ＩＤを対応するミュート可能ノードにマップするために、少なくとも１．５Ｍのサイズのテーブルを用いてダブルハッシングを使用する。各探索に１つずつ、２つの優先キューを維持する。最短パスアルゴリズムの場合、マルチレベルのバケット実装が一番速い傾向にある。Ｐ２Ｐ計算の場合、４ヒープが望ましいことがある。マルチレベルバケットよりは遅いものの、４ヒープはスペースのオーバーヘッドがより少ない（１頂点あたり１ヒープインデックス）。加えて、優先キューは一般に、アプリケーション内でそれほど多くの要素を含まないので、ヒープ操作に関連付けられるオーバーヘッドは、データアクセスに関するものに比して控えめである。プロトタイプ実装では、各ヒープの最大サイズがＭ／８＋１００要素に設定された。
【００６３】
データは強い局所性を持つことがある。この理由と、データがブロックで読み取られるという理由とにより、アルゴリズムは明示的なキャッシング機構を実施する。ページアロケーションテーブルが物理ページアドレスを（ＲＡＭの）バーチャルページアドレスにマップし、その置換戦略はＬＲＵである。すなわち、使用頻度が最も低いページが望まれるならばいつでも追い出される。グラフおよびランドマークに別個のキャッシュが使用される。６個のランドマークキャッシュ（各アクティブなランドマークに１つ）のそれぞれは１ＭＢあり、２個のグラフキャッシュのそれぞれは２ＭＢある。
【００６４】
データは、各ランドマーク毎に別個のファイルに格納される。各距離は、３２ビットの整数で表される。同じ頂点についての行きと帰りの距離は隣接している。グラフは完全には対称ではないが、２つの距離は普通近い。さらに、似通ったＩＤを有する頂点は互いに近くにある傾向があるので、それらのランドマークまでの（または、ランドマークからの）距離もまた似通っている。この類似性は圧縮に望ましく、これによってフラッシュカードにより多くのデータが入るようになり、データ読み出し操作が速くなる。
【００６５】
隣接するワード（距離）の２つの最上位バイトが同じである傾向にあるので、ほぼ５０％の圧縮率が達成できる。ファイルへのランダムアクセスを可能にするために、各ページは別個に圧縮される。圧縮率が変わるので、ファイルはページオフセット付きのディレクトリを有する。
【００６６】
このように、本発明の技法は従来技術の技法よりも（より効率が高いので）少ない数の頂点を検討するだけでなく、（動的選択によりアクティブなランドマークの数が低減されるので）各頂点をより素早く処理することもできる。
【００６７】
本明細書に記載した様々なシステム、方法および技法は、ハードウェアまたはソフトウェアで、あるいは適切な場合には、両者の組合せで実施することができる。このように、本発明の方法および装置、またはその幾つかの態様または部分は、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、ハードドライブ、または他の任意の機械可読記録媒体などの有形媒体中に具現されたプログラムコード（すなわち、命令）の形態をとることができ、そのプログラムコードがコンピュータなどのマシンにロードされて実行されるときそのマシンが本発明を実施するための装置となる。プログラム可能なコンピュータ上でのプログラムコードの実行の場合、コンピュータは、一般にプロセッサ、プロセッサによって可読の記録媒体（揮発性および不揮発性のメモリおよび／または記憶要素を含む）、少なくとも１つの入力装置、および少なくとも１つの出力装置を含むであろう。１つまたは複数のプログラムが、好ましくはコンピュータシステムと通信可能となるように、ハイレベルの手続き型プログラミング言語またはオブジェクト指向プログラミング言語で実装される。しかし、望むなら、この（１つまたは複数の）プログラムは、アセンブリ言語またはマシン語で実装することもできる。いずれの場合も、言語はコンパイルされるか、インタープリットされた言語とすることができ、ハードウェア実装と組み合わせることができる。
【００６８】
本発明の方法および装置はまた、電気配線またはケーブル、光ファイバあるいは他の任意の形態の伝送など、なんらかの伝送媒体を介して伝送されるプログラムコードの形態をとることができ、このプログラムコードは、ＥＰＲＯＭ、ゲートアレイ、プログラム可能論理回路（ＰＬＤ）、クライアントコンピュータ、ビデオレコーダなどのマシンによって受け取られ、ロードされて実行されるとき、そのマシンが本発明を実施するための装置となる。汎用プロセッサ上で実装されると、プログラムコードはプロセッサと組み合わせて、本発明の機能を実行するように動作する独自の装置を提供する。
【００６９】
本発明について様々な図に示した好ましい実施形態に関連して説明したが、本発明から逸脱することなく、本発明の同様の機能を実行するために他の類似の実施形態を使用してよく、あるいは説明した実施形態に修正または追加を行ってもよいことが理解さるべきである。それゆえ、本発明はどの単一の実施形態にも限定されるべきではなく、添付の特許請求の範囲による広がりおよび範囲で解釈されるべきである。
【図面の簡単な説明】
【００７０】
【図１】本発明の一実施形態による、最短パスを計算することができるコンピューティング環境の例示的アーキテクチャを示す簡略化された概略図である。
【図２】本発明の一実施形態による、コンピューティングネットワーク上のコンピューティングデバイスの構成を示す図である。
【図３】本発明の一実施形態による、相互接続された地点のグラフ表現を示す図である。
【図４】最短パス検索方法でスキャンされた地点を示す図である。
【図５】本発明の一実施形態による、ヒューリスティックな最短パス検索方法でスキャンされた地点を示す図である。
【図６】本発明の一実施形態による、２つの地点の間の最短パスを見つける方法を示すフロー図である。
【図７】本発明の一実施形態による、ランドマークを使用してディスティネーション地までの距離を推定する方法を示すフロー図である。
【図８】地点およびあるランドマークの例示的な集合を示す図である。
【図９】本発明による、アクティブなランドマークを動的に選択する例示的な方法のフロー図である。
【図１０】本発明による、例示的なランドマーク選択方法のフロー図である。
【図１１】本発明による、別の例示的なランドマーク選択方法のフロー図である。
【符号の説明】
【００７１】
１００ コンピューティングシステム環境
１１０ コンピュータ
１２０ 処理装置
１２１ システムバス
１２２ メモリキャッシュ
１３０ システムメモリ
１３１ ＲＯＭ
１３２ ＲＡＭ
１３３ ＢＩＯＳ
１３４ オペレーティングシステム
１３５ アプリケーションプログラム
１３６ その他のプログラムモジュール
１３７ プログラムデータ
１４０ 非リムーバブル不揮発性メモリインターフェース
１４１ ハードディスクドライブ
１４４ オペレーティングシステム
１４５ アプリケーションプログラム
１４６ その他のプログラムモジュール
１４７ プログラムデータ
１５０ リムーバブル不揮発性メモリインターフェース
１５１ 磁気ディスクドライブ
１５２ 磁気ディスク
１５５ 光ディスクドライブ
１５６ 光ディスク
１６０ ユーザ入力インターフェース
１６１ マウス
１６２ キーボード
１７０ ネットワークインターフェース
１７１ ローカルエリアネットワーク
１７２ モデム
１７３ ワイドエリアネットワーク
１８０ リモートコンピュータ
１８１ メモリストレージデバイス
１８５ リモートアプリケーションプログラム
１９０ ビデオインターフェース
１９１ モニタ
１９５ 出力周辺インターフェース
１９６ プリンタ
１９７ スピーカ
２００ コンピューティングデバイス
２０２ ローカルエリアネットワーク
２０４ ウェブブラウザ
２０５ インターネット
２０６ 地図経路サービス
２０８ 地図経路サーバ
２１０ データベース
３０２ エッジ
３０４，３０６，３０８，３１０，３１２ 頂点
４０２，４０４，４０６ 頂点
５０２，５０４，５０６，５０８ 頂点
５０５ 集合
８０２ ソース
８０４ ディスティネーション
８０６ ランドマーク
８０８，８１２，８１４，８２０ セグメント
８２２ エッジ
【技術分野】
【０００１】
本発明は、一般に経路指定の分野に関し、より詳しくはコンピュータ化された地図上の２点間の最良経路を判定することに関する。
【背景技術】
【０００２】
「道路地図」プログラムとして知られる既存のコンピュータプログラムは、デジタル地図を提供し、多くの場合、市街路レベルに至る詳細な道路網を完備している。通常、ユーザはある地点を入力することができ、道路地図プログラムが選択された地点のオンスクリーンの地図を表示する。幾つかの既存の道路地図プログラムは、典型的には２つの地点間の「最良経路」を計算する能力を含む。言い換えると、ユーザは２つの地点を入力することができ、道路地図プログラムがソース地点（ｓｏｕｒｃｅ ｌｏｃａｔｉｏｎ）からディスティネーション地点（ｄｅｓｉｔｎａｔｉｏｎ ｌｏｃａｔｉｏｎ）までの道案内を計算することになる。道案内は、典型的には距離、移動時間、およびユーザが好む運転速度や途中の景色の良さなどいくつかのユーザの好みに基づいている。地点間の最良経路の計算には、多くの計算時間と計算リソースが必要となり得る。
【０００３】
既存の道路地図プログラムは、最短パスを計算するためにＥ．Ｄｉｊｋｓｔｒａに帰属する方法の変形を用いている。Ｄｉｊｋｓｔｒａの方法は、非特許文献１に記載されており、それが教示する全てについて、いかなる部分も除外することなくその全体が参照により本明細書に組み込まれる。この文献では、「最短」は「最小コスト」を意味することに留意されたい。というのは、各道路セグメントには、その道路セグメントの長さに必ずしも直接関係しないコストまたは重みが割り当てられているからである。各道路についてコストの計算方法を変えることにより、最速、最短または好みの経路について最短パスを生成することができる。
【０００４】
【特許文献１】米国特許出願第１０／９２５７５１号明細書
【非特許文献１】Ｃｏｒｍｅｎ，Ｌｅｉｓｅｒｓｏｎ ａｎｄ Ｒｉｖｅｓｔ，Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ，ＭＩＴ Ｐｒｅｓｓ，１９９０，ｐｐ．５１４−５３１
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、Ｄｉｊｋｓｔｒａの当初の方法は、スキャンされる地点および可能なパスの数が多いので、実際には常に効率的であるとは限らない。その代わりに、現代の多くの道路地図プログラムは、最短パス計算をほぼ正しい方向に「誘導」するためにＡ*探索（ヒューリスティックなまたは目標指向型探索（ｇｏａｌ−ｏｒｉｅｎｔｅｄ ｓｅａｒｃｈ）とも呼ばれる）を含むＤｉｊｋｓｔｒａの方法のヒューリスティックな変形を使用している。このようなヒューリスティックな変形は、典型的に中間地点とディスティネーション地点との間のパスの重みを推定することを伴う。良好な推定は、道路地図プログラムによって考慮されるべき地点および道路セグメントの数を低減し、その結果最短パスがより速く計算されるが、悪い推定だと逆効果となり、最短パスを計算するのに必要な全体の時間が増加することがある。推定がいくつかの特定のプロパティで距離の下限（ｌｏｗｅｒ−ｂｏｕｎｄ）である場合、Ａ*探索は最適（最短）パスを計算する。これらの下限が実際のパスの重みに近いほど、推定およびアルゴリズムのパフォーマンスは良くなる。バウンドされている実際の値に非常に近い下限は、「良好」であると言われる。以前から知られているヒューリスティックな変形は、地点間のユークリッド距離（すなわち、「直線距離」）などの下限推定技法を使用するが、これらの技法はあまり良好なものではない。
【０００６】
その全体が参照により本明細書に組み込まれる２００４年８月２５日出願の「Ｅｆｆｉｃｉｅｎｔｌｙ Ｆｉｎｄｉｎｇ Ｓｈｏｒｔｅｓｔ Ｐａｔｈｓ Ｕｓｉｎｇ Ｌａｎｄｍａｒｋｓ Ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｌｏｗｅｒ−Ｂｏｕｎｄ Ｄｉｓｔａｎｃｅ Ｅｓｔｉｍａｔｅｓ」という名称の特許文献１には、三角不等式に基づく最短パスを決定するためのアルゴリズムが記載されている。アクティブなランドマークの動的な選択を提供し、パス計算技法やシステムなどでの使用についてメモリ効率を提供することが望ましいであろう。また、ツリーベースのビューリスティックスを使用し、ランドマークの生成において局所探索を使用することが望ましいであろう。
【課題を解決するための手段】
【０００７】
以下の概要は、本発明の様々な態様の概略を提供する。本発明の全ての重要な態様についての包括的な説明を提供したり、本発明の範囲を画定したりするものではない。むしろ、この要約は、これに続く詳細な説明および図面の導入部として意図されている。
【０００８】
本発明は、非負の孤長（ｎｏｎｎｅｇａｔｉｖｅ ａｒｃ ｌｅｎｇｈｔ）を有する有向グラフ（ｄｉｒｅｃｔｅｄ ｇｒａｐｈｓ）上のポイント−ポイントの最短パスの問題（Ｐ２Ｐ問題）を解くことを対象としている。正確な最短パスを見つけることが望ましい。問題を解くためにグラフのあらゆる頂点（ｖｅｒｔｅｘ）を検討しなければならない単一ソースの場合と異なり、Ｐ２Ｐ問題は小さなサブグラフを検討しながら解くことができる。グラフの小さな部分を検討することにより、プロセスの実行時間が改善されるだけでなく、外部メモリの実装が可能になる。一例の実施形態では、グラフと前処理データを二次ストレージ（たとえば、ディスクまたはフラッシュメモリ）に保持し、グラフの検討した部分について使用したデータをメインメモリ（たとえば、ＲＡＭ）に保持する。このアプローチが望ましいのは、いくつかのアプリケーションは大きなグラフ上で機能したり、小さなデバイス（たとえば、モバイルまたはハンドヘルドデバイス）上で稼働したり、あるいはその両方に該当したりするからである。
【０００９】
本発明のいくつかの態様によれば、ランドマークは、ツリーベースのヒューリスティックスや局所探索（ｌｏｃａｌ ｓｅａｒｃｈ）を用いるなど、１つまたは複数の選択ヒューリスティックスを使用して前処理中に生成または選択することができる。
【００１０】
本発明のさらなる特徴および利点は、添付の図面を参照しながら行われる例示的実施形態についての以下の詳細な説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１１】
前述の要約ならびに好ましい実施形態についての以下の詳細な説明は、添付の図面を参照と共に読むとよりよく理解されよう。本発明を例示する目的で図面には本発明の例示的な構成が示されているが、本発明は開示された具体的な方法および手段に限定されるものではない。
【００１２】
この内容は、法的要件を満たすために、詳細に説明されている。しかし、その説明自体は、本発明の範囲を限定するものではない。そうではなくて、本発明者らは、請求される内容が、本明細書に説明されたものと類似の異なるステップまたはステップの組合せを含むように、他の現在または将来の技術と共に、別のやり方で具体化できることを企図している。さらに、「ステップ」という言葉は、用いられる方法の様々な要素を意味するように本明細書では使用されることがあるが、この言葉は、個々のステップの順序が明示的に記載されていない限り、そしてその場合を除いて、本明細書で開示される様々なステップ中のまたはステップ間の特定の順序を示唆しているものと解釈されるべきではない。
【００１３】
本発明は、添付の図面と併せて読まれるべき以下の詳細な説明を通じてより完全に理解されるであろう。この説明において、同様の番号は、本発明の様々な実施形態内の同様の要素を参照している。本発明は、適切なコンピューティング環境で実施されているものとして示される。必須ではないが、本発明はパーソナルコンピュータによって実行される手順などのコンピュータ実行可能命令という一般的なコンテキストで説明されるであろう。一般に、手順には、特定のタスクの実行または特定の抽象データ型の実施を行うプログラムモジュール、ルーチン、関数、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。さらに、本発明がハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサに基づくあるいはプログラム可能な民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む他のコンピュータシステム構成と共に実施できることは、当業者には明らかであろう。本発明はまた、タスクが通信ネットワークでリンクされたリモート処理装置によって実行される分散コンピューティング環境で実施され得る。分散コンピューティングでは、プログラムモジュールを、ローカルおよびリモートの両方のメモリストレージデバイスにも置くことができる。コンピュータシステムという用語は、分散コンピューティング環境で見られ得るようなコンピュータのシステムを指すために使用することができる。
【００１４】
図１は、本発明を実施することができる、適切なコンピューティングシステム環境１００を示す。コンピューティングシステム環境１００は、適切なコンピューティング環境の一例に過ぎず、本発明の使用の範囲または機能に関するいかなる限定も示唆するものではない。また、コンピューティングシステム環境１００も、例示的動作環境１００中で示されるコンポーネントの１つまたはそれらの組合せに関する依存性または要件を有するものと解釈されるべきではない。本発明の一実施形態は、例示的動作環境１００に示される各コンポーネントを含むが、本発明のより典型的な別の実施形態は、たとえばネットワーク通信に必要なもの以外の入出力デバイスなど、本質的でないコンポーネントを含まない。
【００１５】
図１を参照すると、本発明を実施するための例示的システムは、コンピュータ１１０の形態の汎用コンピューティングデバイスを含む。コンピュータ１１０のコンポーネントには、処理装置１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステムコンポーネントを処理装置１２０に結合するシステムバス１２１が含まれ得るが、それだけには限定されない。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのいずれかを使用したローカルバスを含めて、いくつかのタイプのバス構造のずれでもよい。限定ではなく例として、このようなアーキテクチャとしては、ＩＳＡ（Ｉｎｄｕｓｔｒｙ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、およびメザニンバス（Ｍｅｚｚａｎｉｎｅ ｂｕｓ）とも呼ばれるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスなどがある。さらに、コンピュータ１１０のコンポーネントには、メモリキャッシュ１２２も含まれ得る。処理装置１２０は、メモリキャッシュからのデータに、システムメモリ１３０からのデータよりも速くアクセスすることができる。メモリキャッシュ１２２は典型的に、システムメモリ１３０からの直前にアクセスされたデータまたは処理装置１２０によって最近処理されたデータを格納する。処理装置１２０は、システムメモリ１３０からデータを取り出すのに先立って、そのデータがメモリキャッシュ１２２に現在格納されているかどうかをチェックすることができる。そうである場合、「キャッシュヒット」が生じることになり、データは一般により遅いシステムメモリ１３０からではなく、メモリキャッシュ１２２から取り出される。
【００１６】
コンピュータ１１０は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０によってアクセスできる利用可能な任意の媒体でよく、揮発性および不揮発性の媒体、リムーバブルおよび非リムーバブルの媒体を含む。限定ではなく例として、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を備えることができる。コンピュータ記憶媒体には、コンピュータ可読命令、デーダ構造、プログラムモジュールまたは他のデータなど、情報の格納のための任意の方法または技術で実施される揮発性および不揮発性の媒体、リムーバブルおよび非リムーバブルの媒体が含まれる。コンピュータ記憶媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤもしくは他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または所望の情報を格納するために使用し、コンピュータ１１０によってアクセスできる他の任意の媒体があるが、それだけには限定されない。通信媒体は、通常、コンピュータ可読命令、デーダ構造、プログラムモジュール、またはその他のデータを、搬送波や他のトランスポート機構などの変調データ信号に具現し、それには任意の情報送達媒体が含まれる。「変調データ信号」という用語は、信号に情報を符号化するようにその１つまたは複数の特徴を設定または変更した信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、ＲＦ、赤外線およびその他の無線媒体が含まれる。上記の任意の組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。
【００１７】
システムメモリ１３０は、たとえばリードオンリーメモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２など、揮発性および／または不揮発性のメモリの形態のコンピュータ記憶媒体を含む。たとえば起動の際にコンピュータ１１０内の要素間での情報の転送を助ける基本ルーチンを含む基本入出力システム（ＢＩＯＳ）１３３は通常、ＲＯＭ１３１に格納される。ＲＡＭ１３２は、通常、処理装置１２０から直ぐにアクセス可能であり、そして／または処理装置１２０によって現在操作されているデータおよび／またはプログラムモジュールを含む。限定ではなく例として、図１はオペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００１８】
コンピュータ１１０は、他の揮発性および／または不揮発性の媒体、リムーバブルおよび／または非リムーバブルの媒体を含むことができる。あくまで一例として、図１は、非リムーバブルで不揮発性の磁気媒体を読み書きするハードディスクドライブ１４１、リムーバブルで不揮発性の磁気ディスク１５２を読み書きする磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭや他の光媒体などのリムーバブルで不揮発性の光ディスク１５６を読み書きする光ディスクドライブ１５５を示す。この例示的動作環境で使用できる他の揮発性および／または不揮発性の媒体、リムーバブルおよび／または非リムーバブルの媒体としては、磁気テープカセット、フラッシュメモリカード、ＤＶＤ、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどがあるが、それだけには限定されない。ハードディスクドライブ１４１は、通常、インターフェース１４０などの非リムーバブルメモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常インターフェース１５０など、リムーバブルメモリインターフェースを介してシステムバス１２１に接続される。
【００１９】
上に説明し、図１に示したドライブおよびそれらに関連するコンピュータ記憶媒体は、コンピュータ１１０用のコンピュータ可読命令、デーダ構造、プログラムモジュールまたは他のデータのストレージを提供する。たとえば、図１では、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を格納しているものとして示してある。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じでもよく、異なっていてもよいことに留意されたい。ここでは、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７が少なくとも異なるコピーであることを示すために異なる参照番号が付されている。ユーザはタブレット、または電子式デジタイザ１６４、マイクロフォン１６３、キーボード１６２および一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティングデバイス１６１を介して、コンピュータ１１０にコマンドおよび情報を入力することができる。他の入力装置（図示せず）としては、ジョイスティック、ゲームパッド、衛星アンテナ、スキャナなどがある。これらおよび他の入力装置は、システムバスに結合されているユーザ入力インターフェース１６０を介して処理装置１２０に接続されることが多いが、パラレルポート、ゲームポートまたはユニバーサルシリアルバス（ＵＳＢ）など他のインターフェースおよびバス構造によって接続することもできる。モニタ１９１または他のタイプの表示装置も、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続されている。モニタ１９１は、タッチスクリーンパネルなどと統合することもできる。モニタおよび／またはタッチスクリーンパネルは、たとえばタブレットタイプのパーソナルコンピュータの場合など、コンピューティングデバイス１１０が組み込まれている筐体に物理的に結合することができることに留意されたい。加えて、コンピューティングデバイス１１０などのコンピュータは、出力周辺インターフェース１９５などを介して接続することができるスピーカ１９７やプリンタ１９６などの他の周辺出力装置を含んでもよい。
【００２０】
コンピュータ１１０は、リモートコンピュータ１８０など１つまたは複数のリモートコンピュータへの論理接続を用いてネットワーク化された環境で動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイスまたは他の共通ネットワークノードとすることができ、図１ではメモリストレージデバイス１８１のみが図示されているが、通常、コンピュータ１１０に関連して上述した要素の多くまたは全てを含む。図１に示された論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含むこともできる。このようなネットワーク環境は、オフィス、エンタープライズ規模のコンピュータネットワーク、イントラネットおよびインターネットにおいて一般的となっている。たとえば、本発明において、コンピュータ１１０はデータの移動元であるソースマシンを構成することができ、リモートコンピュータ１８０はディスティネーションマシンを構成することができる。しかし、ソースマシンおよびディスティネーションマシンはネットワークまたは他の手段によって接続されている必要はなく、代わりに、データはソースのプラットフォームによって書き込まれ、ディスティネーションの１つまたは複数のプラットフォームによって読み取ることができる任意の媒体を介して移動することができる。
【００２１】
ＬＡＮネットワーク環境で使用する場合、コンピュータ１１０はネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境で使用する場合、コンピュータ１１０は、通常、インターネットなど、ＷＡＮ１７３上での通信を確立するためのモデム１７２または他の手段を含む。モデム１７２は、内蔵でも外付けでもよく、ユーザ入力インターフェース１６０または他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク化された環境では、コンピュータ１１０に関連して図示されたプログラムモジュールあるいはその一部は、リモートメモリストレージデバイスに格納することができる。限定ではなく例として、図１はリモートアプリケーションプログラム１８５をメモリ装置１８１上にあるものとして示している。図示されたネットワーク接続は例示的であり、コンピュータ間の通信リンクを確立する他の手段を使用することもできることが理解できよう。
【００２２】
図２を参照すると、本発明が潜在的に活用されるコンピューティング環境の簡単な例が示されている。この例示の環境において、コンピューティングデバイス２００は、通信媒体を介した通信を容易にするネットワークインタフェースカード（具体的に図示せず）を含む。図２に示す特定の例では、コンピューティングデバイス２００は物理接続を介してローカルエリアネットワーク２０２と通信を行う。あるいは、コンピューティングデバイス２００はＷＷＡＮもしくはＷＬＡＮ媒体、または他の通信媒体を介してローカルエリアネットワーク２０２と通信を行ってもよい。サポートされるネットワーク媒体の結果として、コンピューティングデバイス２００のユーザは、典型的にコンピューティングデバイス２００上で実行されているブラウザアプリケーション２０４の使用を通じて、ネットワークリソースにアクセスすることができる。ブラウザアプリケーション２０４は、たとえばインターネット２０５を介したリモートネットワークとの通信を容易にする。１つの例示的なネットワークリソースが、地図経路サーバ２０８上で稼働する地図経路サービス２０６である。地図経路サーバ２０８は、物理的地点および所在地住所のデータベース２１０を、隣接物、距離、速度制限および格納された地点間のその他の関係などの経路情報と共にホストする。コンピューティングデバイス２００のユーザは、通常、ブラウザアプリケーション２０４を通じて、要求として開始地点およびディスティネーション地点を入力する。地図経路サーバ２０８は、要求を受け取り、開始地点からディスティネーション地点に到達するためにデータベース２１０に格納された地点から最適経路を生成する。次いで、地図経路サーバ２０８は、その最適経路を、要求元のコンピューティングデバイス２００に送り返す。あるいは、地図経路サーバ２０８は、コンピューティングデバイス２００上でホストされ、コンピューティングデバイス２００はローカルエリアネットワーク２０２と通信を行う必要はない。
【００２３】
しかし、最適経路の計算は、些細なタスクではない。ルーティング方法を視覚化し、実施するには、地点および接続するセグメントを、頂点および有向エッジを有する抽象グラフとして表すことが有用である。頂点は地点に対応し、エッジは地点間の道路セグメントに対応する。エッジは、好ましくは移動距離、速度制限および／または対応する道路セグメントについての他の基準に従って重み付けされる。一般的な用語である「長さ」および「距離」は、本文においてはエッジの重みまたはコストが測定されるメトリックを包含するように使用される。パスの長さまたは距離は、パスに含まれるエッジの重みの合計である。たとえば、図３のグラフにおいて、頂点ｓ３０４から頂点ｗ３０６に至るエッジ（ｓ，ｗ）３０２は長さ５を有する。ｓ３０４からｕ３０８へ、ｖ３１０へ、ｔ３１２へのパスの長さは１０＋１＋４＝１５である。ｓ３０２からｔ３１２へのより短いパスはｗ３０６経由であり、長さ７である。コンピューティングデバイスによる操作のために、グラフは、好ましくはレコードの集まりとしてコンピュータメモリの連続ブロックに格納することができ、各レコードは関連データと共に単一のグラフノードまたはエッジを表している。
【００２４】
最適経路を計算する１つのアプローチは、Ｄｉｊｋｓｔｒａの方法を使用することである。一般に、Ｄｉｊｋｓｔｒａの方法は、各頂点毎に距離ラベルおよびその頂点が既にスキャンされているかどうかを示すフラグを維持することにより、ある単一の「ソース（ｓｏｕｒｃｅ）」の頂点から他の全ての頂点までの最短パスを見つける。距離ラベルは最初に各頂点について無限大に設定され、既にスキャンされた頂点のみを使用してソースからその頂点までの最短パスの重みを表す。この方法では未スキャンの頂点を取り上げ、その頂点から出ている全ての（すなわち、隣接する頂点に至る）エッジが緩和される。Ｄｉｊｋｓｔｒａの方法の直接的な実装では、スキャンの対象に最も低い距離ラベルを有する未スキャンの頂点が選ばれる。エッジ（ｖ，ｗ）を緩和するために、この方法はｗのラベルされた距離が、ｖのラベルされた距離とエッジ（ｖ，ｗ）の実際の重みの合計よりも大きいかどうかをチェックする。そうである場合、この方法はその合計と等しくなるようにｗの距離ラベルを更新する。ある頂点がスキャンされると、その距離ラベルがその後に変わらないことを数学的に示すことができる。幾つかの実装では、さらに各スキャン済み頂点ｗ毎に親ラベルを維持し、それによって出エッジが最短パスでｗに至る頂点ｖが示される。この方法で頂点がスキャンされるとき、その頂点について親ポインタによって規定されたパスが最短パスである。
【００２５】
Ｄｉｊｋｓｔｒａの方法は、あるソースから他の全ての頂点までの最短パスを計算するために使用することができるが、あるソースから単一のディスティネーションの頂点までの最短パスを見つけるために使用することもでき、この方法はそのディスティネーションの頂点がスキャンされようとするときに終了する。直感的に、Ｄｉｊｋｓｔｒａの方法は、ソースの頂点を中心とする円内を探索し、頂点を選んでスキャンすることによりその円の半径を増大していく。特定のディスティネーションまでのパスが求められている場合、この方法は、円の境界上のディスティネーションと共に終了する。図４に示されるように、Ｄｉｊｋｓｔｒａの方法を介して頂点ｓ４０２から頂点ｔ４０４までの最短パスを探索すると、ｓ４０２からの距離の昇順において可能性のある頂点がスキャンされる結果になる。任意の頂点までの最短パスも、既にスキャンされた頂点を通過するだけである。頂点ｔ４０４までの距離および最短パスが決定されるとこの方法は停止し、ｓ４０２からの距離がｔ４０４よりも遠い頂点４０６が未スキャンのまま残される。この時点で、従来のＤｉｊｋｓｔｒａの方法では、ｓ４０２からの距離がｔ４０４よりも小さい全ての頂点４０８がスキャンされている。
【００２６】
先に述べたように、Ｄｉｊｋｓｔｒａの当初の方法は、スキャンされる地点および可能なパスの数が多いので、ソースから特定のディスティネーションまでの最短パスを見つけるのに実際には常に効率的であるとは限らない。その代わりに、最短パス計算をほぼ正しい方向に誘導するために、Ａ*探索を使用することができ、それによって途中でスキャンされる頂点の数を減らすことができる。Ａ*探索は、上述したＤｉｊｋｓｔｒａの方法と同様に動作するが、各頂点の推定をさらに維持する。推定は通常、その頂点からディスティネーションまでのパスの実際の重みの下限である。スキャンについてラベルされた頂点を選ぶために、Ａ*探索はラベルされた距離と推定との合計が最小である未スキャンの頂点を選ぶ。Ｄｉｊｋｓｔｒａの方法の残りは同じままである。頂点にわたる推定の集合は、ディスティネーションに対する「ポテンシャル」関数を形成し、頂点のポテンシャルはその頂点からディスティネーションまでの最短パスの重みの推定である。
【００２７】
正確な結果を数学的に保証するために、一般にヒューリスティックな変形は「実現可能な」推定を使用することがある（すなわち、ｖからｗまでのエッジについて、ｖの推定引くｗの推定はエッジの実際の重みを超えない）。これらの下限が実際のパスの重みに近いほど、推定が良くなる。一例を図５に示すが、ここでヒューリスティック探索をｓ５０２からｔ５０４に誘導するために推定が使われている。ヒューリスティック探索によってスキャンされる頂点の集合５０５は、ｔ５０４までの推定距離足すｓ５０４からの実際の距離が最小となる頂点である。この例示的ヒューリスティック探索により、Ｄｉｊｋｓｔｒａの方法の直接的な適用であればスキャンされていたであろう頂点ｖ５０６およびｗ５０８のスキャンが節約された。
【００２８】
以前の下限実装で用いられていた共通の技法は、ユークリッドグラフのユークリッド距離のように、その領域で含意された情報を使用して下限を計算している。本発明の実施形態は、その代わりに「ランドマーク」の小さな集合を選択し、全ての頂点について、あらゆるランドマークまでの、およびあらゆるランドマークからの距離を事前計算する。ここで、例示的な１つの技法を、図６を参照して説明する。前処理ステップ６０２において、集合中の各ランドマークまでの、および各ランドマークからの距離が、各地点（すなわち、対応するグラフ内の頂点）について計算される。ステップ６０４で、ユーザが開始地点およびディスティネーション地点を入力し、ステップ６０６で、そのクエリが地図サービスへ送られる。地図サービスはランドマークを使用して、ステップ６１０で、ソースからディスティネーションまでの最短パスを見つけるためにＡ*探索を行って、探索によって必要とされるときには下限を計算する。ステップ６１２で、地図サービスは最短パスをユーザに戻す。
【００２９】
ランドマークまでの、およびランドマークからの距離は、ディスティネーションまでの距離について下限推定を計算するのに使用することができる。距離は「三角不等式」（すなわち、任意の頂点ｕから他の頂点ｗまでの距離は、ｕから任意の中間頂点ｖまでの距離と、ｖからｗまでの距離との和を超えない）を満たし、次のようにランドマークと共に使用して良好な下限を生成することができる。ランドマークＬを考える。すると、三角不等式により、ｕからＬまでの距離引くｖからＬまでの距離は、ｕからｖまでの距離を超えない。同様に、Ｌからの距離を用いて、Ｌからｖまでの距離引くＬからｕまでの距離は、ｕからｖまでの距離を超えない。
【００３０】
図７を参照すると、本発明の実施形態に従って、ランドマークまでの、およびランドマークからの距離を用いて所定のディスティネーションｔについての緊密な下限推定値を計算するための方法が説明されている。この方法では、ステップ７０２で最初０に設定される最大値を維持することによってある所与の頂点ｕからｔまでの距離に関する緊密な下限が計算される。ステップ７０４で、ランドマークの集合からあるランドマークが選択される。ステップ７０６で、ｕからＬまでの距離とｔからＬまでの距離との差が計算され、ステップ７０８でこの差が最大値と比較される。最大値よりも大きい場合、ステップ７１０で最大値がこの値によって更新される。方法は、次いで、ステップ７１２でＬからｔまでの距離とＬからｕまでの距離との差が計算され、ステップ７１４でこの差が最大値と比較される。最大値よりも大きい場合、ステップ７１６で最大値がこの値によって更新される。方法は、ステップ７１８で、さらに考慮すべきランドマークがないかチェックされる。ある場合、ステップ７０４に戻ることで別のランドマークが選択される。それ以外の場合、方法は終了し、ｕからｔまでの推定距離として最大値が使用される。方法は、グラフ中の各頂点について繰り返し行うことができる。
【００３１】
Ｌまでの、およびＬからの距離が事前計算されるので、各差は一定時間に計算され（すなわち、入力のサイズに関わらず、一定量の計算）、一定の数のランドマークが使用される場合、各頂点ｕの最大差も一定時間内に見つけることもできる。
【００３２】
本発明の実施形態は、全てのランドマークを使用しないこともある。これは、必要な計算回数が少なくなるので、より効率的であることがある。ある所与のソースおよびディスティネーションについて、本発明の実施形態は、ソースからディスティネーションまでの距離に関して最も高い下限を与えるランドマークのサブ集合を選択する。最短パスの計算は、下限を計算するときにこのサブ集合に限定される。サブ集合は静的でも動的でもよく、すなわち計算中に更新されてもよい。
【００３３】
図８に注目すると、本発明の複数の実施形態によって実行されるＡ*探索と共にランドマークを使用することの有効性を示すために、頂点およびエッジの集合が図示されている。この例において、ソースｓ８０２およびディスティネーションｔ８０４は地図上で互いに離れており、ランドマークＬ８０６はｓから、ｔとおよそ同じ方向にある。ｓ８０２からＬ８０６までの最短経路は、ｓ８０２から高速道路までのセグメント８０８、高速道路のみを使用するセグメント８１２、および高速道路からＬまでのセグメント８１４から構成されていそうである。さらに、ｔ８０４までの最短経路は高速道路までの同じセグメント８０８を辿り、しばらく同じ高速道路のパス８１２を進むが、早く出て地方道路８１８を通ってｔ８０４に至る。言い換えると、Ｌ８０６の良好な選択では、ｓ８０２からＬ８０６およびｔ８０４までの最短パスは最初のセグメント８２０を共有する。このセグメント上の頂点ｖ８２４から頂点ｗ８２６までのエッジ８２２を考慮されたい。Ｌ８０６までの距離および三角不等式で与えられる下限関数は、ｖ８２４からＬ８０６までの距離の下限が、ｗ８２６からＬ８０６までの距離の下限とｖ８２４からｗ８２６までのエッジ８２２の実際の重みとの和に等しいという性質を有することが容易に分かる。ｓ８０２からｔ８０４までの最短パスの共有パスセグメント上の任意の２つの頂点についても同じことが言える。これにより、これらのエッジがスキャンされる最初のものとなるであろう。言い換えると、ｖ８２４からｗ８２６までのエッジの「低減されたコスト」が、そのエッジの実際の重みにｖ８２４でのポテンシャルを加え、ｗ８２６でのポテンシャルを減じたものであると定義され、実際の重みは低減されたコストによって置き換えられるならば、この問題は、推定が実現可能な場合、新しいグラフに関するＤｉｊｋｓｔｒａのアルゴリズムに数学的に等価となる。
【００３４】
ＡＬＴ（Ａ*探索、ランドマークおよび三角不等式）アルゴリズムは、ランドマークおよび三角不等式を使用して実現可能な下限を計算する。頂点の小さなサブ集合がランドマークとして選択され、グラフ中の各頂点について、あらゆるランドマークまでの、またはあらゆるランドマークからの距離が事前計算される。ランドマークＬを検討する。ｄ（ｘ，ｙ）がｘからｙまでの距離を表すとすると、三角不等式によりｄ（ｖ，Ｌ）−ｄ（ｗ，Ｌ）≦ｄ（ｖ，ｗ）であり、同様に、ｄ（Ｌ，ｗ）−ｄ（Ｌ，ｖ）≦ｄ（ｖ，ｗ）である。最も緊密な下限を得るには、これらのうち最大のバウンドを、全てのランドマークに対して取ることができる。ｄ（ｖ，ｗ）に関する最良の下限は、ｖの「前」またはｗの「後」に現れるランドマークによって与えられる。
【００３５】
ｓ〜ｔの最短パスの計算の中に、利用可能なランドマークのサブ集合だけを使用するよう推奨される。すなわち、ｓ〜ｔ距離に関して最も高い下限を与えるサブ集合である。これによってパフォーマンスが改善される傾向がある。というのは残りのほとんどのランドマークはこの計算に役立ちそうにないためである。さらなる改良が本明細書に記載されている。
【００３６】
ＡＬＴ技法は、主要段階および前処理段階を備えることができる。主要段階はアクティブなランドマークの動的選択を使用することによって改善することができ、前処理段階は様々なランドマーク選択技法を使用することによって改善することができる。ここにさらに説明したように、前処理中、ＡＬＴアルゴリズムはランドマークの集合を選択し、各ランドマークと全ての頂点との間の距離を事前計算する。次いで、これらの距離を使用して、Ａ*探索に基づく最短パスアルゴリズムのために下限を計算する。
【００３７】
本発明に従って、アクティブなランドマーク（現在の計算に実際に使用されているもの）を動的に選択することができる。例示的な１つの技法は、元の２つのランドマークで開始し、新しいランドマークが現在アクティブなランドマークに比べ、探索の境界について大幅により良い下限を与えるときにそのランドマークを選択することによって改善する。
【００３８】
ＡＬＴの一実装は、各最短パス計算について、ｓ〜ｔ距離に関する最良の下限を与えるｈ個のアクティブなランドマークのサブ集合のみを使用する。このアプローチでは、ランドマークの総数は、利用可能な二次ストレージデバイスの容量によって主に制限される。ｈの選択は、探索効率と、下限を計算するために検討しなければならないランドマークの数との間のトレードオフに依存する。
【００３９】
これは、アクティブなランドマークの集合を動的に更新することによって改善することができる。アクティブなランドマークを動的に選択する例示的な方法のフローチャートを図９に示す。例示的方法は、ステップ９００で２つのアクティブなランドマークのみで開始する。１つはランドマークまでの距離を用いて最良のバウンドを与え、もう１つはランドマークからの距離を用いて最良のバウンドを与える。次いで、規則的なあるいは不規則な間隔で定期的に、アルゴリズムを終了するか、あるいはアクティブなランドマークの総数が上限に達するまで新しいランドマークを追加することにより、アクティブな集合の更新が試行される。
【００４０】
更新の試行は、ステップ９１０で、探索（順方向または逆方向）が、現在の下限関数によって決められたディスティネーションまでの距離推定がある一定の値（チェックポイント）よりも小さい頂点ｖをスキャンするとき常に起こる。この時点で、アルゴリズムはステップ９２０で、（全てのランドマークを用いて）ｖからディスティネーション地までの距離の最良の下限が、（アクティブなランドマークのみを用いて）現在の下限より少なくともあるファクタ１＋∈（たとえば、∈＝０．０１）だけ良いかどうかを検証する。そうである場合、ステップ９３０で、改善されたバウンドをもたらすランドマークがアクティブ化される。そうでない場合、ステップ９４０で、そのランドマークは使用されない。
【００４１】
この計算は、ランドマークからの距離およびランドマークまでの距離をそれぞれ使用してｓ〜ｔ距離について最良のバウンドを与える、最初の最良のランドマークを用いて開始する。計算が進み、下限を必要とする頂点の地点が変化するに従って、他のランドマークがより良いバウンドを与えることがあり、これらはアクティブ集合にもたらされるべきである。あらゆるランドマークの更新の後、ステップ９５０で、ポテンシャル関数が変わり、優先キューが更新される。
【００４２】
チェックポイントは、計算が始まる前に計算されるｓとｔの間の距離についての元の下限ｂによって判定される。たとえば、各探索においてｉ番目のチェックポイントは値ｂ（１０−ｉ）／１０を有することができ、推定された下限が元の値の９０％に達するときにランドマークを更新することをまず試み、次に８０％に達するときに試みられ、以下同様である。この規則はｓとｔが十分離れている場合にうまく機能する。接近している場合、更新の試行が頻繁に起こり過ぎ、アルゴリズムの実行時間を独占してしまう。そのため、同じ方向の２つの連続した更新の試行の間に、アルゴリズムが少なくとも１００個の頂点をスキャンすることが望まれるであろう。
【００４３】
アクティブなランドマークの動的選択は効率を高め、アクティブなランドマークの最終的な数が普通、非常に小さい（たとえば、３に近い）ので、実行時間を短縮する。
【００４４】
前処理中、ランドマークの集合が選択され、各ランドマークと全ての頂点との間の距離が事前計算される。これらの距離は、Ａ*探索に基づく最短パスアルゴリズムについて下限を計算するために使用される。
【００４５】
下限方法の全体的なパフォーマンスを向上する良好なランドマークを見つける幾つかの技法がある。ランドマークを選択する簡単な方法は、ランダムに一定数のランドマーク頂点を選択することである。この「ランダム法」はそれなりにうまく機能する。別のアプローチは、最遠ランドマーク選択アルゴリズムがあるが、これは貪欲に機能する。開始の頂点が選ばれ、それから最も遠い頂点ｖ１が見つけられる。頂点ｖ１がランドマークの集合に加えられる。現在のランドマークの集合から最も遠い頂点（すなわち、集合中の最も近い頂点との距離が最大である頂点）として頂点ｖｉが見つけられる。次いで、頂点ｖｉがランドマークの集合に加えられる。このプロセスは、一定数のランドマークが見つけられるまで繰り返される。この方法は、「最遠ランドマーク選択方法」と呼ばれる。
【００４６】
良好なランドマークを見つけるための別の方法として、「平面ランドマーク選択方法」がある。平面ランドマーク選択方法は一般に、幾何的にディスティネーションの後に位置するランドマークを作り出し、これはグラフと幾何的距離が強く相関される道路グラフや他の幾何的グラフ（非平面グラフを含む）について、通常、良好なバウンドを与える。簡単な平面ランドマーク選択方法は、次のように機能する。まず、平面（または準平面）の埋め込みの中心に最も近い頂点ｃが見つけられる。埋め込みは、ｃを中心とする一定の数のパイ形状のセクタに分割され、それぞれがほぼ同数の頂点を含む。各セクタ毎に、中心から最も遠い頂点が選択される。２つのランドマークが互いに接近し過ぎるのを避けるために、セクタＡが既に処理され、ＡのランドマークがＡおよびＢの境界に近いようにセクタＢが処理されている場合、境界に近いＢの頂点が省かれる。
【００４７】
上記の選択規則は比較的速い。本発明の複数の実施形態によるさらなるランドマーク選択規則には、「回避」および「最大カバー」が含まれる。これらの選択技法はグラフレイアウト情報を使用しないが、従来の選択技法よりもうまく機能する。ランドマークの品質がどのように測定されるかにより、「最適」のランドマーク選択を何通りにも定義できることに留意されたい。たとえば、ｎがグラフ中の頂点の数とすると、全ての可能なＯ（ｎ2）個の最短パス計算について検討する頂点の総数を最小化することを目指すことができる。あるいは、検討した頂点の最大数を最小化することができる。
【００４８】
本発明による、例示的な１つのランドマーク選択方法は「回避」と呼ばれる。この技法は、既存のランドマークを回避することで「うまくカバーされていない」グラフの領域を特定するよう試みる。「回避」は、ランドマーク品質測定を使用して、別個に、あるいは「局所探索」のコンテキストで使用することができる候補の集合を生成する。「回避」では、頂点の重みｗ（ｖ）は、特定の頂点までの実際の最短パスと下限との差として決定される。次いで、頂点のサイズｓ（ｖ）が決定される。これは、「局所探索」により最適化することができる。
【００４９】
図１０は、本発明による例示的なランドマーク選択方法のフローチャートである。たとえば、ステップ１０００で、既に選択されたランドマークの集合Ｓがあり、追加のランドマークが望まれているものと仮定する。ステップ１００５で、ある頂点ｒをルートにもつ最短パスツリーＴｒを計算する。次に、ステップ１０１０で、あらゆる頂点ｖについて、ｄｉｓｔ（ｒ，ｖ）とＳによって与えられるｄｉｓｔ（ｒ，ｖ）の下限との差として定義される重みを計算する。これは、現在の距離推定がどれほど悪いかについての尺度となる。
【００５０】
ステップ１０１５で、あらゆる頂点ｖについて、ｖをルートにもつＴｒのサブツリーであるＴｖに依存するサイズｓ（ｖ）を計算する。ステップ１０２０で、Ｔｖがランドマークを含む場合、ステップ１０２５でｓ（ｖ）＝０に設定する。そうでない場合、ステップ１０３０で、ｓ（ｖ）はＴｖ中の全ての頂点の重みの和となる。ｗを最大サイズの頂点とする。ステップ１０４０で、ｗから開始し、葉に到達するまで常に最大サイズをもつ子を辿るようにＴｗをトラバースする。ステップ１０４５で、この葉を新しいランドマークとする。
【００５１】
このように、ｗから、そのサブツリー中のある頂点までのパスで、その「背後」ランドマークをもつパスはない。ランドマークの集合にこのサブツリーの葉を追加することにより、「回避」はカバレージを改善しようとする。
【００５２】
上で説明したもののように構成的ヒューリスティックスの弱点は、先に選択されたランドマークは、他のランドマークが選択されると、有用性が制限されることがあるということにある。それらをより良いもので置き換えようとすることが望まれる。「局所探索」は、この目的のために使用することができる。探索を実施するには、ある解（すなわち、ランドマークの集合）がどれほど良いかを測定することが望ましい。究極的には、全てのポイント−ポイント間探索の効率をより良くする解を見つけることが目標であるが、これはひどく高価なものである。実際的には、ランドマークの与えられた集合の品質が推定される。
【００５３】
推定には、低減されたコストを使用してもよい。このコンテキストにおいて、ランドマークＬに対する孤の低減されたコストをｌ（ｖ，ｗ）−ｄ（Ｌ，ｗ）＋ｄ（Ｌ，ｖ）と定義し、ここで、ｌ（ｖ，ｗ）は孤（ｖ，ｗ）の長さを表す。低減されたコストがゼロである場合、ランドマークは孤をカバーする。ポイント−ポイント間の最短パスアルゴリズムの最良のケースは、ランドマークがパス上のあらゆる孤をカバーするときに起きる。これを念頭に置いて、ある所与の解のコストを、少なくとも１つのランドマークに対してゼロの低減されたコストを有する孤の個数として定義する。よりコストがかからない解の方が良く、ある一定のｋについて、可能な限り多くの孤をカバーするｋ個のランドマークの集合を見つけることが望ましい。
【００５４】
所与の頂点がどの孤をカバーするかを判断するには、単一ソースの最短パス計算を実行する必要がある。大きいグラフの場合、これを全ての頂点について行うことは現実的ではない。それゆえ、「回避」を用いて選択された候補ランドマークの小さな集合を使用する。
【００５５】
より正確には、図１１に関して、ステップ１１００で、Ｃを最初は空である候補の集合とする。ステップ１１１０で、ｋ個のランドマークを有する解を見つけるために「回避」を実行して開始し、ステップ１１２０でランドマークの全てがＣに追加される。次いで、ステップ１１３０で、現在の解から確率１／２で各ランドマークを取り除く。取り除かれると、ステップ１１４０で、解が再びサイズｋとなるまで、さらにランドマークを（再び「回避」を用いて）生成する。ステップ１１５０で、Ｃにまだない新しい各ランドマークが追加される。ステップ１１６０で、たとえばＣがサイズ４ｋとなるか、あるいは「回避」が５ｋ回実行される（これらのいずれか先に発生するにしても）までこのプロセスを繰り返す。回避のあらゆる実行が必ずしも新しいランドマークを生成するとは限らないので、アルゴリズムの実行時間を制限することが望ましい。
【００５６】
最終的に、ｋ〜４ｋ個の候補ランドマークを有する集合Ｃがヒューリスティック的に得られることになる。各ランドマークをそれがカバーする孤の集合として解釈して、最大カバー問題の事例を解くことが望ましい。マルチスタートヒューリスティックを使用して近似解を見つけることができる。この問題はＮＰハードなので、厳密解を求めることは難しい。各繰り返しは、ｋ個のランドマークを有するＣのランダムなサブ集合Ｓで開始し、それに局所探索手順を適用する。集合の品質が決定される。最後に、全ての繰り返しを通じて得られた最良の解を選ぶ。たとえば、繰り返しの回数をｌｏｇ2ｋ＋１に設定する。
【００５７】
局所探索は、現在の解に属する１つのランドマークを、現在の解には属さないが候補の集合に属する別のもので置き換えようとする。これは、Ｏ（ｋ2）個の可能なスワップのそれぞれに関連付けられるプロフィットを計算することによって働く。プロフィットが負またはゼロのものは破棄される。残っているものの中で、利益に比例した確率でランダムにスワップを選ぶ。次いで、同じ手順が新しい解に適用される。局所探索は、局所的最適点に達するとき、すなわち改善をもたらすようなスワップがなされなくなるときに中止する。局所探索の各繰り返しは０（ｋｍ）時をとる。ランドマーク生成のこの方法は「最大カバー」と呼ばれる。この最適化フェーズはかなり速い。実行時間は、候補ランドマークの集合を生成するのに使用される「回避」の呼出しによって独占される。
【００５８】
ＡＬＴアルゴリズムのメモリ効率の良い実装を説明する。スペース効率の良いデータ構造がキャッシング、データ圧縮およびハッシングと組み合わせて使用される。このような技法は、フラッシュメモリにグラフおよびランドマークデータが格納されたポケットＰＣに使用することができ、約３０００万個の頂点を有する北米の道路ネットワークを含め、幾つかの道路ネットワークで使用されてきた。
【００５９】
例示的な一実装では、グラフおよびランドマークデータをフラッシュメモリカードに格納する。カードから読み出すことができる最低量（たとえば、５１２バイトセクタ）は、システム上の制約によって決まる。データはページ単位で読み出され、１つのページは１つまたは複数のセクタを収容する。
【００６０】
グラフは、次のフォーマットでフラッシュカードに格納することができる。弧は、弧のテールでソートされたレコードのアレイとして表される。各レコードは、１６ビットの弧長（たとえば、秒での移動時間）およびヘッド頂点の３２ビットＩＤを有する。別のアレイは、それぞれが最初の出弧を表すレコードの３２ビットインデックスを備える頂点レコードを表す。逆グラフも（同じフォーマットで）格納される。
【００６１】
探索によって検討された各頂点に必要な追加情報は、メインメモリ中にミュート可能ノード（ｍｕｔａｂｌｅ ｎｏｄｅ）と呼ばれるレコードに保持される。各頂点は２つのミュート可能ノードを必要とすることができる。１つは順方向探索のためのものであり、もう１つは逆方向探索のためのものである。ミュート可能ノードは４つの３２ビットフィールドを有する。すなわちＩＤ、距離ラベル、親ポインタおよびヒープ位置である。幾つかのフィールドは、道路ネットワークアプリケーションにおいて生じそうな最大グラフのためにさえ必要以上に大きいが、実装をクリーンかつ柔軟に保つためにレコードをワード整合することが望ましいことがある。ユーザは、ミュート可能ノードの許容される最大数Ｍを指定する。使用されるＲＡＭの総量はＭに比例する。
【００６２】
頂点ＩＤを対応するミュート可能ノードにマップするために、少なくとも１．５Ｍのサイズのテーブルを用いてダブルハッシングを使用する。各探索に１つずつ、２つの優先キューを維持する。最短パスアルゴリズムの場合、マルチレベルのバケット実装が一番速い傾向にある。Ｐ２Ｐ計算の場合、４ヒープが望ましいことがある。マルチレベルバケットよりは遅いものの、４ヒープはスペースのオーバーヘッドがより少ない（１頂点あたり１ヒープインデックス）。加えて、優先キューは一般に、アプリケーション内でそれほど多くの要素を含まないので、ヒープ操作に関連付けられるオーバーヘッドは、データアクセスに関するものに比して控えめである。プロトタイプ実装では、各ヒープの最大サイズがＭ／８＋１００要素に設定された。
【００６３】
データは強い局所性を持つことがある。この理由と、データがブロックで読み取られるという理由とにより、アルゴリズムは明示的なキャッシング機構を実施する。ページアロケーションテーブルが物理ページアドレスを（ＲＡＭの）バーチャルページアドレスにマップし、その置換戦略はＬＲＵである。すなわち、使用頻度が最も低いページが望まれるならばいつでも追い出される。グラフおよびランドマークに別個のキャッシュが使用される。６個のランドマークキャッシュ（各アクティブなランドマークに１つ）のそれぞれは１ＭＢあり、２個のグラフキャッシュのそれぞれは２ＭＢある。
【００６４】
データは、各ランドマーク毎に別個のファイルに格納される。各距離は、３２ビットの整数で表される。同じ頂点についての行きと帰りの距離は隣接している。グラフは完全には対称ではないが、２つの距離は普通近い。さらに、似通ったＩＤを有する頂点は互いに近くにある傾向があるので、それらのランドマークまでの（または、ランドマークからの）距離もまた似通っている。この類似性は圧縮に望ましく、これによってフラッシュカードにより多くのデータが入るようになり、データ読み出し操作が速くなる。
【００６５】
隣接するワード（距離）の２つの最上位バイトが同じである傾向にあるので、ほぼ５０％の圧縮率が達成できる。ファイルへのランダムアクセスを可能にするために、各ページは別個に圧縮される。圧縮率が変わるので、ファイルはページオフセット付きのディレクトリを有する。
【００６６】
このように、本発明の技法は従来技術の技法よりも（より効率が高いので）少ない数の頂点を検討するだけでなく、（動的選択によりアクティブなランドマークの数が低減されるので）各頂点をより素早く処理することもできる。
【００６７】
本明細書に記載した様々なシステム、方法および技法は、ハードウェアまたはソフトウェアで、あるいは適切な場合には、両者の組合せで実施することができる。このように、本発明の方法および装置、またはその幾つかの態様または部分は、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、ハードドライブ、または他の任意の機械可読記録媒体などの有形媒体中に具現されたプログラムコード（すなわち、命令）の形態をとることができ、そのプログラムコードがコンピュータなどのマシンにロードされて実行されるときそのマシンが本発明を実施するための装置となる。プログラム可能なコンピュータ上でのプログラムコードの実行の場合、コンピュータは、一般にプロセッサ、プロセッサによって可読の記録媒体（揮発性および不揮発性のメモリおよび／または記憶要素を含む）、少なくとも１つの入力装置、および少なくとも１つの出力装置を含むであろう。１つまたは複数のプログラムが、好ましくはコンピュータシステムと通信可能となるように、ハイレベルの手続き型プログラミング言語またはオブジェクト指向プログラミング言語で実装される。しかし、望むなら、この（１つまたは複数の）プログラムは、アセンブリ言語またはマシン語で実装することもできる。いずれの場合も、言語はコンパイルされるか、インタープリットされた言語とすることができ、ハードウェア実装と組み合わせることができる。
【００６８】
本発明の方法および装置はまた、電気配線またはケーブル、光ファイバあるいは他の任意の形態の伝送など、なんらかの伝送媒体を介して伝送されるプログラムコードの形態をとることができ、このプログラムコードは、ＥＰＲＯＭ、ゲートアレイ、プログラム可能論理回路（ＰＬＤ）、クライアントコンピュータ、ビデオレコーダなどのマシンによって受け取られ、ロードされて実行されるとき、そのマシンが本発明を実施するための装置となる。汎用プロセッサ上で実装されると、プログラムコードはプロセッサと組み合わせて、本発明の機能を実行するように動作する独自の装置を提供する。
【００６９】
本発明について様々な図に示した好ましい実施形態に関連して説明したが、本発明から逸脱することなく、本発明の同様の機能を実行するために他の類似の実施形態を使用してよく、あるいは説明した実施形態に修正または追加を行ってもよいことが理解さるべきである。それゆえ、本発明はどの単一の実施形態にも限定されるべきではなく、添付の特許請求の範囲による広がりおよび範囲で解釈されるべきである。
【図面の簡単な説明】
【００７０】
【図１】本発明の一実施形態による、最短パスを計算することができるコンピューティング環境の例示的アーキテクチャを示す簡略化された概略図である。
【図２】本発明の一実施形態による、コンピューティングネットワーク上のコンピューティングデバイスの構成を示す図である。
【図３】本発明の一実施形態による、相互接続された地点のグラフ表現を示す図である。
【図４】最短パス検索方法でスキャンされた地点を示す図である。
【図５】本発明の一実施形態による、ヒューリスティックな最短パス検索方法でスキャンされた地点を示す図である。
【図６】本発明の一実施形態による、２つの地点の間の最短パスを見つける方法を示すフロー図である。
【図７】本発明の一実施形態による、ランドマークを使用してディスティネーション地までの距離を推定する方法を示すフロー図である。
【図８】地点およびあるランドマークの例示的な集合を示す図である。
【図９】本発明による、アクティブなランドマークを動的に選択する例示的な方法のフロー図である。
【図１０】本発明による、例示的なランドマーク選択方法のフロー図である。
【図１１】本発明による、別の例示的なランドマーク選択方法のフロー図である。
【符号の説明】
【００７１】
１００ コンピューティングシステム環境
１１０ コンピュータ
１２０ 処理装置
１２１ システムバス
１２２ メモリキャッシュ
１３０ システムメモリ
１３１ ＲＯＭ
１３２ ＲＡＭ
１３３ ＢＩＯＳ
１３４ オペレーティングシステム
１３５ アプリケーションプログラム
１３６ その他のプログラムモジュール
１３７ プログラムデータ
１４０ 非リムーバブル不揮発性メモリインターフェース
１４１ ハードディスクドライブ
１４４ オペレーティングシステム
１４５ アプリケーションプログラム
１４６ その他のプログラムモジュール
１４７ プログラムデータ
１５０ リムーバブル不揮発性メモリインターフェース
１５１ 磁気ディスクドライブ
１５２ 磁気ディスク
１５５ 光ディスクドライブ
１５６ 光ディスク
１６０ ユーザ入力インターフェース
１６１ マウス
１６２ キーボード
１７０ ネットワークインターフェース
１７１ ローカルエリアネットワーク
１７２ モデム
１７３ ワイドエリアネットワーク
１８０ リモートコンピュータ
１８１ メモリストレージデバイス
１８５ リモートアプリケーションプログラム
１９０ ビデオインターフェース
１９１ モニタ
１９５ 出力周辺インターフェース
１９６ プリンタ
１９７ スピーカ
２００ コンピューティングデバイス
２０２ ローカルエリアネットワーク
２０４ ウェブブラウザ
２０５ インターネット
２０６ 地図経路サービス
２０８ 地図経路サーバ
２１０ データベース
３０２ エッジ
３０４，３０６，３０８，３１０，３１２ 頂点
４０２，４０４，４０６ 頂点
５０２，５０４，５０６，５０８ 頂点
５０５ 集合
８０２ ソース
８０４ ディスティネーション
８０６ ランドマーク
８０８，８１２，８１４，８２０ セグメント
８２２ エッジ
【特許請求の範囲】
【請求項１】
地点の集合の中で開始地点からディスティネーション地点までの最短パスを見つける方法であって、
ランドマークの集合を選択することと、
各ランドマークと、前記地点の集合内の地点との間の距離を計算することと、
前記距離に基づいて下限を計算することと、
前記下限に基づいてＡ*プロセスを実行して最短パスを決定することと
を備えることを特徴とする方法。
【請求項２】
前記ランドマークの集合を選択することは、回避ランドマーク選択方法を用いて前記ランドマークの集合を選択することを備えることを特徴とする請求項１に記載の方法。
【請求項３】
局所探索法を用いて前記回避ランドマーク選択方法を最適化することをさらに備えることを特徴とする請求項２に記載の方法。
【請求項４】
前記ランドマークの集合を選択することは、最大カバー選択方法を用いて前記ランドマークの集合を選択することを備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記Ａ*プロセスは、アクティブなランドマークを使用することを特徴とする請求項１に記載の方法。
【請求項６】
前記アクティブなランドマークを動的に選択することをさらに備えることを特徴とする請求項５に記載の方法。
【請求項７】
前記アクティブなランドマークを動的に選択することは
ランドマークからディスティネーション地点までの距離に関する最良の下限が現在の下限よりも少なくともある所定のファクタだけ優れているかどうかを判定することであって、そうである場合、前記ランドマークをアクティブ化することと
を備えることを特徴とする請求項６に記載の方法。
【請求項８】
ランドマーク選択方法であって、
複数の地点に対応する複数の頂点のサイズを判定することと、
第１のツリーグラフを最大のサイズを有する頂点から開始し、最大のサイズを有する子を辿って葉に到達するまでトラバースすることと、
前記葉をランドマークとしてアクティブ化することと
を備えることを特徴とする方法。
【請求項９】
ある頂点をルートにもつ第２のツリーグラフを判定することと、複数の頂点のサイズを判定するのに先立って、前記第２のツリーグラフ中のあらゆる頂点の重みを判定することとをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１０】
各頂点の重みを判定することは、実際の最短パスと、前記第２のツリーグラフ上の下限との間の差を判定することを備えることを特徴とする請求項９に記載の方法。
【請求項１１】
前記複数の頂点のサイズは、サイズが判定されている頂点をルートとする前記第２のツリーグラフのサブツリーに基づくことを特徴とする請求項９に記載の方法。
【請求項１２】
前記ランドマークに関する局所探索を行うことをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１３】
ランドマーク選択方法であって、
（ａ）複数のランドマークを判定することと、
（ｂ）前記ランドマークを候補の集合に追加することと、
（ｃ）所定の確率でランドマークを廃棄することと、
（ｄ）追加のランドマークを生成することと、
（ｅ）まだ前記集合にない追加のランドマークを前記候補の集合に追加することと、
（ｆ）所定の条件が満たされるまでステップ（ｃ）〜（ｅ）を繰り返すことと
を備えることを特徴とする方法。
【請求項１４】
ステップ（ａ）および（ｄ）は、回避ランドマーク選択プロセスを用いることを備えることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記所定の確率は、１／２であることを特徴とする請求項１３に記載の方法。
【請求項１６】
前記所定の条件は、前記候補の集合の１つが所定のサイズに達し、ステップ（ｄ）が所定の回数実行されることであることを特徴とする請求項１３に記載の方法。
【請求項１７】
（ｇ）前記候補ランドマークの集合を使用して最大カバー選択プロセスを実行することをさらに備えることを特徴とする請求項１３に記載の方法。
【請求項１】
地点の集合の中で開始地点からディスティネーション地点までの最短パスを見つける方法であって、
ランドマークの集合を選択することと、
各ランドマークと、前記地点の集合内の地点との間の距離を計算することと、
前記距離に基づいて下限を計算することと、
前記下限に基づいてＡ*プロセスを実行して最短パスを決定することと
を備えることを特徴とする方法。
【請求項２】
前記ランドマークの集合を選択することは、回避ランドマーク選択方法を用いて前記ランドマークの集合を選択することを備えることを特徴とする請求項１に記載の方法。
【請求項３】
局所探索法を用いて前記回避ランドマーク選択方法を最適化することをさらに備えることを特徴とする請求項２に記載の方法。
【請求項４】
前記ランドマークの集合を選択することは、最大カバー選択方法を用いて前記ランドマークの集合を選択することを備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記Ａ*プロセスは、アクティブなランドマークを使用することを特徴とする請求項１に記載の方法。
【請求項６】
前記アクティブなランドマークを動的に選択することをさらに備えることを特徴とする請求項５に記載の方法。
【請求項７】
前記アクティブなランドマークを動的に選択することは
ランドマークからディスティネーション地点までの距離に関する最良の下限が現在の下限よりも少なくともある所定のファクタだけ優れているかどうかを判定することであって、そうである場合、前記ランドマークをアクティブ化することと
を備えることを特徴とする請求項６に記載の方法。
【請求項８】
ランドマーク選択方法であって、
複数の地点に対応する複数の頂点のサイズを判定することと、
第１のツリーグラフを最大のサイズを有する頂点から開始し、最大のサイズを有する子を辿って葉に到達するまでトラバースすることと、
前記葉をランドマークとしてアクティブ化することと
を備えることを特徴とする方法。
【請求項９】
ある頂点をルートにもつ第２のツリーグラフを判定することと、複数の頂点のサイズを判定するのに先立って、前記第２のツリーグラフ中のあらゆる頂点の重みを判定することとをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１０】
各頂点の重みを判定することは、実際の最短パスと、前記第２のツリーグラフ上の下限との間の差を判定することを備えることを特徴とする請求項９に記載の方法。
【請求項１１】
前記複数の頂点のサイズは、サイズが判定されている頂点をルートとする前記第２のツリーグラフのサブツリーに基づくことを特徴とする請求項９に記載の方法。
【請求項１２】
前記ランドマークに関する局所探索を行うことをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１３】
ランドマーク選択方法であって、
（ａ）複数のランドマークを判定することと、
（ｂ）前記ランドマークを候補の集合に追加することと、
（ｃ）所定の確率でランドマークを廃棄することと、
（ｄ）追加のランドマークを生成することと、
（ｅ）まだ前記集合にない追加のランドマークを前記候補の集合に追加することと、
（ｆ）所定の条件が満たされるまでステップ（ｃ）〜（ｅ）を繰り返すことと
を備えることを特徴とする方法。
【請求項１４】
ステップ（ａ）および（ｄ）は、回避ランドマーク選択プロセスを用いることを備えることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記所定の確率は、１／２であることを特徴とする請求項１３に記載の方法。
【請求項１６】
前記所定の条件は、前記候補の集合の１つが所定のサイズに達し、ステップ（ｄ）が所定の回数実行されることであることを特徴とする請求項１３に記載の方法。
【請求項１７】
（ｇ）前記候補ランドマークの集合を使用して最大カバー選択プロセスを実行することをさらに備えることを特徴とする請求項１３に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００６−２０１１７４（Ｐ２００６−２０１１７４Ａ）
【公開日】平成１８年８月３日（２００６．８．３）
【国際特許分類】
【出願番号】特願２００６−１０４３８（Ｐ２００６−１０４３８）
【出願日】平成１８年１月１８日（２００６．１．１８）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公開日】平成１８年８月３日（２００６．８．３）
【国際特許分類】
【出願日】平成１８年１月１８日（２００６．１．１８）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]