狠狠撸

遺伝的アルゴリズム
でピクロスを解く
@dekosuke

ピクロス

? 縦横に制約がある
? 黒および白を順次確定
させて解いていく
? 人間が解くもの???
ですよね？

3

ピクロス
ピクロスはNP完全 – Ueda et al. (96’)
→人間離れした難しい問題が作れる

名状しがたい問題のようなもの
4

というわけで
コンピュータに解かせよう！！！

5

遺伝的アルゴリズム(GA)

“遺伝的アルゴリズムはもっともよく
使われている進化的アルゴリズムであ
る” - wikpiedia

6

遺伝的アルゴリズム(GA)

? より正解に近い解答へ、回答群を進化させる
? 自然淘汰と突然変異の原理

7

遺伝的アルゴリズムの応用例

? 戦略ゲーム
? ガンダムの歩行

? パズル（ピクロス）←今回

8

遺伝子コーディング

各マスの (黒, 白) の状態を (1, 0) にして、遺伝子
にコーディング

9

実装 - Haskell

“Escape from the ivory tower” –
Simon Peyton Jones

Haskellは象牙の塔（研究の世界）か
らやってきた言語

10

Haskellの特徴

? 名状しがたい純粋関数型言語のよう
なもの
? 可及的速やかに実装できる

? 強力かつバグを出さない

11

結果

道具は揃った、あとはコードを書
くだけ
というわけで、結果は????

12

結果

ハウス(5*5) テレビちゃん(14*14)

ニコニコ(10*10) 名状し難い問題

13

結果
? ちゃんと問題が解けた！！
? 問題サイズが大きくなると、計算が終わらない
（局所解（正しくない解）から抜け出せない）

14

おわり

御清聴ありがとうございました

成果物 https://gist.github.com/2516358

15

解説

アイディアは大体、最初の参考文献（最終頁参照）から来ています。
NP完全について説明します。NP完全問題は、問題の大きさ（パズル
サイズ）が大きくなると、その問題を確実に解くアルゴリズムが、も
のすごい勢いで計算量が増えていく（普通の時間で解けなくなる）問
題です(NPの壁)
遺伝的アルゴリズム (GA)は確率的アルゴリズムなので、必ず問題を
解けることを保証しないかわりに、多くの問題に対して十分早い時間
で解けることが期待できます。ほかにも、モンテカルロと呼ばれる一
連の確率的手法もこのNPの壁に挑むことのできる手法です。実際、
レプリカ交換法（モンテカルロの一種）とどっちをやろうか悩みまし
た。

※GAでも無限の時間をかければ必ず解に到達します

17

解説
そういう動機を持ち、遺伝的アルゴリズムで今回の問題に
トライしました。

遺伝的アルゴリズムを実装してやってみると、14*14のサ
イズでは、数時間内に正解にたどり着けなくなってしまい
ました
遺伝的アルゴリズムでは突然変異の方法と確率をいじる余
地がまだあるので、最適な調整をすればもう少し大きいサ
イズの問題まで解けるかもしれません
ほかのアルゴリズムでは20*20以上のものが解けるものも
あるので、遺伝的アルゴリズムがどうだったかは微妙なと
ころがあります???
18

解説

Haskellを実装に選んだ理由は、主に２点ありま
す。１つは、十分早く実装ができること、そして
２つめはバグが出る率が非常に低いことです。
PythonやRubyなどのLL言語も早く実装するのに
は向いていますが、アルゴリズムの一部にバグが
出ても、気づきにくいことがあります。Haskell
は強い静的型付けを持つ言語ですので、多くのバ
グをコンパイル時に検出することができます

19

参考文献

? “A comparison of a genetic algorithm and a
depth first search algorithm applied to Japanese
nonograms”
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.62.9443

? “Hoogle” http://www.haskell.org/hoogle/

20

狠狠撸

Ga nonogram

Recommended

More Related Content

Recently uploaded (15)

Featured (20)

Ga nonogram