3

我最近开始学习 Prolog 是为了好玩。我发现了以下谋杀之谜。由于除了基础知识之外我对 Prolog 知之甚少,因此我无法真正评估链接中提供的解决方案,但是,它对我来说似乎并不是特别好。我的解决方案不足以产生正确的答案,所以我正在寻找一些关于如何到达那里的指示,或者是否有可能用我的方法到达那里。这是万一链接断开的难题:

要查明是谁杀死了博迪先生,您需要了解每个人在哪里,以及房间里有什么武器。线索分散在整个测验中(在阅读完所有 10 个问题之前,您无法解决问题 1)。

首先,您需要了解嫌疑人。有三个男人(乔治、约翰、罗伯特)和三个女人(芭芭拉、克里斯汀、约兰达)。每个人都在不同的房间(浴室、餐厅、厨房、客厅、储藏室、书房)。在每个房间里都发现了一件可疑的武器(袋子、火器、毒气、刀、毒药、绳子)。谁在厨房被发现?

线索1:厨房里的人没有带绳子、刀或包。那么,在厨房里发现了哪种武器,而不是枪支呢?

线索 2:芭芭拉要么在书房,要么在浴室;约兰达在另一个。芭芭拉是在哪个房间找到的?

线索 3:提包的人既不是芭芭拉也不是乔治,他既不在浴室也不在餐厅。谁把包放在房间里?

线索4:在研究中发现了拿着绳子的女人。绳子是谁拿的?

线索 5:客厅里的武器是在约翰或乔治身上找到的。客厅里放着什么武器?

线索6:刀不在餐厅里。那么刀在哪里呢?

线索 7:Yolanda 没有携带在书房和储藏室中发现的武器。与尤兰达一起发现了什么武器?

线索 8:枪和乔治在房间里。枪支是在哪个房间找到的?

人们发现博迪先生在储藏室里被毒死了。在那个房间里发现的嫌疑人就是凶手。那么,你指的是谁呢?

这是作者解决方案的链接。

这是我尝试的解决方案:

male(george).
male(john).
male(robert).

female(barbara).
female(christine).
female(yolanda).

person(X) :- male(X).
person(X) :- female(X).

room(kitchen).
room(bathroom).
room(diningroom).
room(livingroom).
room(pantry).
room(study).

weapon(bag).
weapon(firearm).
weapon(gas).
weapon(knife).
weapon(poison).
weapon(rope).

/*
Clue 1: The man in the kitchen was not found with 
        the rope, knife, or bag. 
        Which weapon, then, which was not the firearm, 
        was found in the kitchen?
*/

/* X is Weapon, Y is Room, Z is Person */

killer(X, Y, Z) :-
    room(Y) = room(kitchen),
    male(Z),
    dif(weapon(X), weapon(rope)),
    dif(weapon(X), weapon(knife)),
    dif(weapon(X), weapon(bag)),
    dif(weapon(X), weapon(firearm)).

/*
Clue 2: Barbara was either in the study or the bathroom; 
        Yolanda was in the other. 
        Which room was Barbara found in?
*/

/* It was easy to deduce the following from other data */

killer(X, Y, Z) :-
    female(Z) = female(barbara),
    room(study) = room(Y).

killer(X, Y, Z) :-
    female(Z) = female(yolanda),
    room(bathroom) = room(Y).

/*
Clue 3: The person with the bag, who was not Barbara nor 
        George, was not in the bathroom nor the dining room. 
        Who had the bag in the room with them?
*/
killer(X, Y, Z) :-
    weapon(bag) = weapon(X),
    dif(room(Y), room(bathroom)),
    dif(room(Y), room(diningroom)),
    dif(person(Z), male(george)),
    dif(person(Z), female(barbara)).


/*
Clue 4: The woman with the rope was found in the study. 
        Who had the rope?
*/
killer(X, Y, Z) :- 
    weapon(rope) = weapon(X),
    room(study) = room(Y),
    female(Z).

/*
Clue 5: The weapon in the living room was found with either 
        John or George. What weapon was in the living room?
*/

killer(X, Y, Z) :-
    room(Y) = room(livingroom),
    dif(male(Z), male(robert)).

/*
Clue 6: The knife was not in the dining room. 
        So where was the knife?
*/

killer(X, Y, Z) :-
    weapon(knife) = weapon(X),
    room(Y) \= room(diningroom).

/*
Clue 7: Yolanda was not with the weapon found 
        in the study nor the pantry. 
        What weapon was found with Yolanda?
*/

killer(X, Y, Z) :-
    female(yolanda) = female(Z),
    dif(room(study), room(Y)),
    dif(room(pantry), room(Y)).

/*
Clue 8: The firearm was in the room with George. 
        In which room was the firearm found?
*/

killer(X, Y, Z) :-
    weapon(firearm) = weapon(X),
    male(george) = male(Z).

/*
It was discovered that Mr. Boddy was gassed in the pantry. 
The suspect found in that room was the murderer. 
Who, then, do you point the finger towards?
*/

