Serendip

Web Studio

問題2.43

位置の集合 ((1 1)) に新しい場所の座標 (1 2 3 4) を連結する場合を取り出して調べてみる。

通常の queens 手続き

(print (flatmap
         (lambda (rest-of-queens)
                 (print "DONE1") (map (lambda (new-row)
                                             (print "DONE2") (adjoin-position new-row 2 rest-of-queens))
                                     '(1 2 3 4)))
         '(((1 1)))))

gosh> DONE1
DONE2
DONE2
DONE2
DONE2
(((1 2) (1 1)) ((2 2) (1 1)) ((3 2) (1 1)) ((4 2) (1 1)))
#<undef>

遅い queens 手続き

(print (flatmap
         (lambda (new-row)
                 (print "DONE1") (map (lambda (rest-of-queens)
                                             (print "DONE2") (adjoin-position new-row 2 rest-of-queens))
                                     '(((1 1)))))
         '(1 2 3 4)))

gosh> DONE1
DONE2
DONE1
DONE2
DONE1
DONE2
DONE1
DONE2
(((1 2) (1 1)) ((2 2) (1 1)) ((3 2) (1 1)) ((4 2) (1 1)))
#<undef>

リスト (1 2 3 4) つまり (enumerate-interval 1 board-size) に対して map 処理をするとリストの値の数（つまり board-size 回）だけ処理が発生する。
通常の queens 手続きでは、まずリスト(1 2 3 4) に対して map 処理を行い、その戻り値リストに対して flatmap 処理を行うのでリスト(1 2 3 4) に対する map 処理は1回となる。

遅い queens 手続きでは、まず queen-cols 処理の結果の ((1 1)) に対して map 処理を行い、その戻り値リストに対して flatmap 処理を行うのでリスト(1 2 3 4) に対する map 処理は計4回となる。

よって、1回の再帰処理内で board-size 回の queen-cols 処理が発生する。
従って、Louis のプログラムがエイトクイーンパズルを解く時間は、T * board-size ^ board-size となる。

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る