-1

我想在序言中解决这个谜语:

莉莉、杰克和黛西的学生上同一所大学。他们都来自不同的国家,有着不同的爱好。他们都上美国的一所大学,其中一人住在那里。莉莉的成绩比来自意大利的那个好。杰克的成绩比喜欢读书的人要好。最好的成绩有一个喜欢足球的人。杰克来自德国,黛西喜欢做饭。

谁是谁(姓名、国家、爱好、成绩)?

正确的解决方案应该是:

  • Lily,美国,读书,二年级
  • 杰克,德国,足球,一年级
  • Daisy,意大利,烹饪,三年级

我现在的问题是我不知道如何解决这个谜语。我应该如何定义事实以及解决谜题的最佳方法是什么?

4

3 回答 3

2

在 Prolog 中回答这些难题的诀窍是生成(检索)可能的答案,然后根据逻辑约束对其进行测试。因此,如果 Lily 是人 P1,则检索任何人 P2 并测试该人是否来自意大利。等等与其他规则。

这意味着,首先,您需要一些包含可能国家、可能爱好和可能成绩的条款。并不是所有的可能性都是必要的,因为有些可能性已经被这个问题排除了。

下面的解决方案,基于任意制作 Lily 人 1、Jack 人 2 和 Daisy 人 3。

加载到 Prolog 并查询谁(P1,C1,H1,G1,P2,C2,H2,G2,P3,C3,H3,G3)。

country(italy).
country(usa).
hobby(football).
hobby(reading).
grade(c:1).
grade(b:2).
grade(a:3).



who(lily,C1,H1,Grade1, jack,germany,H2,Grade2, daisy,C3,cooking,Grade3):-
    country(C1), country(C3), C1 \= C3,
    hobby(H1), hobby(H2), H1 \= H2,
    grade(G1:Grade1), grade(G2:Grade2), grade(G3:Grade3),
    G1 \= G2, G2 \= G3, G1 \= G3,
    (C3=italy, G1@>G3),
    (H1=reading, G2@>G1),
    ((H1=football, G1@>G2, G1@>G3); (H2=football, G2@>G1, G2@>G3)).
于 2016-12-04T02:10:00.800 回答
0

这是我的看法。它本质上是@RdR 所拥有的,只是我将逻辑分解为更多的谓词,同时还有一个重载较少的who()主谓词。

name(lily).  % (1)
name(jack).
name(daisy).
country(italy).
country(usa).
country(germany).
hobby(football).
hobby(cooking).
hobby(reading).
grade(1).
grade(2).
grade(3).

student(N,C,H,G):-  % (2)
    name(N), country(C), hobby(H), grade(G).

permute(P,X,Y,Z):- (4)
    call(P,X), call(P,Y), call(P,Z)  % (6)
    , X\=Y, Y\=Z, X\=Z.

students(A,B,C):- (3)
    permute(name,N1,N2,N3)   % (5)
    , permute(country,C1,C2,C3)
    , permute(hobby,H1,H2,H3)
    , permute(grade,G1,G2,G3)
    , A = student(N1,C1,H1,G1)  % (7)
    , B = student(N2,C2,H2,G2)
    , C = student(N3,C3,H3,G3)
    .

who(A,B,C):-  % (8)
    students(A,B,C)
    , A = student(lily,C1,H1,G1)  % (9)
    , B = student(jack,C2,H2,G2)
    , C = student(daisy,C3,H3,G3)
    , C2 = germany                % (10)
    , H3 = cooking
    , (( C2=italy -> G1 < G2)     % (11)
      ;( C3=italy -> G1 < G3))
    , (( H1=reading -> G2 < G1)
      ;( H3=reading -> G2 < G3))
    , (( H1=football -> G1 < G2, G1 < G3)
      ;( H2=football -> G2 < G1, G2 < G3)
      ;( H3=football -> G3 < G1, G3 < G2))
    .

% Running it:
% ?- who(A,B,C).
% A = student(lily, usa, reading, 2),
% B = student(jack, germany, football, 1),
% C = student(daisy, italy, cooking, 3) ;
% false.

讨论

