文章/答案/技术大牛

发布

问寻找凶手的Prolog程序
EN

Stack Overflow用户

提问于 2014-06-25 08:40:01

回答 3查看 1.7K关注 0票数 2

在一个练习中，我试图用Prolog编写一个程序来帮助警方找到凶手。我的代码如下：

student(alexander).
student(tobias).
student(michael).
student(peter).
passed(alexander,chemistry).
passed(peter,history).
passed(tobias,maths).
passed(michael,english).
failed(alexander,english).
failed(peter,chemistry).
failed(tobias,chemistry).
failed(alexander,chemistry).
passed(X, maths) :- failed(X, english), failed(X, history).
passed(X, english) :- failed(X, history), passed(X,maths).
passed(X, economics) :- passed(X, english), failed(X, history).
failed(X, history) :- failed(X, economics), passed(X, chemistry).
failed(X, english) :- failed(X, chemistry), passed(X, history).
killer(X):-student(X),failed(X,economics).*

确定了以下事实：

每一个英语和历史都不及格的学生，都通过了数学。
每一个历史不及格但数学及格的学生都通过了英语。
每一个历史不及格但通过英语的学生，都通过了经济学。
每一个经济学不及格，但化学不及格，历史不及格的学生。
每一个化学不及格但通过历史的学生，英语都不及格。
亚历山大英语不及格，但通过了化学考试。
彼得化学不及格，通过了历史考试。
托拜厄斯历史不及格，数学及格。
迈克尔数学不及格，英语及格。

这四个学生中有一个已经杀了他的教授。当验尸官检查身体时，他在右手里发现了一张纸：“杀手经济学失败了”。

我现在该怎么联系到失败呢？

prolog

回答 3

Stack Overflow用户

发布于 2014-06-25 09:03:49

我对你的陈述有一些看法。

首先，您的谓词english/1，maths/1不足以表达特定学生通过考试的事实。如果你断言english(failed)，那么这个短语是关于什么学生的？您需要将学生包括在关系中(例如，english(michael, passed))。

此外，我建议您将failed或passed结果视为关系。您可以使用两个这样的关系failed/2和passed/2，与failed(S, E)的意思是学生S考试不及格E。例如：

∀ X : student(X) ∧ failed(X, english) ∧ failed(X, history) → passed(X, maths)

将在Prolog中部分代表如下：

passed(X, maths) :- student(X), failed(X, english), failed(X, history).

当然，如果student(X)的第一个参数始终是学生，则可以删除failed/2条件。

现在，判决

每一个英语和历史都不及格的学生，都通过了数学。

可以用FOL正式化如下：

∀ X : student(X) ∧ failed(X, english) ∧ failed(X, history) → passed(X, maths)

使用A → B ≡ ¬A ∨ B，您可以找到等效的表单：

∀ X : ¬student(X) ∨ ¬failed(X, english) ∨ ¬failed(X, history) ∨ passed(X, maths)

(以析取的正常形式)，或回指：

∀ X : ¬passed(X, maths) ∧ failed(X, english) ∧ failed(X, history) → ¬student(X)
∀ X : student(X) ∧ ¬passed(X, maths) ∧ failed(X, history) → ¬failed(X, english)
∀ X : student(X) ∧ failed(X, english) ∧ ¬passed(X, maths) → ¬failed(X, history)

小心，Prolog使用封闭世界假设 (¬student(X)不是\+ student(X))，因此不能直接将上述规则转换为Prolog。

假设每个学生都参加了的所有考试，并使用∀ X : ∀ E : passed(X, E) ⟺ ¬failed(X, E)，你可以推断出以下条款：

∀ X : student(X) ∧ failed(X, maths) ∧ failed(X, history) → passed(X, english)
∀ X : student(X) ∧ failed(X, english) ∧ failed(X, maths) → passed(X, history)

因此，从这个短语中(每一个英语和历史都不及格的学生都通过了数学)，您应该在Prolog中提取三个单独的规则：

passed(X, maths) :- student(X), failed(X, english), failed(X, history).
passed(X, english) :- student(X), failed(X, maths), failed(X, history).
passed(X, history) :- student(X), failed(X, english), failed(X, maths).

如果不是所有的学生都参加了所有的考试，你应该介绍一些谓词tooks(Student, Exam)，但是上面的解释就变得更加复杂了。

严格意义上讲，另一个变体是使用一个谓词exam_result/3，其含义如下：exam_result(Student, Exam, Result)表示学生Student参加了Exam考试，其结果是Result。

result(alexander, chemistry, passed).

这样做的目的是不将上述表示意见作为一项规则。

第二个观察是，您使用一个谓词killer/3来表示许多信息。

killer(alexander,english(failed),chemistry(passed)).

更直观的做法是把这种关系分成单独的、更明确的：

killer(alexander).
failed(alexander, english).
passed(chemistry, alexander).

检查某一学生是否通过或不通过某一项考试比较容易。此外，如果学生有两个以上(或更少)的考试，很难扩展killer/3谓词(以及使用该谓词的所有规则)。

