Bisakah kendala kendala kepuasan diselesaikan dengan Prolog?

Apakah masalah "kehadiran pesta" dapat dipecahkan dalam Prolog? Sebagai contoh:

Burdock Muldoon dan Carlotta Pinkstone berkata bahwa mereka akan datang jika Albus Dumbledore datang. Albus Dumbledore dan Daisy Dodderidge keduanya mengatakan mereka akan datang jika Carlotta Pinkstone datang. Albus Dumbledore, Burdock Muldoon, dan Carlotta Pinkstone semua mengatakan mereka akan datang jika Elfrida Clagg datang. Carlotta Pinkstone dan Daisy Dodderidge mengatakan bahwa mereka akan datang jika Falco Aesalon datang. Burdock Muldoon, Elfrida Clagg, dan Falco Aesalon semuanya mengatakan mereka akan datang jika Carlotta Pinkstone dan Daisy Dodderidge keduanya datang. Daisy Dodderidge mengatakan dia akan datang jika Albus Dumbledore dan Burdock Muldoon keduanya datang. Siapa yang perlu dibujuk untuk menghadiri pesta untuk memastikan bahwa semua undangannya hadir?

Saya telah mencoba untuk mengekspresikan ini dalam GNU Prolog:

attend(BM) :- attend(AD).
attend(CP) :- attend(AD).
attend(AD) :- attend(CP).
attend(DD) :- attend(CP). 
attend(AD) :- attend(EC).
attend(BM) :- attend(EC).
attend(CP) :- attend(EC). 
attend(CP) :- attend(FA).
attend(DD) :- attend(FA).
attend(BM) :- attend(CP),attend(DD).
attend(EC) :- attend(CP),attend(DD).
attend(FA) :- attend(CP),attend(DD).
attend(DD) :- attend(AD),attend(BM).

attend(FA). /* try different seed invitees in order to see if all would attend*/

/* input:
write('invited:'),nl,
  attend(X),write(X),nl,
  fail.*/

Saya mengalami stack overflow (tanpa permainan kata-kata), dan tidak memiliki pengetahuan tentang evaluasi prolog, inilah mengapa saya bertanya.

Secara umum, masalah ini dapat dimasukkan ke dalam formula kepuasan Boolean CNF (dengan 6 variabel boolean). Oleh karena itu, apakah perspektif prolog pantas?

Untuk memecahkan masalah dengan Prolog, seperti halnya bahasa pemrograman apa pun, baik itu deklaratif atau imperatif, Anda harus memikirkan representasi solusi dan input.

Karena ini adalah pertanyaan pemrograman, itu akan populer di StackOverflow.com di mana programmer memecahkan masalah pemrograman. Di sini saya berusaha menjadi lebih ilmiah.

Untuk memecahkan masalah dalam OP, seseorang harus membalikkan hubungan yang ditentukan oleh dependensi yang dinyatakan dalam input. Klausul bentuk mudah untuk membalikkan. Klausul Sebuah t t e n d ( A D ) ∧ A t t e n d $Attend(X) \to Attend(Y) \wedge Attend(Z)$ seperti$Attend(AD)\wedge Attend(BM)\to Attend(DD)$

Daisy Dodderidge mengatakan dia akan datang jika Albus Dumbledore dan Burdock Muldoon keduanya datang

lebih sulit diobati.

Dengan Prolog pendekatan sederhana pertama adalah untuk menghindari pembalikan penuh dari hubungan dan diarahkan sebagai tujuan.

Asumsikan pemesanan pada daftar tamu dan gunakan aturan

$\qquad \left\{\begin{align} A(X)\wedge A(Y) &\to A(Z), \\ A(W)&\to A(X), \\ A(W)&\to A(Y), \\ X&<Z, \\ Y&<Z\end{align}\right\}\quad \vdash \quad A(W) \to A(Z)$

(Kami menggunakan alih-alih A t t e n d ( X ) untuk membuatnya singkat)$A(X)$$Attend(X)$

Aturan ini mudah diterapkan.

Pendekatan yang agak naif

Untuk keterbacaan, biarkan followshubungan diberikan sebagai input, dan bringskebalikannya.

Kemudian input diberikan oleh

