問題4-38〜40 - TAKUYA’s CODE RECORDER

｢4.3.2 非決定性プログラムの例｣の一つ目として、与えられた条件に合致する組み合わせを見つけるというロジックを簡潔に書けることが示されています。
問題4-38。五階建てアパートがあって、どの階にどの住人が住んでいるのかを条件から判定する例が示されています。(require (not (= (abs (- smith fletcher)) 1)))の条件を外すと、本文に出ている解以外の組み合わせが見つかるかということですが、いろいろ動かしてみたところ、( (baker 3) (cooper 4) (fletcher 2) (miller 5) (smith 1))という組み合わせを見つけることができました。
問題4-39。効率を考えよということですが、requireによって、できるだけ条件に合致する組み合わせを絞り込めた方が効率が良さそうです。例えば、最初の(require (distinct? list ...))では、全ての組み合わせがtrueになりますが、それ以降のrequireによって、trueになる組み合わせを減らしていき、falseになったら、一つ前のrequireに戻ってambによって、探索を進めていく形になります。できるだけ戻りを減らした方が良さそうですが、(require (not (= baker 5)))のような条件指定では、bakerが5階ではないという条件以外はtrueになってしまいます。falseになる確率が高いrequireを先に持ってくる方が戻りが少なくなるのではないでしょうか。今回の場合だと、二つの要素の比較を行なっているrequireを先に持ってくるべきではないかと思います。
問題4-40。(require (distinct? ...))をする前は、5の5乗の組み合わせを返す可能性がありますが、distinct?をすることで、それが5*4*3*2*1の120通りまで削減されます。しかし、120通りの組み合わせの中から条件に合致するのを一から調べるのは非効率なので、絞れるものを先に絞ってみようと思います。例えば、bakerは5階でないことがわかっているのだから、他との組み合わせを考える前に、その選択肢を除外します。次にcooperは1階ではないので、それを除外しつつ、bakerとcooperが同じ階を選択してしまわないよう、二人の間でdistinct?チェックを行ないます。このようにして、5人の中でdistinct?チェックをやってしまう前に、小さい単位で可能な組み合わせを洗い出していけば、探索処理を軽減させることができるのではないかと思いました。

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

問題4-41はschemeで上記multiple-dwellingが動くよう実装せよとのことですが、これは飛ばしました。そのため、上記ロジックが動くかどうかも未確認です。