みたにっき@はてな

三谷純のブログ

折り紙研究

与えられた折紙の展開図から、折りたたみ後の形を推定する研究を行っているのですが、今日はプログラミングをする時間がたくさん取れたので大きな進展がありました。
ほぼ現実的な時間でかなり複雑なものでも(面の重なり順にループを持つものでも)全ての解が算出できるようになりました。
この問題は、重なり関係を表す行列の要素を全て求めることで実現できるのですが、これを2つのステップに分けて、最初に簡単なルールでわかる範囲の上下関係を求め、それでも求まらなかった箇所を次のステップとして総当りで調べ上げます(以前の日記で具体的な例を示しています)。
最初のステップで、どれだけ多くの上下関係を求めるかが高速化の鍵になります。次のステップは、アルゴリズム的に結構難しく、試行錯誤でどうにか実現できました。
この基本的な考え方は目黒氏が開発した「オリヒメ」というプログラム(以前にWeb上で公開されていました)を参考にしています。まったく同じアルゴリズムではないですが、オリヒメの存在のおかげで今回の実装が実現できたと言えると思っています。目黒氏にはメールで貴重なアドバイスをいただきました。ここに感謝申し上げます。ありがとうございました。

バグとの格闘で大変でしたが、久しぶりに集中してプログラミングできたので楽しかったです(^^
兜で9パターン、鶴で5パターンの解が求まっているので、おそらく正しく動作できていると思います。計算時間はそれぞれ0.3秒、6秒程度でした(もっと高速にできると思っています)。
これを、今後ORIPAに組み込んで一般公開できるレベルまで持っていきたいのですが、それはそれでなかなか大変そうです。気長に進めたいと思います。
「これがどういう風に世の中に役に立つの?」というと、私自身もよくわからなかったりするのですが、何か未解決の問題を解くというのは、それはそれで意味があるのかな、とか思ったり。何より楽しくできればよいかと。

以下、今回求めた9つのパターンの兜(すでに既知のものではありますが)。

それとデバッグのために使った実際の兜の折紙 :-)

さて、筑波大学では来週から2学期が始まります。夏休み期間中に開発が一区切りついてホッとしました。