SICP 読み (211) 4.3.2 非決定性プログラムの例

SICP scheme

問題 4.43

前提として Downing の船は Barnacle のムスメの名前で、Parker の船は Moore のムスメ、ってコトで良いのだろうか。それとも可能性は全部検討すべきなのかなぁ。

Moore    : Lorna
Downing  : Melissa Barnacle
Hall     : Rosalind
Barnacle : Gabrielle
Parker   : Mary Ann Moore

例えばこんなカンジとか??

(let ((Moore (amb 2 3 5))
      (Downing 4)
      (Hall (amb 2 5))
      (Barnacle (amb 2 3 5))
      (Parker 1))

これを 2.40 なソレ式で ... ってゆー事で検討してみる。

つづき

なんとなく微妙。属性が足らないカンジ、と言えば良いのか。可能性を数え上げてみると以下。面倒臭いので (Moore Dowing Hall Barnacle Parker) なリストで表現。

(2 4 5 3 1)
(3 4 5 2 1)
(3 4 2 5 1)
(5 4 2 3 1)

これをどうやって_制限_でフィルタするのか、が一番の問題。制限として設定しなければならないのは_Gabrielle の父親は Parker 博士の娘の名前を付けたヨットを_という部分。この制限は

  • Barnacle の船は Gabrielle なので彼は Gabrielle の父親ではない
  • Moore の娘は Mary Ann なので彼は Gabrielle の父親ではない
  • Dowing の船は Barnacle の娘の名前になっているので Gabrielle の父親ではない

という事になるんで Gabrielle の父親は Hall 又は Parker のどちらかになる。昨晩のエントリにも書きましたが Gabrielle の父親が Parker だとすると、彼の船の名前は Gabrielle でないと駄目、という事になり、これは前提に反している。

頭がテンパっとります

ちょっとこのあたり、昨晩のエントリと違うな。大丈夫かなぁ。
上記をビンゴとすると、Gabrielle の父親は Hall になります。ちょっと整理してみると以下。

  • Moore の船の名前は Lorna で彼女の父親は Dowing 又は Hall
  • Dowing の船の名前は Melissa で彼女の父親は Barnacle
  • Hall の船の名前は Rosalind で彼女の父親は Parker
  • Barnacle の船の名前は Gabrielle で彼女の父親は Hall
  • Parker の船の名前は Mary Ann で彼女の父親は Moore

ええと、Gabrielle (Barnacle の船の名前) の父親が判明した時点で Parker の娘が確定するんですが、これを制限で表現するためには属性が足らない、というのが (以下略
とほほ。今日は駄目だ。あきらめます。(弱