follows(bm,[ad]).
follows(cp,[ad]).
follows(ad,[cp]).
follows(dd,[cp]).
follows(ad,[ec]).
follows(bm,[ec]).
follows(cp,[ec]).
follows(cp,[fa]).
follows(dd,[fa]).
follows(bm,[cp,dd]).
follows(ec,[cp,dd]).
follows(fa,[cp,dd]).
follows(dd,[ad,bm]).

Dan bringsdapat didefinisikan sebagai berikut:

brings(X,S):-brings(X,S,[]).

brings(_X,[],_S).
brings(X,[X|L],S):-brings(X,L,[X|S]).
brings(X,[Y|L],S):-follows(Y,[X]),brings(X,L,[Y|S]).
brings(X,[Y|L],S):-follows(Y,[A,B]),
          member(A,S),member(B,S),brings(X,L,[Y|S]).

brings/3(X,L,S)$X$

Jika kita mendefinisikan

 partymaker(X):-Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests).

Kami mendapatkan solusi unik berikut:

 [ad,ec]

Ini bukan daftar lengkap, karena menurut abjad memesan klausa

 follows(bm,[cp,dd]).

tidak bekerja.

Solusi yang agak terlibat untuk teka-teki asli

Untuk menyelesaikan masalah sepenuhnya Anda harus benar-benar membiarkan sistem mencoba membuktikan kehadiran untuk tamu kemudian tanpa memperkenalkan loop tak terbatas ke pohon pencarian. Ada banyak cara untuk mencapai tujuan ini. Masing masing punya kelebihan dan kekurangan.

Salah satu caranya adalah mendefinisikan ulang brings/2sebagai berikut:

brings(X,S):-brings(X,S,[],[]).

% brings(X,RemainsToBring,AlreadyTaken,AlreadyTried).
%
% Problem solved
brings(_X,[],_S,_N). 
% Self
brings(X,[X|L],S,N):-brings(X,L,[X|S],N). 
% Follower
brings(X,[Y|L],S,N):-follows(Y,[X]),brings(X,L,[Y|S],N). 
% Y is not a follower, but X can bring 2
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]), 
                   follows(Y,[A,B]),
                   try_bring(X,A,L,S,[Y|N]),
                   try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 1
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),\+follows(Y,[_A,_B]), 
                   follows(Y,[C]),
                   try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).

try_bring(_X,A,_L,S,_N):-member(A,S).
try_bring(X,A,L,S,N):- \+member(A,S),sort([A|L],Y),brings(X,Y,S,N).

Argumen terakhir brings/4diperlukan untuk menghindari infinite loop in try_bring.

Ini memberikan jawaban berikut: Albus, Carlotta, Elfrida dan Falco. Namun solusi ini bukan yang paling efisien karena backtracking diperkenalkan di mana kadang-kadang dapat dihindari.

Solusi umum

$r(X,S): V \to V'$

$S \subseteq V$$V' = V \cup \{X\}$

$V$$U$$V$

add_element(X,V,U):- ( var(V) -> % set difference that works in both modes
                           member(X,U),subtract(U,[X],V);
                      \+member(X,V),sort([X|V],U) ).

support(V,U):- guests(G), % rule application
               member(X,G),
               add_element(X,V,U),
               follows(X,S),
               subset(S,V).

set_support(U,V):- support(V1,U), % sort of a minimal set
               ( support(_V2,V1) -> 
                      set_support(V1,V) ; 
                 V = V1). 

is_duplicate(X,[Y|L]):- ( subset(Y,X) ; is_duplicate(X,L) ).

% purging solutions that are not truly minimal
minimal_support(U,L):-minimal_support(U,[],L).
minimal_support([],L,L).
minimal_support([X|L],L1,L2):-( append(L,L1,U),is_duplicate(X,U) -> 
                                    minimal_support(L,L1,L2); 
                                minimal_support(L,[X|L1],L2) ).


solution(L):- guests(G),setof(X,set_support(G,X),S),
              minimal_support(S,L).

Sekarang jika misalnya dataset # 2 diberikan sebagai

follows(fa,[dd,ec]).
follows(cp,[ad,bm]).
guests([ad,bm,cp,dd,ec,fa]).

Kami mendapatkan jawaban L = [[iklan, bm, dd, ec]]. Yang berarti semua tamu kecuali Carlotte dan Falco harus diundang.

