Scheme - 非決定性プログラムの例(論理パズル(各制限の依存関係と効率性))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.3(Scheme の変形 - 非決定性計算)、4.3.2(非決定性プログラムの例)、論理パズル、問題 4.40を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 4.40

人への割当ての組数。

解の割当てが相違なるという要求をする前は5^5、後では5!。

以下のコードの場合の解の割当てが相違なるという要求をする前と後の組数。

前の組数を求める。(後の組数は、解の組数なので1組。)

• fletcherが2の場合
  • cooperが2の場合
    • millerが3の場合
      • smithが2の場合
      • smithが4の場合
      • smithが5の場合
    • millerが4の場合
      • smithが2の場合
      • smithが4の場合
      • smithが5の場合
    • millerが5の場合
      • smithが2の場合
      • smithが4の場合
      • smithが5の場合
  • cooperが4の場合
    • millerが5の場合
      • smithが2の場合
      • smithが4の場合
      • smithが5の場合
  • cooperが5の場合
    • 制限を満たすもの無し。
• fletcherが3の場合
  • cooperが3の場合
    • millerが4の場合
      • smithが1の場合
      • smithが3の場合
      • smithが5の場合
    • millerが5の場合
      • smithが1の場合
      • smithが3の場合
      • smithが5の場合
  • cooperが5の場合
    • 制限を満たすもの無し。
• fletcherが4の場合
  • cooperが2の場合
    • millerが3の場合
      • smithが1の場合
      • smithが2の場合
      • smithが4の場合
    • millerが4の場合
      • smithが1の場合
      • smithが2の場合
      • smithが4の場合
    • millerが5の場合
      • smithが1の場合
      • smithが2の場合
      • smithが4の場合
  • cooperが4の場合
    • millerが5の場合
      • smithが1の場合
      • smithが2の場合
      • smithが4の場合

この各場合について、bakerが1、2、3、4の場合があるので、30*4 = 120通り。5の5乗(5^5)の3125通りより大幅に減らすことができて、手続きdistinct?の実行回数を減らすことができたので、遥かに効率的な非決定性手続きを書くことが出来た。

コード(BBEdit)

sample.scm

(define (multiple-dwelling)
  (let ((fletcher (amb 2 3 4))
        (cooper (amb 2 3 4 5)))
    (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 (- fletcher smit) 1))))
        (let ((baker (amb 1 2 3 4)))
          (require (distinct? (list baker cooper fletcher miller smith)))
          (list (list 'baker baker)
                (list 'cooper copper)
                (list 'fletcher fletcher)
                (list 'miller miller)
                (list 'smith smith)))))))

ambから直接取り除くのではなく、requireで失敗させる場合。(上記の組数を数えるのは、簡便に済ますために最初のコードの考え方で求めた。)

コード(BBEdit)

sample.scm

(define (multiple-dwelling)
  (let ((fletcher (amb 1 2 3 4 5)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (let ((cooper (amb 1 2 3 4 5)))
      (require (not (= cooper 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 (- fletcher smit) 1))))
          (let ((baker (amb 1 2 3 4 5)))
            (require (not (= baker 5)))
            (require (distinct? (list baker cooper fletcher miller smith)))
            (list (list 'baker baker)
                  (list 'cooper copper)
                  (list 'fletcher fletcher)
                  (list 'miller miller)
                  (list 'smith smith))))))))

まだ、Amb-Eval(amb評価器)の実装が完成してないので、完成したら実際に入力して確認してみることに。