Euler : Problem 83

Posted by YpsilonTAKAI On 2012年5月2日水曜日 0 コメント
升目のルートの問題の最後です。

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







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

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


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 83 : 2012/5/2
;;"Elapsed time: 945939.230791 msecs"
(defn neighbors
([size yx] (neighbors [[-1 0][1 0][0 -1][0 1]] size yx))
([deltas size yx]
(filter (fn [new-yx]
(every? #(< -1 % size) new-yx))
(map #(vec (map + yx %)) deltas))))
(defn next-nodes [size route]
(let [ngbrs (neighbors size (first route))]
(filter (fn [nb] (if (some #(= nb %) route) false true) ) ngbrs)))
(defn get-next-step [node-dat [route cost]]
(map #(vector (vec (cons % route)) (+ cost (get-in node-dat %)) )
(next-nodes (count node-dat) route)))
(defn make-sorted-map [seed]
(into (sorted-map-by #(compare [(get seed %1) %1]
[(get seed %2) %2]))
seed))
(defn check-and-set-min-cost [[route cost] db]
(let [min-cost (get @db (first route) )]
(if (or (nil? min-cost) (> min-cost cost))
(do (swap! db assoc (first route) cost)
true)
false)))
(defn remove-big-route [cost-th routes]
(if (< cost-th 0)
routes
(let [abaves (filter #(> (get routes %) cost-th) (keys routes))]
(apply dissoc routes abaves))))
(defn pe83 [n]
(let [node-dat n
size-row (count node-dat)
size-col (count (first node-dat))
res-queue (make-sorted-map {'[[0 0]] (first (first node-dat))})
minimum-cost (atom {})
cost-of-goal (atom -1)]
(loop [res-queue res-queue res-route-list [] ]
(let [tgt (first res-queue)]
(cond (empty? res-queue)
,, res-route-list
(= (first (first tgt)) [(dec size-row) (dec size-col)])
,,(do (reset! cost-of-goal (min (second tgt) @cost-of-goal))
(recur (->> (first tgt)
(dissoc res-queue ,,)
(remove-big-route @cost-of-goal ,,))
(conj res-route-list tgt)))
:t
,, (let [next-node-list (->> (get-next-step node-dat tgt)
(filter #(check-and-set-min-cost % minimum-cost) ,,))]
(recur (->> (into (dissoc res-queue (first tgt)) next-node-list)
(remove-big-route @cost-of-goal ,,))
res-route-list)))))))
(defn pe-83-with-file [input-file]
(with-open [in-file (io/reader input-file)]
(let [node-dat (vec (map (fn [line-dat]
(vec (map (fn [s] (Integer. s))
(.split line-dat ","))))
(line-seq in-file)))]
(->> (pe83 node-dat)
(reduce #(if (> (second %1) (second %2)) %2 %1)
,,)))))
;; test data
(def node-dat
[[131 673 234 103 18]
[201 96 342 965 150]
[630 803 746 422 111]
[537 699 497 121 956]
[805 732 524 37 331]])
(def n1 [[1 8 1]
[7 5 12]
[1 10 1]])
view raw pe_83.clj hosted with ❤ by GitHub



・データ構造
 ノード 枡のリスト(ルート)とそこまでのコスト。ルートは右端がスタート
  [[[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を呼ぶ。
  答えが出たら、コストが最小なものを返す。


ラベル: ,

0 コメント:

コメントを投稿