14

我需要一些帮助来完成我的 AI 课程的序言作业。问题是为爱因斯坦的谜题编写序言代码。我知道如何自己写下来，但在家庭作业中有一些限制。

 there are 5 houses
 the Englishman lives in the red house
 the Spaniard owns the dog
 coffee is drunk in the green house
 the Ukrainian drinks tea
 the green house is immediately to the right of the ivory house
 the Old Gold smoker owns snails
 Kools are smoked in the yellow house
 milk is drunk in the middle house
 the Norwegian lives in the first house
 the man who smokes Chesterelds lives in the house next to the man with the fox
 3 Kools are smoked in the house next to the house where the horse is kept
 the Lucky Strike smoker drinks orange juice
 the Japanese smokes Parliaments
 the Norwegian lives next to the blue house

我知道我需要使用列表来显示房屋，因为它们是有序的。我也想将列表用于房屋特征，但我在这里遇到了问题。

我打算使用匿名变量house(englishman, red, _, _, _)。但我不知道如何为作业解释它。

以下是约束：您应该使用以下二进制谓词符号：

owns(N,Pet)
smokes(N, Cigarette).
drinks(N, Drink).

除此之外，您可以自由使用任意数量的谓词。

这是我初始化事实的方式，但在这种情况下我不知道如何制定规则

next_to(X,Y) :- right_of(X,Y); right_of(Y,X).

owns(spaniard, dog).
drinks(ukrainian, tea).
smokes(japanese, parliaments).
right_of(ivory, green).
lives(englishman, red).
owns(X, snail) :- smokes(X, old_gold).
smokes(X, kools) :- owns(X, yellow).
smokes(X, lucky_strike) :- drinks(X, orange_juice).
drinks(X, coffee) :- owns(X, green_house).

这有点道理，但同时看起来完全错误。我不认为我可以带着这个去任何地方。：/

4

3 回答 3

12

本网站致力于用 CLP(FD) 解决此类难题。但是 CLP(FD) 的全部功能在这里是多余的：当您充分描述了约束时，可以有效地搜索整个解决方案空间来解决您的分配问题。

该解决方案将由 5 个房屋组成，其中每个属性都满足描述所施加的所有约束。

请注意对每个属性使用相同的符号（即green和green_house是错误的，请选择其中一个）。

next_to 似乎也是错误的：如果您从 1 到 5 编号，则可以计算或枚举，但指的是直接邻居。

所以完成“解决方案搜索空间”数据表示，比如

Problem = [
 house(1, Nationality1, Color1, Pet1, Drinks1, Smokes1),
 house(2, Nationality2, Color2, Pet2, Drinks2, Smokes2),
 ...
],
% place constraints
member(house(_, englishman, red, _, _, _), Problem),
member(house(_, spaniard, _, dog, _, _), Problem),
...

member/2 它是更简单的 Prolog 内置函数，但在这种情况下足以解决问题：当所有约束都已发布时，变量将绑定到适当的值。关键是成员能够非确定性地选择解决方案的成员（duh）。

因此，当您需要在 2 个不同元素之间表达约束时，调用 2 次成员，并将约束放置在适当的变量之间：即

抽 Chesterelds 的男人住在养狐狸的男人旁边的房子里

将被翻译成

....,
member(house(N, _, _, _, _, chesterelds), Problem),
member(house(M, _, _, fox, _, _), Problem),
next_to(N, M),
...

当以这种方式表达许多约束时，请注意符号标识：在单独的过程中对每个谓词进行编码可能很有用，以避免过度的别名。但对面也是如此：如果同一个符号涉及多个约束，则需要绕过符号，以缩小搜索范围。

我将让您考虑“几何”谓词的正确表示：next_to 和 right_of 可以枚举，也可以通过算术表示。

于 2012-02-13T08:33:10.763 回答
7

这个谜题（也称为斑马谜题）之前在 Stackoverflow 上已经讨论过很多次了，例如：

于 2012-02-15T09:10:00.333 回答
4

Prolog 翻译可以是直接的、逐条规则的，仍然遵循通过从中选择域来实例化域的范式。这里是房屋属性的域；在链接的答案中，房屋属性由人类程序员固定，域是实际有人居住的房屋，这允许非常简洁的编码。

换句话说，区别在于符号：一个复杂的符号已经把我们带到了一半，但它是一个人发明并遵循它（就像程序员norwegian必须在适当的参数处直接写下第一所房子的规范一样位置）——不是电脑。

在这里，我们尝试在代码中注入尽可能少的人类知识，遵循作业的约束。（当然，任何事情都是值得商榷的，避免人为干扰的最终方法是一个以英文文本作为输入的计算机程序......这将再次受到批评，即该程序是如何专门定制的，以寻找解决方案特定谜题或谜题类型等）