Jawaban solusi ini memberi saya cocok dengan solusi yang diberikan dalam artikel Penyihir Jahat dengan pengecualian dataset # 6, di mana lebih banyak solusi dihasilkan. Ini tampaknya menjadi solusi yang tepat.

Akhirnya, saya harus menyebutkan perpustakaan Prolog CLP (FD) yang sangat cocok untuk masalah seperti ini.

Seperti yang terlihat oleh svick, masalah pertama dengan kode dalam OP adalah bahwa nama yang diawali dengan huruf besar adalah variabel dalam Prolog. Begitu admit(CP) :- admit(AD)juga dengan attend(X) :- attend(Y), yang menghasilkan Prolog segera memasuki infinite loop mencoba menunjukkan yang attendberlaku untuk beberapa istilah dengan menemukan beberapa istilah yang attendberlaku.

Namun, jika Anda bermaksud bahwa setiap set inisial menjadi istilah berbeda yang nyata, maka Anda masih akan mengalami stack overflow karena Anda memiliki siklus, mis.

attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

Jadi untuk mengetahui apakah attend(cp)Hold Prolog akan mencoba menentukan apakah attend(ad)Hold, yang akan dilakukan dengan memeriksa apakah attend(cp)Hold, dan seterusnya sampai stack overflow.

Saya tidak percaya vanilla Prolog melakukan upaya untuk menentukan apakah ada siklus seperti itu, dan memeriksa cara - cara lain untuk membuat salah satu attend(cp)atau attend(ad)benar daripada terjebak dalam loop yang tak terbatas.

Mungkin ada atau tidak ada versi Prolog yang mendukung fitur tersebut. Saya lebih terbiasa dengan Merkurius, dan saya pikir "model minimal tabling" Merkurius adalah persis apa yang Anda butuhkan untuk kasus ini. Saya tidak pernah benar-benar menggunakannya, tetapi pemahaman saya lebih atau kurang memungkinkan istilah yang menyiratkan dirinya dianggap benar jika ada beberapa cara lain untuk membuktikannya, atau salah jika tidak, tanpa terjebak dalam loop yang tak terbatas. Lihat bagian yang relevan dari dokumen Merkurius, dan jika Anda tertarik makalah yang menjelaskan implementasinya.

Merkurius adalah bahasa pemrograman logis yang dipaksakan dengan kemurnian murni, dengan sintaksis yang mirip dengan Prolog tetapi tipe dan sistem mode yang kuat, dan dikompilasi daripada ditafsirkan.

Saya baru saja membaca ulang pengantar makalah (yang belum saya baca sebentar lagi), dan itu menyebutkan tabling telah diimplementasikan dalam beberapa versi Prolog, jadi mungkin Anda bisa melangkah lebih jauh dengan googling untuk tabling dalam Prolog.

Saya menemukan makalah berikut tentang pemecahan SAT menggunakan prolog:

• A Pearl on SAT Memecahkan dalam Prolog oleh Jacob M. Howe dan Andy King

Implementasi solver dapat ditemukan di sini .

Lihat jawaban stackoverflow ini untuk perincian tentang kode dan cara menggunakannya.

Mengesampingkan masalah huruf kecil / huruf besar, ada siklus dalam klausa:

attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

Jadi, ketika Anda memanggil penerjemah top-down, itu akan berulang. Anda mungkin lebih beruntung dengan Answer Set Programming (ASP), yang berfungsi dari bawah ke atas. Berikut ini adalah pengkodean via perpustakaan ( minimal / asp ):

:- use_module(library(minimal/asp)).

choose([admit(bm)]) <= posted(admit(ad)).
choose([admit(cp)]) <= posted(admit(ad)).
choose([admit(ad)]) <= posted(admit(cp)).
choose([admit(dd)]) <= posted(admit(cp)).
choose([admit(ad)]) <= posted(admit(ec)).
choose([admit(bm)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(fa)).
choose([admit(dd)]) <= posted(admit(fa)).
choose([admit(bm)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(ec)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(fa)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(dd)]) <= posted(admit(ad)),posted(admit(bm)).

choose([admit(fa)]) <= posted(init).

Ini adalah contoh run:

Jekejeke Prolog 3, Runtime Library 1.3.8 (23 May 2019)

?- post(init), listing(admit/1).
admit(fa).
admit(cp).
admit(ad).
admit(bm).
admit(dd).
admit(ec).