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