最短経路探索方法

発明者： , ,
出願人/特許権者：
代理人 (2件)：清水守 , 川合誠
公報種別：公開公報
出願番号（国際出願番号）：特願2007-158176
公開番号（公開出願番号）：特開2008-309665
出願日： 2007年06月15日
公開日（公表日）： 2008年12月25日
要約：

【課題】幾何学的な構造を用いた前処理を行い、探索を速め、スケーラビリティとグラフの疎化に優れた最短経路探索方法を提供する。【解決手段】最短経路探索方法において、第1の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、各メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第2の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第2の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、この最短経路を出力する。【選択図】図1

請求項（抜粋）：

(a)第1の外部記憶装置から地図情報を主記憶装置に読み込み、 (b)前記地図情報に基づきメッシュの形状、該メッシュを含む領域である外領域の設定を行い、 (c)各メッシュの疎化ネットワークの構築を行い、 (d)第2の外部記憶装置に記憶し、 (e)始点と終点の位置情報を入力し、 (f)前記始点と前記終点の両者を外領域に含まないメッシュを集め、 (g)該メッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、 (h)前記残った極大なメッシュの境界をまたぐ利用枝を探索し、 (i)該探索した利用枝で前記メッシュをつなぎ、前記第2の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、 (j)該求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力することを特徴とする最短経路探索方法。

IPC (3件)：

G01C 21/00 , G08G 1/096 , G09B 29/10

FI (3件)：

G01C21/00 G , G08G1/0969 , G09B29/10 A

Fターム (12件)：

2C032HB03 , 2C032HD16 , 2C032HD21 , 2F129AA02 , 2F129AA03 , 2F129CC15 , 2F129CC16 , 2F129DD02 , 2F129DD62 , 5H180AA01 , 5H180AA21 , 5H180FF14

引用特許：

出願人引用 (3件)

特許第3244517号公報
特許第3186794号公報
特許第3085054号公報

審査官引用 (4件)

経路計算機能を有するナビゲーション装置
公報種別：公開公報出願番号：特願平5-109646 出願人：住友電気工業株式会社
経路選出方法およびシステム
公報種別：公開公報出願番号：特願平8-259747 出願人：松下電器産業株式会社
経路設定装置およびナビゲーション装置
公報種別：公開公報出願番号：特願2003-421321 出願人：株式会社デンソー

全件表示

前のページに戻る