Problem 81 - 最短経路問題
きました。最短経路。
下記の5次の正方行列で、左上のセルから開始し右下のセルで終わる道を探索する。 ただし下方向と右方向にのみ移動できるものとする。一番小さなパスは下で赤で示されたものである。 このときの合計は2427になる。 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 今、31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 左上のセルから開始し右下のセルで終わりかつ右方向と下方向にのみ移動するときの最小の道の和を求めよ.
4*4行列での経路数は24本。
んじゃ、80*80の経路数はいくつになるかって考える。
n*n行列の経路数は、点がn^2個あって、経路が2本伸びていたと考えると、2n^2。末端は経路が無いので、2n本ひいてやると、2n(n - 1)
つまり、80*80行列の場合、2 * 80 (80 - 1)で12640経路あるわけ。「経路数だけで１万経路」
経路の組合せはあわわわわわ・・・・普通に再帰してたら終わらない。
- 最初は131なので、671,201に131を足してリストに加える(802 331)。(リストは位置つき)
- 最小の331を選ぶ。96,630に331を足してリストに加える(802 437 961)。
- もしも同じ位置だった場合は比較して低いほうを選択する。
- 続ける。
ダイクストラのアルゴリズムはO(n^2)だから・・・お・終わるかな・・・。
ま、やってみる。
(define (problem81 data) (letrec ((y-len (vector-length data)) (x-len (vector-length (vector-ref data 0))) (get (lambda (x y) (if (or (>= x x-len) (>= y y-len)) 999999999999999999999999 ; 無限 (vector-ref (vector-ref data y) x)))) (remove-min (lambda (s cont) (letrec ((iter (lambda (x m acc) (if (null? x) (cont m acc) (if (< (cdar x) (cdr m)) (iter (cdr x) (car x) (cons m acc)) (iter (cdr x) m (cons (car x) acc))))))) (iter (cdr s) (car s) '())))) (update (lambda (x y sum l) (let ((res (assoc (cons x y) l)) (new (+ (get x y) sum))) (if res (begin (if (< new (cdr res)) (set-cdr! res new)) ; update l) (cons (cons (cons x y) new) l))))) ; new (update2 (lambda (m l) (let ((x (caar m)) (y (cdar m)) (sum (cdr m))) (update x (+ y 1) sum (update (+ x 1) y sum l))))) ; (iter (lambda (l end) ; (remove-min l ; (lambda (m acc) ; (if (equal? (car m) end) ; m ; (iter (update2 m acc) ; end)))))) (iter (lambda (l end) (let ((e (assoc end l))) (or e (iter (remove-min l update2) end)))))) (cdr (iter (list (cons '(0 . 0) (get 0 0))) (cons (- x-len 1) (- y-len 1)))))) (problem81 *data81*) ; 427337
本当の最短経路ではないかも知れないけど、とりあえず末端まで行ったら計算を打ち切ることにした。計算時間は100秒くらい。
コメントアウトしてあるバージョンだと終わらないのだ。
最小の値を求めるのに時間がかかっているっぽいので、順序付きリストで挿入すればまだまだ早くなりそう。
