ECLiPSe CLPのsearch/6のChoiceの実験

ECLiPSe CLPで記述するソルバーの構成はおおまかに以下の部分に分かれます。
1.制約の記述
2.解のサーチ
3.解の表示

2.の解のサーチというのは、具体的には以下の2つのループの入れ子の構造となります。
 ループ1:複数の制約変数の中から1つを選択する
 ループ2:変数にドメイン内の値を一つ割り当てる

このとき、ループ1で「どのような順番で変数を選択するか」ループ2で「どのような順番で値を決定するか」という2つの制御をおこなうことができます。この記事はループ2の値決定の順番をいろいろ試す記事となります。

ECLiPSe CLPではループ1,ループ2は例えば以下のような方法で記述可能です(他にもあると思いますが)
labeling/1を使用
 ループ1:リストの先頭の変数から選択
 ループ2:ドメイン内の数値の小さい値から大きい値へと順に値を決定
search/6を使用(ループ1、ループ2の制御を一括で指定)
・以下の2つの述語を使用
 ループ1:delete/5を使用して値を決める変数を決定
 ループ2:indomain/2を使用してどのように変数に値を設定するかを決定

本記事ではsearch/6に関して、「どのような順で変数に値を割り当てるか」というのをオプションを変えながら実験したいと思います。

以下のテスト用プログラムで実験します。

Choice の部分を色々変更することにより実験します。解説の部分は直訳なので自分でも意味わかってない箇所あります。特に「テストされた値を削除」「ドメイン分割」のところが良くわかってません。誰か教えて下さい。

①indomain
組み込みのindomain/1を使用します。値は昇順で試行されます。失敗しても以前にテストされた値は削除されません。

②indomain_min
昇順で試行されます。失敗すると以前にテストされた値が削除されます。値はindomainの場合と同じ順序でテストされますが、バックトラックがより早く発生する可能性があります。

③indomain_max
値は降順で試行されます。 失敗すると以前にテストされた値が削除されます。

④indomain_reverse_min
indomain_minと同様ですが、選択は逆の順序で試行されます。つまり最小の値が最初にドメインから削除され、それが失敗した場合にのみ、値が割り当てられます。

⑤indomain_reverse_max
indomain_maxと同様ですが、選択は逆の順序で試行されます。 つまり、最大値が最初にドメインから削除され、それが失敗した場合にのみ、値が割り当てられます。

⑥indomain_middle
値はドメインの中央から開始して試行されます。 失敗すると以前にテストされた値が削除されます。

⑦indomain_median
値はドメインの中央値から開始して試行されます。 失敗すると以前にテストされた値が削除されます。

⑧indomain_split
ドメインの下半分を最初に試行して、連続するドメイン分割によって試行されます。 失敗すると、試行された間隔が削除されます。 これは、indomainまたはindomain_minと同じ順序で値を列挙しますが、それより早く失敗する可能性があります(注:解サーチ時はなるべく早く失敗したほうが処理時間が速くなる。早く失敗≒変数の決定の入れ子のループのより外側のループ回数が減ることと同等)

⑨indomain_reverse_split
ドメインの上半分を最初に試行して、連続するドメイン分割によって試行されます。 失敗すると、試行された間隔が削除されます。 これは、indomain_maxと同じ順序で値を列挙しますが、それより早く失敗する可能性があります。

⑩indomain_random
値はランダムな順序で試行されます。 バックトラック時に、以前に試行された値が削除されます。 このルーチンを使用すると、別の呼び出しで異なる順序で乱数が作成されるため、再現性のない結果が生じる可能性があります。 この方法では、組み込みのrandom / 1を使用して乱数を作成し、seed / 1を使用して別の実行で同じ番号生成シーケンスを強制することができます。

⑪indomain_interval
ドメインが複数の間隔で構成されている場合は、最初に間隔の選択で分岐します。 1つの間隔では、ドメイン分割を使用します。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">