並列制約解消とオブジェクト指向プログラミング

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

オブジェクトとそれらの間の制約を組み合わせたシステムに対してはlocal propagation が有効な手法として知られている。Local propagationの利点として、並列性が高いこと、変更する必要のある値だけを再計算するので無駄がないことなどが挙げられる。ただし、制約の種類が固定されていれば、それに対する propagation のアルゴリズムを用意しておくことができるが、任意の制約をユーザが記述可能にしようとすると問題が発生する。第一に、システムが自動的に制約充足を行なうことができないので、ユーザが制約充足のメソッドをプログラミングしなければならない。第二に、用意に矛盾が発生するので、矛盾解消の戦略が必要となる。この時、高い並列性を維持するためには、全体の評価値を計算するようなものではなく、局所的に決定できるようなものでなければならない。本研究ではテキスト編集を例として上記の問題を試みた。まず第一の問題を解決するために、ユーザの操作を記録することによって制約充足のメソッドを自動的に学習することとした。第二の問題を解決するためには、制約の優先度を採用した。ここでも、優先度をあらかじめ決めておくことはできないので、矛盾発生時のユーザの選択を記録することによって優先度を学習する。したがって、ある時点での制約の優先度は部分的にしか決まっておらず、半順序で表現されている。Local propagationには、DeltaBlueという効率の良い充足アルゴリズムがあるが、これに半順序優先度を組み込むことも可能である。このような手法により、ユーザは最小限の労力で任意の制約を使用できるようになる。