SICPゼミ第58回

練習問題4.38

#lang racket
(require sicp-pict)

(define (require p) (if (not p) (amb) 0))

(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items )))))

(define (multiple-dwelling)
  (let (( baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5))
                                 (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5))
                                 (smith (amb 1 2 3 4 5)))
    (require
      (distinct? (list baker cooper fletcher miller smith )))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper ))
    ;(require (not (= (abs (- smith fletcher )) 1)))
    (require (not (= (abs (- fletcher cooper )) 1)))
    (list (list 'baker baker) (list 'cooper cooper)
          (list 'fletcher fletcher) (list 'miller miller)
          (list 'smith smith ))))

実行結果

> (multiple-dwelling)
'((baker 1)
  (cooper 2)
  (fletcher 4)
  (miller 3)
  (smith 5))
> (amb)
'((baker 1)
  (cooper 2)
  (fletcher 4)
  (miller 5)
  (smith 3))
> (amb)
'((baker 1)
  (cooper 4)
  (fletcher 2)
  (miller 5)
  (smith 3))
> (amb)
'((baker 3)
  (cooper 2)
  (fletcher 4)
  (miller 5)
  (smith 1))
> (amb)
'((baker 3)
  (cooper 4)
  (fletcher 2)
  (miller 5)
  (smith 1))
> (amb)
. . amb tree exhausted

by tube

練習問題4.39

制約の順番が最終的な解に影響を与えることはない(集合のcap演算子は結合的)．順番が時間に影響をあたえることはある． 最初は120個の可能性があるが，

(require (not (= baker 5)))

みたいなのは24個を除外する．

(require (> miller cooper))

は60個を除外する．

(require (not (= (abs (- smith fletcher)) 1)))

は4!×2=48個を除外する．

なので最初に60個除外してしまうのがよい．

↑間違い。
各制約について、そのrequire命令が下された時点では、「今探索している各変数の値がその制約を満たすかどうか」を判定するだけであり、「その制約を満たさない可能性（枝）をすべて取り除いている」というわけではない。
本質的に深さ1の5^5分木を深さ優先で探索しているにすぎない。そのため、require文によって計算時間は変わらない……と言いたいところだが、ここで各制約の実行時間がキーファクターとなることに注意されたい。 今回の制約の中で、distinct? だけが再帰的であり、他の制約に比べ実行時間が非常に長くなっている。そのため、できるだけdistinct?の実行回数を減らすことで計算時間の短縮が可能となる。
元のコードのようにdistinct?の制約を一番上に持ってくると (amb) が更新される（何らかの制約を満たさないことによって）たびにdistinct?から判定されることになる。逆にdistinct?を一番下に持ってくることでできるだけdistinct?の実行回数を減らすことができ、計算時間の短縮につながる。

by tube

練習問題4.40

階の割り当てが別々でないといけないという制約の前は5^5通り、制約の後では5!通り。

4.39で述べた通り、各 require 文の判定の時に「その制約を満たさない」探索範囲がすべて排除されているわけではない。例えば baker が5階でない、という制約については何度も繰り返しその制約文に帰って判定が行われていることになるが、これは非常に無駄が多い。
そこで、各 require 文では（特に制約をかける変数が1つや二つなど少数の場合には）、その制約に関係のない他の変数を宣言する前に無駄な探索範囲をすべて削ってしまったほうが良い。
すなわち、深さ1の 5^5 分木だった探索範囲を、深さ5にしてやり、各制約について枝刈りをしてやれば効率化できる。

;もとのアルゴリズム
(define (multiple-dwelling)
  (let (( baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5))
                                 (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5))
                                 (smith (amb 1 2 3 4 5)))
    (require
      (distinct? (list baker cooper fletcher miller smith )))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper ))
    (require (not (= (abs (- smith fletcher )) 1)))
    (require (not (= (abs (- fletcher cooper )) 1)))
    (list (list 'baker baker) (list 'cooper cooper)
          (list 'fletcher fletcher) (list 'miller miller)
          (list 'smith smith))))

;高速化したもの
(define (multiple-dwelling-tube)
  (let ((baker (amb 1 2 3 4 5)))
    (require (not (= baker 5)))
    (let ((cooper (amb 1 2 3 4 5)))
      (require (not (= cooper 1)))
      (let ((fletcher (amb 1 2 3 4 5)))
        (require (not (= fletcher 5)))
        (require (not (= fletcher 1)))
        (require (not (= (abs (- fletcher cooper)) 1)))
        (let ((miller (amb 1 2 3 4 5)))
          (require (> miller cooper))
          (let ((smith (amb 1 2 3 4 5)))
            (require (not (= (abs (- smith fletcher)) 1)))
            (require (distinct? (list baker cooper fletcher miller smith)))
            (list (list 'baker baker) (list 'cooper cooper)
                  (list 'fletcher fletcher) (list 'miller miller)
                  (list 'smith smith ))))))))

by tube