2

我正在使用 Ivan Bratko 的书学习 Prolog：人工智能编程，我发现一些问题试图了解如何使用图形来决定如何移动块并按顺序排列它们的练习。

这是与程序必须执行的操作相关的图像：

在此处输入图像描述

正如您在上图中所见，块 A、B、C 可以使用一些允许的移动来移动，这些移动是：

  • 只有在栈顶的块才能被移动
  • 一个方块可以在地面上移动（在一个虚空栈上）
  • 一个块可以移动到另一个块上（在另一个包含其他块的堆栈的顶部）

因此，这些可接受的移动会导致图中的一个状态和另一个状态之间可能的转换图，如下所示：

在此处输入图像描述

因此，正如您在上图中看到的那样，我可以使用包含 3 个子列表的列表来表示一种情况。

每个子列表代表一个堆栈，我可以根据之前的约束在其中放置块

所以例如上图的中心节点的情况可以表示为：

[[A], [B], [C]]

因为每个堆栈都包含一个块

左上角节点表示的情况，我在其他块 C、A、B 下方堆叠一个节点可以表示为：

[[C,A,B], [], []]

因为所有的块都在一个堆栈中（第一个）

现在，我必须编写一个谓词s(Situation1, Situation2)，如果 Situation1 和 Situation1 是块世界的两个表示（如前一个）并且 Situazion1 和 Situazion2 之间允许合法移动，则该谓词 s(Situation1, Situation2) 为 TRUE。

所以我可以在下面使用一系列事实来表示这个东西（这个东西显示在我老师的幻灯片上，而不是 Bratko 的书上：

s([[A|RA],B,C],[RA,[A|B],C]).
s([[A|RA],B,C],[RA,B,[A|C]]).
…

我是这样解释的：我有 2 个堆栈：

Situation1 = [A|RA], B, C]其中 RA 是没有块 A 的第一个堆栈的其余部分（在这种情况下它是无效的，因为这是我在每个堆栈中有一个块的情况）

Situation2 = [RA,[A|B],C]这是另一种情况，第一个堆栈是 void (RA)，第二个堆栈是旧的第二个堆栈，顶部是 A 块，第三个堆栈包含只有 C 块

所以它代表了一个合法的过渡......所以我可以声明一系列明确表示所有可能的过渡的事实。

但这不是一个好主意（我可以有很多转换来编码事实）所以在 Bratko 书中以这种方式以编程方式实现 s(Situation1, Situation2) 谓词：

/* BASE CASE: If I delete X from List and X is the HEAD of List, NewList is
              the Tail of List
*/
del(X, [X|Tail], Tail).

/* GENERAL CASE: If the head of List is not X then the program have to delete
                 X in the Tail of List
*/
del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).


s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-

                                 del([Top1|Stack1], Stacks, Stacks1),
                                 del(Stack1, Stacks1, OtherStacks).


goal(Situation) :- member([a,b,c], Situation).

solve(N,[N]) :- goal(N).

del/3谓词非常简单（只需从列表中删除 X 项），并没有太多有趣的地方。

我有一些问题要理解计算合法移动的s/2谓词是如何工作的。

书上说：

后继关系可以根据以下规则进行编程：如果有两个堆栈，则 Situation2 是 Situation1 的 SUCCESSOR：Situation1 中的 Stack1 和 Stack2，并且 Stack1 的顶部块可以在 Stack2 上移动

直觉上，这对我来说并不难，因为很明显，如果我可以在 3 个堆栈中的一个顶部取一个块并且我可以将它放在另一个堆栈的顶部（也是一个空堆栈，对应于到我在地上放块的情况）

但是我发现很多难以理解s/2谓词的先前代码在编写时：

s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-

                                 del([Top1|Stack1], Stacks, Stacks1),
                                 del(Stack1, Stacks1, OtherStacks).

我很难理解如何阅读它以及使用del/3 谓词时究竟做了什么，以及究竟什么代表了Stacks、Stack1、Stack2、Stacks1变量

4

2 回答 2

3

你问，以下是什么意思：

s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-
                             del([Top1|Stack1], Stacks, Stacks1),
                             del(Stack1, Stacks1, OtherStacks).

我们可以这样解读：s/2当然是“一步”（或“移动”，或“后继”）关系。首先，我们有Stacks堆栈列表。第二个参数是我们的结果，以某种方式在其中移动一个块。

由于del是一个回溯谓词，所以将是s。所以，它会一一产生结果。在这里，声明式阅读会有所帮助。:)

我们是这样解读身体的：在A = [Top1|Stack1]之间有，从它们中去除后Stacks变成。如果我们有三个，我们将有两个，还有另一个 stack ，其中第一个- 元素显然是该堆栈上的顶部块（并且是树桩，该堆栈的其余部分）。IOW，我们在三个堆栈中选择一些堆栈，其余的是. 上块是.Stacks1AStacksStacks1ATop1Stack1AStacks1ATop1

到下一行。Stack1:) 如果我们要从两者中删除树桩Stacks1，我们会得到OtherStacks. 那只是胡说八道，我们知道树桩不在Stacks1. 所以这显然是一个错误（“错字”）。

我们如何纠正它？我们的目标是将Top1放在其中一个堆栈上Stacks1，所以让我们这样做：

    del(A,Stacks1,B), Result = [ Stack1 ,         % a stump
                                 [Top1 | A] |     % move the top block
                                 B].

这是我们的第二个参数，直到重命名变量：A = Stack2, B = OtherStacks. 所以，正确的第二行是

                         %   del(Stack1, Stacks1, OtherStacks).   % ERROR
                             del(Stack2, Stacks1, OtherStacks).   % CORRECT

就像 CapelliC 的回答一样。

CapelliC 是对的，命名太可怕了，:) 很容易输入错误。A, B, C好多了。

于 2013-05-08T18:31:43.433 回答
1

在修正 s/2 中的单例后，得到

s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-
    del([Top1|Stack1], Stacks, Stacks1),
    del(Stack2, Stacks1, OtherStacks).

我参加考试

?- s([[a,b,c],[],[]],R).
R = [[b, c], [a], []] .
于 2013-05-08T17:54:14.020 回答