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

森畑明昌; 松崎公紀; 武市正人

文献

J-GLOBAL ID：201102223098464440 整理番号：11A1900664

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

Optimal Path Querying Based on a Domain-specific Language

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=11A1900664&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=11A1900664&from=J-GLOBAL&jstjournalNo=L7379A") }}

著者 (3件)： , ,
資料名：
巻： 2010 号： 2 ページ： ROMBUNNO.PUROGURAMINGU,VOL.4,NO.2,116-133 発行年： 2011年04月15日
JST資料番号： L7379A ISSN： 1882-7772 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：日本語 (JA)

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

, , , , , , , , , ,
,

ネットワーク法 , 数理言語学 , 汎用プログラミング言語

引用文献 (45件)：

1) Arnborg, S., Lagergren, J. and Seese, D.: Easy Problems for Tree-Decomposable Graphs, Journal of Algorithms, Vol.12, No.2, pp.308-340 (1991).
2) Barrett, C.L., Bisset, K., Jacob, R., Konjevod, G. and Marathe, M.V.: Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router, Algorithms ・ Proc. ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Lecture Notes in Computer Science, Vol.2461, pp.126-138, Springer (2002).
3) Barrett, C.L., Jacob, R. and Marathe, M.V.: Formal-Language-Constrained Path Problems, SIAM Journal on Computing, Vol.30, No.3, pp.809-837 (2000).
4) Bellman, R.: Dynamic Programming, Princeton University Press (1957).
5) Bird, R.S.: Maximum marking problems, Journal of Functional Programming, Vol.11, No.4, pp.411-424 (2001).

, ,

前のページに戻る