如何为这个“移动块"实现解决谓词?序言练习? [英] 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 皇后问题(我有一个目标要满足和解决谓词):

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屋！