killer(X, Y, Z) :-
    room(Y) = room(pantry),
    weapon(X) = weapon(gas).
4

3 回答 3

4

我对这个问题采取了更积极的态度。我没有尝试任何形式的否定,而是进行了简单的统一。

关键是这个谓词对:

members([],_).
members([M|Ms],Xs) :- select(M,Xs,Ys),members(Ms,Ys).

这是一个基本的置换谓词。它将采用第一个参数的列表并尝试统一第二个列表的所有排列。

现在很多规则变得很容易表达:

例如,线索 1:

clue1(House) :- members([[P,kitchen,_],[_,_,rope],[_,_,knife],[_,_,bag],[_,_,firearm]],House),man(P).

所以这意味着rope,knife和都是房子的成员,但在不同的房间bag里。Prolog 将继续回溯,直到找到适合这些项目的情况。firearmkitchen

这是我的完整解决方案:

man(george).
man(john).
man(robert).
woman(barbara).
woman(christine).
woman(yolanda).

members([],_).
members([M|Ms],Xs) :- select(M,Xs,Ys),members(Ms,Ys).

clue1(House) :- members([[P,kitchen,_],[_,_,rope],[_,_,knife],[_,_,bag],[_,_,firearm]],House),man(P).
clue2(House) :- member([barbara,study,_],House), member([yolanda,bathroom,_],House).
clue2(House) :- member([barbara,bathroom,_],House), member([yolanda,study,_],House).
clue3(House) :- members([[_,_,bag],[barbara,_,_],[george,_,_]],House),members([[_,_,bag],[_,bathroom,_],[_,dining_room,_]],House).
clue4(House) :- members([[P,study,rope]],House),woman(P).
clue5(House) :- members([[john,living_room,_]],House).
clue5(House) :- members([[george,living_room,_]],House).
clue6(House) :- members([[_,_,knife],[_,dining_room,_]],House).
clue7(House) :- members([[yolanda,_,_],[_,study,_],[_,pantry,_]],House).
clue8(House) :- member([george,_,firearm],House).
clue9(House,P) :- members([[P,pantry,gas]],House).

solve(X) :-
    House = [[_,bathroom,_],[_,dining_room,_],[_,kitchen,_],[_,living_room,_],[_,pantry,_],[_,study,_]],
    clue1(House),
    clue2(House),
    clue3(House),
    clue4(House),
    clue5(House),
    clue6(House),
    clue7(House),
    clue8(House),
    clue9(House,X),
    members([[george,_,_],[john,_,_],[robert,_,_],[barbara,_,_],[christine,_,_],[yolanda,_,_]],House),
    members([[_,_,bag],[_,_,firearm],[_,_,gas],[_,_,knife],[_,_,poison],[_,_,rope]],House),
    write(House),
    true.

那给了我:

?- solve(X).
[[yolanda,bathroom,knife],[george,dining_room,firearm],[robert,kitchen,poison],[john,living_room,bag],[christine,pantry,gas],[barbara,study,rope]]
X = christine .
于 2020-05-17T08:52:38.017 回答
1

编辑:在https://swish.swi-prolog.org/p/crime_constraints.pl查看参考解决方案的改进版本。

我同意您链接到的解决方案很丑陋,但它确实使用了正确的方法。你的方向并不完全正确。一些备注:

/* X is Weapon, Y is Room, Z is Person */

为什么不使用变量名Weapon, Room,Person然后呢?它使您的程序更易于阅读。

weapon(rope) = weapon(X)

这完全等同于只写X = ropeor rope = X

但除此之外,您处理这个难题的方式还有另外两个大问题:

首先,您没有将对象之间的关系建模为数据。例如,对于“在研究中发现了拿着绳子的女人”。你有这个条款:

killer(X, Y, Z) :- 
    weapon(rope) = weapon(X),
    room(study) = room(Y),
    female(Z).

这确实有三个解决方案,可以将其解释为“关系killer(rope, study, barbara)、、killer(rope, study, christine)killer(rope, study, yolanda)”,但您的程序不知道如何以这种方式解释它。您实际上并没有构建表达这种关系的数据。这就是您链接到的解决方案正确执行的操作:它将房间和武器建模为可以绑定到代表人的原子的变量。因此,它可以将这条线索表达为woman(Rope)(“拿着绳子的人是女人”)和Rope = Study(“绳子和书房与同一个人相关联”)。

第二个大问题是您将所有线索建模为同一谓词的不同子句。这是错误的,因为在 Prolog 中,谓词的不同子句表达了一个选择:如果第一个子句成立第二个子句成立第三个子句成立,等等。但是你想表达第一条线索第二条线索成立,第三条线索成立,依此类推。而“和”是通过在一个子句,的主体中结合不同的条件来表示的。这就是为什么链接的解决方案有不同的谓词,等等,所有这些都是从一个大谓词的主体中调用的。clue1clue2

于 2020-05-13T14:58:26.660 回答
0

