1

我正在使用 Ivan Bratko 的书学习 Prolog：人工智能编程，我发现在实施建议的练习的最后部分时遇到了一些困难

该练习是一个程序，它使用图形来决定如何移动块并按顺序排列它们。

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

在此处输入图像描述

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

  • 只有在栈顶的块才能被移动

  • 一个方块可以在地面上移动（在一个虚空栈上）

  • 一个块可以移动到另一个块上（在另一个包含其他块的堆栈的顶部）

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

在此处输入图像描述

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

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

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

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

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

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

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

好的，所以我的程序如下：

del(X, [X|Tail], Tail).

del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).

/* s(CurrentState, SuccessorState): Predicate that calculate a legal move from
                                    the CurrentState to the SuccessorState:
*/
s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :- 
                                     del( [Top1|Stack1], Stacks, Stacks1),
                                     del( Stack2, Stacks1, OtherStacks).

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

在这最后的日子里，我深入研究了它，我了解它是如何工作的。

基本上s/3谓词是我的后继函数s(CurrentState, SuccessorState)，它计算从CurrentState到 的合法移动SuccessorState。

这个谓词效果很好，事实上，如果我启动以下查询：

[debug]  ?- s([[a,b,c],[],[]],R).
R = [[b, c], [a], []]

我知道[[b,c],[a],[]]是状态[[a,b,c],[],[]]的后继状态，这很好，因为我已将块从第一个堆栈的顶部在第二个堆栈的顶部（无效），这是一个完全合法的举动。a

好的，继续我有goal/1谓词说当我达到最终状态时（当计算必须停止时）：

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

如果在相关的堆栈列表中有一个堆栈是 [a,b,c] 列表，则它表示一种情况（特定的堆栈列表配置）是目标情况。

所以以下情况是目标情况：

[[a,b,c],[],[]]
[[], [a,b,c],[]]
[[],[], [a,b,c]]

好的，现在我的问题是以下一个：我必须solve/2像这样实现谓词：

solve([[c,a,b],[],[]], Situation)

从通过的情况开始（在这种情况下，堆栈列表中的所有块都在第一个堆栈中，并且c在地面，b中间和a顶部）并到达目标情况。

我不确切知道我必须做什么以及如何解决它（不幸的是我没有老师）

我试图激励自己查看这个版本的 8 皇后问题，它使用了类似的编程技术（我的目标是满足和解决谓词）：

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens, 1).

goal([_,_,_,_,_,_,_,_]).

noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :-   Y =\= Y1,
                                  Y1-Y =\= Xdist,
                                  Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

solve(N,[N]) :- goal(N).      % sample call: solve([], X).

solve(N, [N|Sol1]) :- s(N,N1),
                      solve(N1,Sol1).
4

1 回答 1

2

空间搜索图中会有循环，然后你可以切换到某种形式的绑定搜索。我越容易知道它是有界深度搜索：

?- length(Situation,_), solve([[c,a,b],[],[]], Situation).
Situation = [[[c, a, b], [], []], [[a, b], [c], []], [[b], [a], [c]], [[], [b, c], [a]], [[], [a, b|...], []]] .

length/2 枚举增长长度的未绑定列表。所以我们得到一个结果。

请注意，如果从初始状态到目标/1 没有解决方案，这仍然会循环。如果这很糟糕，我认为 solve/2 将需要一个服务 solve2/2 谓词，它将获得路径，以\+ memberchk(NewState, Visited)在非确定性 s/2 调用之后启用通常的功能。然后它将是（未经测试）

solve(N, SearchPath) :- solve2([N], SearchPath).

solve2([N|Visited], [N|Visited]) :- goal(N).
solve2([N|Visited], Path) :-
   s(N,N1),
   \+ memberchk(N1, Visited),
   solve2([N1,N|Visited], Path).
于 2013-05-09T17:30:47.123 回答