@article{oai:kutarr.kochi-tech.ac.jp:00000226,
 author = {森畑, 明昌 and 松崎, 公紀 and 武市, 正人},
 issue = {2},
 journal = {情報処理学会論文誌 プログラミング},
 month = {},
 note = {グラフ中の最短経路を求める問題，またはより一般に何らかの意味で最適な経路を求める問題は，非常に多くの応用を持つ重要な問題である．そのため，最短経路問題やその変種はさかんに議論され，様々なアルゴリズムが提案されてきた．しかし，これらの成果はアルゴリズムになじみのない人には利用が難しい．自分の解きたい問題に応じて適切にアルゴリズムを選択するのは一般に難しく，またそれぞれのアルゴリズムに効率の良い実装を与えるのも容易でない．本論文では，領域限定言語に基づいた最適経路問合せ手法を提案する．提案手法では，発見したい最適経路の仕様を領域限定言語によって記述する．この言語は，その記述から最適経路問合せを行う効率の良いアルゴリズムが機械的に導出できるよう設計されている．また，この言語では最適経路問合せに関する既知の問題クラスの多くを自然に記述できる．よって，アルゴリズムに関する知識をまったく要することなく広い範囲の最短経路問合せを効率良く行うことができる．我々は実際に提案手法を実装した．このシステムは，最適経路の仕様記述をもとに，効率の良い最適経路問合せを行うプログラムを出力する．最短経路問題の実装に関する既知の成果を利用し，また最適経路問合せに特有のいくつかの効率化を加えることにより，我々のシステムによる最適経路問合せは，既存のライブラリに比べても，その利用が簡便であるだけでなく実行効率も良いことが確認された．The problem to find the shortest path in a graph, or those to find the optimal path according to some criterion of optimality, are very important because of their numerous applications, and there are many studies on this topic. However, algorithmic results on solving optimal path problems are not very accessible for nonspecialists. It is difficult to choose an algorithm that enables us to achieve our objective, and moreover, its efficient implementation should be nontrivial. In this paper, we propose a method of optimal path querying. Our method is based on a domain specific language. The language is designed so that we can mechanically derive an efficient algorithm to find the described path. Therefore, we can efficiently find the optimal path with little algorithmic knowledge. Describing the specification of desirable paths by the language suffices. We implemented the method as an optimal path querying system. The system generates a program code for optimal path querying from the description of the optimal path. By virtue of a known efficient implementation of shortest path problems and our careful tuning, our system is not only easier to use but also more efficient than an existing library.},
 pages = {116--133},
 title = {領域限定言語に基づく最適経路問合せ},
 volume = {4},
 year = {2011}
}