うそつき娘問題を制約プログラミングで解く

コメント

“うそつき娘問題を制約プログラミングで解く” への2件のフィードバック

1. 

   2015年10月13日

   SUGA

   実行時間は瞬時ですか？

   「３人が当たり、１人が外れました。」とありますが、
   この制約はプログラムではどの部分で表現されていますか？

   返信
   1. 

      2015年10月13日

      koyahata

      >>sugaさん
      実行時間は瞬時で、今回は解が１つのみでしたが他に可能性のある順位の組み合わせも全部取得できます。

      リスト HatugenFlgLst の各要素に各発言者の発言の真偽が入るのですが、
      HatugenFlgLst ins 0..1　　という文が「それぞれの要素が0(偽)または1(真)のみ」という制約で、
      appear_times(HatugenFlgLst,0,1),　　という文が「HatugenFlgLstの中には0が1回出現する」という制約を表しています(残りの3つが1というのは変数が0か1しか取らないという制約があるので記載する必要が無い）

      下のほうでappear_times述語を定義しているのですが、この説明は少し難しく、
      まず中で使われている eq_b(X,Y,B)という述語の説明をすると、これはXとYとBの関係を表す制約なのですが、
      eq_b(X,Y,B):-(X#=Y) #<==>B　という文で「 X=Y と B=1 という条件が互いに必要十分条件を満たす」という制約を表します(Bが1:True 0:False)
      具体的には、以下の制約が満たされます
      「X=Yであれば必ずB=1」
      「B=1であれば必ずX=Y」
      「X!=Yであれば必ずB=0」
      「B=0であれば必ずX!=Y」

      そして appear_times述語の説明ですが、
      maplist というのは prolog でよく使われる述語でだいたい以下のような役割をしています
      「述語にリストの各要素を引数として渡し、その結果を新しいリストに出力する」
      appear_times(Lst,Num,Times):-
      maplist(eq_b(Num),Lst,Bs),
      上記の記述の場合は、eq_b の3つの引き数のうち、
      「はじめの引き数にはNum固定、2番目にはLstの各要素を渡し、eq_bをLstの要素数回呼ぶ。Bsには各eq_b呼出し毎の戻り値がリストになって返ってくる」ことを意味しています。
      (実際はPrologは引き数と戻り値の概念がなくもっと入出力双方向性があるのですが今回はこの解釈でよいです)

      この時点でBsには各発言者の「発言が正しければ1、間違っていれば0」という制約がついた変数のリストが存在することになります。

      そして
      sum(Bs,#=,Times)　で 「Bsの和がTimesと同じ(今回は1)」という制約を記述しています。

      説明するときにPrologの文法か CLPFDライブラリの文法かを明確に分けなくてはいけないのですが、以下となります。
      Prologの組み込み述語　…　write,maplist
      CLPFDライブラリの述語　…　ins A..B , #<==>, #=, label, sum, #<, #\/, all_different

      返信