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

• Item type: Trans(1)
• 公開日: 2011-03-25
• タイトル: 領域限定言語に基づく最適経路問合せ
• タイトル / 言語: en
• タイトル: Optimal Path Querying Based on a Domain-specific Language
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東北大学電気通信研究所
• 著者所属: 高知工科大学情報学群
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communications, Tohoku University
• 著者所属(英): en
• 著者所属(英): School of Information, Kochi University of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 森畑, 明昌; 松崎, 公紀; 武市, 正人
• 著者名(英): Akimasa, Morihata; Kiminori, Matsuzaki; Masato, Takeichi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフ中の最短経路を求める問題，またはより一般に何らかの意味で最適な経路を求める問題は，非常に多くの応用を持つ重要な問題である．そのため，最短経路問題やその変種はさかんに議論され，様々なアルゴリズムが提案されてきた．しかし，これらの成果はアルゴリズムになじみのない人には利用が難しい．自分の解きたい問題に応じて適切にアルゴリズムを選択するのは一般に難しく，またそれぞれのアルゴリズムに効率の良い実装を与えるのも容易でない．本論文では，領域限定言語に基づいた最適経路問合せ手法を提案する．提案手法では，発見したい最適経路の仕様を領域限定言語によって記述する．この言語は，その記述から最適経路問合せを行う効率の良いアルゴリズムが機械的に導出できるよう設計されている．また，この言語では最適経路問合せに関する既知の問題クラスの多くを自然に記述できる．よって，アルゴリズムに関する知識をまったく要することなく広い範囲の最短経路問合せを効率良く行うことができる．我々は実際に提案手法を実装した．このシステムは，最適経路の仕様記述をもとに，効率の良い最適経路問合せを行うプログラムを出力する．最短経路問題の実装に関する既知の成果を利用し，また最適経路問合せに特有のいくつかの効率化を加えることにより，我々のシステムによる最適経路問合せは，既存のライブラリに比べても，その利用が簡便であるだけでなく実行効率も良いことが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 4, 号 2, p. 116-133, 発行日 2011-03-25
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会