Y箱

升目のルートの問題の最後です。

これは全探索しかないんじゃないかなぁ。
速度向上のために、枝刈りを2つ入れてみたけど、やっぱり時間がかかる。
15分以上かかった。 根本的に考え直さないとだめかなぁ。







・ 探索は左上から始めて、全ての枝を生成する方法。
・ 次の候補は、コストの低いもの優先。 sorted-mapを使って実現
・ 枝刈りは
  ① とあるマスに到達したときに、そこを通ったときにそれよりコストの低いルートがあれば、そのルートは除外する。
  ② ゴールに到着したルートがある場合、すでにそのコストを超えているルートが生成されたらそのルートは除外する。

①は、あとからより低いコストのルートが出たときに、前のルートを消すようにできればより効果的なんだけどやってない。 そこを通るやつを全部消しちゃってもいいのかなぁ。 ちゃんと考えていない。
それに、枝刈りの方法と探索の方式も合っていない気がする。





・データ構造
 ノード 枡のリスト(ルート)とそこまでのコスト。ルートは右端がスタート
  [[[3 0][2 0][1 0][0 0]] 50]

・ neighbors
 とある升目の 上下左右の升目の位置を生成。
 Joy of Clojure から取ってきた。

・ next-nodes
 あるルートから 1つ進んだ全てのルートを生成。戻ったり、ループしてたりするルートは除外している。

・ get-next-step
 あるノードから1つ進んだ全てのノードを生成。 全てのルートを作って、そののコストを計算したものを付加する。

・ make-sorted-map
 sorted-map-byを使ってsorted-mapを作る。コストの低い順に並ぶようにする。
 本体に組みこむと、ごちゃごちゃするのでくくり出した。

・ check-and-set-min-cost
 枝刈りフィルター用。
 与えられたルートの末端でのコストがすでにそこを通ったルートより高ければ、falseを返す。
 低い場合は、コストを更新して、trueを返す。

・ remove-big-route
 枝刈りフィルター
 ルートのリストから与えられたコストを超えるものを削除して返す。

・ pe83
 ルートを順に展開する。
 枡のコストの表はnode-dat、展開中のルートはres-queueに入っている。
 minimum-costはノードの最小コストの一覧。 cost-of-goalはそこまでのゴールの最小コストで初期値は無効値の-1。
 展開しながら、
  - 展開中のものが無くなったら終り
  - ゴールについたルートは保存して続ける。

 ・ pe-83-with-file
  ファイルからデータを読んで、pe83を呼ぶ。
  答えが出たら、コストが最小なものを返す。