数理解析研究所講究録
第 1843 巻 2013 年 51-55

51

ブーリアングレブナ基底の時間割作成問題への応用
井上秀太郎

SHUTARO INOUE

東京理科大学理学部
DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE,TOKYO UNIVERSITY OF SCIENCE*

1

はじめにすべての要素が幕等であるような単位元 1 をもつ可換環 $B$ をブール環と呼ぶ．さらに多項式環 $B[X_{1}, \ldots, X_{n}]$のイデアルによる剰余環をブール多項式環と呼び、 $B(X_{1}, \ldots, X_{n})$ と表す．プー
リアングレブナ基底とはこのブール多項式環上のグレブナ基底のことである．我々はブーリアングレブナ基底を使用した数独パズルの解法についての研究を行ってきた．本稿では、 我々の数独解法アルゴリズムを時$\langle X_{1}^{2}-X_{1},$$\ldots,$$X_{n}^{2}-X_{n}\rangle$

間割作成問題に適用し，有効性を検証した．

2ブール多項式環
ブール環とプール多項式環を次のように定義する．

定義 1 全ての要素が幕等であるような、 単位元をもつ可換環 $B$ をブール環とよぶ．
定養 2 ブール環 $B$ を係数とする多項式環 $B[X_{1}, \ldots, X_{n}]$ のイデアル環をブール多項式環とよひ、$B(X_{1}, \ldots,X_{n})$$\langle X_{1}^{2}-X_{1},$$\ldots,$$X_{n}^{2}-X_{n}\rangle$による剰余で表す．

プール多項式に関しては拡張定理と零点定理が成り立つ．

定瑚 1(拡張定理)
たいして

$I$

$(\overline{a},\overline{b})\in V(I)$

定瑠 2(零点定理)$I$をブール多項式環$B(\overline{A},\overline{X})$のイデアルとする．このとき任意のとなるわが存在する．

をプール多項式環$B(\overline{X})$のイデアルとする．このとき$V(I)=\emptyset\Leftrightarrow\exists a\in Ba\in I$が成り立つ．また$I$(弱形の零点定理)が有限生成であると仮定する．このとき$f(X)\in I\Leftrightarrow\forall\overline{a}\in V(I)f(\overline{a})=0$が成り立つ．

.

tsinoue(l)rs. kagu. $tus$ ac.jp(強形の零点定理)$\overline{a}\in V(I\cap B(\overline{X}))$に

523

ブーリアングレブナ基底
まず始めに係数プール環上の多項式環でのグレブナ基底について説明する．以降は次の記号を使用する．

