有限領域
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/15 19:56 UTC 版)
「制約論理プログラミング」の記事における「有限領域」の解説
有限領域（Finite Domains）は、有限集合について制約を扱う領域である。多くの制約充足問題はこの領域で表現することができる。変数の値として有限領域の要素をとるもので、特定の範囲内の整数などがその代表である。個々の変数について、例えば1から5までの整数であれば X::[1..5] （あるいは X::[1,2,3,4,5] ）のように領域が指定される。数値以外であれば X::[george,mary,john] のような形になる。有限領域での制約としては算術式による制約や記号的制約などが使われ、言語により指定方法は異なる。以下は古典的な覆面算 SEND+MORE=MONEY を解くプログラムの例である。 sendmore(Digits) :- Digits = [S,E,N,D,M,O,R,Y], % 変数生成 Digits :: [0..9], % 変数の領域を定義 S #\= 0, % 制約: S, M は 0 ではない M #\= 0, alldifferent(Digits), % 制約: 要素はそれぞれ異なった値となる 1000*S+100*E+10*N+D + 1000*M+100*O+10*R+E #= 10000*M+1000*O+100*N+10*E+Y, % 制約: SEND+MORE=MONEY labeling(Digits). % 探索開始 有限領域では、制約の一貫性チェックにより各変数の取りえる領域が変化した場合、その変化を制約伝播により他の関連する変数の領域に反映し、解の範囲を順次狭めていくことで最終的な解を求めることが多い。全体の一貫性が取れなくなった場合はバックトラックを行い途中からやり直す。
※この「有限領域」の解説は、「制約論理プログラミング」の解説の一部です。
「有限領域」を含む「制約論理プログラミング」の記事については、「制約論理プログラミング」の概要を参照ください。
- 有限領域のページへのリンク
