Path Finding Algorithms Based on the Hierarchical Representation of a Road Map and Its Application to a Map Information System

IPSJ 7 Citations

Bibliographic Information

Other Title
  • 道路網の階層的表現にもとづく経路探索アルゴリズムと地図情報システムへの応用
  • 数理計画法

Search this article

Description

地図には 道路網 地名 町名 建物 鉄道 河川など種々の情報が示されている.最近 これらの地図情報のデータベース化がいろいろな目的に合わせて進められている.本論文では これらの地図情報のうちで道路網をとりあげ これを 階層化して表現する.これにもとづき 各種の経路探索問題に対して Dijkstra のアルゴリズムを基本にした より効率的なアルゴリズムを構成する.道路網の階層としては 町内の道路のような生活道路 表通りあるいは幹線道路 (パス通りなど) 高速道路 国道などを基準として考える.全体の道路網を一様に扱うと 道路網のデータが大規模になるのみならず 最短経路探索の手間が極めて大きくなる.これに対して 本論文で述べる 道路の階層性を考慮した手法によれば 完全な意味での最短ではなくて むしろ 人の直感に合った意味でのある種の最適経路を効率よく求めることができる.本論文では このような考え方にもとづいた道路網データの表現法と その上での最適経路探索アルゴリズム およびこれらを応用して構成された地図情報の検索システムについて述べる.

Journal

Citations (7)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top