$LM$ (f) の係数と項をそれぞれ $LC(f)$ある順序に対してプール多項式 $f$ の最大の単項式を $LM(f)$ で表し，と $LT(f)$ で表す． また $f-LM(f)$ を $Rd(f)$ で表す．
$\acute{}$のイデアル に対して， の有限部分集合 $G$ が定義 3 ブール多項式環$\langle LM(I)\rangle=(LM(G)\rangle$ を満たすことである．
$I$$B[\overline{X}]$$I$

定養 4 ブール多項式 $f=a\alpha+h\in B[X^{-}]$ による単項式簡約$arrow f$$I$のグレブナ基底であるとはを$b\alpha\betaarrow_{f}b(1+a)\alpha\beta+ba\beta h$と定義する．
$($

ただし $a=LC(f),b\in B,$ $ab\neq 0$ とし， $=LT(f),\beta\in T(X),$ $h=Rd(f)$ とする．
$)$$\alpha$係数プール環上のグレブナ基底の計算には次の定義が必要になる．
$lc(f)f$ を定養 5 多項式 $f$ 力 $z\iota_{C}(f)f=f$ を満たすとき $f$ はブール閉であるという．

$f$のブール閉包とよび、$bc(f)$ で表す．

一般の係数体のときと違い，簡約グレブナ基底は一意性をもたない．よって新しい条件を加える．
定義 6 $G$ を既約グレブナ基底とする．任意の異なる多項式 $f,g\in G$ にたいして $LT(f)\neq LT(g)$ が成り立
つとき $G$ は stratifi

定瑠 3 $G,H$ をであるとよぶ．

$\langle G\rangle=\langle H\rangle$を満たす $stmt;fid$ なグレプナ基底であるとする．このとき $G=H$ が成り立つ．

係数ブール環上のグレブナ基底は上記の単項式簡約を利用したブッフバーガーアルゴリズムで計算できる．
Algoritm $BC$Input: $F$ a finite subset of
Output: $F’$ a set of boolean closed polynomials such thatbegin
$B[\overline{X}]$$F’=\emptyset$

while$F\neq\emptyset$

selectdofrom $F$$f$$F=F\backslash \{f\}$$F’=F’$$\cup${加 (f)}$F=F\cup\{f-be(f)\}$end

retum $F’$
Algoritm $GB$
Input: $F$ a finite subset of
Output: $G$ a Gr\"obner basis ofbigin$B[\overline{X}]$$G=BC(F)$

while$G’=G$$\langle F\rangle$

w.r.t

$>$

$\langle F\rangle=\langle F’\rangle$53
for each pair $\{p,q\}(p, q\in G’,p\neq q)$ do$h=a$ normal form of $S(p,q)$ modulo $G’$ i.e.
if $h\neq 0$ then $G=G\cup\{h\}$$G=G’$ doend$S(p,q)\sim^{\alpha_{G}}h$

ブーリアングレブナ基底に関しても今までの定義や定理と同じょうな議論ができる．またアルゴリズムも非常にシンプルである．

定義 7 ブール多項式環 $B(X)$ のイデアルであるとは$\langle LM(I)\rangle=\langle LM(G)\rangle$$I$に対して， の有限部分集合$I$$G$が $I$ のブーリアングレブナ基底を満たすことである．

Algoritm BGB
Input:
a finite subset of $B(X_{1}, \ldots,X_{n})$Output: a boolean Gr\"obner basis ofw.r.t
begin
$F$

$G$

$\langle F\rangle$$>$$G=GB(F\cup\{X_{1}^{2}-X_{1}, \ldots,X_{n}^{2}-X_{n}\})(X_{1}^{2}-X_{1}, \ldots,X_{n}^{2}-X_{n}\in B[X])$$G=G\backslash \{X_{1}^{2}-X_{1}, \ldots,X_{n}^{2}-X_{n}\}$end

return4$G$

ブーリアングレブナ基底を使つた数独の解法

時間割作成問題の前に数独解法アルゴリズムについて説明する．数独とはブロックの枠内に 1 かブロックに同じ数字は入れられない “ というルールに従ってら 9 までの数字を “縦，横，区分けされた埋めていくペンシルパズルの 1 つである．我々は集合制約問題への有効性を示すために、 ブーリアングレブナ基底を使ったこの数独パズルの解法について研究を行ってきた．我々の方法は始めに 81 個のブロックに$9\cross 9$$3\cross 3$対して変数を割り当てる．

さらに 1 から 9 までの数字は集合の要素とする．つまり $S=$ {1,2,3,4,5,6, 7,8, 9} としたとき，係数プール環は $B=\mathcal{P}(S)$ となる．これらの変数を用いて、 数独のルールを約 1000 個のブール多項式で表すことができる．さらに我々は almoet solution polynomial という特殊な形のブール多項式に注目した．
定義 8 $S=\{s_{1}, s_{2}, \ldots, s_{k}\}$ とする．

$\mathcal{P}(S)$から$(\mathbb{G}\mathbb{F}_{2})^{k}$への同型写像$\phi$

を次のように与える．

$\phi(\{s_{1}\})=(1,0, \ldots, 0), \phi(\{s_{2}\})=(O, 1, \ldots,0), \ldots,\phi(\{s_{k}\})=(O,0, \ldots, 1)$

54$\mathcal{P}(S)$から $GF_{2}$ への同型写像

任意の$T\subseteq S$$\phi_{j}$を次のように与える．

に対して，吻$(T)=\{\begin{array}{l}1 s_{j}\in T0 s_{j}\not\in T\end{array}$と集合の要素 $8j$ に対して、 次の条件のどちらかを満たす 7–, 多項式 $f,g$ を窟義 9 変数
関する almost solution polynomial とよぶ．
$\nu$

$X_{i}$$X_{1}$の $Sj$ に(i) $\phi_{j}(f(\overline{X}))=X_{i}+1$(ii)$X_{i}$$j$以外の全ての $t\in S$ に射して $\phi_{t}(g(X))=X_{1}$の $Sj$ に関する dmost $solu\hslash on\mu l\psi omid$ に対して $X_{1}+\{Sj\}$ を associated solution polynomial とよぶ．

mlmoet solution polynomial は数独の解を探す重要な手がかりとなる．我々は almoet solution polynomialが任意の項順序のブーリアングレブナ基底を計算すれば得られることを示した．
窟瑠 4 $I\subseteq B(x)$ を定数項を含まないイデアルとし，$G$ を任意の単項式順序での の簡約ブーリアングレブナ基底とする．任意の dmost solutionomidf に対して，$f\in I$ ならば $f\in G$ となる．
$I$$\mu l\psi\iota$

ブーリアングレプナ基底を計算し、 mlmoet solution polynomial を associated solution polynomial に置き換えることで数独の空きマスに数字を埋めていくことができる．しかし常に almoet solution polynomial が見つかるとは限らない．この場合は適当な associated solution polynomial を付け加えてプーリアングレブナ基底の計算を続ける必要がある．我々の方法は与えられた数独パズルに解がない場合や複数の解がある場合にも対応している．

5時閥割作成問題への応用

本研究では、学校の時間割作成を想定し、教科と担当教員、 その教科を受講する学生のデータが与えられているとき、 1 時限から 6 時限まで 5 日間を対象に制約条件を満たす時間割の作成を行う．さらに以下の制約条件を加える．

.
$\bullet$.
$\bullet$

担当教員と学生が同じ時間帯で重複しない．

教員の都合の悪い時間帯に配置しない．
全ての教科がどこかの時間帯に配置される．

特定の教師や学生の負担ができる限り偏らないように配慮する．

これらの制約条件を多項式で表し、 ブーリアングレブナ基底を使用する．はじめに、 時間帯に表す変数を$t_{1},t_{2},$$\ldots,$$t_{30}$とし、 この変数を使用して $S=\{t_{1},t_{2}, \ldots, t_{30}\}$ とおく．時間帯変数を係数とする理由は全ての教科はどこかの時間帯に配置されるが、空きの時間帯が存在することはあるからであり、集合の要素数が1 であるという条件の下での集合制約問題に帰着させるためである．教員数を n、学生のグループ数を $m$ とする．教科を表す変数を$8_{k,g}$とする．ただし、 $k=1,$$\ldots,n$とし、 $g=1,$$\ldots,$$m$とする．教員と学生を同じ時間帯に配置しないために添え字のどちらかが同じである変数同士の積は空集合とする．例えば、 $s_{1,2}s_{1,3}=0$の多項式としてプーリアングレブナ基底の. や $s_{2,2}s_{1,2}=0$ が成り立つ．上記の方程式の左辺を係数が計算を繰り返す．基本的な解法は数独解法アルゴリズムと同様であるが、具体的な計算には改良を施した．
$\mathcal{P}(S)$55
集合 $S=\{t_{1}, t_{2}, \ldots, t_{m}\}$ とブール多項式の集合の係数部分を比較し，$S$を係数部分に現れている集合$S_{1}$とで分ける．ahost solution polynomial がブーリアングレブナ基底に存在する場合は係数ブール環を $P(S_{1})$ として計算を続ける．almost solution polynomial が存在しない場合，ブーリアングレ現れていない集合$S_{2}$

ブナ基底に associated solution polynomlal $v_{i}+\{t_{j}\}$ を加えて再度ブーリアングレブナ基底の計算を行う．

このとき，$sj\in S_{1}$のときも係数ブーノレ環をを $S_{2}-\{t_{j}\}$ に変えて，係数ブール環をとして計算を続ける．
ならば， をとを保存することとして計算を続ける．さらに，$\mathcal{P}(S_{1})$$\mathcal{P}(S_{1})$$t_{j}\in S_{2}$$S_{1}$$v_{i}+\{t_{j}\}$$S_{1}+\{t_{j}\},$$S_{2}$$S_{2}$

で，全く同じ計算を避けることができる、このように係数ブール環を少しずつ拡大させることで，重複計算を事前に止められる．almost solution polynomial が見っからない場合には、 特に大規模な重複計算が発生する。 このような場合だけでも上記の対処を行うことで大幅に計算量を抑えることができる。

6

さいこに

莫大な計算量を抑えるためにはアルゴリズムの改良だけでは限界がある．最近の研究で almoet solution
polynomial が他にも存在する可能性を発見している．これを発見できれば、 プーリアングレブナ基底の計算回数を減少し、 分岐の数も減らすことができる．

参献[1] Inoue, $S.(2009)$ . On tbe Computation of Comprehensive Boolean Gr\"obner Bases. Proceedings of the

11th Intemational Workshop on Computer Algebra in Scientific Computing(CASC 2009), LNCS
5743, pp $13\{k141$ , Springer-Verlag Berlin Heidelberg.
[2] Sakai, K. and Sato, Y. (1988). Boolean Gr\"obner bases. ICOT Technical Momorandum 488.

http: $//www$ . icot. or.ip/ARCHIVE/Museum/TRTM/tm-list- . html
$E$[3] Sakai, K., Sato, Y. and Menju, S. (1991). Boolean Gr\"obner bases(revised). ICOT Technical Report613.
http: $//www$ . icot. or.jp/ARCHIVE/Museum/TRTM/tr-list- . html
$E$[4] Sato, $Y.(1998)$ .
new type of cmonical Gr\"obner bases in polynomial rings over Von Neumannregular rings. Proceedings of ISSAC 1998, ACM Press, pp 317-32.
$A$

$[5J$

Sato, Y. et al.(1998). Set Constrains Solvers(Klic version).
http: //www.iipdec.jp/icot/ARCHIVE/Museum/FUNDING/fimding-9s-$E$. html

[6] Sato, Y., Nagai, A. and Inoue, I.(2008). On the Computation of Elimination Ideals of Boolean
Polynomial Rings, LNAI 5081, pp 338-348, Springer-Verlag Berlin Heidelberg.
[7] Weispfenning, V. (1989). $Gr6bner$ bases in polynomial ideals over commutative regular rings. In
Davenport Ed., editor, EUROCAL’87, pp 336-347. Springer LNCS 378, 1989.