本当は怖いHPC

HPC屋の趣味&実益ブログ

前からやってみようと思っていたのだが、人材獲得作戦・4 試験問題ほか に書いてある迷路の問題をやってみた。2時間くらいかかってしまって反省。学会に参加するための新幹線の中でビールを飲みながらやったのが、それを差し引いてももう少し速くできない物かなぁと。修行が足りません。

アルゴリズムは、スタートに隣接しているセルからスタートしてスタートからの距離を再帰的に求めていくというもので、単純に実装したので計算量は大きい(しかも、最短性を保証するためには、各マスの距離が収束するまでやらないといけないし)

具体的には、全マス数Nに対して O(N^2)になると思う(あまりちゃんと考えていない)。スタート地点から始めてグラフの幅優先探索をすれば、空白のセル数N_{sp}に対して O(N_{sp})になるはずだが面倒だったので実装しなかった。

で、これをやってみたのは、単にアルゴリズムをやりたかっわけではなくて、言語の勉強のネタにしたかったから。とりえずアルゴリズムの確認のためにPythonで書いたけど、次にHaskellClojure、Goあたりで練習を兼ねて作成する予定。

あー、はてなダイアリーはgistの貼り付けはできないのか。

https://gist.github.com/keisukefukuda/6119007

【広告】