整数計画法を用いたスリザーリンクの解法杉村由花 (東京大学) 2005 年 9 月 12 日，ミニ研究集会“組合せゲーム・パズル” @ 京都大学工学部情報第一講義室，京都発表の流れ • パズル「スリザーリンク」 • 新しいパズル「スリザーリンクス」 – 定義 – NP完全性の証明 – IP定式化 • スリザーリンクの解法 • まとめパズル「スリザーリンク」ルール： • 盤面上に1つのループを作る • 数字の周囲の4辺には, その数字の数だけ線を引く解の有無判定はNP完全 →八登（2000）, ハミルトン閉路問題に帰着新しいパズル「スリザーリンクス」ルール： • 盤面上にいくつかのループを作る • 数字の周囲の4辺には, その数字の数だけ線を引くスリザーリンクスのルール：詳細 × × ○ 認めない認めない認めるスリザーリンクスのNP完全性スリザーリンクスの解の有無判定は NP完全 → 今回証明した • NPに属す → OK • NP完全 → 各頂点の次数4以下の平面グリッドグラフの3彩色問題に帰着 NP完全性が知られている問題平面グリッドグラフの3彩色問題 • 各頂点を3色のうち 1色で塗る • 辺で結ばれた頂点同士は同じ色で塗られない彩色問題の頂点：模式図拡大部品：端子可能なパターン部品：交差可能なパターン部品：電源可能なパターンスリザーリンクスの解法 • 緩和問題であるスリザーリンクスも, 多項式時間では解くことはできないと予想される → なるべく速く解ける方法を探す • IP（整数計画）で定式化 → IPソルバーで解くスリザーリンクスの整数計画定式化各辺に変数∈{0, 1} を対応させる a  b  c  d  2, • 頂点 a  a  b  c  d  0, d b a  b  c  d  0, c a  b  c  d  0, a  b  c  d  0. • 数字 a' d ' k b' c' a'b'c'd '  k. 切除平面法による解の更新追加する式: 各ループLについて  x  (Lの長さ) 1 xi L i ( xi : i 番目の辺) スリザーリンクの解法スリザーリンクスを解く制約式の追加ループが 1つ? Yes スリザーリンクの解 No サイズ 10×10 10×18 問題No. 時間(秒) 回数時間(秒) 回数 1 0.129 1 0.266 2 易 2 0.219 1 0.266 2 3 0.266 3 3.344 4 4 0.282 3 1.797 5 5 0.250 3 0.266 1 6 0.375 4 1.282 3 7 0.672 3 0.266 1 8 0.250 2 1.657 5 9 0.282 3 2.079 4 難 10 0.422 3 1.141 4 0.306 2.6 1.236 3.1 平均 15×25 時間(秒) 回数 3.454 4 2.656 4 1.954 4 693.438 8 4.015 4 22.891 9 10.734 4 Out of memory 4.672 3 190.547 9 103.818 5.4 実験結果の考察 • 人間にとっての難易度とこの方法で解く場合の難易度にはあまり関係がない • 解くのにかかる時間は, 時々かなり長くなるまとめ • パズル「スリザーリンクス」を考案 • スリザーリンクと同様, スリザーリンクスも NP完全であることを証明 • スリザーリンクスをIPで解き, 切除平面法によりスリザーリンクの解を得る方法を提案, 実装今後の課題 • スリザーリンクスのNP完全性証明に使用した部品を小さくする • よりきつい制約を見つけて, 線形緩和問題でスリザーリンクスを解く • オリジナルのスリザーリンクソルバーを作る • スリザーリンクをIP/LP定式化する以上