領域限定言語に基づく最適経路問合せ

概要

論文の詳細を見る
グラフ中の最短経路を求める問題,またはより一般に何らかの意味で最適な経路を求める問題は,非常に多くの応用を持つ重要な問題である.そのため,最短経路問題やその変種はさかんに議論され,様々なアルゴリズムが提案されてきた.しかし,これらの成果はアルゴリズムになじみのない人には利用が難しい.自分の解きたい問題に応じて適切にアルゴリズムを選択するのは一般に難しく,またそれぞれのアルゴリズムに効率の良い実装を与えるのも容易でない.本論文では,領域限定言語に基づいた最適経路問合せ手法を提案する.提案手法では,発見したい最適経路の仕様を領域限定言語によって記述する.この言語は,その記述から最適経路問合せを行う効率の良いアルゴリズムが機械的に導出できるよう設計されている.また,この言語では最適経路問合せに関する既知の問題クラスの多くを自然に記述できる.よって,アルゴリズムに関する知識をまったく要することなく広い範囲の最短経路問合せを効率良く行うことができる.我々は実際に提案手法を実装した.このシステムは,最適経路の仕様記述をもとに,効率の良い最適経路問合せを行うプログラムを出力する.最短経路問題の実装に関する既知の成果を利用し,また最適経路問合せに特有のいくつかの効率化を加えることにより,我々のシステムによる最適経路問合せは,既存のライブラリに比べても,その利用が簡便であるだけでなく実行効率も良いことが確認された.
2011-03-25

領域限定言語に基づく最適経路問合せ

スポンサーリンク

概要

著者

関連論文

スポンサーリンク