OBDDを用いた ナンバーリンクの解法 古妻浩一・武永康彦 （電気通信大学） 研究の背景 • 二分決定グラフ (Ordered Binary Decision Diagram : OBDD) – 論理関数の効率的表現方法 • ナンバーリンク ： パズルの一種 – 決まった解法が知られていない 本研究 • ナンバーリンクを論理関数で表し、 OBDDを用いて解を求める • 与えた問題の正当性の判定 OBDD(二分決定グラフ) • 論理関数の表現方法の一つ 例：f = x1x2 + x2x3 変数の順序を決めた順に 変数節点が現れる • x1 0 1 特長 • • • 変数順序を決めると、 OBDDの表現が一つに定まる 実用的な論理関数をコンパクトに 表現 関数同士の論理演算を 少ない計算量で実現 0 x2 1 x2 0 x3 0 0 1 1 1 ナンバーリンクのルール1 • 入力 m×nの盤面に1からsまでの数字を それぞれ2つずつ盤面上のマスに与える • 数字を与えた点を基点と呼ぶ 1 2 1 2 ナンバーリンクのルール2 • 解の条件 1. １つのマスに上下左右のうち2つを結ぶ直線、 または折れ線が一本だけ引かれる 2. 同じ数字の基点のマス同士を線で結ぶ 3. 全ての線は2つの基点同士を結ぶ 4. 基点以外の全てのマスに線を引く 全て満たすなら 正当解 3、4を満たさない（空白を許す） 解は短絡解 1 1 2 1 2 2 1 2 ナンバーリンクの符号化 • • 盤面の数字をrビットの2進数で符号化(空白は0) 繋がれたマスは同じ数字を割り当てる 1 2 2 3 01 00 10 10 01 11 1 3 11 11 01 01 01 11 ナンバーリンクの符号化2 論理変数を x i , j ,k 1 : マス(i,j)上の数字のkビット目が1 〃 が0 0 : と定義 例：マス(i,j)に数字1001(2)を割り当てる j i 1001 j i xi , j , 3 xi , j , 2 xi , j ,1 xi , j ,0 解の制約条件 ある解（後述する）を求める関数 C1：基点における接続条件 C2：基点でない点における接続条件 CONNECT(P,S) = 1 となるような充足解を求める ことで解を得ることができる。 基点の接続条件 • 関数C1の表す条件 1. 基点(i,j)に数字tを割り当てる 2. 上下左右のうち、 1方向だけ同じ数字をとる それ以外の方向には違う数字をとる 3. 4方向についての論理和をとる SET：マス(i,j)に 値tを割り当てる関数 S1-S4： マス(i,j)の左（上右下）に 値tを割り当てる関数 i j t 基点でないマスの接続条件 • 関数C2の表す条件 1. マス(i,j)に対して上下左右のうち、 2方向はマス(i,j)と同じ数、 それ以外は異なる数を割り当て j る 2. 全ての選び方について 論理和をとる M1-M4： マス(i,j)の値と左（上右下） の値が一致する ことを表す関数 i 得られる解について ・明らかに短絡解が存在する場合 3 3 3 1 3 1 2 1 2 1 2 この場合には正当解を得られない 2 得られる解について2 線のループが存在する場合 1 1 2 3 01 01 10 11 11 11 10 11 2 3 11 11 10 11 上のようなことが起こりうる 正当解の条件のうち 「全ての線は2つの基点同士を結ぶ」 という条件を除いた解が得られることになる 短絡解を許す制約条件 • 基点でないマスの接続条件において、 0を割り当てても良いようにする つまりマスの空白を許す条件 i j i または j 0 問題の正当性の判定 • 正当な問題の定義 唯一の正当解を持ち、 短絡解を持たない問題 短絡解を許す場合と許さない場合 の両方について唯一の解を持つ 問題の正当性の判定 短絡解を許さない場合にただ一つ解を 持つがそれが正当解でないとき、 （つまり線のループを持つとき） 短絡解を許す場合の条件では 必ず複数の解を持つ （線のループは空白と同等であるため） 両方の場合で正当解を唯一つ持つ ことが正当な問題の条件となる 解を求める実験 実際に問題を与えて解を求めた •8×8 その1 短絡解 実行時間 OBDDサイズ 許さない 0.2秒 10,393 許す 1.7秒 41,412 •8×8 その2 短絡解 許さない 許す 実行時間 OBDDサイズ 0.7秒 23,540 20.9秒 466,246 解を求める実験 実際に問題を与えて解を求めた •10×10 その1 短絡解 許さない 許す 実行時間 OBDDサイズ 1.6秒 58,873 8分40秒 13,400,524 •10×10 その2 短絡解 許さない 許す 実行時間 OBDDサイズ 0.3秒 8,960 1分4秒 1,114,248 ・15×20以上では正当解も短絡解も求められなかった 解を求める実験2 同じ問題でもマスに対する条件の適用順序によって 最大OBDDサイズが大きく変わる • 左上のマスから実行 短絡解 実行時間 許さない 許す 5 1 OBDDサイズ 0.3秒 4,813 46.8秒 1,598,287 2 4 3 2 • 右上のマスから実行 短絡解 許さない 許す 実行時間 1 5 OBDDサイズ 5.8秒 141,906 1時間58分53秒 84,586,122 3 4 出展：ニコリ「ナンバーリンク1」 接続条件の適用順序 • 基点でない点の接続条件を 適用順序を変更して BDDの最大サイズの変化を観察する 接続が決定しそうなところから実行する •基点の周囲 ● ○ ● •4隅（実験中） ○ t ○ ● ○ ● ● ● ○ 適用順序の実験１ • 先ほどの左上からの結果との比較 OBDDサイズ ・元の結果 短絡解 実行時間 許さない 許す ・周囲4マス 短絡解 許さない 許す ・周囲8マス 短絡解 許さない 許す 0.3秒 4,813 46.8秒 1,598,287 実行時間 OBDDサイズ 33.2秒 697,762 17分14秒 16,588,110 実行時間 OBDDサイズ 2分13秒 1,053,016 13分37秒 6,774,414 適用順序の実験2 • 先ほどの左上からの結果との比較 OBDDサイズ ・元の結果 短絡解 実行時間 許さない ・周囲4マス 5.8秒 141,906 許す 1時間58分53秒 84,586,122 短絡解 実行時間 許さない 3分50秒 5,533,526 ---- ---- 許す ・周囲8マス メモリ不足で 計算出来ず 短絡解 許さない 許す OBDDサイズ 実行時間 OBDDサイズ 6分4秒 5,345,051 ---- ---- 適用順序の実験3 基点の周囲を先に適用するだけでは サイズは大幅に増加してしまった 基点の周囲4マスと8マスの比較では 8マスを適用した方が小さくなることもあった ・基点同士の位置関係が重要か 今後の課題 • 正当解だけを得るプログラムの実装 – • 最大OBDDサイズを小さくする – – • アルゴリズムは考案済 変数順序を変更してみる 条件の適用、条件の追加を行う 問題の作成、列挙への応用
© Copyright 2024 ExpyDoc
