Prolog中的配方

Question

我目前有以下问题,我想用Prolog解决.这是一个简单的例子,在Java/C /中很容易解决.我的问题是,我认为过于依赖于Java的思想来实际以一种利用Prolog逻辑能力的方式来表达问题.

问题是..

我有一组6个箭头,指向左或右.我们假设它们处于以下起始配置中:

->
<-
->
<-
->
<-

现在,只要它们彼此相邻,我就可以切换两个箭头.我的目标是发现哪个动作序列将使箭头的初始配置变为

<-
<-
<-
->
->
->

我最初尝试制定问题的是......

right(arrow_a).
left(arrow_b).
right(arrow_c).
left(arrow_d).
right(arrow_e).
left(arrow_f).

atPosition(1, arrow_a).
atPosition(2, arrow_b).
atPosition(3, arrow_c).
atPosition(4, arrow_d).
atPosition(5, arrow_e).
atPosition(6, arrow_f).

这将告诉Prolog箭头的初始配置是什么.但是现在如何在其中插入aditional逻辑？例如,如何实施switchArrows(Index)？在Prolog中,它是否正确地说明了这样的初始条件？当我试图设置,例如,arrow_a在位置6时,它不会干扰atPosition(6, arrow_a)吗？

Answer 1

您的问题可以表示为配置之间的一系列转换.首先考虑如何表示单个配置.您可以使用列表来执行此操作,例如[ - >,< - , - >,< - , - >,< - ]来表示初始配置.可以使用用作步骤(State0,State)的关系步骤/ 2来描述单个移动,并且描述通过翻转两个相邻箭头而彼此"可达"的两个配置之间的关系.它通常是不确定的.然后,您的主谓词描述了从初始状态导致所需目标状态的一系列状态转换.由于您要描述(配置)列表,DCG非常适合:

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ). 

然后使用迭代深化来找到解决方案(如果存在),如:

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).

好消息是,一旦尝试了给定长度的所有序列并且还无法达到目标状态,Prolog会自动回溯.您现在只需执行步骤/ 2即可完成.

Answer 2

由于已经发布了完整的解决方案,这是我的:

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ).

flip(->, <-).
flip(<-, ->).

step([], []).
step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).

示例查询:

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
Solution = [[->, <-, ->, <-, <-, ->],
            [->, <-, ->, ->, ->, ->],
            [->, ->, <-, ->, ->, ->],
            [<-, <-, <-, ->, ->, ->]].

由于使用了迭代深化,我们知道不可能有更短的解决方案(少于4个步骤).

我对你所说的内容也有一般性评论:

这是一个简单的例子,在Java/C /中很容易解决.我的问题是,我认为过于依赖于Java的思想来实际以一种利用Prolog逻辑能力的方式来表达问题.

就个人而言,我认为这个例子已经远远超过了一开始就可以预料的,比如Java程序员.请尝试用Java/C /解决这个问题,看看你能得到多少.根据我的经验,当学生说他们"过于依赖Java思维"等时,他们也无法解决Java中的问题.Prolog是不同的,但没有那么不同,如果你清楚地知道如何用Java解决它,就不能直接将它翻译成Prolog.我的解决方案使用Prolog的内置搜索机制,但您不必:您可以像在Java中一样自己实现搜索.