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 箭头的初始配置是什么。但现在我如何在其中插入额外的逻辑呢？例如，如何实现 switchArrows(Index) ？在 Prolog 中这样表述初始条件是否正确？例如，当我尝试设置 arrow_a 位于位置 6、atPosition(6, arrow_a) 时，它不会干扰吗？

Answer 1

您的问题可以表述为配置之间的一系列转换。首先考虑如何表示单个配置。您可以使用列表来执行此操作，例如 [->,<-,->,<-,->,<-] 来表示初始配置。单个移动可以用关系step/2来描述，该关系用作step(State0, State)，并描述通过翻转两个相邻箭头彼此“可达”的两个配置之间的关系。它通常是不确定的。然后，您的主谓词描述了从初始状态到所需目标状态的一系列状态转换。由于您想要描述一个（配置）列表，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 中一样自己实现搜索。

Answer 3

这是我的解决方案：

solution(Begin, End, PrevSteps, [Step | Steps]) :-
    Step = step(Begin, State1),
    Step,
    forall(member(step(S, _), PrevSteps),
           State1 \= S
          ), % prevent loops
    (   State1 == End
    ->  Steps = []
    ;   solution(State1, End, [Step | PrevSteps], Steps)
    ).

rev(->,<-).
rev(<-,->).

step([X,Y|T], [XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,X,Y|T], [A,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,X,Y|T], [A,B,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,X,Y|T], [A,B,C,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,D,X,Y], [A,B,C,D,XX,YY]) :- rev(X,XX), rev(Y, YY).


run :-
    solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->],[],Steps),
    !,
    forall(member(Step,Steps),writeln(Step)).

它只找到所有可能的解决方案，尽管我认为找到的解决方案不是最佳的，而是第一个可行的解决方案。

Answer 4

设法将 mat 的代码转换为汞：

:- module arrows.

:- interface.

:- import_module io.

:- pred main(io, io).
:- mode main(di, uo) is cc_multi.

:- implementation.

:- import_module list, io, int.

:- type arrow ---> (->); (<-).

:- mode solution(in, in, in, in, out, in) is cc_nondet.
solution(State0, Target, MaxDepth, CurrentDepth) -->
    {CurrentDepth =< MaxDepth},
    (    { State0 = Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target, MaxDepth, CurrentDepth + 1)
    ).

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

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

main -->
    (({
    member(N, 1..10),
        solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->], N, 0, Solution, [])
    }) 
    -> print(Solution)
    ; print("No solutions")
    ).

编译
mmc --infer-all arrows.m
推断签名和决定论