【手続補正書】
【提出日】平成23年9月13日(2011.9.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置において、
ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルと、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定手段と、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索手段と、
前記経路探索手段が展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力手段と、を備え、
前記経路探索手段は、前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照してさらに前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことに加えて片方のノード番号を読み出すものであり、該片方のノード番号が、前記さらに読み出されたもう一方のノード番号の直前に読み出されたもう一方のノード番号と一致しないときには、前記さらに読み出されたもう一方のノードの接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索装置。
【請求項２】
請求項１に記載のネットワーク経路探索装置において、
さらに前記経路探索手段は、前記接続先リンク番号により参照したリンク接続先テーブルに前記もう一方のノードの接続先リンク番号が存在しないとき、該接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索装置。
【請求項３】
請求項１又は請求項２に記載のネットワーク経路探索装置において、
前記ネットワークは道路網をモデル化したものであることを特徴とするネットワーク経路探索装置。
【請求項４】
請求項３記載のネットワーク経路探索装置を備えたことを特徴とするカーナビゲーション装置。
【請求項５】
請求項４記載のカーナビゲーション装置を備えたことを特徴とする車両。
【請求項６】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルを備えたネットワーク経路探索装置によるネットワーク経路探索方法において、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定ステップと、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索ステップと、
前記経路探索ステップで展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力ステップと、を備え、
前記経路探索ステップは、前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照してさらに前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことに加えて片方のノード番号を読み出すものであり、該片方のノード番号が、前記さらに読み出されたもう一方のノード番号の直前に読み出されたもう一方のノード番号と一致しないときには、前記さらに読み出されたもう一方のノードの接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索方法。
【請求項７】
請求項６に記載のネットワーク経路探索方法において、
さらに前記経路探索ステップは、前記接続先リンク番号により参照したリンク接続先テーブルに前記もう一方のノードの接続先リンク番号が存在しないとき、該接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索方法。
【請求項８】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルを備えたネットワーク経路探索装置の機能をコンピュータに実現させるネットワーク経路探索プログラムにおいて、
コンピュータに
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定機能、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索機能であって、前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照してさらに前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことに加えて片方のノード番号を読み出すものであり、該片方のノード番号が、前記さらに読み出されたもう一方のノード番号の直前に読み出されたもう一方のノード番号と一致しないときには、前記さらに読み出されたもう一方のノードの接続先リンク番号による経路展開は行わない経路探索機能、
前記経路探索機能が展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力機能、
を実現させるためのネットワーク経路探索プログラム。
【請求項９】
請求項８に記載のネットワーク経路探索プログラムにおいて、
さらに前記経路探索機能は、前記接続先リンク番号により参照したリンク接続先テーブルに前記もう一方のノードの接続先リンク番号が存在しないとき、該接続先リンク番号による経路展開は行わないものであることを特徴とするネットワーク経路探索プログラム。
【請求項１０】
請求項８又は請求項９に記載のネットワーク経路探索プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
このリンクＬ４への接続については、経路展開なし２４４ａの点線の矢印で示しているように、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂのＢ端のノード番号２３７に設定されているノード番号がＮ４であって、接続元のリンクＬ３のＢ端のノードＮ４に戻るので、最小コスト計算に不要な経路であることは自明であるから、ここでは経路展開を打ち切る。なお、接続先のリンクのＡ端のノードかＢ端のノードのどちらか一方は接続元のリンクのＢ端のノードと一致する。そして、同一のリンクのＡ端のノードとＢ端のノードが一致することはないから、経路展開の打ち切りの判定は、接続先のリンクのＡ端のノードが接続元のリンクのＢ端のノードと一致するかにより行うことができる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
ステップＳ８１３では、経路情報の接続数に１を加え、累積コストに接続コストとステップＳ８１１で読み出したリンク接続先テーブルのＢ端へのコストを加えると共に、経路情報の経路リストの書込位置に次のノード番号と接続先リンク番号を書き込み、書込位置を更新する。ここで接続コストは、図８Ａに示すステップＳ８０４で初期設定されているか、あるいは後記ステップＳ８１８で設定されたものである。また、経路情報は、図７の（ｂ）に示す経路情報テーブル２８１の１行分の項目を持つ一時記憶領域である。具体例における最初の処理では、経路情報の接続数と累積コストには、図８Ａに示すステップＳ８０２で値“−１”と“０”がそれぞれ初期設定されており、リンク接続先テーブルの初期化されたリンク情報の読出位置のＢ端へのコスト２３４ａには１が格納されているので、経路情報の接続数と累積コストは、それぞれ０と１になる。また、経路情報の経路リストの先頭位置に、図８Ａに示すステップＳ８０２とステップＳ８０３で初期設定されている次のノード番号Ｎ１と接続先リンク番号Ｌ１が書き込まれる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】変更
【補正の内容】
【００８１】
一方、ステップＳ８１５で接続先リンク情報が存在すると判定されるとステップＳ８１６に進み、次のノード番号にＢ端のノード番号を設定し、ステップＳ８１７において、リンク情報の読出位置に、リンク接続先テーブルのＢ端のノードの接続先リンク情報の先頭位置を設定する。このリンク情報の読出位置の設定により、経路探索の優先順位が決定され、具体例の経路探索ツリーについて説明したように、ツリーの右側優先で経路が探索される。
ステップＳ８１７に続いてステップＳ８１８で、リンク情報の読出位置の指すリンク接続先テーブルのＢ端のノードの接続先リンク情報より、接続先リンク番号と接続コストを取り出して設定する。具体例における最初の処理では、Ｂ端のノードの接続先リンク情報からリンク２３８ａとコスト２３９ａとして格納されているＬ２と１が取り出され、接続先リンク番号と接続先コストに設定され、ステップＳ８１０に戻る。
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図８Ｂ
【補正方法】変更
【補正の内容】
【図８Ｂ】
2010071767.tif 000001