Pythonでぷるるん〜

こんにちはゆっけです。
皆伝を取ったので競プロを始めようと思い最近蟻本のイージーを狙っています。

はじめにですが今回の記事は音ゲー全く関係ないです(´･_____･`)

タイトルのぷるるんとはなんぞやという話ですが、これはGoogleplayやAppStoreにある一筆書きを考える系脳トレアプリのことです(´･_･`)
Google
https://play.google.com/store/apps/details?id=jp.co.OneStroke
Appstore
https://itunes.apple.com/jp/app/da-rengahamaru-naotore!pururun/id1145262669?mt=8

で、今日このアプリをひとからやらされたわけなんですが、まあ一筆書きを考えるだけなんですが結構難しいんですよね(´･_･`)

と、いうことでPythonで解いてみました(^o^)丿
脳トレアプリでさえ脳トレしないぞ(^o^)丿


蟻本では一番最初の方で全探索というものが紹介されます(´･_･`)
で、今回の問題もだいたいそれで解けるわけですね〜

直感的な戦略は

1. 上下左右に移動
2. 壁や既に通った道に来てしまったら終了
3. 全部の道を通っていたら解答として出力

となります。

全探索にはざっくり深さ優先探索と幅優先探索があるわけなんですが(詳しくはこちら→http://mathtrain.jp/dfsbfs)
今回は全部の道を埋めたいわけなので深さ優先探索となりますね(´･_･`)

ということでまずこれで書いてみます。
"."が道で"#"は壁、"S"がスタートです。



道が全部埋まったかどうかを確認するために、最初に道のマス目を全部数えて、移動するたびにマス目の数を1引いています。
全要素を見て全部の道を通ったかどうか確認するより、ビミョーに計算量が減ります(´･_･`)

また、Pythonのリストは参照渡しなので、関数やキューに渡すときはcopyモジュールのdeepcopyで複製を作っています。(もしかしたらコレが結構遅いかもしれない…)

結果はこちら(´･_･`)



さ、僕が自力で考えても10分ぐらい解けなかった問題も解くことができました。が、
Pythonが遅いのとコーディング力が無いので6×7の問題を解くのに70秒近くかかってしまいました(´･_･`)
う〜ん(´･_･`)
Python書きやすくていいんですが速さのほしいときにはどうしても使えません(´･_･`)
コレぐらいのとても小さい問題ならいいっすけどね…

ちなみにキューをFIFOで使って"幅"優先探索すると11分かかったのでそこは間違えないようにしましょう(´･_･`)


そこで高速化するために枝刈りを行います(´･_･`)
どう見てもこれ以上進んでもダメだ〜〜という場合にそれ以上先を考えないというやつですね(´･_･`)
今回枝刈りにはLakeCountingという有名(？)な問題を使ってみました。

LakeCountingというのは次のような問題です(´･_･`)



で、この問題をどのように応用したのかというと、

一筆書きできる➔道が2つに分かれていない

ということを利用します(´･_･`)

LakeCountingでは周囲8マスを見たわけですが、今回はそれを上下左右4マスのみ見るようにして、道を湖と見立てて分断されていないかどうかを調べるわけです。
道が分断されていればその時点で探索をやめていいわけですね。

LakeCountingの計算量は要素数をNとしてO(N)なわけなんですが、一筆書きの解を得るアルゴリズムはO(N⁴)ですからLakeCountingをいちいちやっていても大した計算にはなりません。


結果(^o^)丿


早い！！！！！
よく計れないレベルまで早くすることができました。

Search関数の呼び出し回数も測ってみました。



枝刈りって重要ですね〜〜
これなら安心して考えるより高速に問題を解くことができます。

と、いうことで脳トレを台無しにしてみよう！というお話でした。おしまい。
ぷるるん、やってみてください。


狙っているVOXUPがなかなかハードできないのでどういう呼吸法を使えばいいのか誰か教えてください…

Tweet