| Item type |
学術雑誌論文 / Journal Article(1) |
| 公開日 |
2016-03-25 |
| タイトル |
|
|
タイトル |
領域限定言語に基づく最適経路問合せ |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者 |
森畑, 明昌
松崎, 公紀
武市, 正人
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
グラフ中の最短経路を求める問題，またはより一般に何らかの意味で最適な経路を求める問題は，非常に多くの応用を持つ重要な問題である．そのため，最短経路問題やその変種はさかんに議論され，様々なアルゴリズムが提案されてきた．しかし，これらの成果はアルゴリズムになじみのない人には利用が難しい．自分の解きたい問題に応じて適切にアルゴリズムを選択するのは一般に難しく，またそれぞれのアルゴリズムに効率の良い実装を与えるのも容易でない．本論文では，領域限定言語に基づいた最適経路問合せ手法を提案する．提案手法では，発見したい最適経路の仕様を領域限定言語によって記述する．この言語は，その記述から最適経路問合せを行う効率の良いアルゴリズムが機械的に導出できるよう設計されている．また，この言語では最適経路問合せに関する既知の問題クラスの多くを自然に記述できる．よって，アルゴリズムに関する知識をまったく要することなく広い範囲の最短経路問合せを効率良く行うことができる．我々は実際に提案手法を実装した．このシステムは，最適経路の仕様記述をもとに，効率の良い最適経路問合せを行うプログラムを出力する．最短経路問題の実装に関する既知の成果を利用し，また最適経路問合せに特有のいくつかの効率化を加えることにより，我々のシステムによる最適経路問合せは，既存のライブラリに比べても，その利用が簡便であるだけでなく実行効率も良いことが確認された．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. |
| 書誌情報 |
情報処理学会論文誌 プログラミング
巻 4,
号 2,
p. 116-133,
発行日 2011
|
| 権利 |
|
|
権利情報 |
ここに掲載した著作物の利用に関する注意 本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 |
| 権利 |
|
|
権利情報 |
Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. |
| 著者版フラグ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| 出版者 |
|
|
出版者 |
情報処理学会 |
27-27.pdf (429.1 kB)