我们以自上而下的方式对其进行编码。显然，这个问题不见了。应该是“谁喝水？谁拥有斑马？” ：

zebra( Z, W ,HS) :-         
    length(        HS, 5),      % nation? color? what's that? define it later...
    member(  H1,   HS),    nation( H1, eng    ),    color( H1, red    ),
    member(  H2,   HS),    nation( H2, spa    ),    owns(  H2, dog    ),            
    member(  H3,   HS),    drink(  H3, coffee ),    color( H3, green  ),         
    member(  H4,   HS),    nation( H4, ukr    ),    drink( H4, tea    ),
    right_of(B, A, HS),    color(  A , ivory  ),    color( B , green  ),
    member(  H5,   HS),    smoke(  H5, oldgold),    owns(  H5, snails ),   
    member(  H6,   HS),    smoke(  H6, kools  ),    color( H6, yellow ), 
    middle(  C,    HS),    drink(  C , milk   ),  
    first(   D,    HS),    nation( D , nor    ),
    next_to( E, F, HS),    smoke(  E , chester),    owns(  F , fox    ),
    next_to( G, H, HS),    smoke(  G , kools  ),    owns(  H , horse  ),
    member(  H7,   HS),    smoke(  H7, lucky  ),    drink( H7, orange ),
    member(  H8,   HS),    nation( H8, jpn    ),    smoke( H8, parlamt),
    next_to( I, J, HS),    nation( I , nor    ),    color( J , blue   ),
    member(  W,    HS),    drink(  W , water  ),
    member(  Z,    HS),    owns(   Z , zebra  ).

right_of( B, A, HS) :- append( _, [A, B | _], HS).
next_to( A, B, HS) :- right_of( B, A, HS) ; right_of( A, B, HS).
middle( A, [_,_,A,_,_]).
first( A, [A | _]).

nation(H, V) :-  attr( H, nation-V).
owns(  H, V) :-  attr( H, owns-V).        % select an attribute
smoke( H, V) :-  attr( H, smoke-V).       %   from an extensible record H
color( H, V) :-  attr( H, color-V).       %   of house attributes
drink( H, V) :-  attr( H, drink-V).       %   which *is* a house

attr(House, Attr-Value) :- 
    memberchk( Attr-X, House),            % unique attribute names
    X = Value.

测试，使用失败驱动的循环执行穷举搜索，

3 ?- time((zebra(Z,W,_), maplist(nation,[Z,W],R), writeln(R), false ; true)).
[jpn,nor]
% 180,974 inferences, 0.016 CPU in 0.020 seconds (78% CPU, 11600823 Lips)
true.

以下是房屋的最终定义方式：

5 ?- zebra(_, _, HS), maplist( writeln, HS),
     false.
[smoke-kools,  color-yellow, nation-nor,    owns-fox,      drink-water |_G859]
[nation-ukr,   drink-tea,    smoke-chester, owns-horse,    color-blue  |_G853]
[nation-eng,   color-red,    smoke-oldgold, owns-snails,   drink-milk  |_G775]
[nation-spa,   owns-dog,     color-ivory,   smoke-lucky,   drink-orange|_G826]
[drink-coffee, color-green,  nation-jpn,    smoke-parlamt, owns-zebra  |_G865]
false.

或者，通过固定长度来“冻结”属性列表，然后排序，

7 ?- zebra( _, _, HS), maplist( length, HS, _), !, maplist( sort, HS, S),
     maplist( writeln, S), false.
[color-yellow, drink-water,  nation-nor,  owns-fox,    smoke-kools  ]
[color-blue,   drink-tea,    nation-ukr,  owns-horse,  smoke-chester]
[color-red,    drink-milk,   nation-eng,  owns-snails, smoke-oldgold]
[color-ivory,  drink-orange, nation-spa,  owns-dog,    smoke-lucky  ]
[color-green,  drink-coffee, nation-jpn,  owns-zebra,  smoke-parlamt]
false.

attr/2使谓词接受对列表Name-Value也很容易，允许更自然流动、更高层次的编码风格，以及一种“可扩展记录” ——甚至可以说是“对象” ——规范，比如

zebra( Z, W ,HS):-         
    length(       HS, 5), 
    member(  H1,  HS),    attr( H1,  [nation-eng,   color-red  ] ),
    member(  H2,  HS),    attr( H2,  [nation-spa,   owns-dog   ] ),
    member(  H3,  HS),    attr( H3,  [drink-coffee, color-green] ),
    ......

等等。。

于 2013-11-20T09:50:46.043 回答