経路発見計算のための複数のコストレベルの使用
【課題】電子地図もしくは他のネットワークの特定のカテゴリの要素を回避することができ、電子地図もしくは他のネットワークを使用して経路を計算できるシステムを提供する。
【解決手段】
処理装置で読取可能に表現したネットワークにおいて経路を計算するためのシステム。このシステムは認識されたコストを最小にできる。コストには時間、距離、支払った通行料、曲がり易さ、風景の質、処理時間、待ち時間等が含まれる。経路発見システムのユーザは、回避するための一つ以上の要素のカテゴリを選択できる。例えば、道路地図において有料道路を避けたいと望む可能性がある。回避する要素に関連するコストには少なくとも二つの表現のレベルが含まれる。二つの表現のレベルには第１レベルおよび第２レベルが含まれ、第２レベルが第１レベルよりも優先される。経路発見システムはコストを最小にする経路を決定する。
【解決手段】
処理装置で読取可能に表現したネットワークにおいて経路を計算するためのシステム。このシステムは認識されたコストを最小にできる。コストには時間、距離、支払った通行料、曲がり易さ、風景の質、処理時間、待ち時間等が含まれる。経路発見システムのユーザは、回避するための一つ以上の要素のカテゴリを選択できる。例えば、道路地図において有料道路を避けたいと望む可能性がある。回避する要素に関連するコストには少なくとも二つの表現のレベルが含まれる。二つの表現のレベルには第１レベルおよび第２レベルが含まれ、第２レベルが第１レベルよりも優先される。経路発見システムはコストを最小にする経路を決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路発見計算に複数のコストレベルを使用するシステムに関する。
関連出願への相互参照
本出願は下記の出願に関連する。
１９９６年１１月２５日出願のリチャード・エフ・ポッペンによる米国特許出願「ネットワーク内の領域の出口および入口を決定する方法」（米国特許出願Ｎｏ．０８／７５６，２５８）。この関連出願を本出願の一部を構成するものとしてここに援用する。
【背景技術】
【０００２】
発明の背景
発明の分野
関連技術
コンピュータは、システムの高度な研究および利用を可能にするためにそのシステムをモデル化するというアイデアに変革をもたらした。その一例は、システムをネットワークとしてモデル化する事である。最も一般的な意味では、ネットワークは相互接続および分岐のための多くの経路を含むものであると定義されている。判断を必要とする多くのシステムはネットワークとしてモデル化できる。例えば、製造工程もしくは医学療法を提供するシステムは、決定点および決定点間のアクションから成るネットワークとしてモデル化できる。このネットワークを電子的な形で表し、処理装置が読取可能な記憶媒体に記憶することができ、これにより、このネットワークモデルを用いてシステムを研究または使用するためのソフトウェアの開発を可能にする。
電子的な形で記憶できる有益なネットワークの一例として電子地図がある。これは、地理学的に参照される、物理的、社会的、もしくは経済的なシステムを量的に表した電子データを含む。電子地図に含まれる情報の範囲には制限が無く、例えば、要素間の距離、移動時間、割り当て番号（lot number）、税金情報、ツーリスト情報、処理時間、待ち時間などを含むことが出きる。更に、地図をコンピュータ上にファイルとして記憶することで、無制限のアプリケーションソフトによるそのデータの操作を可能にする。
電子地図の一利点は、地図の種々の部分に関連するコストを記憶および決定できることである。コストとは最小化もしくは最大化できる変数である。コストは必ずしも金銭的なコストであるとは限らない。コストとは最小化または最大化しなければならない何かである。通常、コストは整数で表される。コストは実数で表されることもある。コストの例として、時間、距離、支払った料金、曲がり易さ、風景の質などがある。
電子地図は、他のネットワークと同様に、経路発見に使用できる。経路発見とは始点と終点との間のルートを計算する方法である。いくつかのシステムは推奨ルートを計算し、地図表示装置上に推奨ルートを強調表示することによって、もしくは曲がりがあるたびに指示を出すことによって、またはその両方によって運転者を誘導する。
経路発見システムは、ある規定の基準に従って最も望ましいルートを発見することによって終点までの推奨ルートを計算する。これらの基準は運転者によって規定されるか、製造時にデフォルトとして設定される。システムは、多くの場合、あるコスト、例えば運転時間を最小化（または最大化）する経路を発見するために使用される。経路発見システムの使用者にとって有用である一特徴として、電子地図の特定の要素を回避する機能が挙げられる。使用者は特定の種類の道路、曲がり、交差点などを回避したいことがある。例えば、特定の地理領域において、非有料道路および有料道路が存在するとする。使用者は、たとえ運転時間が長くなったとしても有料道路を回避する経路を発見したいことがある。或いは、使用者は、フェリー、トンネル、もしくは橋などの使用も避けたいことがある。従来、この望みは、望ましくない道路（または地図中の他の要素）の単位距離当りのコストを極めて高くすることで実現していた。そのような方法では、望ましくない道路（または要素）は、その道路を避けることによりコストが非常に大きくなる場合にのみ使用される。
【０００３】
【特許文献１】特開平８―２９２０５８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
電子地図中の望ましくない要素のコストを大きくする手法は、望ましくない要素の使用を回避する手段として有効ではないことが分かった。第１に、道路線分のコストを大きくしても、可能な限り望ましくない道路が回避されることが保証されるわけではない。そのような特定の種類の道路は、更にコストが大きい他の道路上のルートを避けるために依然として選択されることがある。第２に、望ましくない道路を回避するための従来の技術は、経路が望ましくない道路上の移動を必要とする場合に、この望ましくない道路上の移動が最小にされることが保証されるわけではない。最後に、従来のように、高いコストを表すために極めて大きな整数を使用しようとすると、多くのコンピュータ内でオーバーフローを起こす可能性がある。同様に、大きな実数を使用すると、その意義が失われてしまうことがある。
従って、電子地図もしくは他のネットワークの特定のカテゴリの要素を回避することができ、電子地図もしくは他のネットワークを使用して経路を計算できるシステムが必要である。
【課題を解決するための手段】
【０００５】
発明の要約
本発明は、大まかに説明すると、複数のコストレベルを使用してネットワークにおける経路を計算するシステムを提供する。どの要素を回避するべきかの判断が行われる。少なくとも一つの要素に関連するコストには二つ以上の表現のレベルが含まれる。二つ以上の表現のレベルには第１レベルおよび第２レベルが含まれる。その後、システムは経路発見探索を実行する。
一実施例においては、システムには、処理装置で読取可能に表現したネットワークにおける要素の第１集合を識別するステップと、要素の第１集合の第１の要素に関連した第１コストを作成するステップとが含まれる。第１コストには少なくとも二つの表現のレベルが含まれる。次いで、システムは、作成した第１コストを使用して経路発見探索を実行する。上記識別ステップは、経路発見システムの使用者からの入力を受け付けることであったり、経路発見システムにより自動的に行われたりすることができる。二つの表現のレベルには第１レベルおよび第２レベルが含まれ、第２レベルは第１レベルよりも優先される。他の例には、回避する要素の追加集合を識別すること、およびこれらの追加要素のための、三つの表現のレベルを含んだコストを作成することが含まれる。三つの表現のレベルには、第１レベル、第２レベルおよび第３レベルが含まれる。第３レベルは第１レベルおよび第２レベルよりも優先される。
一実施例においては、本発明は、始点から終点までの経路発見探索を実行するが、これには第１ノードから第２ノードまでの第１経路を発見するステップが含まれ、この第１経路には一以上のリンクの第１集合および一以上のコストの第２集合が含まれる。経路発見探索には更に、第１ノードから第２ノードまでの第２経路を発見することが含まれ、第２経路には一以上のリンクの第２集合および一以上のコストの第２集合が含まれる。コストの第２集合の内の少なくとも一つには二つの表現のレベルが含まれる。経路発見探索では、一つ以上のコストの第１集合の方が一つ以上のコストの第２集合よりも効率的なため、第２経路ではなく第１経路が選択される。
処理装置で読取可能に表現したネットワークは、ノードの識別、ノード間のリンクの識別、およびリンク上を移動するためのコストの識別によって作成することができる。ノード、リンク、およびコストを表すデータは処理装置で読取可能な記憶媒体上のデータベース内に記憶される。記憶されたコストの内の少なくとも一つには、二つの表現のレベルが含まれる。
本発明の、これらのおよび他の目的および利点は、図と共に実施例を示す以下の詳細な説明から明らかになるだろう。
【発明の効果】
【０００６】
本発明のシステムによれば、電子地図もしくは他のネットワークの特定のカテゴリの要素を回避することができ、電子地図もしくは他のネットワークを使用して経路を計算できる。
【発明を実施するための最良の形態】
【０００７】
詳細な説明
図１は、本発明の実施に使用可能なハードウェアアーキテクチャの一例を示すブロック図である。ハードウェアはＣＰＵ１２を含む。このＣＰＵ１２は、インテル８０４８６互換ＣＰＵ、ペンティアム（登録商標）プロセッサ、もしくはその他の適切なプロセッサであることができる。ＣＰＵ１２は、ＣＰＵバス１４に接続されるアドレス、データ、およびコントロールバスラインを有する。また、ＣＰＵバス１４は、いずれもシステム制御論理回路２０によって制御されるキャッシュメモリ１６および主記憶装置１８に接続される。システム制御論理回路２０はＣＰＵバス１４およびコントロール、アドレス、データバスラインから成るバス２２に接続されている。システムＢＩＯＳの入ったＲＯＭ２４および周辺装置２６がバス２２に接続されている。周辺装置２６はフロッピー（登録商標）、ハードディスクドライブ、ＣＤ−ＲＯＭドライブもしくはその他の周辺装置を含むことができる。キャッシュメモリ１６、ＤＲＡＭメモリ１８、ＲＯＭ２４、ＣＤ−ＲＯＭ、およびフロッピー（登録商標）ディスクはいずれも処理装置で読取可能な記憶装置（または媒体）である。本発明の種々の実施例は、様々な量のソフトウェアを使用して記載してある方法を実行する。このソフトウェアは、処理装置で読取可能な、任意の適切な記憶装置に存在することができる。図１には描かれていないが、このハードウェアは、表示装置およびキーボードもしくはポインティングデバイス等の入力装置を含む。図１のシステムは本発明に使用可能な一つのプラットフォームを示す。他の多くのプラットフォームであってもよく、例えば、アップルコンピュータ社から入手可能なマッキントッシュベースのプラットフォーム、異なるバス構造を有するプラットフォーム、ネットワーク型プラットフォーム、マルチプロセッサプラットフォーム、その他のパーソナルコンピュータ、ワークステーション、メインフレーム、ナビゲーションシステム等である。
電子地図は、地図を構成するのに必要なデータを含んだ一つ以上のコンピュータファイルに記憶される。このデータには、経度および緯度データ、住所、距離、方向転換の制限、運転時間、高速道路出口番号、土地の商用利用の説明等を含むことができる。上述の情報は電子地図中に見ることができるが、上述した情報の一部分のみもしくは他の情報を有する電子地図を作成することが可能である。電子地図を表すコンピュータファイルは処理装置で読取可能な記憶媒体に記憶される。
通常、経路発見に使用する電子地図にはグラフが含まれる。グラフはノードとエッジの集合である。ノードはプロパティを有するオブジェクトで、グラフ上の決定点を表わす。エッジは二つのノード間の接続である。グラフ中のノードＡからノードＢへの経路は、ノードのリストとして記載される。このリストは、リスト中の各ノードから次のノードへのエッジが存在するように記載される。有向グラフ（directed graph）とは、グラフ内の各エッジがそれに関連する単一の方向を有するグラフである。ある一組のノード間には、各方向に一つづつ、合計で二つのエッジがある場合もある。有向グラフ中では、エッジはリンクと呼ばれる。重み付きグラフとは、グラフ内の各リンク（またはエッジ）がそれに関連するコストを有するグラフである。他の方法には、コストをノード、またはノードおよびリンクと関連付けたり、コストをグラフの他の要素と関連付けたりすることが含まれる。非有向グラフ（undirected graph）とは、グラフ内の各リンクが双方向性であるグラフである。非有向グラフは、グラフ内の各リンクが、端点は同じであるが向きが異なる二つのリンクを表している有向グラフであると考えることができる。
【０００８】
図２Ａは有向グラフの一例を示す。このグラフは、東行きの一方通行路５０および対面通行路５２を示し、いずれの通行路も対面通行路５４と交差している。道路５０は交差点６０で道路５４と交差する。道路５２は交差点７０で道路５４と交差する。交差点６０には二つのノード６２および６４がある。ノードの頭は丸である。ノードの後部は直線尾部である。丸はノードがどこに位置するかを表し、尾部は移動者がどこから来てそのノードへたどり着くであろうかを表す。見やすくするため、ノード記号は実際の交差点からずらした位置にある。例えば、ノード６２は、道路５４上における、交差点６０へ向かう北行きの移動を表す。ノード６４は、道路５０上における、交差点６０へ向かう東行きの移動を表す。交差点６０には西行きの移動を表すノードは無く、これは道路５０が東行きの一方通行路であるからである。そのため、道路５４上を北へ進む移動者は、交差点６０に着くと右折することしかできない。ノード７２は、道路５４上を南へ移動することで交差点７０に着くことを表す。ノード７４は、道路５２上を東へ移動することで交差点７０に着くことを表す。ノード７６は、道路５２上を西へ移動することで交差点７０に着くことを表す。
リンクはノード間における経路を表す。例えば、ノード６４から、移動者は交差点６０を右折することで道路５４へ入ることができ、また、道路５０上を直進することができる。リンク８６は、道路５０上を東を向いて交差点６０から出発し、交差点６０で右折して道路５４上を南へ進む移動を表す。このようにして、リンク８６はノード６４とノード７２とを接続する。リンク８８は、ノード６４を道路５０上の次のノード（図２Ａ上に示されていない）と接続し、道路５０に沿って東に進み、交差点６０を曲がらずに直進する移動を表す。リンク８９は、道路５４上を北を向いて交差点６０から出発し、交差点６０を右折して道路５０上を東へ進む移動を表す。従って、リンク８９はノード６２と道路５０上の次のノード（図２Ａ上に示されていない）とを接続する。図２Ａはノード６２と６４についてのリンクのみを示す。全てのノードに対するリンクを描くと、有向グラフが大変込み合い、判読が困難になる。そのため、この有向グラフを簡略化して、描き直したものが図２Ｂである。
【０００９】
後述の説明を簡略化するため、図２Ｂでは同一の交差点におけるノードの全て一つのノードに統合してある。（実際に使用する場合、本発明は図２Ａもしくは図２Ｂと同様のグラフを使用できる。）従って、ノード１００はノード６４およびノード６２を表す。ノード１０２はノード７２、７４および７６を表す。ノードの尾部が描かれていない。リンクは、移動可能な方向を示すのに使用される。リンク１０４は交差点７０から交差点６０への移動を示し、リンク１０６は交差点６０から交差点７０への移動を示す。方向転換の制限および一方通行路はリンクの有無で表す。
図２Ｂの有向グラフを、処理装置で読取可能な記憶媒体に記憶されたデータ構造を抽象的に理解するために使用する。処理装置で読取可能な記憶媒体は、実際に有向グラフのイメージを記憶するわけではなく、データ構造を記憶する。データ構造内の各項目はノードを表す。データ構造は、各ノードについて、ノードの位置（例えば緯度および経度）、隣接するノード（一つのリンクを経由して移動できるノード）のリスト、および隣接するノードへの移動に関連する種々のコストを記憶する。本発明は、前述したデータ構造とは異なる、多くの適切なデータ構造でもうまく実施できるものと考えられる。更に、本発明は有向グラフについての使用に限定されるものではない。本発明は地図データベース全体、もしくは他の適切な情報の部分集合（subset）に使用できる。更に、データ構造内の一つ以上の項目はデータのクラスタ内に集められることができる。データのクラスタとは関連データの集まりである。クラスタは性能を向上させるが、本発明はクラスタ無しで使用できる。
【００１０】
図３は、ネットワークの一部分についての有向グラフを表す。この有向グラフには、５個のノード（Ｑ、Ｐ、Ｒ、ＳおよびＴ）および６個のリンク（１３０、１３２、１３４、１３６、１３８および１４０）が含まれる。各リンクはそのリンクに隣接して数字が示されている。この数字はそのリンクに沿った移動のコストを表す。リンク１３０はノードＱをノードＰに接続し、そのコストは４である。リンク１３２はノードＱをノードＲに接続し、そのコストは１である。リンク１３４はノードＱをノードＴに接続し、そのコストは２である。リンク１３６はノードＰをノードＲに接続し、そのコストは２である。リンク１３８はノードＲをノードＳに接続し、そのコストは２である。リンク１４０はノードＳをノードＴに接続し、そのコストは２である。
ノードＱからノードＴへ移動するには三つの経路がある。第１経路にはリンク１３４に沿ってノードＱからノードＴへ直接移動することが含まれる。この経路はＱＴとして識別され、コストは２である。第２経路にはノードＱからノードＲとノードＳを経由してノードＴに至る移動が含まれる。第２経路はＱＲＳＴとして識別される。経路ＱＲＳＴはリンク１３２、１３８、および１４０に沿っており、総コストは５である。総コストは、経路に沿って移動したときに通る各リンクのコストを合計することで計算される。第３経路には経路ＱＰＲＳＴが含まれ、総コストは１０である。
コストを各リンクに別々に割り当てることができる。効率化のため、コストの割り当てには体系だった方法が使用される。例えば、電子地図は通常、道路の種類（または分類）についての比較的小さな集合および曲がりの種類についての比較的小さな集合を使用する。このシステムは、各種道路および各種方向転換に対して、単位長さ当りのコストを割り当てる。次いで、リンクの長さ（例えば距離）を発見し、この長さに道路の種別に対応する単位長さ当りのコストを乗じ、リンクに沿った曲がりのコストを加えることでリンクのコストが計算される。コストには、追加コスト（例えば通行料）もしくはコストの割り引（例えば風景の価値）も含まれることがある。実施される方法にもよるが、コストの計算および割り当ては、データファイルの構築時に行われる。或いは、動作時にコストが決定される。
【００１１】
通常の経路発見システムはコストを整数もしくは実数として表す。しかしながら、本発明は複数のコストレベルを使用する。複数レベルのコストの使用は、コストは「非標準演算（nonstandard arithmetic）」と呼ばれる概念により数学的に正当化される。
経路発見計算において使用される通常（または標準）の演算は、整数の集合Ｚを使用する（または実数の集合Ｒ）（この型の注釈の繰り返しを避けるため、整数についてのみを述べる。しかし、実数についての解釈もまた正しい。）。「非標準演算」とは、*Ｚと呼ばれるより大きな数の集合、即ち「非標準整数（nonstandard integers）」についての演算である。非標準整数の集合は以下のような性質を有する。（１）*Ｚには標準整数が含まれる（Ｚ⊂*Ｚ）。（２）*Ｚには「無限整数（infinite integers）」が含まれる。つまり*Ｚには、Ｚの任意の要素ｎに対してｚ＞ｎとなるような複数の要素ｚが含まれる。（３）*Ｚは、数学者の間で環（ring）と呼ばれる構造を成している。つまり、*Ｚにおいては、加算、減算および乗算の通常の特性が全て適用できる。（４）整数の集合Ｚは*Ｚの「部分環（subring）」である。つまり、Ｚにおける整数の加算、減算および乗算の結果は、*Ｚにおけるそれと同一である。
表記を容易にするため、特定の無限整数をωで表す。ωは、*Ｚの一要素であり、Ｚのいかなる要素ｎよりも大きい。
本発明は非標準コストをａnωｎ＋ａｎ−１ωｎ−１＋...＋ａ１ω＋ａ0として表す。二つの非標準整数の加算は以下のように行われる。
【００１２】
【表１】
【００１３】
同様に、非標準整数ａ１ω＋ａ0に整数ｘを乗算した結果はｘａ１ω＋ｘａ0に等しい。非標準演算の下では、二つのコストＡ=ａnωｎ＋ａｎ−１ωｎ−１＋...＋ａ１ω＋ａ0およびＢ=ｂnωｎ＋ｂｎ−１ωｎ−１＋...＋b1ω＋b0を、ａj≠ｂjとなるような最大のｊを発見することにより比較する。そのようなｊがあり、ａｊ＞ｂｊである場合、Ａ＞Ｂである。ａｊ＜ｂｊである場合、Ａ＜Ｂである。ａj≠ｂjとなるようなｊが無い場合、Ａ＝Ｂである。
一実施例においては、ある固定の最大値までのωのべき乗がコストとして使用される。例えば、全てのコストにはωおよびω２のみが使用される。他のコストモデルには、より高次の、ωのべき乗が使用される。ωのべき乗の最大数値を固定して使用することにより、非標準値はコンピュータで整数の配列として表される。使用するωの最大値がωｎである場合、コストは（ｎ＋１）個の整数の配列（array）で表すことができる。配列［ａ［ｎ］，ａ［ｎ−１］，...，ａ［１］，ａ［０］］が値ａ［ｎ］ωｎ＋ａ［ｎ−１］ωｎ−１＋...＋ａ［１］ω＋ａ［０］］を表すようにすると、コンピュータでの使用が容易になる。当然のことながら、非標準数字を表す方式は他にも存在する。
このような非標準コストの表現による二つのコストは、対応する要素およびこれらの各配列を加えることによって加算される。即ち、二つのコストが［ａ［ｎ］，ａ［ｎ−１］，...，ａ［１］，ａ［０］］および［ｂ［ｎ］，ｂ［ｎ−１］１，...，ｂ［１］，ｂ［０］］で表される場合、合計は配列［ａ［ｎ］＋ｂ［ｎ］，ａ［ｎ−１］＋ｂ［ｎ−１］，...，ａ［１］＋ｂ［１］，ａ［０］＋ｂ［０］］で表される。同様に、二つの非標準コストの表現を比較するには、ｎ番目の要素から０番目の要素に向かって、差異を発見するまで連続的に配列値が比較される。対応する二つの値の中で異なるものが無い場合、二つのコストは等しい。例えば、上述の二つの配列において、最初に、ａ［ｎ］がｂ［ｎ］と比較される。二つの値が異なる場合、より大きな値を有する配列が、より大きなコストになる。二つの値が等しい場合、続いてａ［ｎ−１］とｂ［ｎ−１］とが比較される。配列Ｂがａ［ｎ］に対応する値を有さない場合、即ち、ｂ［ｎ］は存在しない、もしくはｂ［ｎ］＝０である場合、配列Ａがより大きなコストになる。配列で表現された非標準整数を標準整数ｘで乗算する場合、乗算結果は配列［ｘａ［ｎ］，ｘａ［ｎ−１］，...，ｘａ［１］，ｘａ［０］］で表される。
上記の原則を使用すると、経路発見手順のためのコストは複数の表現のレベルを有し、表現の各レベルは配列内の異なる要素となる。配列［ａ［ｎ］，ａ［ｎ−１］，...，ａ［１］，ａ［０］］において、表現の第１レベルはａ［０］であり、表現の第２レベルはａ［１］であり、表現の第３レベルはａ［２］であり、．．．表現の第（ｎ＋１）レベルはａ［ｎ］である。配列内のそれぞれの値は、コストの表現のレベルの大きさに対応する。即ち、配列要素ａ［ｎ］は表現の（ｎ＋１）番目のレベルの大きさである。より上位の表現のレベルは、より下位の表現のレベルよりも優先される。例えば、表現の第２レベルに０でない最大の大きさを有するコストは、表現の第１レベルに０でないの最大の大きさを有するコストよりも常に大きい。数学的に見ると、集合Ｚのメンバであり、０でない、全てのａおよびｂに対して、ａωｎ＞ｂωｎ−１となる。
【００１４】
図３のネットワークが電子地図であり、各リンクが電子地図内の道路を表すと仮定する。道路は種々の道路に分類されている。例えば、路地、住宅道路、幹線道路、高速道路、有料道路、およびフェリーなどに分類されている。ユーザが本当に必要な時以外は有料道路を回避したい場合、ユーザは、有料道路以外の全ての道路タイプが、表現の第１レベルに０以外の大きさを有し、他の全てのレベルに０の大きさを有するコストを含むようにコストモデルを作成できる。この場合、有料道路の表現の第２レベルは０以外の大きさを有するようにする。例えば、コストが運転時間であり、特定の有料道路（リンク）の線分が５運転時間単位の運転時間を有する場合、コストは５ω＋０もしくは配列［５，０］で表される。ユーザが有料道路を回避するよりも更にフェリーを回避したい場合、コストモデルには、フェリーのコスト（フェリーによる横断時間を１０とする）を１０ω２＋０ω＋０もしくは［１０，０，０］で表したコストが含まれる。
図３において、リンク１３２および１３４は有料道路を表し、ユーザが有料道路を回避したいと望んでいると仮定する。コストモデルは、二つの表現レベルを用いて設定される。リンク１３２のコストは［１，０］となり、リンク１３４のコストは［２，０］となる。経路ＱＴのコストは［２，０］となり、経路ＱＲＳＴのコストは［１，４］であり、経路ＱＰＲＳＴのコストは［０，１０］である。この例において、最小コストを有する経路はＱＰＲＳＴである。ＱＰＲＳＴの総コストが最小であるため、この経路が最も効率的な経路であると定義される。
２番目の例では、ユーザが有料道路を回避したいと望み、また、有料道路を回避するよりも更にフェリーを回避したいと望むと仮定する。リンク１３４が有料道路を表し、リンク１３２がフェリーを表すと仮定する。コストモデルは三つの表現レベルにより設定される。リンク１３４のコストは［０，２，０］として表される。リンク１３２のコストは［１，０，０］として表される。経路ＱＴに沿った移動のコストは［０，２，０］に等しく、ＱＲＳＴに沿った移動のコストは［１，０，４］である。即ち、経路ＱＲＳＴには横断リンク１３２、１３８および１４０が含まれる。これらのリンクのコストの合計は、［１，０，０］＋［０，０，２］＋［０，０，２］＝［１，０，４］である。経路ＱＰＲＳＴに沿った移動のコストは［０，０，１０］である。最短の経路は再びＱＰＲＳＴとなる。
３番目の例においては、ユーザが有料道路の使用を避けたいと望み、リンク１３０、１３２および１３４は全て有料道路であると仮定する。コストモデルは二つの表現のレベルで設定される。経路ＱＴに沿った移動のコストは［２，０］である。経路ＱＲＳＴに沿った移動のコストは［１，４］である。経路ＱＰＲＳＴに沿った移動のコストは［４，６］に等しい。この場合、全ての経路には有料道路上の移動が含まれるため、有料道路の使用を最小限に抑えることが目標となる。この目標は三つのコストの全てを比較することで達成される。上述のように、三つのコストを比較するためには、まず始めに最も高次のωのべき乗もしくは配列内で最大の指数（index）を有する要素に注目する。本事例において、経路ＱＲＳＴのコストの表現の第２レベルが１であるため、この経路のコストが最小である。経路ＱＴについてのコストの表現の第２レベルの大きさは２であり、経路ＱＰＲＳＴについてのコストの表現の第２レベルの大きさは４である。
複数のコストレベルを使用することにより２次的な最小化を実行できる。例えば、一つのリンクが実際には他の多くのリンクの集合を表すことにより図を簡略化できる場合がある。この集合リンクを作成する場合、コストの合計を表現の第２レベルとして記憶できる。表現の第１レベルは集合における多数のリンクの合計を保持するのに使用される。従って、コストが２である二つのリンクを足し合わせた場合、この集合の合計結果は４ω＋２即ち［４，２］となる。４ωは二つのコストの合計を表す。＋２は足し合わせたリンクの個数を表す。このタイプのコストモデルを使用すると、経路発見システムは、計算された経路におけるリンクの総数を最小にすることにより、同一コストを有する複数の経路間のコストを最小化することができる。他の方法では、リンクの個数を実際のコストよりも上位の表現のレベルに置くことで、コストを最小化する前にリンクの個数を最小化できる。
他の方法には、コストのノルム（norm）を使用することが含まれる。コストの値がＡ＝ａnωｎ＋ａｎ−１ωｎ−１＋...＋ａ１ω＋ａ0である場合、ノルムはａn＋ａｎ−１＋...＋ａ１＋ａ0と定義される。あるリンクのコストのノルムがこのリンクの運転時間（または他のタイプのコスト）の見積もりを提供するようにコストを設定できる。しかし、それ自身の大きさは必ずしも運転時間と同じである必要はない。その結果、コストを最小化するために他の要因を使用することが可能となる。例えば、任意の地理的領域がいずれも運転時間が１０である二つの高速道路リンクを有すると仮定する。片方の高速道路は景色が不快で、多くのくぼみがあり、もう一方の高速道路は滑らかな道路であり、美しい景色が見える。経路発見システムが良い方の高速道路の使用を促すことが望まれるだろう。両方のコストを［１０，０］と表すのではなく、良い方の高速道路を２ω＋８もしくは［２，８］として表し、不快な高速道路を７ω＋３もしくは［７，３］と表す。
【００１５】
図４は、複数のコストレベルを使用する経路発見の手順を記載するフローチャートを示す。ステップ１５０には、コストレベルが異なる要素を識別することが含まれる。これには一つ以上の、回避するべき要素（例えばリンクまたはノード等）の集合を特定することが含まれる。一実施例においては、経路発見システムのユーザは一つのコストレベルのみを含む標準の地図データベースを使用する。ユーザは起動時に、経路発見に先立って、どの要素が回避されるべきかを問われる。この問い合わせは自由に変更できユーザが任意の回避要素を選択できたり、特定のカテゴリの要素を回避するかどうかがユーザに問われるようにすることができる。カテゴリはネットワークデータベース固有の予め定義されたのカテゴリ（例えば、有料道路、幹線道路、住宅道路）もしくはユーザが定義した道路である。或いは、経路発見手順が回避するカテゴリを自動的に選択する。例えば、経路発見システムは、常に有料道路を回避するシステムとして販売されるであろう。或いは、異なるコストレベルを含むように地図データベースを作成し、これによって回避する要素を前もって選択するようにもできる。ステップ１５０には、一つのカテゴリの要素、または多くのカテゴリの要素を識別することを含むことができる。
【００１６】
他の実施例には、好ましいリンクのカテゴリを選別することが含まれる。即ち、解析を反転できる。表現の第２レベルを有するコストの方が表現の第１レベルを有するコストよりも少ないとみなされるであろう。或いは、全ての好まくないコストは表現の第２レベルを含み、好ましいコストは表現の第１レベルのみを含むであろう。
ステップ１５２において、システムは新たなコストレベルを作成する。コスト構造がまだ設定されていない場合、コスト構造を設定する必要がある。ステップ１５０において識別された各カテゴリについて、コスト情報が表現の第１レベルよりも上位の表現のレベルに０以外の大きさを含むようにデータを配列内に挿入する。例えば、ステップ１５０において、ユーザが、有料道路を唯一の回避すべきカテゴリとして識別した場合、ステップ１５２において、有料道路についてのコストは表現の第２レベルに０以外の大きさを有するように設定される。ユーザが、ステップ１５０において、有料道路とフェリーを異なるレベルの要素として、即ちフェリーを有料道路よりも回避するように識別した場合、ステップ１５２において、有料道路は表現の第２レベルに０以外の大きさを有するように設定され、フェリーは表現の第３レベルに０以外の大きさを有するように設定される。ステップ１５２には上述の配列を作成しこれを埋めることが含まれる。システムが、一つの表現レベルのみを有するコストを既に含んでいる既存の地図データベースにより実行されている場合、これらのコストの内のいくつかは表現の第２レベルに０以外の大きさを有する新たなコストと置き換えられる。一つの方法では、新たなコストを含む新規の地図データベースを作成できる。新規の地図データベースは処理装置で読取可能な記憶媒体内に記憶される。別の方法では、元の地図データベースは未編集のまま残り、新たなコストは追加のデータ構造に記憶される。ステップ１５２の後、システムはステップ１５４において経路発見探索を実行する。
【００１７】
図５は電子地図の一部分の有効グラフを表す。描かれた有効グラフには十個のノード（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｊ，Ｏ）およびこれらノード間の種々のリンクが含まれる。リンクは、それぞれそのリンクに隣接して数字が示されている。この数字は、リンクに沿った移動のコストを表す。
図４中のステップ１５４を更に詳細に説明するために図５を図６と共に使用する。例えば、ユーザが、図４のステップ１５０において、有料道路を唯一の回避すべきリンクのカテゴリとして識別したと仮定する。この例で、ノードＨからノードＤを接続するリンク（反対方向の二つのリンク）が有料道路の一部分であり、残りのリンクが有料道路ではないと仮定する。元の地図データベースには図５に示すコストが含まれていたとする。ステップ１５２において、有料道路のコスト構造は二つの表現のレベルを含むように変換される。ノードＨからノードＤまで移動するためのリンクのコストは、４ω＋０または［４，０］で表される。
【００１８】
図６は経路発見計算（経路発見探索とも呼ばれる）を説明するフローチャートである。図６の経路発見計算は、Edsger W. Dijkstra による方法に少なくとも部分的に基づいており本発明に使用可能な多くの経路発見方法の内の一つにすぎない。Dijkstraの方法を論じている参考文献として、M.N.S. SwamyとK. Thulasiramanらによる「Graphs, Networks, and Algorithms, John Wiley & Soas (1981)」が挙げられる。システムは、ステップ２０２において経路発見計算を初期化する。即ち、システムは、経路の始点および終点を記憶し、二つのキュー、即ち始点優先キュー（origin priority queue）および終点優先キューを（destination priority queue）セットアップする。始点優先キューは、始点からの経路がわかっているノードを整列したリスト、および各ノードについてのキーから成る。このキューはキーに従ってソートされる。キーの決定には種々の異なる方法がある。一方法では、キーは、始点からノードまでの移動についての既知の最低コストである。もう別の方法におけるキーは、始点からノードまでの既知の最短距離にノードから終点までの移動に要する見積もりコストを加えたものである。本方法に適した、ノードから終点までの移動に要するコストを見積る方法には種々のものがある。その一例は、「烏が飛ぶであろう」（"As-the-Crow-Flies"）直線距離に単位距離当たりの見積もりコストを乗ずる方法である。即ち、ノードおよびリンクを無視して、ノードと終点との間の物理的な距離を測定し、その距離に単位距離当たりの見積もりコストを乗ずるのである。
終点優先キューは、終点までの経路が分かっているノードを整列したリスト、および各ノードについてのキーから成る。このキューはキーに従ってソートされる。終点キーの決定には多くの方法がある。一方法は、ノードから終点までの既知の最低コストの経路を使用することである。もう別の方法におけるキーは、ノードから終点までの既知の最低コストに、始点からノードまでの見積もりコストを加えた合計を使用する。本発明の範囲内であれば、他の方法でキーを計算してもよい。
更に、システムは始点訪問済みリスト（origin visited list）および終点訪問済みリスト（destination visited list）をセットアップする。始点訪問済みリストは、始点からの経路が分かっている全てのノードのリスト、始点からそのノードまでの移動の最低コスト、およびコストが最低の経路に沿った直前のノードを保持する。終点訪問済みリストは終点までの経路が分かっている各ノードの名前、そのノードから終点までの移動の既知の最低コスト、およびコストが最低の経路に沿った次のノードの識別情報を記憶する。ステップ２０２による初期化が完了すると、始点優先キューおよび始点訪問済みリストには始点が含まれ、終点優先キューおよび終点訪問済みリストには終点が含まれる。
システムが初期化されると、システムは所定のルールに従いステップ２０４においてキューを選択する。本発明に適したキュー選択ルールには多くのものが存在する。あるシステムにおいては、最小のキーを有する要素を含んだキューが選択され要素間の結びつきは任意に断たれる。別のルールのシステムにおいては、キューに含まれる要素の数が最も少ないキューが選択される。キュー選択ルールのその他の例としては、キューを交互に切り換え、ある期間は始点キューを選択し、別の期間は終点キューに切換え、更に別の期間は始点キューに再び切換えることが挙げられる。キューはキーによってソートされるので、最小のキーを有するノードがキューの先頭（キューの前部またはキューのトップとも言う）に来る。このノードを「ヘッドノード」と呼ぶ。後述の例では、キューが選択される方法としてキューを切換える方法を使用し、始点優先キューから開始される。
システムは、ステップ２０６において、選択したキューのヘッドノードに隣接する全てのノードを探索する。システムは開始したばかりなので、始点優先キュー中に存在する唯一のノードは始点である。隣接ノードとは、始点から、他ノードのノードも通過せずに移動できるノードである。始点Ｏの隣接ノードは、ノードＡ、Ｂ、ＧおよびＨである。４個の隣接ノードがあるため、システムは任意に一つの隣接ノードを選択する。システムは、ステップ２０８において、選択した隣接ノードについて、より低いコストが訪問済みリストおよび優先キュー上に既に存在するかどうかを判断する。つまり、システムは隣接ノードとヘッドノードとの間の移動コストを判断する。この場合、選択された隣接ノードはノードＡであり、始点からノードＡまでの移動のコストは９である。経路発見計算は始まったばかりなので、ノードＡは訪問済みリストおよび始点優先キュー上になく、ノードＡについての他の既知のコストは存在しない。既知のコストが存在しないので、システムは、ステップ２１０において、訪問済みリストおよび優先キューにノードＡおよびそのコストを追加して編集する。その後、ステップ２０６へ戻り、検討されていない隣接ノードが他にないかどうかを判断する。この場合、三個の隣接ノードＢ、ＧおよびＨが未検討である。
システムはステップ２０８において、ノードＢについて、より低い既知のコストが無いかどうかを判断する。始点からＢまでの移動のコストは３であり、Ｂは優先キューおよび訪問済みリスト上に存在しない。ステップ２１０において、ノードＢを優先キューおよび訪問済みリストに追加する。システムはステップ２０６へ戻って、ノードＧについて検討する。始点ＯからＧへと直接行く場合のコスト、即ち７よりも低い既知のコストは存在しないため、Ｇを優先キューおよび訪問済みリストに加える。システムはステップ２０６へ戻って、ノードＨについて検討する。始点ＯからＨへと直接行く場合のコスト、即ち２よりも低い既知のコストは存在しないため、Ｈをビジターリスト内の優先キュー加える。システムはステップ２０６へ戻って、これ以上隣接するノードが無いことを判断する。従って、ステップ２１２において、ヘッドノード、即ちこの時点では始点Ｏ、を優先キューから取り除く。表２は、経路発見計算におけるこの時点での始点優先キューおよび訪問済みリストの内容を表す。始点優先キューにはＢ、Ｇ、Ａ、およびＨの４個のノードがある。これらのキーは始点からそのノードまでの移動のコストを表す。訪問済みリストはノード、コスト、およびＰｒｅｖの３つの欄を有する。ノード欄はノード識別情報を列記する。コスト欄は始点からそのノードまでの移動についての既知の最小コストを列記する。Ｐｒｅｖ欄は既知の最小コストを利用して経路に沿って移動した時の、始点からノードまでの経路に沿った直前のノードを列記する。訪問済みリストに列記されるノードの順番はリストの検索を容易にする任意の順番とすることができる。例えば、ノードをアルファベット順に列記できる。一実施例においては、ノードは数値コード名が付けられ、訪問済みリストはハッシュテーブルである。
【００１９】
【表２】
【００２０】
システムはステップ２１４において、停止条件が満たされたかどうかを判断する。本発明に適した停止条件には多くのものがある。例えば、あるノードが、始点優先キューおよび終点優先キューの何れにおいてもヘッドノードであるときに停止する。他の停止条件は、始点から始点優先キュー内のヘッドノードまでの移動のコストに終点キューのヘッドノードから終点までの移動のコストを加えたコストが最適コネクションノードの総コスト以上である場合に停止する。この停止条件が本実施例において使用する停止条件である。コネクションノードとは、終点訪問済みリストおよび始点訪問済みリストに現れるノードである。コネクションノードの総コストとは、始点からコネクションノードまでのコストにコネクションノードから終点までのコストを加えたコストである。最適コネクションノードとは、最小の総コストを有するコネクションノードである。本事例においてコネクションノードは存在せず、停止条件は満たされておらず、システムはステップ２０４においてキューを選択する。
【００２１】
上述のように、本実施例における、優先キューを選択する方法は単純な切換え方式であるため、システムは終点キューを選択する。システムはステップ２０６において、終点Ｄに隣接するノードがあるかどうかを判断する。本実施例において、三個の隣接ノードＣ、Ｆ、およびＨがある。システムはステップ２０８において、ノードＣに着目し、より低い既知のコストがあるかどうかを判断する。そのようなコストは存在しないので、ステップ２１０において、終点優先キューおよび訪問済みリストにノードＣおよびそのコストを追加して編集する。その後、ステップ２０６へ戻って、もう一つの隣接ノード、即ちノードＦがあることを判断する。システムはステップ２０８において、Ｆについて、より低い既知のコストが無いことを判断する。ステップ２１０において、優先キューおよび訪問済みリストにノードＦを追加して編集する。その後、ステップ２０６へ戻り、もう一つの隣接ノード、即ちノードＨがあることを判断する。システムはステップ２０８において、ＨからＤの移動について、より低い既知のコストが無いことを判断する。ステップ２１０において、終点優先キューおよび終点訪問済みリストにノードＨおよびＨからＤまでの移動のコスト、即ち４ωもしくは［４，０］を追加して編集する。システムはステップ２０６において、ノードＤに隣接するノードがこれ以上無いことを判断し、ステップ２１２において、ノードＤを終点優先キューから取り除く。表３は、この時点での終点優先キューおよび訪問済みリストの状態を表す。
【００２２】
【表３】
【００２３】
システムはステップ２１４において、停止条件が満たされたかどうかを判断する。この時点では、コネクションノードが存在する。ノードＨが両方の訪問済みリスト上に存在する。ノードＨについての総コストは［４，２］もしくは４ω＋２である。つまり、始点からノードＨまでの移動のコストは［０，２］であり、ノードＨから終点までの移動のコストは［４，０］である。始点から始点優先キューにおけるヘッドノード（Ｈ）までの移動のコストは［０，２］であり、また、終点優先キューにおけるヘッドノード（Ｆ）から終点までの移動のコストは［０，２］であるため、停止条件は満たされない。この二つのコストの合計は［０，４］であり、コネクションノードＨの総コストよりも低いため、停止条件は満たされず、システムはステップ２０４において、始点優先キューを選択する。
始点優先キュー上のヘッドノードはノードＨである。ノードＤがノードＨに隣接する唯一のノードである。システムはステップ２０８において、ノードＤについて、より低い既知のコストが無いことを判断する。従って、ステップ２１０において、訪問済みリストおよび優先キューにノードＨからノードＤまでの移動のコスト、即ち［４，０］を含むように編集する。表４は、ノード４を優先キューから取り除いた（ステップ２１２）後の、始点優先キューおよび始点訪問済みリストの現在の状態を表す。
【００２４】
【表４】
【００２５】
システムはステップ２１４において、停止条件が満たされたかどうかを判断する。この時点では、２つのコネクションノード、ノードＨおよびノードＤが存在する。ノードＨの総コストは［４，２］である。ノードＤの総コストも［４，２］である。始点から始点優先キューのヘッドノードまでの移動のコストおよび終点キューのヘッドノードから終点までの移動のコストの合計は［０，７］に等しく、ノードＨおよびノードＤについてのコストの合計よりも少ないため、停止条件は満たされない。
システムはステップ２０６において、終点キュー上のヘッドノードに隣接するノードを探索する。ヘッドノードはノードＦなので、ノードＥが唯一の隣接ノードとなる。ノードＤはＦへ到達するために使用されるノードであるため、隣接ノードとして処理されない。ＥからＦまでの移動のコストは［０，２］であるため、ＥからＦを経由してＤに至る移動のコストは［０，４］である。システムはステップ２０８において、ＥからＤまでの移動について、より低い既知のコストが無いことを判断し、それに従って、訪問済みリストおよび優先キューを更新する。システムはステップ２０６において、他に隣接ノードが無いことを判断し、ステップ２１２においてＦを優先キューから取り除く。表５は、本方法におけるこの時点での終点優先キューおよび訪問済みリストの状態を表す。
【００２６】
【表５】
【００２７】
ステップ２１４において、システムは停止条件が満たされたかどうかを判断する。この時点でもやはり、二つのコネクションノードＨおよびＤが存在する。始点から始点優先キュー内のヘッドノード（Ｂ）までの移動のコストは［０，３］で、終点優先キュー内のヘッドノード（Ｃ）から終点までの移動のコストは［０，５］であるため、停止条件は満たされない。二つのコストの合計は［０，８］であり、コネクションノードＨもしくはＤについての総コストよりも低い。
表４より、始点優先キュー上のヘッドノードはノードＢであることがわかる。ノードＢに隣接するノードはノードＡおよびノードＥである。ステップ２０８においてノードＡを検討し、ノードＡについて、より低い既知のコストは存在しないことを判断する。ノードＡはコストが［０，９］であるとして訪問済みリストに現れないが、ノードＢを経由した始点からノードＡまでの移動のコストは「０，６］である。つまり、ＯからＢまでの移動のコストは［０，３］であり、ＢからＡまでの移動のコストは［０，３］である。即ち、ＯからＢを経由してＡに至る移動のコストは［６，０］であり、Ｏから直接Ａに移動した場合のコストよりも低い。従って、ステップ２１０において、始点からノードＡまでの移動のコスト、即ち［０，６］を訪問済みリストおよび優先キューに含めるように編集し、ノードＡについての、訪問済みリストにおける直前ノードがＢとなる。つまり、ＯからＡにコスト［０，６］で着くためには、ノードＢを通って移動しなくてはならない。システムはステップ２０６において、もう一つの隣接ノードであるＥがあることを判断する。システムはステップ２０８において、Ｅについて、より低いコストが無いことを判断し、優先キューおよび訪問済みリストにＥを含めるように編集する。表６は、ノードＢを優先キューから取り除いた（ステップ２１２）後の始点優先キューおよびビジターリストの状態を表す。
【００２８】
【表６】
【００２９】
システムはステップ２１４において停止条件が満たされたかどうかを判断する。この時点では３つのコネクションノードＥ、Ｈ、Ｄが存在する。コネクションノードＥの総コストは［０，９］であり、コネクションノードＨの総コストは［４，２］であり、コネクションノードＤの総コストは［４，２］である。ノードＥが全てのコネクションノードの中でコストが最も低いので、ノードＥが最適なコネクションノードをみなされる。起点から起点優先キュー上のヘッドノードまでの移動のコストは［０，６］である。終点優先キュー上のヘッドノードから終点までの移動のコストは［０，５］である。従って、ヘッドノードまでおよびヘッドノードからの移動のコストは［０，１１］であり、最適なコネクションノードの総コストである［０、９］よりも大きい。その結果、停止条件が満たされ、システムはステップ２１６において、経路を構築する。
【００３０】
経路を構築するステップは以下の通りである。ルールに従いあるコネクションノードを選択する。その様なルールの一つは、最適なコネクションノードを選択することである。始点訪問済みリストにおいて、選択されたコネクションノードＫを探索し、始点からの経路上の直前のノードＰ１を発見する。Ｐ１が始点でなければ、訪問済みリストにおいてＰ１を探索し、始点からの経路上の直前のノードＰ２を発見する。始点に着くまでこの探索を繰り返す。始点に着いたと仮定し、この始点をノードＰLとする。同様に、終点訪問済みリストにおいてＫを探索し、終点までの経路上の次ノードＮ１を発見する。Ｎ１が終点でなければ、訪問済みリストにおいてＮ１を探索する。終点に着くまでこの探索を繰り返す。終点に着いたと仮定し、この終点をノードＮMとする。この時点で始点から終点までの経路がわかる。その経路とは、ＰL（始点）からＰL-1へ、ＰL-2へ、・・・、Ｐ2へ、Ｐ1へ、Ｋへ、Ｎ１へ、・・・ＮM-1へ、ＮM（終点）への経路である。
本実施例において、Ｅは最適なコネクションノードである。表６における訪問済みリストを参照し、始点からノードＥまでの移動についての最適な既知のコストにはノードＢからノードＥまでの移動が含まれることを判断する。従って、構築される経路ではＢからＥへの移動が行われる。システムは、訪問済みリストにおいてノードＢを発見し、ノードＢまでの最適な経路は始点Ｏからの直接の経路であることを判断する。この時点で、構築された経路はＯからＢを経由してＥに至る移動を含む。システムは始点に着くと、コネクションノードから終点までの経路を作る。表５における訪問済みリストを参照し、Ｅから終点までの最適な経路にはＥからＦまでの移動が含まれることを判断する。また、訪問済みリストは、ＦからＤまでの最適な経路がＦからＤまで直接移動する経路であることを表す。従って、ＯＢＥＦＤの経路が構築される。この様に、経路発見計算はＨからＤへのリンクにより表される有料道路の使用を回避する。
いくつかのシステムにおいては、ヘッドノードが接続されている全てのノードを検討しないことで経路発見計算を速める。探索を特定の近隣のノードに限定する。このような方法の一つは、ノードを、それが存在する道路の重要度に従って分類し、始点から（または終点まで）の距離が増すにつれて近隣のノードを使用することを累進的に制限する。例えば、使用されるコスト測定値が見積もり運転時間である場合、始点もしくは終点から車で２分以上かかる住宅道路、および始点もしくは終点から車で１０分以上かかる幹線道路等は、探索に使用されないだろう。
【００３１】
本発明の一実施例においては、電子マップは分離したデータベースとして記憶され、経路発見装置には二つの主モジュールを有するソフトウェアが含まれる。第１モジュールは図４のステップ１５０および１５２を実行する。第２モジュールは経路発見機能を実行する。第１モジュールは、コストを記憶するために何個の表現のレベルを使用するかを表すコストモデルおよびコストの決定のためのインデックス（または定義）をセットアップする。インデックスには、各幹線道路に関してのコストはＸにリンクの単位距離を乗じたものに等しく、各住宅道路に関してのコストはＹにリンクの単位距離を乗じたもの等しい等のような情報が含まれる。コストモデルは経路発見機能に受け渡される。
他の実施例においては、本発明を、電子地図を使用する動的交通回避システムの一部分として使用できる。運転者が、ある特定の道路もしくは道路の集合に交通上の問題が発生していることを知ったとする。図４のステップ１５０において、運転者はシステムを使用して交通問題が発生している道路を特定する。交通問題が発生している道路のコストは、表現の第２レベルに０以外の大きさを有する（例えば、ａ１ω＋ａ0ただし、ａ１≠０）。ステップ１５４において、運転者を、交通問題が発生している道路を回避させて終点へ向かわせる経路が計算される。
本発明を記載するために既に使用した例は、道路から成る電子地図のためのものであるが、本発明を適切な、処理装置で読取可能に表現したネットワークにも適用できる。適切なネットワークには、製造工程のグラフ、共同一貫移動プラン（intermodal travel plan）（例えば、飛行機、電車、車、バス等を使用した地点間の移動を表すグラフ）、医学療法を提供するシステム等が含まれる。例えば、ネットワークが製造工程を表す場合、ノードは工程中の決定点を表すことができ（例えば、製造品をどのステーションへ移送するか、もしくはどの半導体プロセスを使用するかなど）、リンクは処理時間もしくは製造コストを表すことができる。
【００３２】
以上の本発明の詳細な説明は、例示および説明を目的として提供するものである。本発明を完全に表したものではなく、また、開示された通りのものに限定されるものではない。また、上記の教示に鑑みて、多くの変形および変更を施すことが可能である。記載した実施例は、本発明の原理および実際的なアプリケーションを最もよく説明し、これにより、当業者が種々の実施形態でかつ予想される特定の使用に適した種々の変形を加えて本発明を最適に利用できるようにするために選択したものである。本発明の範囲は添付のクレームによって定義されるものである。
【００３３】
なお、本発明の特徴点を下記列挙する。
１．処理装置で読取可能に表現したネットワークを使用して経路を発見する、コンピュータによって実施される方法であって、
前記ネットワークにおける一つ以上の要素の第１集合を識別するステップと、
前記要素の第１集合の第１要素に関連する第１コストを作成するステップであって、前記第１コストは少なくとも二つの表現のレベルについて０以外の大きさを含むステップと、
処理装置によって、前記第１コストを使用して経路発見探索を実行するステップと、
を含む方法。
２．上記１に記載の方法であって、前記要素の第１集合がリンクの集合である方法。
３．上記１に記載の方法であって、前記処理装置で読取可能に表現したネットワークが電子地図であり、前記要素の第１集合が複数の有料道路を表すリンクの集合である方法。
４．上記１に記載の方法であって、前記処理装置で読取可能に表現したネットワークが電子地図であり、前記要素の第１集合が一つの有料道路を表すリンクである方法。
５．上記１に記載の方法であって、前記識別するステップが、ユーザからの入力を受け取ることを含み、前記入力に基づき前記第１集合の要素を特定することを含む方法。
６．上記１に記載の方法であって、前記識別するステップが、ユーザの入力なしに、前記入力に基づいて前記第１集合の要素を自動的に特定することを含む方法。
７．上記１に記載の方法であって、前記作成するステップが、既存のコストを前記第１コストと置き換えることを含み、前記既存のコストには一つの表現のレベルについてのみ０以外の大きさが含まれる方法。
８．上記１に記載の方法であって、更に、
前記第１要素に加えて、前記第１集合の前記要素に関連する追加コストを作成するステップであって、前記追加コストは少なくとも二つの表現のレベルについて０以外の大きさを含むステップ
を含む方法。
９．上記１に記載の方法であって、前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルが前記第１レベルよりも優先される方法。
１０．上記１に記載の方法であって、更に、
前記電子地図において回避する一つ以上の要素の第２集合を識別するステップと、
前記第２集合の第１要素に関連する第２コストを作成するステップであって、前記第２コストが少なくとも三つの表現のレベルが０以外の大きさを含むステップと、
前記第２コストを使用する前記実行するステップと、
を含む方法。
１１．上記１０に記載の方法であって、前記第２コストは、前記第１コストの大きさおよび前記第２コストの大きさに関わらず前記第１コストよりも大きい方法。
１２．上記１に記載の方法であって、前記第１コストは非標準型数字である方法。
１３．上記１に記載の方法であって、前記第１コストは無限整数の０以外の倍数で表すことができる方法。
１４．上記１に記載の方法であって、前記第１コストは複数要素のデータ構造内に記憶される方法。
１５．上記１に記載の方法であって、前記第１コストは配列として記憶される方法。
１６．上記１に記載の方法であって、更に、少なくとも二つの表現のレベルを含むコストモデルを作成するステップを含む方法。
１７．上記１に記載の方法であって、前記処理装置で読取可能に表現したネットワークは電子地図である方法。
１８．上記１７に記載の方法であって、前記経路発見探索を実行するステップがDijkstraによる方法を使用することを含む方法。
１９．上記１７に記載の方法であって、前記実行するステップは、コストの最小化を試みる方法。
２０．上記１７に記載の方法であって、前記経路発見を実行するステップは、
優先キューおよび訪問済みリストをセットアップするステップであって、前記優先キューがノードの識別記号およびキーを記憶し、前記訪問済みリストがノード識別記号および始点からの移動のコストを記憶するステップと、
前記優先キューを初期化するステップと、
前記始点に隣接するノードの集合を発見するステップと、
前記始点から前記隣接ノードの各々までの移動のコストを決定するステップと、
前記隣接ノードをキーでソートされた前記優先キューに挿入するステップと、
前記ノードを前記訪問済みリストに挿入するステップと、
前記優先キューから前記始点を取り除くステップと、
前記キューの先頭のノードに隣接するノードの集合を発見するステップと、
前記キューの先頭のノードに隣接する前記ノードの各々への移動のコストを決定するステップと、
少なくとも前記キューの先頭のノードに隣接する前記ノードの部分集合を前記優先キューに挿入するステップと、
前記優先キューの先頭のノードに隣接する前記ノードが、より低いコストを有して前記訪問済みリスト中にまだ存在しない場合に、前記ノードを前記訪問済みリストに挿入するステップと
前記優先キューから前記キューの先頭のノードを取り除くステップと、
を含む方法。
２１．上記１７に記載の方法であって、
前記電子地図がリンクおよびノードを含み、前記要素の第１集合がリンクの集合であり、前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルより優先され、前記第２レベルは無限整数の０以外でのべき乗の倍数である方法。
２２．上記１に記載の方法であって、
前記第１要素がリンクの集合を表し、前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第１レベルが前記集合における前記リンクの数を表している方法。
２３．上記１に記載の方法であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第１レベルの大きさおよび前記第２レベルの大きさの合計が、最小化される見積もり量である方法。
２４．処理装置で読取可能に表現したネットワークを使用する、コンピュータによって実施される方法であって、
処理装置を使用して始点から終点までの経路発見を実行するステップを含み、前記経路発見を実行するステップは、
第１ノードから第２ノードまでの第１経路を発見するステップであって、前記第１経路が一つ以上のリンクの第１集合および一つ以上のコストの第１集合を含むステップと、
第１ノードから第２ノードまでの第２経路を発見するステップであって、前記第２経路が一つ以上のリンクの第２集合および一つ以上のコストの第２集合を含み、少なくとも前記コストの第２集合の内の一つが少なくとも二つの表現のレベルを含むステップと、
一つ以上のコストの第１集合が一つ以上のコストの第２集合よりも効率的である理由から前記第１経路を選択するステップと
を含む方法。
２５．上記２４に記載の方法であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される方法。
２６．上記２５に記載の方法であって、
前記処理装置で読取可能に表現したネットワークが電子地図である方法。
２７．上記２６に記載の方法であって、
前記第２経路は有料道路を含み、前記第１経路は有料道路を含まず、前記コストの第２集合の内の一つが第２レベルについて０以外の大きさを有し、前記有料道路と関連付けられている方法。
２８．上記２６に記載の方法であって、
前記選択するステップが、前記第２レベルについて０以外の大きさを有するコストと前記第１レベルについて０以外の大きさを有するコストとを比較すること含む方法。
２９．上記２６に記載の方法であって、
前記コストの第２集合の内の少なくとも一つが三つの表現のレベルを有する方法。
３０．上記２９に記載の方法であって、
前記三つの表現のレベルが第１レベル、第２レベル、および第３レベルを含み、前記表現の第３レベルが前記第２レベルよりも優先される方法。
３１．上記２６に記載の方法であって、
前記選択するステップが前記コストの第１集合の合計と前記コストの第２集合の合計を比較することを含む方法。
３２．上記２６に記載の方法において、
前記比較するステップが無限数字の一乗の大きさの比較および無限数字の二乗の大きさの比較を含む方法。
３３．上記２６に記載の方法であって、
前記第１経路が前記始点と前記終点との間の最終経路の一部分である方法。
３４．電子地図を作成する方法であって、
ノードを特定するステップと、
ノード間のリンクを特定するステップと、
前記リンクを移動するためのコストを特定するステップであって、前記コストの内の少なくとも一つが表現の第１レベルおよび表現の第２レベルを含み、前記表現の第２レベルは前記表現の第１レベルよりも優先されるステップと、
前記ノード、前記リンク、および前記コストを表すデータを地図データベース内に記憶するステップであって、前記地図データベースは処理装置で読取可能な記憶装置内にあるステップと、
を含む方法。
３５．上記３４に記載の方法であって、
前記記憶するステップが、前記コストを配列で表すデータを記憶することを含む方法。
３６．上記３４に記載の方法であって、前記第２レベルが無限整数の０以外でのべき乗の倍数を含んでいる方法。
３７．電子地図が組み込まれている、処理装置で読取可能な記憶媒体であって、
前記電子地図は上記３４の方法に従って作成され、前記電子地図は、表現の第１レベルおよび表現の第２レベルが含まれる前記コストの内の少なくとも一つを記憶し、前記表現の第２レベルは前記表現の第１レベルよりも優先される方法。
３８．電子地図データベースの機能を高める方法であって、
前記地図データベースはノード、ノード間のリンク、およびリンクのコストを含み、
前記リンクを分類するステップと、
少なくとも一つのリンクの分類についてのコストの第２レベルを作成するステップと、
前記コストの第２レベルを処理装置で読取可能な記憶媒体に記憶するステップと、
を含む方法。
３９．上記３８に記載の方法であって、
前記記憶するステップが、前記コストの第２レベルを配列で表すデータを記憶することを含む方法。
４０．上記３８に記載の方法であって、前記分類するステップが、どのリンクが有料道路であってどのリンクが非有料道路であるかを特定することを含む方法。
４１．上記３８に記載の方法であって、前記作成するステップが、既存のコストを新しいコストと置き換えることを含み、前記新しいコストは前記既存のコストおよび無限数字の積である方法。
４２．機能の高められた電子地図が組み込まれている、処理装置で読取可能な記憶媒体であって、前記前記機能の高められた電子地図は、ノード、ノード間を接続するリンク、およびリンクのためのコストを含み、前記電子地図は、上記３８の方法によって機能が高められる方法。
４３．処理装置で読取可能に表現したネットワークを使用する、経路を発見するための装置であって、
第１ノードから第２ノードまでの第１経路を発見する手段であって、第１経路が一つ以上のリンクの第１集合および一つ以上のコストの第１集合を含む手段と、
第１ノードから第２ノードまでの第２経路を発見する手段であって、第２経路が一つ以上のリンクの第２集合および一つ以上のコストの第２集合を含み、少なくとも前記コストの第２集合の内の一つが少なくとも二つの表現のレベルを含む手段と、
前記一つ以上のコストの第１集合が前記一つ以上のコストの第２集合よりも効率的であるとの理由に基づき前記第１経路を選択する手段と、
を含む装置。
４４．上記４３に記載の装置であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される装置。
４５．上記４３に記載の装置であって、
前記処理装置で読取可能に表現したネットワークは電子地図である方法。
４６．処理装置で読取可能なプログラムコードが組み込まれている、処理装置で読取可能な記憶媒体であって、前記処理装置で読取可能なプログラムコードは、処理装置で読取可能に表現したネットワークを使用して経路を発見するためのものであり、
第１ノードから第２ノードまでの経路を発見する第１プログラムコードであって、前記第１経路が一つ以上のリンクの第１集合および一つ以上のコストの第１集合を含んでいる第１プログラムコードと、
第１ノードから第２ノードまでの第２経路を発見する第２プログラムコードであって、前記第２経路が一つ以上のリンクの第２集合および一つ以上のコストの第２集合を含み、前記コストの第２集合の内の一つが少なくとも二つの表現のレベルを有している第２プログラムコードと、
前記一つ以上のコストの第１集合が前記一つ以上のコストの第２集合よりも効率的であるとの理由に基づき、前記第１経路を選択する第３プログラムコードと、
を含む処理装置で読取可能な記憶媒体。
４７．上記４６に記載の処理装置で読取可能な記憶媒体であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される処理装置で読取可能な記憶媒体。
４８． 上記４７に記載の処理装置で読取可能な記憶媒体であって、
前記処理装置で読取可能に表現したネットワークが電子地図である処理装置で読取可能な記憶媒体。
４９．上記４８に記載の処理装置で読取可能な記憶媒体であって、
前記第３プログラムコードは前記コストの第１集合の第１合計および前記コストの第２集合の第２合計を決定し、前記第３プログラムコードは前記第１合計が前記第２合計よりも少ないことを判断する、処理装置で読取可能な記憶媒体。
５０．上記４９に記載の処理装置で読取可能な記憶媒体であって、前記第１合計および前記第２合計はコンピュータ記憶装置に配列として記憶される、処理装置で読取可能な記憶媒体。
５１．上記４７に記載の処理装置で読取可能な記憶媒体であって、更に、
前記ネットワークのためのコストモデルを作成する第４プログラムコードを含む、処理装置で読取可能な記憶媒体。
５２．上記４７に記載の処理装置で読取可能な記憶媒体であって、前記第３プログラムコードは、動的交通状況に少なくとも部分的に基づいて前記第１経路を選択する処理装置で読取可能な記憶媒体。
５３．処理装置で読取可能なプログラムコードが組み込まれている、処理装置で読取可能な記憶媒体であって、前記処理装置で読取可能なプログラムコードは、処理装置で読取可能に表現したネットワークを使用して経路を発見し、前記処理装置で読取可能なプログラムコードは、
前記ネットワークにおける一つ以上の要素の第１集合を識別するのに使用される第１プログラムコードと、
前記要素の第１集合の第１要素に関連する第１コストを作成する第２プログラムコードであって、前記第１コストが少なくとも二つの表現のレベルを有している、第２プログラムコードと、
前記第１コストを使用して、経路発見探索を実行する第３プログラムコードと、
を含む処理装置で読取可能な記憶媒体。
５４．上記５３に記載の処理装置で読取可能な記憶媒体であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される処理装置で読取可能な記憶媒体。
５５．上記５４に記載の処理装置で読取可能な記憶媒体であって、
前記処理装置で読取可能に表現したネットワークが電子地図である処理装置で読取可能な記憶媒体。
５６．上記５４に記載の処理装置で読取可能な記憶媒体であって、
前記第１プログラムコードは交通問題を特定するのに使用され、前記第３プログラムコードは前記交通問題を回避する経路を発見する、処理装置で読取可能な記憶媒体。
５７．処理装置で読取可能に表現したネットワークを使用して経路を発見するための装置であって、
入力装置と、
処理装置で読取可能に表現したネットワークの少なくとも一部分を記憶することができる処理装置で読取可能な記憶装置と、
表示装置と、
入力装置、記憶装置、および表示装置と通じている処理装置と、
を含み、前記処理装置は、
ネットワークにおける一つ以上の要素の第１集合を識別し、
前記要素の第１集合の第１要素に関連するコストを作成し、前記第１コストが少なくとも二つの表現のレベルを含み、
前記第１コストを使用して経路発見探索を実行するようにプログラムされている装置。
５８．上記５７に記載の装置であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される装置。
５９．上記５７に記載の装置であって、
前記処理装置で読取可能に表現したネットワークが電子地図である装置。
【図面の簡単な説明】
【００３４】
【図１】図１は、本発明の実施に使用可能なハードウェアアーキテクチャの一例を示すブロック図である。
【図２Ａ】図２Ａは、電子地図の一部分を表す有向グラフ（directed graph）の一番目の例である。
【図２Ｂ】図２Ｂは、電子地図の一部分を表す有向グラフの二番目の例である。
【図３】図３は、ネットワークの一部分を表す有向グラフの三番目の例である。
【図４】図４は、複数のコストレベルを使用して経路を発見する手順を記載したフローチャートである。
【図５】図５は、ネットワークの一部分を表す有向グラフの四番目の例である。
【図６】図６は、図４の経路発見ステップを記載したフローチャートである。
【符号の説明】
【００３５】
１２：ＣＰＵ、１６：キャッシュメモリ、１８：主メモリ、２０：システムコントロール、２４：ＲＯＭ、２６：周辺機器。
【技術分野】
【０００１】
本発明は経路発見計算に複数のコストレベルを使用するシステムに関する。
関連出願への相互参照
本出願は下記の出願に関連する。
１９９６年１１月２５日出願のリチャード・エフ・ポッペンによる米国特許出願「ネットワーク内の領域の出口および入口を決定する方法」（米国特許出願Ｎｏ．０８／７５６，２５８）。この関連出願を本出願の一部を構成するものとしてここに援用する。
【背景技術】
【０００２】
発明の背景
発明の分野
関連技術
コンピュータは、システムの高度な研究および利用を可能にするためにそのシステムをモデル化するというアイデアに変革をもたらした。その一例は、システムをネットワークとしてモデル化する事である。最も一般的な意味では、ネットワークは相互接続および分岐のための多くの経路を含むものであると定義されている。判断を必要とする多くのシステムはネットワークとしてモデル化できる。例えば、製造工程もしくは医学療法を提供するシステムは、決定点および決定点間のアクションから成るネットワークとしてモデル化できる。このネットワークを電子的な形で表し、処理装置が読取可能な記憶媒体に記憶することができ、これにより、このネットワークモデルを用いてシステムを研究または使用するためのソフトウェアの開発を可能にする。
電子的な形で記憶できる有益なネットワークの一例として電子地図がある。これは、地理学的に参照される、物理的、社会的、もしくは経済的なシステムを量的に表した電子データを含む。電子地図に含まれる情報の範囲には制限が無く、例えば、要素間の距離、移動時間、割り当て番号（lot number）、税金情報、ツーリスト情報、処理時間、待ち時間などを含むことが出きる。更に、地図をコンピュータ上にファイルとして記憶することで、無制限のアプリケーションソフトによるそのデータの操作を可能にする。
電子地図の一利点は、地図の種々の部分に関連するコストを記憶および決定できることである。コストとは最小化もしくは最大化できる変数である。コストは必ずしも金銭的なコストであるとは限らない。コストとは最小化または最大化しなければならない何かである。通常、コストは整数で表される。コストは実数で表されることもある。コストの例として、時間、距離、支払った料金、曲がり易さ、風景の質などがある。
電子地図は、他のネットワークと同様に、経路発見に使用できる。経路発見とは始点と終点との間のルートを計算する方法である。いくつかのシステムは推奨ルートを計算し、地図表示装置上に推奨ルートを強調表示することによって、もしくは曲がりがあるたびに指示を出すことによって、またはその両方によって運転者を誘導する。
経路発見システムは、ある規定の基準に従って最も望ましいルートを発見することによって終点までの推奨ルートを計算する。これらの基準は運転者によって規定されるか、製造時にデフォルトとして設定される。システムは、多くの場合、あるコスト、例えば運転時間を最小化（または最大化）する経路を発見するために使用される。経路発見システムの使用者にとって有用である一特徴として、電子地図の特定の要素を回避する機能が挙げられる。使用者は特定の種類の道路、曲がり、交差点などを回避したいことがある。例えば、特定の地理領域において、非有料道路および有料道路が存在するとする。使用者は、たとえ運転時間が長くなったとしても有料道路を回避する経路を発見したいことがある。或いは、使用者は、フェリー、トンネル、もしくは橋などの使用も避けたいことがある。従来、この望みは、望ましくない道路（または地図中の他の要素）の単位距離当りのコストを極めて高くすることで実現していた。そのような方法では、望ましくない道路（または要素）は、その道路を避けることによりコストが非常に大きくなる場合にのみ使用される。
【０００３】
【特許文献１】特開平８―２９２０５８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
電子地図中の望ましくない要素のコストを大きくする手法は、望ましくない要素の使用を回避する手段として有効ではないことが分かった。第１に、道路線分のコストを大きくしても、可能な限り望ましくない道路が回避されることが保証されるわけではない。そのような特定の種類の道路は、更にコストが大きい他の道路上のルートを避けるために依然として選択されることがある。第２に、望ましくない道路を回避するための従来の技術は、経路が望ましくない道路上の移動を必要とする場合に、この望ましくない道路上の移動が最小にされることが保証されるわけではない。最後に、従来のように、高いコストを表すために極めて大きな整数を使用しようとすると、多くのコンピュータ内でオーバーフローを起こす可能性がある。同様に、大きな実数を使用すると、その意義が失われてしまうことがある。
従って、電子地図もしくは他のネットワークの特定のカテゴリの要素を回避することができ、電子地図もしくは他のネットワークを使用して経路を計算できるシステムが必要である。
【課題を解決するための手段】
【０００５】
発明の要約
本発明は、大まかに説明すると、複数のコストレベルを使用してネットワークにおける経路を計算するシステムを提供する。どの要素を回避するべきかの判断が行われる。少なくとも一つの要素に関連するコストには二つ以上の表現のレベルが含まれる。二つ以上の表現のレベルには第１レベルおよび第２レベルが含まれる。その後、システムは経路発見探索を実行する。
一実施例においては、システムには、処理装置で読取可能に表現したネットワークにおける要素の第１集合を識別するステップと、要素の第１集合の第１の要素に関連した第１コストを作成するステップとが含まれる。第１コストには少なくとも二つの表現のレベルが含まれる。次いで、システムは、作成した第１コストを使用して経路発見探索を実行する。上記識別ステップは、経路発見システムの使用者からの入力を受け付けることであったり、経路発見システムにより自動的に行われたりすることができる。二つの表現のレベルには第１レベルおよび第２レベルが含まれ、第２レベルは第１レベルよりも優先される。他の例には、回避する要素の追加集合を識別すること、およびこれらの追加要素のための、三つの表現のレベルを含んだコストを作成することが含まれる。三つの表現のレベルには、第１レベル、第２レベルおよび第３レベルが含まれる。第３レベルは第１レベルおよび第２レベルよりも優先される。
一実施例においては、本発明は、始点から終点までの経路発見探索を実行するが、これには第１ノードから第２ノードまでの第１経路を発見するステップが含まれ、この第１経路には一以上のリンクの第１集合および一以上のコストの第２集合が含まれる。経路発見探索には更に、第１ノードから第２ノードまでの第２経路を発見することが含まれ、第２経路には一以上のリンクの第２集合および一以上のコストの第２集合が含まれる。コストの第２集合の内の少なくとも一つには二つの表現のレベルが含まれる。経路発見探索では、一つ以上のコストの第１集合の方が一つ以上のコストの第２集合よりも効率的なため、第２経路ではなく第１経路が選択される。
処理装置で読取可能に表現したネットワークは、ノードの識別、ノード間のリンクの識別、およびリンク上を移動するためのコストの識別によって作成することができる。ノード、リンク、およびコストを表すデータは処理装置で読取可能な記憶媒体上のデータベース内に記憶される。記憶されたコストの内の少なくとも一つには、二つの表現のレベルが含まれる。
本発明の、これらのおよび他の目的および利点は、図と共に実施例を示す以下の詳細な説明から明らかになるだろう。
【発明の効果】
【０００６】
本発明のシステムによれば、電子地図もしくは他のネットワークの特定のカテゴリの要素を回避することができ、電子地図もしくは他のネットワークを使用して経路を計算できる。
【発明を実施するための最良の形態】
【０００７】
詳細な説明
図１は、本発明の実施に使用可能なハードウェアアーキテクチャの一例を示すブロック図である。ハードウェアはＣＰＵ１２を含む。このＣＰＵ１２は、インテル８０４８６互換ＣＰＵ、ペンティアム（登録商標）プロセッサ、もしくはその他の適切なプロセッサであることができる。ＣＰＵ１２は、ＣＰＵバス１４に接続されるアドレス、データ、およびコントロールバスラインを有する。また、ＣＰＵバス１４は、いずれもシステム制御論理回路２０によって制御されるキャッシュメモリ１６および主記憶装置１８に接続される。システム制御論理回路２０はＣＰＵバス１４およびコントロール、アドレス、データバスラインから成るバス２２に接続されている。システムＢＩＯＳの入ったＲＯＭ２４および周辺装置２６がバス２２に接続されている。周辺装置２６はフロッピー（登録商標）、ハードディスクドライブ、ＣＤ−ＲＯＭドライブもしくはその他の周辺装置を含むことができる。キャッシュメモリ１６、ＤＲＡＭメモリ１８、ＲＯＭ２４、ＣＤ−ＲＯＭ、およびフロッピー（登録商標）ディスクはいずれも処理装置で読取可能な記憶装置（または媒体）である。本発明の種々の実施例は、様々な量のソフトウェアを使用して記載してある方法を実行する。このソフトウェアは、処理装置で読取可能な、任意の適切な記憶装置に存在することができる。図１には描かれていないが、このハードウェアは、表示装置およびキーボードもしくはポインティングデバイス等の入力装置を含む。図１のシステムは本発明に使用可能な一つのプラットフォームを示す。他の多くのプラットフォームであってもよく、例えば、アップルコンピュータ社から入手可能なマッキントッシュベースのプラットフォーム、異なるバス構造を有するプラットフォーム、ネットワーク型プラットフォーム、マルチプロセッサプラットフォーム、その他のパーソナルコンピュータ、ワークステーション、メインフレーム、ナビゲーションシステム等である。
電子地図は、地図を構成するのに必要なデータを含んだ一つ以上のコンピュータファイルに記憶される。このデータには、経度および緯度データ、住所、距離、方向転換の制限、運転時間、高速道路出口番号、土地の商用利用の説明等を含むことができる。上述の情報は電子地図中に見ることができるが、上述した情報の一部分のみもしくは他の情報を有する電子地図を作成することが可能である。電子地図を表すコンピュータファイルは処理装置で読取可能な記憶媒体に記憶される。
通常、経路発見に使用する電子地図にはグラフが含まれる。グラフはノードとエッジの集合である。ノードはプロパティを有するオブジェクトで、グラフ上の決定点を表わす。エッジは二つのノード間の接続である。グラフ中のノードＡからノードＢへの経路は、ノードのリストとして記載される。このリストは、リスト中の各ノードから次のノードへのエッジが存在するように記載される。有向グラフ（directed graph）とは、グラフ内の各エッジがそれに関連する単一の方向を有するグラフである。ある一組のノード間には、各方向に一つづつ、合計で二つのエッジがある場合もある。有向グラフ中では、エッジはリンクと呼ばれる。重み付きグラフとは、グラフ内の各リンク（またはエッジ）がそれに関連するコストを有するグラフである。他の方法には、コストをノード、またはノードおよびリンクと関連付けたり、コストをグラフの他の要素と関連付けたりすることが含まれる。非有向グラフ（undirected graph）とは、グラフ内の各リンクが双方向性であるグラフである。非有向グラフは、グラフ内の各リンクが、端点は同じであるが向きが異なる二つのリンクを表している有向グラフであると考えることができる。
【０００８】
図２Ａは有向グラフの一例を示す。このグラフは、東行きの一方通行路５０および対面通行路５２を示し、いずれの通行路も対面通行路５４と交差している。道路５０は交差点６０で道路５４と交差する。道路５２は交差点７０で道路５４と交差する。交差点６０には二つのノード６２および６４がある。ノードの頭は丸である。ノードの後部は直線尾部である。丸はノードがどこに位置するかを表し、尾部は移動者がどこから来てそのノードへたどり着くであろうかを表す。見やすくするため、ノード記号は実際の交差点からずらした位置にある。例えば、ノード６２は、道路５４上における、交差点６０へ向かう北行きの移動を表す。ノード６４は、道路５０上における、交差点６０へ向かう東行きの移動を表す。交差点６０には西行きの移動を表すノードは無く、これは道路５０が東行きの一方通行路であるからである。そのため、道路５４上を北へ進む移動者は、交差点６０に着くと右折することしかできない。ノード７２は、道路５４上を南へ移動することで交差点７０に着くことを表す。ノード７４は、道路５２上を東へ移動することで交差点７０に着くことを表す。ノード７６は、道路５２上を西へ移動することで交差点７０に着くことを表す。
リンクはノード間における経路を表す。例えば、ノード６４から、移動者は交差点６０を右折することで道路５４へ入ることができ、また、道路５０上を直進することができる。リンク８６は、道路５０上を東を向いて交差点６０から出発し、交差点６０で右折して道路５４上を南へ進む移動を表す。このようにして、リンク８６はノード６４とノード７２とを接続する。リンク８８は、ノード６４を道路５０上の次のノード（図２Ａ上に示されていない）と接続し、道路５０に沿って東に進み、交差点６０を曲がらずに直進する移動を表す。リンク８９は、道路５４上を北を向いて交差点６０から出発し、交差点６０を右折して道路５０上を東へ進む移動を表す。従って、リンク８９はノード６２と道路５０上の次のノード（図２Ａ上に示されていない）とを接続する。図２Ａはノード６２と６４についてのリンクのみを示す。全てのノードに対するリンクを描くと、有向グラフが大変込み合い、判読が困難になる。そのため、この有向グラフを簡略化して、描き直したものが図２Ｂである。
【０００９】
後述の説明を簡略化するため、図２Ｂでは同一の交差点におけるノードの全て一つのノードに統合してある。（実際に使用する場合、本発明は図２Ａもしくは図２Ｂと同様のグラフを使用できる。）従って、ノード１００はノード６４およびノード６２を表す。ノード１０２はノード７２、７４および７６を表す。ノードの尾部が描かれていない。リンクは、移動可能な方向を示すのに使用される。リンク１０４は交差点７０から交差点６０への移動を示し、リンク１０６は交差点６０から交差点７０への移動を示す。方向転換の制限および一方通行路はリンクの有無で表す。
図２Ｂの有向グラフを、処理装置で読取可能な記憶媒体に記憶されたデータ構造を抽象的に理解するために使用する。処理装置で読取可能な記憶媒体は、実際に有向グラフのイメージを記憶するわけではなく、データ構造を記憶する。データ構造内の各項目はノードを表す。データ構造は、各ノードについて、ノードの位置（例えば緯度および経度）、隣接するノード（一つのリンクを経由して移動できるノード）のリスト、および隣接するノードへの移動に関連する種々のコストを記憶する。本発明は、前述したデータ構造とは異なる、多くの適切なデータ構造でもうまく実施できるものと考えられる。更に、本発明は有向グラフについての使用に限定されるものではない。本発明は地図データベース全体、もしくは他の適切な情報の部分集合（subset）に使用できる。更に、データ構造内の一つ以上の項目はデータのクラスタ内に集められることができる。データのクラスタとは関連データの集まりである。クラスタは性能を向上させるが、本発明はクラスタ無しで使用できる。
【００１０】
図３は、ネットワークの一部分についての有向グラフを表す。この有向グラフには、５個のノード（Ｑ、Ｐ、Ｒ、ＳおよびＴ）および６個のリンク（１３０、１３２、１３４、１３６、１３８および１４０）が含まれる。各リンクはそのリンクに隣接して数字が示されている。この数字はそのリンクに沿った移動のコストを表す。リンク１３０はノードＱをノードＰに接続し、そのコストは４である。リンク１３２はノードＱをノードＲに接続し、そのコストは１である。リンク１３４はノードＱをノードＴに接続し、そのコストは２である。リンク１３６はノードＰをノードＲに接続し、そのコストは２である。リンク１３８はノードＲをノードＳに接続し、そのコストは２である。リンク１４０はノードＳをノードＴに接続し、そのコストは２である。
ノードＱからノードＴへ移動するには三つの経路がある。第１経路にはリンク１３４に沿ってノードＱからノードＴへ直接移動することが含まれる。この経路はＱＴとして識別され、コストは２である。第２経路にはノードＱからノードＲとノードＳを経由してノードＴに至る移動が含まれる。第２経路はＱＲＳＴとして識別される。経路ＱＲＳＴはリンク１３２、１３８、および１４０に沿っており、総コストは５である。総コストは、経路に沿って移動したときに通る各リンクのコストを合計することで計算される。第３経路には経路ＱＰＲＳＴが含まれ、総コストは１０である。
コストを各リンクに別々に割り当てることができる。効率化のため、コストの割り当てには体系だった方法が使用される。例えば、電子地図は通常、道路の種類（または分類）についての比較的小さな集合および曲がりの種類についての比較的小さな集合を使用する。このシステムは、各種道路および各種方向転換に対して、単位長さ当りのコストを割り当てる。次いで、リンクの長さ（例えば距離）を発見し、この長さに道路の種別に対応する単位長さ当りのコストを乗じ、リンクに沿った曲がりのコストを加えることでリンクのコストが計算される。コストには、追加コスト（例えば通行料）もしくはコストの割り引（例えば風景の価値）も含まれることがある。実施される方法にもよるが、コストの計算および割り当ては、データファイルの構築時に行われる。或いは、動作時にコストが決定される。
【００１１】
通常の経路発見システムはコストを整数もしくは実数として表す。しかしながら、本発明は複数のコストレベルを使用する。複数レベルのコストの使用は、コストは「非標準演算（nonstandard arithmetic）」と呼ばれる概念により数学的に正当化される。
経路発見計算において使用される通常（または標準）の演算は、整数の集合Ｚを使用する（または実数の集合Ｒ）（この型の注釈の繰り返しを避けるため、整数についてのみを述べる。しかし、実数についての解釈もまた正しい。）。「非標準演算」とは、*Ｚと呼ばれるより大きな数の集合、即ち「非標準整数（nonstandard integers）」についての演算である。非標準整数の集合は以下のような性質を有する。（１）*Ｚには標準整数が含まれる（Ｚ⊂*Ｚ）。（２）*Ｚには「無限整数（infinite integers）」が含まれる。つまり*Ｚには、Ｚの任意の要素ｎに対してｚ＞ｎとなるような複数の要素ｚが含まれる。（３）*Ｚは、数学者の間で環（ring）と呼ばれる構造を成している。つまり、*Ｚにおいては、加算、減算および乗算の通常の特性が全て適用できる。（４）整数の集合Ｚは*Ｚの「部分環（subring）」である。つまり、Ｚにおける整数の加算、減算および乗算の結果は、*Ｚにおけるそれと同一である。
表記を容易にするため、特定の無限整数をωで表す。ωは、*Ｚの一要素であり、Ｚのいかなる要素ｎよりも大きい。
本発明は非標準コストをａnωｎ＋ａｎ−１ωｎ−１＋...＋ａ１ω＋ａ0として表す。二つの非標準整数の加算は以下のように行われる。
【００１２】
【表１】
【００１３】
同様に、非標準整数ａ１ω＋ａ0に整数ｘを乗算した結果はｘａ１ω＋ｘａ0に等しい。非標準演算の下では、二つのコストＡ=ａnωｎ＋ａｎ−１ωｎ−１＋...＋ａ１ω＋ａ0およびＢ=ｂnωｎ＋ｂｎ−１ωｎ−１＋...＋b1ω＋b0を、ａj≠ｂjとなるような最大のｊを発見することにより比較する。そのようなｊがあり、ａｊ＞ｂｊである場合、Ａ＞Ｂである。ａｊ＜ｂｊである場合、Ａ＜Ｂである。ａj≠ｂjとなるようなｊが無い場合、Ａ＝Ｂである。
一実施例においては、ある固定の最大値までのωのべき乗がコストとして使用される。例えば、全てのコストにはωおよびω２のみが使用される。他のコストモデルには、より高次の、ωのべき乗が使用される。ωのべき乗の最大数値を固定して使用することにより、非標準値はコンピュータで整数の配列として表される。使用するωの最大値がωｎである場合、コストは（ｎ＋１）個の整数の配列（array）で表すことができる。配列［ａ［ｎ］，ａ［ｎ−１］，...，ａ［１］，ａ［０］］が値ａ［ｎ］ωｎ＋ａ［ｎ−１］ωｎ−１＋...＋ａ［１］ω＋ａ［０］］を表すようにすると、コンピュータでの使用が容易になる。当然のことながら、非標準数字を表す方式は他にも存在する。
このような非標準コストの表現による二つのコストは、対応する要素およびこれらの各配列を加えることによって加算される。即ち、二つのコストが［ａ［ｎ］，ａ［ｎ−１］，...，ａ［１］，ａ［０］］および［ｂ［ｎ］，ｂ［ｎ−１］１，...，ｂ［１］，ｂ［０］］で表される場合、合計は配列［ａ［ｎ］＋ｂ［ｎ］，ａ［ｎ−１］＋ｂ［ｎ−１］，...，ａ［１］＋ｂ［１］，ａ［０］＋ｂ［０］］で表される。同様に、二つの非標準コストの表現を比較するには、ｎ番目の要素から０番目の要素に向かって、差異を発見するまで連続的に配列値が比較される。対応する二つの値の中で異なるものが無い場合、二つのコストは等しい。例えば、上述の二つの配列において、最初に、ａ［ｎ］がｂ［ｎ］と比較される。二つの値が異なる場合、より大きな値を有する配列が、より大きなコストになる。二つの値が等しい場合、続いてａ［ｎ−１］とｂ［ｎ−１］とが比較される。配列Ｂがａ［ｎ］に対応する値を有さない場合、即ち、ｂ［ｎ］は存在しない、もしくはｂ［ｎ］＝０である場合、配列Ａがより大きなコストになる。配列で表現された非標準整数を標準整数ｘで乗算する場合、乗算結果は配列［ｘａ［ｎ］，ｘａ［ｎ−１］，...，ｘａ［１］，ｘａ［０］］で表される。
上記の原則を使用すると、経路発見手順のためのコストは複数の表現のレベルを有し、表現の各レベルは配列内の異なる要素となる。配列［ａ［ｎ］，ａ［ｎ−１］，...，ａ［１］，ａ［０］］において、表現の第１レベルはａ［０］であり、表現の第２レベルはａ［１］であり、表現の第３レベルはａ［２］であり、．．．表現の第（ｎ＋１）レベルはａ［ｎ］である。配列内のそれぞれの値は、コストの表現のレベルの大きさに対応する。即ち、配列要素ａ［ｎ］は表現の（ｎ＋１）番目のレベルの大きさである。より上位の表現のレベルは、より下位の表現のレベルよりも優先される。例えば、表現の第２レベルに０でない最大の大きさを有するコストは、表現の第１レベルに０でないの最大の大きさを有するコストよりも常に大きい。数学的に見ると、集合Ｚのメンバであり、０でない、全てのａおよびｂに対して、ａωｎ＞ｂωｎ−１となる。
【００１４】
図３のネットワークが電子地図であり、各リンクが電子地図内の道路を表すと仮定する。道路は種々の道路に分類されている。例えば、路地、住宅道路、幹線道路、高速道路、有料道路、およびフェリーなどに分類されている。ユーザが本当に必要な時以外は有料道路を回避したい場合、ユーザは、有料道路以外の全ての道路タイプが、表現の第１レベルに０以外の大きさを有し、他の全てのレベルに０の大きさを有するコストを含むようにコストモデルを作成できる。この場合、有料道路の表現の第２レベルは０以外の大きさを有するようにする。例えば、コストが運転時間であり、特定の有料道路（リンク）の線分が５運転時間単位の運転時間を有する場合、コストは５ω＋０もしくは配列［５，０］で表される。ユーザが有料道路を回避するよりも更にフェリーを回避したい場合、コストモデルには、フェリーのコスト（フェリーによる横断時間を１０とする）を１０ω２＋０ω＋０もしくは［１０，０，０］で表したコストが含まれる。
図３において、リンク１３２および１３４は有料道路を表し、ユーザが有料道路を回避したいと望んでいると仮定する。コストモデルは、二つの表現レベルを用いて設定される。リンク１３２のコストは［１，０］となり、リンク１３４のコストは［２，０］となる。経路ＱＴのコストは［２，０］となり、経路ＱＲＳＴのコストは［１，４］であり、経路ＱＰＲＳＴのコストは［０，１０］である。この例において、最小コストを有する経路はＱＰＲＳＴである。ＱＰＲＳＴの総コストが最小であるため、この経路が最も効率的な経路であると定義される。
２番目の例では、ユーザが有料道路を回避したいと望み、また、有料道路を回避するよりも更にフェリーを回避したいと望むと仮定する。リンク１３４が有料道路を表し、リンク１３２がフェリーを表すと仮定する。コストモデルは三つの表現レベルにより設定される。リンク１３４のコストは［０，２，０］として表される。リンク１３２のコストは［１，０，０］として表される。経路ＱＴに沿った移動のコストは［０，２，０］に等しく、ＱＲＳＴに沿った移動のコストは［１，０，４］である。即ち、経路ＱＲＳＴには横断リンク１３２、１３８および１４０が含まれる。これらのリンクのコストの合計は、［１，０，０］＋［０，０，２］＋［０，０，２］＝［１，０，４］である。経路ＱＰＲＳＴに沿った移動のコストは［０，０，１０］である。最短の経路は再びＱＰＲＳＴとなる。
３番目の例においては、ユーザが有料道路の使用を避けたいと望み、リンク１３０、１３２および１３４は全て有料道路であると仮定する。コストモデルは二つの表現のレベルで設定される。経路ＱＴに沿った移動のコストは［２，０］である。経路ＱＲＳＴに沿った移動のコストは［１，４］である。経路ＱＰＲＳＴに沿った移動のコストは［４，６］に等しい。この場合、全ての経路には有料道路上の移動が含まれるため、有料道路の使用を最小限に抑えることが目標となる。この目標は三つのコストの全てを比較することで達成される。上述のように、三つのコストを比較するためには、まず始めに最も高次のωのべき乗もしくは配列内で最大の指数（index）を有する要素に注目する。本事例において、経路ＱＲＳＴのコストの表現の第２レベルが１であるため、この経路のコストが最小である。経路ＱＴについてのコストの表現の第２レベルの大きさは２であり、経路ＱＰＲＳＴについてのコストの表現の第２レベルの大きさは４である。
複数のコストレベルを使用することにより２次的な最小化を実行できる。例えば、一つのリンクが実際には他の多くのリンクの集合を表すことにより図を簡略化できる場合がある。この集合リンクを作成する場合、コストの合計を表現の第２レベルとして記憶できる。表現の第１レベルは集合における多数のリンクの合計を保持するのに使用される。従って、コストが２である二つのリンクを足し合わせた場合、この集合の合計結果は４ω＋２即ち［４，２］となる。４ωは二つのコストの合計を表す。＋２は足し合わせたリンクの個数を表す。このタイプのコストモデルを使用すると、経路発見システムは、計算された経路におけるリンクの総数を最小にすることにより、同一コストを有する複数の経路間のコストを最小化することができる。他の方法では、リンクの個数を実際のコストよりも上位の表現のレベルに置くことで、コストを最小化する前にリンクの個数を最小化できる。
他の方法には、コストのノルム（norm）を使用することが含まれる。コストの値がＡ＝ａnωｎ＋ａｎ−１ωｎ−１＋...＋ａ１ω＋ａ0である場合、ノルムはａn＋ａｎ−１＋...＋ａ１＋ａ0と定義される。あるリンクのコストのノルムがこのリンクの運転時間（または他のタイプのコスト）の見積もりを提供するようにコストを設定できる。しかし、それ自身の大きさは必ずしも運転時間と同じである必要はない。その結果、コストを最小化するために他の要因を使用することが可能となる。例えば、任意の地理的領域がいずれも運転時間が１０である二つの高速道路リンクを有すると仮定する。片方の高速道路は景色が不快で、多くのくぼみがあり、もう一方の高速道路は滑らかな道路であり、美しい景色が見える。経路発見システムが良い方の高速道路の使用を促すことが望まれるだろう。両方のコストを［１０，０］と表すのではなく、良い方の高速道路を２ω＋８もしくは［２，８］として表し、不快な高速道路を７ω＋３もしくは［７，３］と表す。
【００１５】
図４は、複数のコストレベルを使用する経路発見の手順を記載するフローチャートを示す。ステップ１５０には、コストレベルが異なる要素を識別することが含まれる。これには一つ以上の、回避するべき要素（例えばリンクまたはノード等）の集合を特定することが含まれる。一実施例においては、経路発見システムのユーザは一つのコストレベルのみを含む標準の地図データベースを使用する。ユーザは起動時に、経路発見に先立って、どの要素が回避されるべきかを問われる。この問い合わせは自由に変更できユーザが任意の回避要素を選択できたり、特定のカテゴリの要素を回避するかどうかがユーザに問われるようにすることができる。カテゴリはネットワークデータベース固有の予め定義されたのカテゴリ（例えば、有料道路、幹線道路、住宅道路）もしくはユーザが定義した道路である。或いは、経路発見手順が回避するカテゴリを自動的に選択する。例えば、経路発見システムは、常に有料道路を回避するシステムとして販売されるであろう。或いは、異なるコストレベルを含むように地図データベースを作成し、これによって回避する要素を前もって選択するようにもできる。ステップ１５０には、一つのカテゴリの要素、または多くのカテゴリの要素を識別することを含むことができる。
【００１６】
他の実施例には、好ましいリンクのカテゴリを選別することが含まれる。即ち、解析を反転できる。表現の第２レベルを有するコストの方が表現の第１レベルを有するコストよりも少ないとみなされるであろう。或いは、全ての好まくないコストは表現の第２レベルを含み、好ましいコストは表現の第１レベルのみを含むであろう。
ステップ１５２において、システムは新たなコストレベルを作成する。コスト構造がまだ設定されていない場合、コスト構造を設定する必要がある。ステップ１５０において識別された各カテゴリについて、コスト情報が表現の第１レベルよりも上位の表現のレベルに０以外の大きさを含むようにデータを配列内に挿入する。例えば、ステップ１５０において、ユーザが、有料道路を唯一の回避すべきカテゴリとして識別した場合、ステップ１５２において、有料道路についてのコストは表現の第２レベルに０以外の大きさを有するように設定される。ユーザが、ステップ１５０において、有料道路とフェリーを異なるレベルの要素として、即ちフェリーを有料道路よりも回避するように識別した場合、ステップ１５２において、有料道路は表現の第２レベルに０以外の大きさを有するように設定され、フェリーは表現の第３レベルに０以外の大きさを有するように設定される。ステップ１５２には上述の配列を作成しこれを埋めることが含まれる。システムが、一つの表現レベルのみを有するコストを既に含んでいる既存の地図データベースにより実行されている場合、これらのコストの内のいくつかは表現の第２レベルに０以外の大きさを有する新たなコストと置き換えられる。一つの方法では、新たなコストを含む新規の地図データベースを作成できる。新規の地図データベースは処理装置で読取可能な記憶媒体内に記憶される。別の方法では、元の地図データベースは未編集のまま残り、新たなコストは追加のデータ構造に記憶される。ステップ１５２の後、システムはステップ１５４において経路発見探索を実行する。
【００１７】
図５は電子地図の一部分の有効グラフを表す。描かれた有効グラフには十個のノード（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｊ，Ｏ）およびこれらノード間の種々のリンクが含まれる。リンクは、それぞれそのリンクに隣接して数字が示されている。この数字は、リンクに沿った移動のコストを表す。
図４中のステップ１５４を更に詳細に説明するために図５を図６と共に使用する。例えば、ユーザが、図４のステップ１５０において、有料道路を唯一の回避すべきリンクのカテゴリとして識別したと仮定する。この例で、ノードＨからノードＤを接続するリンク（反対方向の二つのリンク）が有料道路の一部分であり、残りのリンクが有料道路ではないと仮定する。元の地図データベースには図５に示すコストが含まれていたとする。ステップ１５２において、有料道路のコスト構造は二つの表現のレベルを含むように変換される。ノードＨからノードＤまで移動するためのリンクのコストは、４ω＋０または［４，０］で表される。
【００１８】
図６は経路発見計算（経路発見探索とも呼ばれる）を説明するフローチャートである。図６の経路発見計算は、Edsger W. Dijkstra による方法に少なくとも部分的に基づいており本発明に使用可能な多くの経路発見方法の内の一つにすぎない。Dijkstraの方法を論じている参考文献として、M.N.S. SwamyとK. Thulasiramanらによる「Graphs, Networks, and Algorithms, John Wiley & Soas (1981)」が挙げられる。システムは、ステップ２０２において経路発見計算を初期化する。即ち、システムは、経路の始点および終点を記憶し、二つのキュー、即ち始点優先キュー（origin priority queue）および終点優先キューを（destination priority queue）セットアップする。始点優先キューは、始点からの経路がわかっているノードを整列したリスト、および各ノードについてのキーから成る。このキューはキーに従ってソートされる。キーの決定には種々の異なる方法がある。一方法では、キーは、始点からノードまでの移動についての既知の最低コストである。もう別の方法におけるキーは、始点からノードまでの既知の最短距離にノードから終点までの移動に要する見積もりコストを加えたものである。本方法に適した、ノードから終点までの移動に要するコストを見積る方法には種々のものがある。その一例は、「烏が飛ぶであろう」（"As-the-Crow-Flies"）直線距離に単位距離当たりの見積もりコストを乗ずる方法である。即ち、ノードおよびリンクを無視して、ノードと終点との間の物理的な距離を測定し、その距離に単位距離当たりの見積もりコストを乗ずるのである。
終点優先キューは、終点までの経路が分かっているノードを整列したリスト、および各ノードについてのキーから成る。このキューはキーに従ってソートされる。終点キーの決定には多くの方法がある。一方法は、ノードから終点までの既知の最低コストの経路を使用することである。もう別の方法におけるキーは、ノードから終点までの既知の最低コストに、始点からノードまでの見積もりコストを加えた合計を使用する。本発明の範囲内であれば、他の方法でキーを計算してもよい。
更に、システムは始点訪問済みリスト（origin visited list）および終点訪問済みリスト（destination visited list）をセットアップする。始点訪問済みリストは、始点からの経路が分かっている全てのノードのリスト、始点からそのノードまでの移動の最低コスト、およびコストが最低の経路に沿った直前のノードを保持する。終点訪問済みリストは終点までの経路が分かっている各ノードの名前、そのノードから終点までの移動の既知の最低コスト、およびコストが最低の経路に沿った次のノードの識別情報を記憶する。ステップ２０２による初期化が完了すると、始点優先キューおよび始点訪問済みリストには始点が含まれ、終点優先キューおよび終点訪問済みリストには終点が含まれる。
システムが初期化されると、システムは所定のルールに従いステップ２０４においてキューを選択する。本発明に適したキュー選択ルールには多くのものが存在する。あるシステムにおいては、最小のキーを有する要素を含んだキューが選択され要素間の結びつきは任意に断たれる。別のルールのシステムにおいては、キューに含まれる要素の数が最も少ないキューが選択される。キュー選択ルールのその他の例としては、キューを交互に切り換え、ある期間は始点キューを選択し、別の期間は終点キューに切換え、更に別の期間は始点キューに再び切換えることが挙げられる。キューはキーによってソートされるので、最小のキーを有するノードがキューの先頭（キューの前部またはキューのトップとも言う）に来る。このノードを「ヘッドノード」と呼ぶ。後述の例では、キューが選択される方法としてキューを切換える方法を使用し、始点優先キューから開始される。
システムは、ステップ２０６において、選択したキューのヘッドノードに隣接する全てのノードを探索する。システムは開始したばかりなので、始点優先キュー中に存在する唯一のノードは始点である。隣接ノードとは、始点から、他ノードのノードも通過せずに移動できるノードである。始点Ｏの隣接ノードは、ノードＡ、Ｂ、ＧおよびＨである。４個の隣接ノードがあるため、システムは任意に一つの隣接ノードを選択する。システムは、ステップ２０８において、選択した隣接ノードについて、より低いコストが訪問済みリストおよび優先キュー上に既に存在するかどうかを判断する。つまり、システムは隣接ノードとヘッドノードとの間の移動コストを判断する。この場合、選択された隣接ノードはノードＡであり、始点からノードＡまでの移動のコストは９である。経路発見計算は始まったばかりなので、ノードＡは訪問済みリストおよび始点優先キュー上になく、ノードＡについての他の既知のコストは存在しない。既知のコストが存在しないので、システムは、ステップ２１０において、訪問済みリストおよび優先キューにノードＡおよびそのコストを追加して編集する。その後、ステップ２０６へ戻り、検討されていない隣接ノードが他にないかどうかを判断する。この場合、三個の隣接ノードＢ、ＧおよびＨが未検討である。
システムはステップ２０８において、ノードＢについて、より低い既知のコストが無いかどうかを判断する。始点からＢまでの移動のコストは３であり、Ｂは優先キューおよび訪問済みリスト上に存在しない。ステップ２１０において、ノードＢを優先キューおよび訪問済みリストに追加する。システムはステップ２０６へ戻って、ノードＧについて検討する。始点ＯからＧへと直接行く場合のコスト、即ち７よりも低い既知のコストは存在しないため、Ｇを優先キューおよび訪問済みリストに加える。システムはステップ２０６へ戻って、ノードＨについて検討する。始点ＯからＨへと直接行く場合のコスト、即ち２よりも低い既知のコストは存在しないため、Ｈをビジターリスト内の優先キュー加える。システムはステップ２０６へ戻って、これ以上隣接するノードが無いことを判断する。従って、ステップ２１２において、ヘッドノード、即ちこの時点では始点Ｏ、を優先キューから取り除く。表２は、経路発見計算におけるこの時点での始点優先キューおよび訪問済みリストの内容を表す。始点優先キューにはＢ、Ｇ、Ａ、およびＨの４個のノードがある。これらのキーは始点からそのノードまでの移動のコストを表す。訪問済みリストはノード、コスト、およびＰｒｅｖの３つの欄を有する。ノード欄はノード識別情報を列記する。コスト欄は始点からそのノードまでの移動についての既知の最小コストを列記する。Ｐｒｅｖ欄は既知の最小コストを利用して経路に沿って移動した時の、始点からノードまでの経路に沿った直前のノードを列記する。訪問済みリストに列記されるノードの順番はリストの検索を容易にする任意の順番とすることができる。例えば、ノードをアルファベット順に列記できる。一実施例においては、ノードは数値コード名が付けられ、訪問済みリストはハッシュテーブルである。
【００１９】
【表２】
【００２０】
システムはステップ２１４において、停止条件が満たされたかどうかを判断する。本発明に適した停止条件には多くのものがある。例えば、あるノードが、始点優先キューおよび終点優先キューの何れにおいてもヘッドノードであるときに停止する。他の停止条件は、始点から始点優先キュー内のヘッドノードまでの移動のコストに終点キューのヘッドノードから終点までの移動のコストを加えたコストが最適コネクションノードの総コスト以上である場合に停止する。この停止条件が本実施例において使用する停止条件である。コネクションノードとは、終点訪問済みリストおよび始点訪問済みリストに現れるノードである。コネクションノードの総コストとは、始点からコネクションノードまでのコストにコネクションノードから終点までのコストを加えたコストである。最適コネクションノードとは、最小の総コストを有するコネクションノードである。本事例においてコネクションノードは存在せず、停止条件は満たされておらず、システムはステップ２０４においてキューを選択する。
【００２１】
上述のように、本実施例における、優先キューを選択する方法は単純な切換え方式であるため、システムは終点キューを選択する。システムはステップ２０６において、終点Ｄに隣接するノードがあるかどうかを判断する。本実施例において、三個の隣接ノードＣ、Ｆ、およびＨがある。システムはステップ２０８において、ノードＣに着目し、より低い既知のコストがあるかどうかを判断する。そのようなコストは存在しないので、ステップ２１０において、終点優先キューおよび訪問済みリストにノードＣおよびそのコストを追加して編集する。その後、ステップ２０６へ戻って、もう一つの隣接ノード、即ちノードＦがあることを判断する。システムはステップ２０８において、Ｆについて、より低い既知のコストが無いことを判断する。ステップ２１０において、優先キューおよび訪問済みリストにノードＦを追加して編集する。その後、ステップ２０６へ戻り、もう一つの隣接ノード、即ちノードＨがあることを判断する。システムはステップ２０８において、ＨからＤの移動について、より低い既知のコストが無いことを判断する。ステップ２１０において、終点優先キューおよび終点訪問済みリストにノードＨおよびＨからＤまでの移動のコスト、即ち４ωもしくは［４，０］を追加して編集する。システムはステップ２０６において、ノードＤに隣接するノードがこれ以上無いことを判断し、ステップ２１２において、ノードＤを終点優先キューから取り除く。表３は、この時点での終点優先キューおよび訪問済みリストの状態を表す。
【００２２】
【表３】
【００２３】
システムはステップ２１４において、停止条件が満たされたかどうかを判断する。この時点では、コネクションノードが存在する。ノードＨが両方の訪問済みリスト上に存在する。ノードＨについての総コストは［４，２］もしくは４ω＋２である。つまり、始点からノードＨまでの移動のコストは［０，２］であり、ノードＨから終点までの移動のコストは［４，０］である。始点から始点優先キューにおけるヘッドノード（Ｈ）までの移動のコストは［０，２］であり、また、終点優先キューにおけるヘッドノード（Ｆ）から終点までの移動のコストは［０，２］であるため、停止条件は満たされない。この二つのコストの合計は［０，４］であり、コネクションノードＨの総コストよりも低いため、停止条件は満たされず、システムはステップ２０４において、始点優先キューを選択する。
始点優先キュー上のヘッドノードはノードＨである。ノードＤがノードＨに隣接する唯一のノードである。システムはステップ２０８において、ノードＤについて、より低い既知のコストが無いことを判断する。従って、ステップ２１０において、訪問済みリストおよび優先キューにノードＨからノードＤまでの移動のコスト、即ち［４，０］を含むように編集する。表４は、ノード４を優先キューから取り除いた（ステップ２１２）後の、始点優先キューおよび始点訪問済みリストの現在の状態を表す。
【００２４】
【表４】
【００２５】
システムはステップ２１４において、停止条件が満たされたかどうかを判断する。この時点では、２つのコネクションノード、ノードＨおよびノードＤが存在する。ノードＨの総コストは［４，２］である。ノードＤの総コストも［４，２］である。始点から始点優先キューのヘッドノードまでの移動のコストおよび終点キューのヘッドノードから終点までの移動のコストの合計は［０，７］に等しく、ノードＨおよびノードＤについてのコストの合計よりも少ないため、停止条件は満たされない。
システムはステップ２０６において、終点キュー上のヘッドノードに隣接するノードを探索する。ヘッドノードはノードＦなので、ノードＥが唯一の隣接ノードとなる。ノードＤはＦへ到達するために使用されるノードであるため、隣接ノードとして処理されない。ＥからＦまでの移動のコストは［０，２］であるため、ＥからＦを経由してＤに至る移動のコストは［０，４］である。システムはステップ２０８において、ＥからＤまでの移動について、より低い既知のコストが無いことを判断し、それに従って、訪問済みリストおよび優先キューを更新する。システムはステップ２０６において、他に隣接ノードが無いことを判断し、ステップ２１２においてＦを優先キューから取り除く。表５は、本方法におけるこの時点での終点優先キューおよび訪問済みリストの状態を表す。
【００２６】
【表５】
【００２７】
ステップ２１４において、システムは停止条件が満たされたかどうかを判断する。この時点でもやはり、二つのコネクションノードＨおよびＤが存在する。始点から始点優先キュー内のヘッドノード（Ｂ）までの移動のコストは［０，３］で、終点優先キュー内のヘッドノード（Ｃ）から終点までの移動のコストは［０，５］であるため、停止条件は満たされない。二つのコストの合計は［０，８］であり、コネクションノードＨもしくはＤについての総コストよりも低い。
表４より、始点優先キュー上のヘッドノードはノードＢであることがわかる。ノードＢに隣接するノードはノードＡおよびノードＥである。ステップ２０８においてノードＡを検討し、ノードＡについて、より低い既知のコストは存在しないことを判断する。ノードＡはコストが［０，９］であるとして訪問済みリストに現れないが、ノードＢを経由した始点からノードＡまでの移動のコストは「０，６］である。つまり、ＯからＢまでの移動のコストは［０，３］であり、ＢからＡまでの移動のコストは［０，３］である。即ち、ＯからＢを経由してＡに至る移動のコストは［６，０］であり、Ｏから直接Ａに移動した場合のコストよりも低い。従って、ステップ２１０において、始点からノードＡまでの移動のコスト、即ち［０，６］を訪問済みリストおよび優先キューに含めるように編集し、ノードＡについての、訪問済みリストにおける直前ノードがＢとなる。つまり、ＯからＡにコスト［０，６］で着くためには、ノードＢを通って移動しなくてはならない。システムはステップ２０６において、もう一つの隣接ノードであるＥがあることを判断する。システムはステップ２０８において、Ｅについて、より低いコストが無いことを判断し、優先キューおよび訪問済みリストにＥを含めるように編集する。表６は、ノードＢを優先キューから取り除いた（ステップ２１２）後の始点優先キューおよびビジターリストの状態を表す。
【００２８】
【表６】
【００２９】
システムはステップ２１４において停止条件が満たされたかどうかを判断する。この時点では３つのコネクションノードＥ、Ｈ、Ｄが存在する。コネクションノードＥの総コストは［０，９］であり、コネクションノードＨの総コストは［４，２］であり、コネクションノードＤの総コストは［４，２］である。ノードＥが全てのコネクションノードの中でコストが最も低いので、ノードＥが最適なコネクションノードをみなされる。起点から起点優先キュー上のヘッドノードまでの移動のコストは［０，６］である。終点優先キュー上のヘッドノードから終点までの移動のコストは［０，５］である。従って、ヘッドノードまでおよびヘッドノードからの移動のコストは［０，１１］であり、最適なコネクションノードの総コストである［０、９］よりも大きい。その結果、停止条件が満たされ、システムはステップ２１６において、経路を構築する。
【００３０】
経路を構築するステップは以下の通りである。ルールに従いあるコネクションノードを選択する。その様なルールの一つは、最適なコネクションノードを選択することである。始点訪問済みリストにおいて、選択されたコネクションノードＫを探索し、始点からの経路上の直前のノードＰ１を発見する。Ｐ１が始点でなければ、訪問済みリストにおいてＰ１を探索し、始点からの経路上の直前のノードＰ２を発見する。始点に着くまでこの探索を繰り返す。始点に着いたと仮定し、この始点をノードＰLとする。同様に、終点訪問済みリストにおいてＫを探索し、終点までの経路上の次ノードＮ１を発見する。Ｎ１が終点でなければ、訪問済みリストにおいてＮ１を探索する。終点に着くまでこの探索を繰り返す。終点に着いたと仮定し、この終点をノードＮMとする。この時点で始点から終点までの経路がわかる。その経路とは、ＰL（始点）からＰL-1へ、ＰL-2へ、・・・、Ｐ2へ、Ｐ1へ、Ｋへ、Ｎ１へ、・・・ＮM-1へ、ＮM（終点）への経路である。
本実施例において、Ｅは最適なコネクションノードである。表６における訪問済みリストを参照し、始点からノードＥまでの移動についての最適な既知のコストにはノードＢからノードＥまでの移動が含まれることを判断する。従って、構築される経路ではＢからＥへの移動が行われる。システムは、訪問済みリストにおいてノードＢを発見し、ノードＢまでの最適な経路は始点Ｏからの直接の経路であることを判断する。この時点で、構築された経路はＯからＢを経由してＥに至る移動を含む。システムは始点に着くと、コネクションノードから終点までの経路を作る。表５における訪問済みリストを参照し、Ｅから終点までの最適な経路にはＥからＦまでの移動が含まれることを判断する。また、訪問済みリストは、ＦからＤまでの最適な経路がＦからＤまで直接移動する経路であることを表す。従って、ＯＢＥＦＤの経路が構築される。この様に、経路発見計算はＨからＤへのリンクにより表される有料道路の使用を回避する。
いくつかのシステムにおいては、ヘッドノードが接続されている全てのノードを検討しないことで経路発見計算を速める。探索を特定の近隣のノードに限定する。このような方法の一つは、ノードを、それが存在する道路の重要度に従って分類し、始点から（または終点まで）の距離が増すにつれて近隣のノードを使用することを累進的に制限する。例えば、使用されるコスト測定値が見積もり運転時間である場合、始点もしくは終点から車で２分以上かかる住宅道路、および始点もしくは終点から車で１０分以上かかる幹線道路等は、探索に使用されないだろう。
【００３１】
本発明の一実施例においては、電子マップは分離したデータベースとして記憶され、経路発見装置には二つの主モジュールを有するソフトウェアが含まれる。第１モジュールは図４のステップ１５０および１５２を実行する。第２モジュールは経路発見機能を実行する。第１モジュールは、コストを記憶するために何個の表現のレベルを使用するかを表すコストモデルおよびコストの決定のためのインデックス（または定義）をセットアップする。インデックスには、各幹線道路に関してのコストはＸにリンクの単位距離を乗じたものに等しく、各住宅道路に関してのコストはＹにリンクの単位距離を乗じたもの等しい等のような情報が含まれる。コストモデルは経路発見機能に受け渡される。
他の実施例においては、本発明を、電子地図を使用する動的交通回避システムの一部分として使用できる。運転者が、ある特定の道路もしくは道路の集合に交通上の問題が発生していることを知ったとする。図４のステップ１５０において、運転者はシステムを使用して交通問題が発生している道路を特定する。交通問題が発生している道路のコストは、表現の第２レベルに０以外の大きさを有する（例えば、ａ１ω＋ａ0ただし、ａ１≠０）。ステップ１５４において、運転者を、交通問題が発生している道路を回避させて終点へ向かわせる経路が計算される。
本発明を記載するために既に使用した例は、道路から成る電子地図のためのものであるが、本発明を適切な、処理装置で読取可能に表現したネットワークにも適用できる。適切なネットワークには、製造工程のグラフ、共同一貫移動プラン（intermodal travel plan）（例えば、飛行機、電車、車、バス等を使用した地点間の移動を表すグラフ）、医学療法を提供するシステム等が含まれる。例えば、ネットワークが製造工程を表す場合、ノードは工程中の決定点を表すことができ（例えば、製造品をどのステーションへ移送するか、もしくはどの半導体プロセスを使用するかなど）、リンクは処理時間もしくは製造コストを表すことができる。
【００３２】
以上の本発明の詳細な説明は、例示および説明を目的として提供するものである。本発明を完全に表したものではなく、また、開示された通りのものに限定されるものではない。また、上記の教示に鑑みて、多くの変形および変更を施すことが可能である。記載した実施例は、本発明の原理および実際的なアプリケーションを最もよく説明し、これにより、当業者が種々の実施形態でかつ予想される特定の使用に適した種々の変形を加えて本発明を最適に利用できるようにするために選択したものである。本発明の範囲は添付のクレームによって定義されるものである。
【００３３】
なお、本発明の特徴点を下記列挙する。
１．処理装置で読取可能に表現したネットワークを使用して経路を発見する、コンピュータによって実施される方法であって、
前記ネットワークにおける一つ以上の要素の第１集合を識別するステップと、
前記要素の第１集合の第１要素に関連する第１コストを作成するステップであって、前記第１コストは少なくとも二つの表現のレベルについて０以外の大きさを含むステップと、
処理装置によって、前記第１コストを使用して経路発見探索を実行するステップと、
を含む方法。
２．上記１に記載の方法であって、前記要素の第１集合がリンクの集合である方法。
３．上記１に記載の方法であって、前記処理装置で読取可能に表現したネットワークが電子地図であり、前記要素の第１集合が複数の有料道路を表すリンクの集合である方法。
４．上記１に記載の方法であって、前記処理装置で読取可能に表現したネットワークが電子地図であり、前記要素の第１集合が一つの有料道路を表すリンクである方法。
５．上記１に記載の方法であって、前記識別するステップが、ユーザからの入力を受け取ることを含み、前記入力に基づき前記第１集合の要素を特定することを含む方法。
６．上記１に記載の方法であって、前記識別するステップが、ユーザの入力なしに、前記入力に基づいて前記第１集合の要素を自動的に特定することを含む方法。
７．上記１に記載の方法であって、前記作成するステップが、既存のコストを前記第１コストと置き換えることを含み、前記既存のコストには一つの表現のレベルについてのみ０以外の大きさが含まれる方法。
８．上記１に記載の方法であって、更に、
前記第１要素に加えて、前記第１集合の前記要素に関連する追加コストを作成するステップであって、前記追加コストは少なくとも二つの表現のレベルについて０以外の大きさを含むステップ
を含む方法。
９．上記１に記載の方法であって、前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルが前記第１レベルよりも優先される方法。
１０．上記１に記載の方法であって、更に、
前記電子地図において回避する一つ以上の要素の第２集合を識別するステップと、
前記第２集合の第１要素に関連する第２コストを作成するステップであって、前記第２コストが少なくとも三つの表現のレベルが０以外の大きさを含むステップと、
前記第２コストを使用する前記実行するステップと、
を含む方法。
１１．上記１０に記載の方法であって、前記第２コストは、前記第１コストの大きさおよび前記第２コストの大きさに関わらず前記第１コストよりも大きい方法。
１２．上記１に記載の方法であって、前記第１コストは非標準型数字である方法。
１３．上記１に記載の方法であって、前記第１コストは無限整数の０以外の倍数で表すことができる方法。
１４．上記１に記載の方法であって、前記第１コストは複数要素のデータ構造内に記憶される方法。
１５．上記１に記載の方法であって、前記第１コストは配列として記憶される方法。
１６．上記１に記載の方法であって、更に、少なくとも二つの表現のレベルを含むコストモデルを作成するステップを含む方法。
１７．上記１に記載の方法であって、前記処理装置で読取可能に表現したネットワークは電子地図である方法。
１８．上記１７に記載の方法であって、前記経路発見探索を実行するステップがDijkstraによる方法を使用することを含む方法。
１９．上記１７に記載の方法であって、前記実行するステップは、コストの最小化を試みる方法。
２０．上記１７に記載の方法であって、前記経路発見を実行するステップは、
優先キューおよび訪問済みリストをセットアップするステップであって、前記優先キューがノードの識別記号およびキーを記憶し、前記訪問済みリストがノード識別記号および始点からの移動のコストを記憶するステップと、
前記優先キューを初期化するステップと、
前記始点に隣接するノードの集合を発見するステップと、
前記始点から前記隣接ノードの各々までの移動のコストを決定するステップと、
前記隣接ノードをキーでソートされた前記優先キューに挿入するステップと、
前記ノードを前記訪問済みリストに挿入するステップと、
前記優先キューから前記始点を取り除くステップと、
前記キューの先頭のノードに隣接するノードの集合を発見するステップと、
前記キューの先頭のノードに隣接する前記ノードの各々への移動のコストを決定するステップと、
少なくとも前記キューの先頭のノードに隣接する前記ノードの部分集合を前記優先キューに挿入するステップと、
前記優先キューの先頭のノードに隣接する前記ノードが、より低いコストを有して前記訪問済みリスト中にまだ存在しない場合に、前記ノードを前記訪問済みリストに挿入するステップと
前記優先キューから前記キューの先頭のノードを取り除くステップと、
を含む方法。
２１．上記１７に記載の方法であって、
前記電子地図がリンクおよびノードを含み、前記要素の第１集合がリンクの集合であり、前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルより優先され、前記第２レベルは無限整数の０以外でのべき乗の倍数である方法。
２２．上記１に記載の方法であって、
前記第１要素がリンクの集合を表し、前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第１レベルが前記集合における前記リンクの数を表している方法。
２３．上記１に記載の方法であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第１レベルの大きさおよび前記第２レベルの大きさの合計が、最小化される見積もり量である方法。
２４．処理装置で読取可能に表現したネットワークを使用する、コンピュータによって実施される方法であって、
処理装置を使用して始点から終点までの経路発見を実行するステップを含み、前記経路発見を実行するステップは、
第１ノードから第２ノードまでの第１経路を発見するステップであって、前記第１経路が一つ以上のリンクの第１集合および一つ以上のコストの第１集合を含むステップと、
第１ノードから第２ノードまでの第２経路を発見するステップであって、前記第２経路が一つ以上のリンクの第２集合および一つ以上のコストの第２集合を含み、少なくとも前記コストの第２集合の内の一つが少なくとも二つの表現のレベルを含むステップと、
一つ以上のコストの第１集合が一つ以上のコストの第２集合よりも効率的である理由から前記第１経路を選択するステップと
を含む方法。
２５．上記２４に記載の方法であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される方法。
２６．上記２５に記載の方法であって、
前記処理装置で読取可能に表現したネットワークが電子地図である方法。
２７．上記２６に記載の方法であって、
前記第２経路は有料道路を含み、前記第１経路は有料道路を含まず、前記コストの第２集合の内の一つが第２レベルについて０以外の大きさを有し、前記有料道路と関連付けられている方法。
２８．上記２６に記載の方法であって、
前記選択するステップが、前記第２レベルについて０以外の大きさを有するコストと前記第１レベルについて０以外の大きさを有するコストとを比較すること含む方法。
２９．上記２６に記載の方法であって、
前記コストの第２集合の内の少なくとも一つが三つの表現のレベルを有する方法。
３０．上記２９に記載の方法であって、
前記三つの表現のレベルが第１レベル、第２レベル、および第３レベルを含み、前記表現の第３レベルが前記第２レベルよりも優先される方法。
３１．上記２６に記載の方法であって、
前記選択するステップが前記コストの第１集合の合計と前記コストの第２集合の合計を比較することを含む方法。
３２．上記２６に記載の方法において、
前記比較するステップが無限数字の一乗の大きさの比較および無限数字の二乗の大きさの比較を含む方法。
３３．上記２６に記載の方法であって、
前記第１経路が前記始点と前記終点との間の最終経路の一部分である方法。
３４．電子地図を作成する方法であって、
ノードを特定するステップと、
ノード間のリンクを特定するステップと、
前記リンクを移動するためのコストを特定するステップであって、前記コストの内の少なくとも一つが表現の第１レベルおよび表現の第２レベルを含み、前記表現の第２レベルは前記表現の第１レベルよりも優先されるステップと、
前記ノード、前記リンク、および前記コストを表すデータを地図データベース内に記憶するステップであって、前記地図データベースは処理装置で読取可能な記憶装置内にあるステップと、
を含む方法。
３５．上記３４に記載の方法であって、
前記記憶するステップが、前記コストを配列で表すデータを記憶することを含む方法。
３６．上記３４に記載の方法であって、前記第２レベルが無限整数の０以外でのべき乗の倍数を含んでいる方法。
３７．電子地図が組み込まれている、処理装置で読取可能な記憶媒体であって、
前記電子地図は上記３４の方法に従って作成され、前記電子地図は、表現の第１レベルおよび表現の第２レベルが含まれる前記コストの内の少なくとも一つを記憶し、前記表現の第２レベルは前記表現の第１レベルよりも優先される方法。
３８．電子地図データベースの機能を高める方法であって、
前記地図データベースはノード、ノード間のリンク、およびリンクのコストを含み、
前記リンクを分類するステップと、
少なくとも一つのリンクの分類についてのコストの第２レベルを作成するステップと、
前記コストの第２レベルを処理装置で読取可能な記憶媒体に記憶するステップと、
を含む方法。
３９．上記３８に記載の方法であって、
前記記憶するステップが、前記コストの第２レベルを配列で表すデータを記憶することを含む方法。
４０．上記３８に記載の方法であって、前記分類するステップが、どのリンクが有料道路であってどのリンクが非有料道路であるかを特定することを含む方法。
４１．上記３８に記載の方法であって、前記作成するステップが、既存のコストを新しいコストと置き換えることを含み、前記新しいコストは前記既存のコストおよび無限数字の積である方法。
４２．機能の高められた電子地図が組み込まれている、処理装置で読取可能な記憶媒体であって、前記前記機能の高められた電子地図は、ノード、ノード間を接続するリンク、およびリンクのためのコストを含み、前記電子地図は、上記３８の方法によって機能が高められる方法。
４３．処理装置で読取可能に表現したネットワークを使用する、経路を発見するための装置であって、
第１ノードから第２ノードまでの第１経路を発見する手段であって、第１経路が一つ以上のリンクの第１集合および一つ以上のコストの第１集合を含む手段と、
第１ノードから第２ノードまでの第２経路を発見する手段であって、第２経路が一つ以上のリンクの第２集合および一つ以上のコストの第２集合を含み、少なくとも前記コストの第２集合の内の一つが少なくとも二つの表現のレベルを含む手段と、
前記一つ以上のコストの第１集合が前記一つ以上のコストの第２集合よりも効率的であるとの理由に基づき前記第１経路を選択する手段と、
を含む装置。
４４．上記４３に記載の装置であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される装置。
４５．上記４３に記載の装置であって、
前記処理装置で読取可能に表現したネットワークは電子地図である方法。
４６．処理装置で読取可能なプログラムコードが組み込まれている、処理装置で読取可能な記憶媒体であって、前記処理装置で読取可能なプログラムコードは、処理装置で読取可能に表現したネットワークを使用して経路を発見するためのものであり、
第１ノードから第２ノードまでの経路を発見する第１プログラムコードであって、前記第１経路が一つ以上のリンクの第１集合および一つ以上のコストの第１集合を含んでいる第１プログラムコードと、
第１ノードから第２ノードまでの第２経路を発見する第２プログラムコードであって、前記第２経路が一つ以上のリンクの第２集合および一つ以上のコストの第２集合を含み、前記コストの第２集合の内の一つが少なくとも二つの表現のレベルを有している第２プログラムコードと、
前記一つ以上のコストの第１集合が前記一つ以上のコストの第２集合よりも効率的であるとの理由に基づき、前記第１経路を選択する第３プログラムコードと、
を含む処理装置で読取可能な記憶媒体。
４７．上記４６に記載の処理装置で読取可能な記憶媒体であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される処理装置で読取可能な記憶媒体。
４８． 上記４７に記載の処理装置で読取可能な記憶媒体であって、
前記処理装置で読取可能に表現したネットワークが電子地図である処理装置で読取可能な記憶媒体。
４９．上記４８に記載の処理装置で読取可能な記憶媒体であって、
前記第３プログラムコードは前記コストの第１集合の第１合計および前記コストの第２集合の第２合計を決定し、前記第３プログラムコードは前記第１合計が前記第２合計よりも少ないことを判断する、処理装置で読取可能な記憶媒体。
５０．上記４９に記載の処理装置で読取可能な記憶媒体であって、前記第１合計および前記第２合計はコンピュータ記憶装置に配列として記憶される、処理装置で読取可能な記憶媒体。
５１．上記４７に記載の処理装置で読取可能な記憶媒体であって、更に、
前記ネットワークのためのコストモデルを作成する第４プログラムコードを含む、処理装置で読取可能な記憶媒体。
５２．上記４７に記載の処理装置で読取可能な記憶媒体であって、前記第３プログラムコードは、動的交通状況に少なくとも部分的に基づいて前記第１経路を選択する処理装置で読取可能な記憶媒体。
５３．処理装置で読取可能なプログラムコードが組み込まれている、処理装置で読取可能な記憶媒体であって、前記処理装置で読取可能なプログラムコードは、処理装置で読取可能に表現したネットワークを使用して経路を発見し、前記処理装置で読取可能なプログラムコードは、
前記ネットワークにおける一つ以上の要素の第１集合を識別するのに使用される第１プログラムコードと、
前記要素の第１集合の第１要素に関連する第１コストを作成する第２プログラムコードであって、前記第１コストが少なくとも二つの表現のレベルを有している、第２プログラムコードと、
前記第１コストを使用して、経路発見探索を実行する第３プログラムコードと、
を含む処理装置で読取可能な記憶媒体。
５４．上記５３に記載の処理装置で読取可能な記憶媒体であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される処理装置で読取可能な記憶媒体。
５５．上記５４に記載の処理装置で読取可能な記憶媒体であって、
前記処理装置で読取可能に表現したネットワークが電子地図である処理装置で読取可能な記憶媒体。
５６．上記５４に記載の処理装置で読取可能な記憶媒体であって、
前記第１プログラムコードは交通問題を特定するのに使用され、前記第３プログラムコードは前記交通問題を回避する経路を発見する、処理装置で読取可能な記憶媒体。
５７．処理装置で読取可能に表現したネットワークを使用して経路を発見するための装置であって、
入力装置と、
処理装置で読取可能に表現したネットワークの少なくとも一部分を記憶することができる処理装置で読取可能な記憶装置と、
表示装置と、
入力装置、記憶装置、および表示装置と通じている処理装置と、
を含み、前記処理装置は、
ネットワークにおける一つ以上の要素の第１集合を識別し、
前記要素の第１集合の第１要素に関連するコストを作成し、前記第１コストが少なくとも二つの表現のレベルを含み、
前記第１コストを使用して経路発見探索を実行するようにプログラムされている装置。
５８．上記５７に記載の装置であって、
前記二つの表現のレベルが第１レベルおよび第２レベルを含み、前記第２レベルは前記第１レベルよりも優先される装置。
５９．上記５７に記載の装置であって、
前記処理装置で読取可能に表現したネットワークが電子地図である装置。
【図面の簡単な説明】
【００３４】
【図１】図１は、本発明の実施に使用可能なハードウェアアーキテクチャの一例を示すブロック図である。
【図２Ａ】図２Ａは、電子地図の一部分を表す有向グラフ（directed graph）の一番目の例である。
【図２Ｂ】図２Ｂは、電子地図の一部分を表す有向グラフの二番目の例である。
【図３】図３は、ネットワークの一部分を表す有向グラフの三番目の例である。
【図４】図４は、複数のコストレベルを使用して経路を発見する手順を記載したフローチャートである。
【図５】図５は、ネットワークの一部分を表す有向グラフの四番目の例である。
【図６】図６は、図４の経路発見ステップを記載したフローチャートである。
【符号の説明】
【００３５】
１２：ＣＰＵ、１６：キャッシュメモリ、１８：主メモリ、２０：システムコントロール、２４：ＲＯＭ、２６：周辺機器。
【特許請求の範囲】
【請求項１】
処理装置で読取可能に表現した電子地図を有するネットワークを使用して始点と終点の間の経路を発見する、コンピュータによって実施される方法であって、
前記ネットワークにおける１つ以上の要素の第１集合を識別するステップと、
前記要素の第１集合の第１要素に関連する第１コストを作成するステップであって、前記第１コストは配列として記憶され、少なくとも２つの表現のレベルを有し、該少なくとも２つの表現レベルは第１と第２のレベルを有し、該第２レベルは該第１レベルよりも優先される、ステップと、
０以外の大きさを有するコスト情報が、前記第１レベルより高位の表現レベルに挿入されるように、前記配列にデータを挿入するステップと、
前記第１コストを使用し、前記処理装置で読み取り可能に表現したネットワーク内で始点から終点への経路を決定するために、前記処理装置を使用するステップと、
を有するコンピュータによって実施される方法。
【請求項２】
請求項１に記載の方法であって、前記要素の第１集合がリンクの集合である方法。
【請求項３】
請求項１又は２に記載の方法であって、前記要素の第１集合が複数の有料道路を表すリンクの集合である方法。
【請求項４】
請求項１に記載の方法であって、前記要素の第１集合が一つの有料道路を表すリンクである方法。
【請求項５】
請求項１乃至４の中の１に記載の方法であって、前記識別するステップが、ユーザからの入力を受け取ることを含み、前記入力に基づき前記第１集合の要素を特定することを含む方法。
【請求項６】
請求項１乃至5の中の１に記載の方法であって、前記作成するステップが、既存のコストを前記第１コストと置き換えることを含み、前記既存のコストは第１の表現のレベルのみ含む、方法。
【請求項７】
請求項１乃至６の中の１に記載の方法であって、更に、
前記第１集合の前記要素に関連する追加コストを作成するステップであって、前記追加コストは少なくとも二つの表現のレベルを含むステップ、
を含む方法。
【請求項８】
請求項１乃至７の中の１に記載の方法であって、前記第２の表現レベルを有するコストは、前記第１の表現レベルを有するコストよりも常に大きい、方法。
【請求項９】
請求項１乃至８の中の１に記載の方法であって、更に
回避するために前記電子地図内の１以上の要素の第２のセットを識別するステップと、
前記要素の第２のセットの第１の要素に関連する第２のコストを作成するステップであって、前記第２のコストは少なくとも３つの表現のレベルを有する、ステップと、
前記第２のコストを使用するステップと、有する、
方法。
【請求項１０】
請求項９に記載の方法であって、前記第２のコストは前記第１のコストよりも大きく、第３の表現のレベルを有するコストは常に第２の表現のレベルのみを有するコストよりも大きい、
方法。
【請求項１１】
請求項１乃至１０の中の１に記載の方法であって、前記第１コストは非標準型数字である方法。
【請求項１２】
請求項１乃至１１の中の１に記載の方法であって、前記第１コストは無限整数の０以外の倍数で表すことができる方法。
【請求項１３】
請求項１乃至１2の中の１に記載の方法であって、前記第１コストは複数要素のデータ構造内に記憶される方法。
【請求項１４】
請求項１乃至１３の中の１に記載の方法であって、前記経路は、コストの最小化を試みることにより決定される、方法。
【請求項１５】
請求項１４に記載の方法であって、経路を決定するために処理装置を使用することは、
優先キューおよび訪問済みリストをセットアップするステップであって、前記優先キューがノードの識別記号およびキーを記憶し、前記訪問済みリストがノード識別記号および始点からの移動のコストを記憶するステップと、
前記優先キューを初期化するステップと、
前記始点に隣接するノードの集合を発見するステップと、
前記始点から前記隣接ノードの各々までの移動のコストを決定するステップと、
前記隣接ノードをキーでソートされた前記優先キューに挿入するステップと、
前記隣接ノードを前記訪問済みリストに挿入するステップと、
前記優先キューから前記始点を取り除くステップと、
前記キューの先頭のノードに隣接するノードの集合を発見するステップと、
少なくとも前記キューの先頭のノードに隣接する前記ノードの部分集合を前記優先キューに挿入するステップと、
前記優先キューの先頭のノードに隣接する前記ノードが、より低いコストを有して前記訪問済みリスト中にまだ存在しない場合に、前記ノードを前記訪問済みリストに挿入するステップと
前記優先キューから前記キューの先頭のノードを取り除くステップと、
を含む方法。
【請求項１６】
請求項１乃至１５の中の１に記載の方法であって、
前記第１要素はリンクの集合を表し、前記第１レベルが前記集合における前記リンクの数を表している方法。
【請求項１７】
請求項１乃至１６の中の１に記載の方法であって、
前記第１レベルの大きさおよび前記第２レベルの大きさの合計が、最小化される見積もり量を含む、方法。
【請求項１８】
請求項１乃至１7の中の１に記載の方法であって、更に
前記経路を報告するステップを含む方法。
【請求項１９】
請求項１乃至１８の中の１に記載の方法であって、更に、
前記始点の表示を受け取るステップを含む方法。
【請求項２０】
請求項１乃至１９の中の１に記載の方法であって、更に、
前記終点の表示を受け取るステップを含む方法。
【請求項２１】
処理装置で読取可能に表現した電子地図を含むネットワークを使用して始点と終点の間の経路を発見するための装置であって、
入力装置と、
前記処理装置で読取可能に表現したネットワークの少なくとも一部を記憶することが可能な処理装置で読取可能な記憶装置と、
表示装置と、
前記入力装置と前記記憶装置と前記表示装置と通じている処理装置と、を含み、該処理装置は、
前記要素の第１集合の第１要素に関連する第１コストを作成し、前記第１コストは配列として記憶され、少なくとも２つの表現のレベルを有し、該少なくとも２つの表現レベルは第１と第２のレベルを有し、該第２レベルは該第１レベルよりも優先され、
０以外の大きさを有するコスト情報が、前記第１レベルより高位の表現レベルに挿入されるように、前記配列にデータを挿入し、
前記第１コストを使用し、前記処理装置で読み取り可能に表現したネットワーク内で始点から終点への経路を決定するために、前記処理装置を使用する、
ようにプログラムされている、
経路を発見するための装置。
【請求項２２】
請求項２１に記載の装置であって、前記処理装置は、
前記始点の表示を受け取り、前記終点の表示を受け取り、前記経路を報告するようにプログラムされている装置。
【請求項２３】
電子地図を作成する方法であって、
ノードを特定するステップと、
ノード間のリンクの集合を特定するステップと；
回避を試みるためにリンクの第１の部分集合を特定するステップと；
前記リンクの集合を移動するためのコストを割り当てるステップであって、１以上のコストのうち少なくとも第１の部分集合が表現の第１レベルおよび表現の第２レベルを含み、前記表現の第２レベルは前記表現の第１レベルよりも優先され、前記１以上のコストの第１の部分集合は前記リンクの第１の部分集合と関連するステップと；
前記ノード、前記リンク、および前記コストを表すデータを地図データベース内に記憶するステップであって、前記地図データベースは処理装置で読取可能な記憶装置内にあるステップと、
を含む方法。
【請求項２４】
電子地図データベースの機能を高める方法であって、
前記地図データベースはノード、ノード間のリンク、およびリンクのコストを含み、
回避を試みるためのリンクの集合を特定する入力を受け取るステップと；
前記リンクの集合についてのコストの第２レベルの表示を作成するステップと；
前記コストの第２レベルの表示を処理装置で読取可能な記憶媒体に記憶するステップであって、前記記憶されたコストの第２レベルは前記電子地図データベースと関連しており、その結果前記電子地図データベースと前記コストの第２レベルは前記電子地図データベース内における始点から終点までの経路を決定するために使用可能となり、前記リンクの集合の回避を試みる、ステップと、
を含む方法。
【請求項２５】
処理装置で読取可能なプログラムコードが組み込まれている、処理装置で読取可能な記憶媒体であって、前記処理装置で読取可能なコードは、処理装置で読取可能に表現したネットワークを使用して経路を発見するための方法を実行する処理装置をプログラミングするためのものであり、
第１ノードから第２ノードまでの第１の経路を発見する第１プログラムコードであって、前記第１経路が１以上のリンクの第１集合および１以上のコストの第１集合を含んでいる第１プログラムコードと、
前記第１ノードから前記第２ノードまでの第２経路を発見する第２プログラムコードであって、前記第２経路が１以上のリンクの第２集合および１以上のコストの第２集合を含み、前記コストの第２集合の内の少なくとも一つが少なくとも二つの表現のレベルを有している第２プログラムコードと、
前記１以上のコストの第１集合が前記１以上のコストの第２集合よりも効率的であるとの理由に基づき、前記第１経路を選択する第３プログラムコードと、
を含む処理装置で読取可能な記憶媒体。
【請求項１】
処理装置で読取可能に表現した電子地図を有するネットワークを使用して始点と終点の間の経路を発見する、コンピュータによって実施される方法であって、
前記ネットワークにおける１つ以上の要素の第１集合を識別するステップと、
前記要素の第１集合の第１要素に関連する第１コストを作成するステップであって、前記第１コストは配列として記憶され、少なくとも２つの表現のレベルを有し、該少なくとも２つの表現レベルは第１と第２のレベルを有し、該第２レベルは該第１レベルよりも優先される、ステップと、
０以外の大きさを有するコスト情報が、前記第１レベルより高位の表現レベルに挿入されるように、前記配列にデータを挿入するステップと、
前記第１コストを使用し、前記処理装置で読み取り可能に表現したネットワーク内で始点から終点への経路を決定するために、前記処理装置を使用するステップと、
を有するコンピュータによって実施される方法。
【請求項２】
請求項１に記載の方法であって、前記要素の第１集合がリンクの集合である方法。
【請求項３】
請求項１又は２に記載の方法であって、前記要素の第１集合が複数の有料道路を表すリンクの集合である方法。
【請求項４】
請求項１に記載の方法であって、前記要素の第１集合が一つの有料道路を表すリンクである方法。
【請求項５】
請求項１乃至４の中の１に記載の方法であって、前記識別するステップが、ユーザからの入力を受け取ることを含み、前記入力に基づき前記第１集合の要素を特定することを含む方法。
【請求項６】
請求項１乃至5の中の１に記載の方法であって、前記作成するステップが、既存のコストを前記第１コストと置き換えることを含み、前記既存のコストは第１の表現のレベルのみ含む、方法。
【請求項７】
請求項１乃至６の中の１に記載の方法であって、更に、
前記第１集合の前記要素に関連する追加コストを作成するステップであって、前記追加コストは少なくとも二つの表現のレベルを含むステップ、
を含む方法。
【請求項８】
請求項１乃至７の中の１に記載の方法であって、前記第２の表現レベルを有するコストは、前記第１の表現レベルを有するコストよりも常に大きい、方法。
【請求項９】
請求項１乃至８の中の１に記載の方法であって、更に
回避するために前記電子地図内の１以上の要素の第２のセットを識別するステップと、
前記要素の第２のセットの第１の要素に関連する第２のコストを作成するステップであって、前記第２のコストは少なくとも３つの表現のレベルを有する、ステップと、
前記第２のコストを使用するステップと、有する、
方法。
【請求項１０】
請求項９に記載の方法であって、前記第２のコストは前記第１のコストよりも大きく、第３の表現のレベルを有するコストは常に第２の表現のレベルのみを有するコストよりも大きい、
方法。
【請求項１１】
請求項１乃至１０の中の１に記載の方法であって、前記第１コストは非標準型数字である方法。
【請求項１２】
請求項１乃至１１の中の１に記載の方法であって、前記第１コストは無限整数の０以外の倍数で表すことができる方法。
【請求項１３】
請求項１乃至１2の中の１に記載の方法であって、前記第１コストは複数要素のデータ構造内に記憶される方法。
【請求項１４】
請求項１乃至１３の中の１に記載の方法であって、前記経路は、コストの最小化を試みることにより決定される、方法。
【請求項１５】
請求項１４に記載の方法であって、経路を決定するために処理装置を使用することは、
優先キューおよび訪問済みリストをセットアップするステップであって、前記優先キューがノードの識別記号およびキーを記憶し、前記訪問済みリストがノード識別記号および始点からの移動のコストを記憶するステップと、
前記優先キューを初期化するステップと、
前記始点に隣接するノードの集合を発見するステップと、
前記始点から前記隣接ノードの各々までの移動のコストを決定するステップと、
前記隣接ノードをキーでソートされた前記優先キューに挿入するステップと、
前記隣接ノードを前記訪問済みリストに挿入するステップと、
前記優先キューから前記始点を取り除くステップと、
前記キューの先頭のノードに隣接するノードの集合を発見するステップと、
少なくとも前記キューの先頭のノードに隣接する前記ノードの部分集合を前記優先キューに挿入するステップと、
前記優先キューの先頭のノードに隣接する前記ノードが、より低いコストを有して前記訪問済みリスト中にまだ存在しない場合に、前記ノードを前記訪問済みリストに挿入するステップと
前記優先キューから前記キューの先頭のノードを取り除くステップと、
を含む方法。
【請求項１６】
請求項１乃至１５の中の１に記載の方法であって、
前記第１要素はリンクの集合を表し、前記第１レベルが前記集合における前記リンクの数を表している方法。
【請求項１７】
請求項１乃至１６の中の１に記載の方法であって、
前記第１レベルの大きさおよび前記第２レベルの大きさの合計が、最小化される見積もり量を含む、方法。
【請求項１８】
請求項１乃至１7の中の１に記載の方法であって、更に
前記経路を報告するステップを含む方法。
【請求項１９】
請求項１乃至１８の中の１に記載の方法であって、更に、
前記始点の表示を受け取るステップを含む方法。
【請求項２０】
請求項１乃至１９の中の１に記載の方法であって、更に、
前記終点の表示を受け取るステップを含む方法。
【請求項２１】
処理装置で読取可能に表現した電子地図を含むネットワークを使用して始点と終点の間の経路を発見するための装置であって、
入力装置と、
前記処理装置で読取可能に表現したネットワークの少なくとも一部を記憶することが可能な処理装置で読取可能な記憶装置と、
表示装置と、
前記入力装置と前記記憶装置と前記表示装置と通じている処理装置と、を含み、該処理装置は、
前記要素の第１集合の第１要素に関連する第１コストを作成し、前記第１コストは配列として記憶され、少なくとも２つの表現のレベルを有し、該少なくとも２つの表現レベルは第１と第２のレベルを有し、該第２レベルは該第１レベルよりも優先され、
０以外の大きさを有するコスト情報が、前記第１レベルより高位の表現レベルに挿入されるように、前記配列にデータを挿入し、
前記第１コストを使用し、前記処理装置で読み取り可能に表現したネットワーク内で始点から終点への経路を決定するために、前記処理装置を使用する、
ようにプログラムされている、
経路を発見するための装置。
【請求項２２】
請求項２１に記載の装置であって、前記処理装置は、
前記始点の表示を受け取り、前記終点の表示を受け取り、前記経路を報告するようにプログラムされている装置。
【請求項２３】
電子地図を作成する方法であって、
ノードを特定するステップと、
ノード間のリンクの集合を特定するステップと；
回避を試みるためにリンクの第１の部分集合を特定するステップと；
前記リンクの集合を移動するためのコストを割り当てるステップであって、１以上のコストのうち少なくとも第１の部分集合が表現の第１レベルおよび表現の第２レベルを含み、前記表現の第２レベルは前記表現の第１レベルよりも優先され、前記１以上のコストの第１の部分集合は前記リンクの第１の部分集合と関連するステップと；
前記ノード、前記リンク、および前記コストを表すデータを地図データベース内に記憶するステップであって、前記地図データベースは処理装置で読取可能な記憶装置内にあるステップと、
を含む方法。
【請求項２４】
電子地図データベースの機能を高める方法であって、
前記地図データベースはノード、ノード間のリンク、およびリンクのコストを含み、
回避を試みるためのリンクの集合を特定する入力を受け取るステップと；
前記リンクの集合についてのコストの第２レベルの表示を作成するステップと；
前記コストの第２レベルの表示を処理装置で読取可能な記憶媒体に記憶するステップであって、前記記憶されたコストの第２レベルは前記電子地図データベースと関連しており、その結果前記電子地図データベースと前記コストの第２レベルは前記電子地図データベース内における始点から終点までの経路を決定するために使用可能となり、前記リンクの集合の回避を試みる、ステップと、
を含む方法。
【請求項２５】
処理装置で読取可能なプログラムコードが組み込まれている、処理装置で読取可能な記憶媒体であって、前記処理装置で読取可能なコードは、処理装置で読取可能に表現したネットワークを使用して経路を発見するための方法を実行する処理装置をプログラミングするためのものであり、
第１ノードから第２ノードまでの第１の経路を発見する第１プログラムコードであって、前記第１経路が１以上のリンクの第１集合および１以上のコストの第１集合を含んでいる第１プログラムコードと、
前記第１ノードから前記第２ノードまでの第２経路を発見する第２プログラムコードであって、前記第２経路が１以上のリンクの第２集合および１以上のコストの第２集合を含み、前記コストの第２集合の内の少なくとも一つが少なくとも二つの表現のレベルを有している第２プログラムコードと、
前記１以上のコストの第１集合が前記１以上のコストの第２集合よりも効率的であるとの理由に基づき、前記第１経路を選択する第３プログラムコードと、
を含む処理装置で読取可能な記憶媒体。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００９−４２２４３（Ｐ２００９−４２２４３Ａ）
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願番号】特願２００８−２７３７７９（Ｐ２００８−２７３７７９）
【出願日】平成２０年１０月２４日（２００８．１０．２４）
【分割の表示】特願平１０−５２４６５４の分割
【原出願日】平成９年１０月２９日（１９９７．１０．２９）
【出願人】（５００３７９３０３）テレ アトラス ノース アメリカ インコーポレイテッド (3)
【Ｆターム（参考）】
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願日】平成２０年１０月２４日（２００８．１０．２４）
【分割の表示】特願平１０−５２４６５４の分割
【原出願日】平成９年１０月２９日（１９９７．１０．２９）
【出願人】（５００３７９３０３）テレ アトラス ノース アメリカ インコーポレイテッド (3)
【Ｆターム（参考）】
[ Back to top ]