整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)

Presentation on theme: "整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)"— Presentation transcript:

1 整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
2005 年 9 月 12 京都大学 工学部 情報第一講義室，京都

2 発表の流れ パズル「スリザーリンク」 新しいパズル「スリザーリンクス」 定義 NP完全性の証明 IP定式化 スリザーリンクの解法 まとめ

3 パズル「スリザーリンク」 ルール： 盤面上に1つのループを作る 数字の周囲の4辺には, その数字の数だけ 線を引く 解の有無判定はNP完全
→八登（2000）, 　 ハミルトン閉路問題に 　 帰着

4 新しいパズル「スリザーリンクス」 ルール： 盤面上にいくつかのループを作る 数字の周囲の4辺には, その数字の数だけ 線を引く

5 スリザーリンクスのルール： 詳細 ○ 認める × 認めない × 認めない

6 スリザーリンクスのNP完全性 スリザーリンクスの解の有無判定は NP完全 → 今回証明した NPに属す → OK
平面グリッドグラフの3彩色問題に帰着 NP完全性が知られている問題

7 平面グリッドグラフの3彩色問題 各頂点を3色のうち 1色で塗る 辺で結ばれた 頂点同士は同じ色で 塗られない

8 彩色問題の頂点： 模式図 拡大

9 部品： 端子 可能なパターン

10 　　　　　　部品： 交差 可能なパターン

11 　　　　　　部品： 電源 可能なパターン

12 スリザーリンクスの解法 緩和問題であるスリザーリンクスも, 多項式時間では解くことはできないと予想される → なるべく速く解ける方法を探す
IP（整数計画）で定式化 → IPソルバーで解く

13 スリザーリンクスの整数計画定式化 各辺に変数∈{0, 1} を対応させる 頂点 数字 a c d b k

14 切除平面法による解の更新 追加する式:

15 スリザーリンクの解法 スリザーリンクスを解く 制約式の追加 ループが 1つ? No Yes スリザーリンクの解

16 サイズ 問題No. 10×10 10×18 15×25 時間(秒) 回数 易 難 1 0.129 0.266 2 3.454 4 0.219 2.656 3 3.344 1.954 0.282 1.797 5 8 0.250 4.015 6 0.375 1.282 22.891 9 7 0.672 10.734 1.657 Out of memory 2.079 4.672 10 0.422 1.141 平均 0.306 2.6 1.236 3.1 5.4

17 実験結果の考察 人間にとっての難易度とこの方法で解く場合の難易度にはあまり関係がない 解くのにかかる時間は, 時々かなり長くなる

18 まとめ パズル「スリザーリンクス」を考案 スリザーリンクと同様, スリザーリンクスも NP完全であることを証明
スリザーリンクスをIPで解き, 切除平面法に　よりスリザーリンクの解を得る方法を提案, 　実装

19 今後の課題 スリザーリンクスのNP完全性証明に使用した部品を小さくする よりきつい制約を見つけて, 線形緩和問題でスリザーリンクスを解く
オリジナルのスリザーリンクソルバーを作る スリザーリンクをIP/LP定式化する 以上