依次从线索中推导出规则

每个人都在不同的房间(浴室、餐厅、厨房、客厅、储藏室、书房)。在每个房间里都发现了一件可疑的武器(袋子、火器、毒气、刀、毒药、绳子)。

unique(A,B,C,D,E,F) :- 
     A \= B, A \= C, A \= D, A \= E, A \= F,
     B \= C, B \= D, B \= E, B \= F,
     C \= D, C \= E, C \= F,
     D \= E, D \= F,
     E \= F.

suspicious(pwr(george,WA,RA), pwr(john,WB,RB), pwr(robert,WC,RC), pwr(barbara,WD,RD), pwr(christine,WE,RE), pwr(yolanda,WF,RF)) :- 
    weapon(WA), weapon(WB), weapon(WC), weapon(WD), weapon(WE), weapon(WF),
    unique(WA,WB,WC,WD,WE,WF),
    room(RA), room(RB), room(RC), room(RD), room(RE), room(RF),
    unique(RA,RB,RC,RD,RE,RF).

现在让我们检查

线索1:厨房里的人没有带绳子、刀或包。那么,在厨房里发现了哪种武器,而不是枪支呢?

clue1(L) :-
    oneof(pwr(P,W,kitchen),L),
    male(P),
    weapon(W),
    W \= rope, W \= knife, W \= bag, W \= firearm.

我们对 8 条线索中的每一条都执行此操作,最后

人们发现博迪先生在储藏室里被毒死了。在那个房间里发现的嫌疑人就是凶手。那么,你指的是谁呢?

killer(X, L) :- member(pwr(X,gas,pantry),L).

resolved(X) :-
    suspicious(A,B,C,D,E,F),
    L = [A,B,C,D,E,F],
    clue1(L),
    clue2(L),
    clue3(L),
    clue4(L),
    clue5(L),
    clue6(L),
    clue7(L),
    clue8(L),
    killer(X, L).

可以找到运行完整的程序。推理相当慢(但比作者的解决方案更快)。

为什么认为使用关系而不是变量绑定是更好的设计?

我将序言程序理解为获取知识的规则集。这意味着:

  • prolog 中的每个关系都应该描述域中的关系
  • 向世界添加实体(武器、人员、房间)不应使规则集过时。问题没有改变(我们只是扩展了世界),所以不需要触及规则和查询。
  • 扩展问题(例如通过添加第七个位置)应该具有最小的影响

在引用的解决方案中,并非每个方面都是最佳的,如果更熟悉 prolog,某些方面可能会更好地表达。

为什么我认为规则集应该对世界变化具有鲁棒性?

我在程序分析中使用了数据日志。这意味着源代码(或字节码)中的每个关系都被建模为事实,规则推断类型、安全漏洞、设计模式等。有数百万个事实和数千个规则集代码。添加实体(例如源代码行、类型注释)不应该促使我重新实现规则集代码(这很难正确编写)。

为什么我认为使用隐式关系是不好的代码?

考虑参考解决方案中的这段代码,它完全具有误导性:

clue1(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope) :-
   man(Kitchen),       // a man is a kitchen?
   \+Kitchen=Rope,     // a kitchen is not a rope?
   \+Kitchen=Knife,    // a kitchen is not a knife?
   \+Kitchen=Bag,      // a kitchen is not a bag
   \+Kitchen=Firearm.  // a kitchen is not a firearm

好的,变量名很难看,可读性更好

clue1(InBathroom, InDiningroom, InKitchen, InLivingroom, InPantry, InStudy, WithBag, WithFirearm, WithGas, WithKnife, WithPoison, WithRope) :-
   man(InKitchen),     // (person) in the kitchen is a man - ok
   \+Kitchen=Rope,     // (person) in the kitchen is not 
                          (person) with a rope - better than above
   \+Kitchen=Knife,    // ...
   \+Kitchen=Bag,      // ...
   \+Kitchen=Firearm.  // ...

但是我们将等式关系误用于显式关系。有一个明确的指标:名称中包含谓词的变量可能是隐式关系。“personInKitchen”是连接两个实体“person”和“kitchen”的(逻辑)谓词“in”。

作为比较具有列表和功能符号的模型(suspect/3是将人员与武器和房间连接起来的关系函数,Suspects是嫌疑人列表):

clue1(Suspects) :-    
    member(suspect(Person,Weapon,Room),Suspects), 
    male(Person),     // The man (Person)
    Room = kitchen,   // in the Kitchen (Room)
    Weapon \= rope,   // was not found with the (Weapon) rope
    Weapon \= knife,  // (Weapon) knife
    Weapon \= bag,    // (Weapon) bag
    Weapon \= firearm.// (Weapon) firearm

概括

因此,如果您将 prolog 用于私人目的,我不介意“滥用”变量来快速解决问题。但是,如果您的规则集和数据增长,在我看来,对所有关系进行显式建模是非常必要的。

于 2020-05-13T21:47:35.907 回答