特許

J-GLOBAL ID：200903098714693544

経路探索装置および方法

発明者： 白川 貴久
出願人/特許権者： 日本電気株式会社
代理人 (1件)： 加藤 朝道
公報種別：公開公報
出願番号（国際出願番号）：特願平9-187733
公開番号（公開出願番号）：特開平11-023303
出願日： 1997年06月27日
公開日（公表日）： 1999年01月29日
要約：

【要約】【課題】少量の追加データでグラフ構造の最小コスト経路探索の探索範囲限定を行う経路探索装置の提供。【解決手段】各ノード間の最小経路コストを求め、それを相違度として数値化4類にて各ノードの仮想座標を求める。再度全対問題を解く過程で、仮想座標上での出発点と到達点との領域を迂回する最大量と、経路中の各アークのうち、到達点と逆方向に進む、後戻り量の最大量を求める。求めた、迂回量と後戻り量をしきい値として記憶し、最小コスト経路探索を行う際に探索範囲を限定する。

請求項（抜粋）：

与えられたグラフについて経路を探索し、与えられた2つのノードを結ぶ最小コスト経路を出力する経路探索装置において、ノードの仮想座標値を記憶する仮想座標記憶手段と、ノードとノード間を結ぶアークからなるネットワーク構造を記憶するグラフ構造記憶手段と、前記グラフ構造記憶手段よりグラフ構造を逐次読み出して、探索の対象範囲を探索処理の途中状態として記憶する探索範囲記憶手段と、前記探索範囲記憶手段に対して探索範囲を逐次読み出し、書き出しを行いながら、与えられた出発点ノードから到達点ノードに至る最短コスト経路を探索する経路探索手段と、迂回量を記憶する第1のしきい値記憶手段と、前記仮想座標記憶手段に記憶された、出発点ノードの仮想座標と、到達点ノードの仮想座標とで定まる領域を、前記第1のしきい値記憶手段に記憶された、迂回量のしきい値以上に逸脱する仮想座標を持つノードを経由する経路を、前記探索範囲記憶手段から削除する探索範囲限定手段と、を備えたことを特徴とする経路探索装置。

IPC (5件)：

G01C 21/00 ,  G06F 17/30 ,  G06F 17/50 ,  H04L 12/56 ,  H04Q 3/00 101

FI (5件)：

G01C 21/00 G ,  H04Q 3/00 101 ,  G06F 15/40 500 N ,  G06F 15/60 650 A ,  H04L 11/20 102 D

引用特許：

審査官引用 (1件)

• 経路計算方法及び装置
  公報種別：公開公報   出願番号：特願平5-248243   出願人：住友電気工業株式会社