■
前からやってみようと思っていたのだが、人材獲得作戦・4 試験問題ほか に書いてある迷路の問題をやってみた。2時間くらいかかってしまって反省。学会に参加するための新幹線の中でビールを飲みながらやったのが、それを差し引いてももう少し速くできない物かなぁと。修行が足りません。
アルゴリズムは、スタートに隣接しているセルからスタートしてスタートからの距離を再帰的に求めていくというもので、単純に実装したので計算量は大きい(しかも、最短性を保証するためには、各マスの距離が収束するまでやらないといけないし)
具体的には、全マス数Nに対してになると思う(あまりちゃんと考えていない)。スタート地点から始めてグラフの幅優先探索をすれば、空白のセル数に対して になるはずだが面倒だったので実装しなかった。
で、これをやってみたのは、単にアルゴリズムをやりたかっわけではなくて、言語の勉強のネタにしたかったから。とりえずアルゴリズムの確認のためにPythonで書いたけど、次にHaskell、Clojure、Goあたりで練習を兼ねて作成する予定。
あー、はてなダイアリーはgistの貼り付けはできないのか。