制約プログラミングによる視覚化モデルの形式化と実現

点击翻译按钮获取中文摘要

本研究の目標は,制約プログラミングを用いて視覚的システムの仕様を視覚化モデルとして形式化し実現するというソフトウェア構築の新しいアプローチに基づいて,Webブラウザの視覚化モデルを扱う技術を構築することである.特に,このアプローチに基づく多くの従来研究において制約プログラミングの基盤技術として利用されているCassowaryアルゴリズムを改良することで,Webブラウザの視覚化モデルのためのより適切な処理技術の構築を試みた.2年目である平成17年度においては,階層的制約の解析によってCassowaryを高速化する手法を提案した.これは,本研究代表者が過去に提案した線形制約解消系のための制約の階層独立性の解析手法に基づくものである.階層独立性解析では,制約が有効(最大限に充足すべきである),または無効(完全に無視してよい)であるかどうかについて判定する処理を行う.これによって,アルゴリズムの内部で構成されるタブローから無効な制約を除去することができるため,タブローが小型化される.その結果,本研究で提案した制約解消法は,多くの場合にCassowaryよりも高速となる.本手法では,制約の有効性の判定のために,本研究代表者が過去に提案した線形制約解消法におけるものと同様の考え方に基づき,かつ,Cassowaryに適合する新しい方法を開発した.本研究の成果は,複数の国際会議及び国内会議において発表された.