如何为此“移动块"实现求解谓词?序言练习? [英] How to implement a solve predicate for this "moving blocks" Prolog exercise?

问题描述

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

I am studying Prolog using Ivan Bratko book: Programming for Artificial Intelligence and I am finding some difficulties to implement the final part of an exercise proposed

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

The exercise is a program that use graphs to decide how to move blocks and to arrange them in an order.

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

This is an image related to what the program have to do:

正如您在上图中所见，块 A、B、C 可以使用以下允许的移动来移动:

As you can see in the previous immage the blocks A,B,C can be moved using a number of admissible moves that are:

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

一个方块可以在地面上移动(在一个虚空栈上)

一个块可以移动到另一个块上(在另一个堆栈的顶部包含其他一些块)

因此，这些可接受的移动会在图中生成一个状态与另一个状态之间可能转换的图，如下所示:

So these admissible moves induce a graph of the possible transitions between one state and another state in the graph, something like this:

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

So, as you can se in the previous graph I can rappresent a situation using a list of 3 sublist.

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

Each sublist rappresent a stack where I can put the blocks according to the previous constraints

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

So for example the situation of the central node of the previous graph can be represented by:

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

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

Because each stack contains a single block.

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

The situation represented by the node at the top left where I stacked one below the other blocks C,A,B can be represented by:

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

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

Ok, so my program is the following one:

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).

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

In these last days I have deeply studied it and I understand how it works.

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

Substantially the s/3 predicate is my successor function s(CurrentState, SuccessorState) that calculates a legal move from the CurrentState to the SuccessorState.

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

This predicate works well, in fact if I launch the following query:

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

我得到 [[b,c],[a],[]] 是状态 [[a,b,c],[],[]] 这很好，因为我已经将 a 块从第一个堆栈的顶部移到了第二个堆栈的顶部(那是无效的)这是完全合法的举动.

I obtain that [[b,c],[a],[]] is a successor state for the state [[a,b,c],[],[]] and this is good because I have moved the a block from the top of the first stack on the top of the second stack (that was void) and this is a perfectly legal move.

好的，继续我有 goal/1 谓词表示我何时达到最终状态(当计算必须停止时):

Ok, going on I have the goal/1 predicate that says when I have reached a final state (when the computation have to stop):

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

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

It says that a situation (a specific stacks list configuration) is a goal situation if in the related stacks list there is a stack that is the [a,b,c] list.

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

So the following situations are goal situations:

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

好的，现在我的问题是:我必须像这样实现 solve/2 谓词:

Ok now my problem is the following one: I have to implement the solve/2 predicate like this:

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

从传递的情况开始(在这种情况下，堆栈列表包含第一个堆栈中的所有块，c 在地面上，b 在中间和顶部的a)并到达目标情况.

that starts from a passed situation (in this case the list of stacks that have all the blocks in the first stack with c on the ground, b in the middle and a on the top) and arrives to a goal situation.

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

I don't know exactly what I have to do and how I have to solve it (unfortunately I have no teacher)

我试图通过查看这个版本的 8 Queen 问题来启发自己，它使用了类似的编程技术(我的目标是满足和解决谓词):

I was trying to inspire myself looking at this version of 8 queen problem that uses a similar programming technique (in which I have a goal to satisfy and the solve predicate):

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).

推荐答案

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

There will be loops in space search graph, then you can switch to some form of bound search. The easier I know it's bounded depth search:

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

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

length/2 enumerates unbound lists of growing length. So we get a result.

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

Note that this will still loop if there are no solutions from initial state to goal/1. If this is bad, I think solve/2 will need a service solve2/2 predicate, that will get the path, to enable the usual + memberchk(NewState, Visited) after the nondeterministic s/2 call. Then it will be (untested)

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).

这篇关于如何为此“移动块"实现求解谓词?序言练习?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！