所以这里发生了很多事情(这让我很感兴趣),并且可以做出不同的选择(因此它可能与@RdR 的解决方案形成鲜明对比)。

  • 正如其他人指出的那样,一方面是如何对问题描述中给出的信息进行编码。您可以非常具体地表达它(仅解决这种情况),或者更笼统地表达(例如,允许将问题扩展到 3 个以上的学生)。
  • 这个问题与其他问题的不同之处在于,您有多种约束条件,这些约束条件会影响一个学生(“杰克来自德国”),影响两个学生(“莉莉的成绩比来自意大利的学生好”),或者涉及所有这些(“喜欢足球的人成绩最好”)。
  • 此外,您还有析取约束(“他们都来自不同的国家,并且有不同的爱好”)。Prolog 非常擅长遍历一个事实的所有可能实例,但是让它选择一个实例并将这个实例留给谓词的下一次调用会更加复杂。这迫使您找到一种方法来从成对不同的事实中获取一组值。(例如,当 Prolog 确定 Lily 的爱好是阅读时,它不能也将阅读指定为 Jack 的爱好)。
  • 因此,在列出所有已知事实及其可能值 (1) 之后,我首先定义了一个谓词student/4(2) 来简单地说明一个学生具有这 4 个属性。这产生了学生及其属性的所有可能组合,也允许他们都有相同的名字,来自同一个国家,asf。
  • 这是一个很好的例子,如何在 Prolog 中创建一个太大的结果集,然后尝试进一步缩小它(就像其他人写的那样)。进一步的谓词可以利用这个“生成器”并从其结果集中过滤越来越多的解决方案。这也更容易测试,在每个阶段您都可以检查中间输出是否有意义。
  • 在下一个谓词students/3(3) 中,我完全尝试了我之前提到的方法,创建了至少不会两次使用相同属性的学生实例(就像两个具有相同爱好的学生)。为了实现这一点,我必须遍历所有属性事实(name/1、country/1、...),为每个属性获取三个值,并确保它们成对不同。
  • 为了不必为每个属性显式地执行此操作,除了属性名称之外,实现总是相同的,我构造了一个辅助谓词permute/4(4),我可以传递属性名称,它会查找属性作为事实三次,并确保界限值都不相同。
  • 因此,当我调用permute(name,N1,N2,N3)( students/35) 时,它将导致查找call(P,X), call(P,Y), call(P,Z)(6),其结果与 invoking 相同name(X), name(Y), name(Z)。(因为我总是从相同属性的 3 个事实中收集 3 个不同的值,这实际上与执行 3 值集的 3 排列相同,因此是辅助谓词的名称。)
  • 当我到达 (7) 时,我知道每个学生属性都有不同的值,我只是将它们分布在三个学生实例中。(这实际上应该在没有student/4谓词的情况下同样工作,因为您总是可以在 Prolog 中即时组成这样的结构化术语。拥有student 谓词提供了额外的好处,可以检查没有愚蠢的学生可以构造,例如“student(lily, 23 , asdf, -7.4)".)
  • 因此:- students(A,B,C).生成 3 名学生及其属性的所有可能组合,而不使用任何涉及的属性两次。好的。它还将(更困难的)student()结构包装在方便的单字母变量中,从而使界面更加简洁。
  • 但除了那些不相交约束之外,我们还没有实现任何其他约束。这些现在遵循(不太优雅的)who/3 谓词(8)。它基本上students/3用作生成器,并尝试通过添加更多约束来过滤掉所有不需要的解决方案(因此它具有与 . 基本相同的签名students/3
  • 现在另一个有趣的部分开始了,因为我们不仅要能够过滤单个student实例,还要能够单独引用它们(“Daisy”、“Jack”……)以及它们各自的属性(“Daisy's hobby”等)。 )。因此,在绑定我的结果变量 A、B 和 C 时,我对特定名称进行模式匹配。因此,文字名称lily, jackasf 来自 (9)。这让我不必考虑 Lily 可能排在第一位、排在第二位或排在第三位的情况(因为students/3会产生这样的排列)。因此,所有未按此顺序出现的 3 组学生都将被丢弃。
  • 我也可以稍后在像N1 = lilyasf 这样的显式约束中做到这一点。我现在这样做是为了强制执行杰克来自德国且黛西喜欢烹饪的简单事实 (10)。当那些失败时,Prolog 会回溯到最初的调用students/3,以获取另一组学生,它可以尝试。
  • 现在关注关于 Lily 的成绩、Jack 的成绩和足球爱好者的成绩的其他已知事实 (11)。这是特别难看的代码。
  • 一方面,最好有一个辅助谓词能够返回查询“具有属性 X 的学生”的答案。它将采用当前选择的学生 A、B 和 C、一个属性名称(“国家”)和一个值(“意大利”),并返回适当的学生。因此,您可以只查询来自意大利的学生,而不是假设它必须是第二个或第三个学生(因为问题描述表明 Lily 本人不是来自意大利)。
  • 所以这个假设的辅助谓词,让我们称之为它student_from_attribute 需要另一个辅助器,它通过名称在学生结构中找到一个值并返回相应的值。在所有支持某种对象/命名元组/记录的语言中都很容易,您可以通过名称访问其中的字段。但香草 Prolog 没有。所以会有一些提升要做,一些我无法摆脱的事情。
  • 谓词也who/3可以利用这个其他助手,因为您需要与从返回的学生不同的属性 student_from_attribute,例如“等级”,并将其与莉莉的等级进行比较。这将使所有这些约束变得更好,例如 student_from_attribute([A,B,C], country, italy, S), attrib_by_name(S, grade, G), G1 < G. 这可以以相同的方式应用于阅读和足球约束。这不会更短,而是更简洁、更通用。

我不确定有人会阅读所有这些:-)。不管怎样,这些考虑让这个谜题对我来说很有趣。

于 2016-12-05T21:53:40.423 回答
0

首先,通过填写我们从第一个语句中得到的内容,我们有以下内容。

(Lily, _, _, _)
(Jack,Germany, _, _)
(Daisy, _, Cooking, _)

_我们不知道在哪里的状态。我还应该说这不一定是序言,它比任何东西都更常识。

我们得到短语“莉莉的成绩比来自意大利的人好”,这意味着黛西来自德国,莉莉来自美国——因为杰克来自德国。

(Lily, USA, _, Grade>Daisy)
(Jack,Germany, _, _)
(Daisy, Italy, Cooking, Grade<Lily)

接下来,我们有“Jack 的成绩比那个喜欢读书的人好”,这给了我们这样一个事实,即他将成为足球运动员,下一行告诉我们他的成绩最好。然后我们可以及时填满剩余的,我们得到:

(Lily, USA, Reading, Grade2)
(Jack,Germany, Football, Grade1)
(Daisy, Italy, Cooking, Grade3)

可能有一个用 prolog 编写的程序可以非常迂回地解决这个难题,但这个难题比一般情况更具体。

于 2016-12-03T22:03:03.940 回答