要找到一个没有通过具体考试(如经济学)的学生，你可以问Prolog：

?- failed(Student, economics).
Student=alexander ;
...

票数 1

Stack Overflow用户

发布于 2014-06-25 16:12:31

将问题视为CSP

解决这个难题的另一个方法是把它看作是一个约束满意度问题。CSP由一组变量、每个变量的域和一组表示这些变量之间关系的约束来定义。解决这样一个问题意味着为其域中的每个变量分配一个值，以便满足所有约束条件。

在这种情况下，一种可能的表示是将每个学生考试对看作一个变量，可以接受这两个值中的一个：[passed, failed]。限制因素将完全是问题中所作的陈述。在Prolog中表示解决方案的一种可能性是使用包含结构Exams的列表exam(Student, Exam, Result) (例如Exams = [exam(alexander, history, passed), exam(tobias, maths, failed), ...])。这个列表对于每对学生考试都有一个元素。

在一种天真的方法中，所有可能的解决方案依次生成并根据约束进行检查。

检查约束

现在，检查亚历山大失败的英语限制是很简单的(使用member/2)。检查是否

每一个英语和历史都不及格的学生，都通过了数学。

您可能需要修改它：

不是这样的，学生英语和历史都不及格，数学也不及格。

看看为什么这两者是等价的：

∀ X : failed(X, english) ∧ failed(X, history) → passed(X, maths)
≡
∀ X : ¬failed(X, english) ∨ ¬failed(X, history) ∨ passed(X, maths)
≡
¬( ¬(∀ X : ¬failed(X, english) ∨ ¬failed(X, history) ∨ passed(X, maths)))
≡
¬( ∃ X : failed(X, english) ∧ failed(X,history) ∧ ¬passed(X, maths))

假设每个学生都参加了所有的考试并使用∀ X : ∀ E : passed(X, E) ⟺ ¬failed(X, E)

¬( ∃ X : failed(X, english) ∧ failed(X,history) ∧ failed(X, maths))

最后一个表单可以很容易地转换为候选解决方案的约束：

\+ ( member(exam(X, english, failed), Exams),
     member(exam(X, history, failed), Exams),
     member(exam(X, maths, failed), Exams) )

稍后的编辑:这不是解决CSP的有效方法(这里有更好的算法和启发式:前向检查、AC3、值排序、变量排序等)，但这是一个很好的开始。

票数 0

Stack Overflow用户

发布于 2014-06-26 14:58:46

这是我对这个很好的谜题的看法，但我已经完全重写了代码。请注意，您的问题仍然存在一些不一致的地方，例如

passed(alexander,chemistry).
...
failed(alexander,chemistry).

无论如何，Prolog中的相互递归规则很容易导致程序的不终止，所以“真相表示”最好像数据一样处理，而不是规则.

:- module(killer, [killer/1, possible_killer/1]).

killer(S) :-
    student(S, Facts),
    sure(Facts, Results),
    compatible(-economics, Results).

possible_killer(S) :-
    student(S, Facts),
    sure(Facts, Results),
    % memberchk(-economics, Results).
    \+ memberchk(+economics, Results).

student(alexander, [-english, +chemistry]). % Alexander failed English but passed chemistry.
student(peter, [-chemistry, +history]).     % Peter failed chemistry and passed history.
student(tobias, [-history, +maths]).        % Tobias failed history and passed maths.
student(michael, [-maths, +english]).       % Michael failed maths and passed English.

rule([-english, -history], +maths   ). % Every student that failed both English and History, passed Maths.
rule([-history, +maths], +english   ). % Every student that failed history but passed math, passed English.
rule([-history, +english], +economics). % Every student that failed history but passed English, passed economics.
rule([-economics, +chemistry], -history).   % Every student that failed economics but passed chemistry, failed history.
rule([-chemistry, +history], -english). % Every student that failed chemistry but passed history, failed English.

sure(Facts, Results) :-
    rule(IF, THEN),
    forward(IF, THEN, Facts, Update),
    !, sure(Update, Results).
sure(Facts, Facts).

forward(Conditions, Consequence, Facts, [Consequence|Facts]) :-
    \+ memberchk(Consequence, Facts),
    forall(member(C, Conditions), memberchk(C, Facts)).

invert(+C, -C).
invert(-C, +C).

compatible(R, Results) :-
    invert(R, I),
    \+ memberchk(I, Results),
    rule(Conditions, Fact),
    memberchk(R, Conditions),
    forall(member(C, Conditions), compatible(Fact, [C|Results])).
compatible(R, Results) :-
    memberchk(R, Results).

结果：

?- possible_killer(X).
X = alexander ;
X = peter ;
X = michael.

“积极”的知识足以排除托拜厄斯。我们需要一种更好的方法去探索“消极”的知识，正如都铎所指出的，在Prolog中评估是有问题的。

?- killer(X).
X = michael ;
false.

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/24403945

复制

相似问题

问寻找凶手的Prolog程序
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问寻找凶手的Prolog程序EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问寻找凶手的Prolog程序
EN