真に実用的な最短経路アルゴリズム

点击翻译按钮获取中文摘要

現在の自動車社会において,目的地まで渋滞を避つつ時間的もしくは距離的に最短な経路を見つけることは,日常生活をする上で重要な問題である.また,渋滞,工事,事故による通行止め,車線規制などは,リアルタイムに変化するものであり,VICSなどの普及によりリアルタイムに入手できる時代になっている。一方、計算幾何学の分野では、現実社会で利用できるかのような最短経路問題を解くアルゴリズムが数多く提案されている.しかし,提案されているアルゴリズムを現実社会に適用するには,-入力誤差,入力サイズの大きさによる問題-アルゴリズムの停止性を保証できないといった大きな問題があるように思われる.しかしながら,現実社会ではGPSを利用し,最短経路をリアルタイムに探索するナビゲーションシステムが実用化し普及している。ナビゲーションシステムにおいては,真に最短であることを保証する必要がないために近似的解法,ヒューリスティックなどの導入で十分実用的であるとはいえる.しかしながら,計算幾何学での研究結果と現実社会での解決方法のギャップが大きすぎるように思われる.このギャップを埋めるために,誤差に強いアルゴリズムの開発,オーダに惑わされない現実社会に則したアルゴリズムの評価法が大切である.そこで誤差を考慮した最短経路アルゴリズムを開発するにあたって、計算幾何学で基本的な問題である凸包問題をとりあげ、1つの結果を得た。この結果をもとに、最短経路問題を解くためにいくつかの解決すべき点を洗い出した。