有限領域上の等式制約コンパイルのための一最適化手法とその実装

概要

論文の詳細を見る
近年の重要なプログラミングパラダイムの1つに, 制約論理プログラミング(以下, CLP)がある.CLPは高い宣言性を有し, プログラムの開発効率や保守性を大幅に向上させるものとして期待されている.この中でCLP(FD)は, 離散的な有限領域上の制約を扱うCLPの一種で, 様々な探索問題に適応できることが知られ, 近年, 高性能な処理系の実現が重要な研究課題になってきた.ところが, これらの探索問題は, 問題ごとにその特性が異なるため, 一般的な解法により, そのすべてを効率良く処理できる処理系の実現は困難である.この問題に対処するため, 筆者の1人周は遅延節を利用する方法を提案し, これを用いて問題の特性を用いた種々のアルゴリズムを実現できることを示した.しかし周が実装したアルゴリズムでは探索空間の大きな問題に対しては, 十分な性能は得られなかった.そこで本論文では, 部分ルックアヘッド・アルゴリズムと完全ルックアヘッド・アルゴリズムを組み合わせて制約を処理することにより, この問題を解決する方法を提案する.この方法では, 制約内に変数が3つ以上含まれるときは部分ルックアヘッド・アルゴリズムを用い, 制約内の変数が2つになると完全ルックアヘッド・アルゴリズムを用いる.実験結果から, この手法が一般的に優れていることが確認できた.
一般社団法人情報処理学会の論文
2001-03-15

有限領域上の等式制約コンパイルのための一最適化手法とその実装

スポンサーリンク

概要

著者

関連論文

スポンサーリンク