摩訶不思議!深さ優先探索
Rails側のViewの実装がほぼ終わり、土曜日から延々シミュレーションの部分のアルゴリズムを書いていました。
やりたいことは時間量を少し無視しつつも、それなりに速い探索でしたので、「欲張り法 + 深さ優先探索」を利用しました。
速さを出すために、これまで頑張って作ってきたはずのモデル類から切り離して、DBアクセスを初期値読み込みのときのみに絞り込んでいます。
大体はボクの思惑通りだったのですが、「深さ優先探索」が落とし穴でした。(^^;
Haskellで勉強しているとは言っても、やはり「再帰表現」は慣れないですね。再帰呼出をするときは、
- 終了条件考えて、
- 探索失敗時の返値を決めて、
- 破壊した部分を元に戻して、
- 戻り値の整合性を解決する
わけですが、この再帰表現を使うと嬉しいのは、1番2番さえきちんとやっておけば、3番の処理をシンプルに書けることです。今回の探索では、配列の配列が返値ですので、
- 終了条件:⇒ 探索{失敗 or 成功}
- 探索失敗時の返値:⇒ 空の配列
- 破壊した部分を元に戻す:⇒ 選択したオブジェクトを未選択状態にする
- 戻り値の整合性を解決する:⇒ 配列の足し算
という感じになったわけですが、途中までメチャクチャいい加減な値を返していたメソッドが突然正しそうな結果を出力すると、かなり焦ります。(^^;;;
とりあえず、簡単なサンプルでいくつか手計算したものと同様の結果を出しましたので、今回はここで止めておくことにします。
ようやく最後のビューの作成に入れます。これが終われば、ようやくプレー再開です。