4

我目前有以下问题，我想用 Prolog 解决。这是一个简单的例子，很容易用 Java/C/whatever 解决。我的问题是，我认为太依赖于 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)吗？

4

4 回答 4

7

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

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

然后使用迭代深化来找到解决方案（如果存在），如：

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

好消息是，一旦尝试了给定长度的所有序列并且尚未达到目标状态，Prolog 就会自动回溯。您现在只需执行 step/2 即可。

于 2010-10-05T20:49:01.273 回答
5

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

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/whatever 解决。我的问题是，我认为太依赖于 Java 的思想，无法以利用 Prolog 逻辑能力的方式来实际制定问题。

就个人而言，我认为这个例子已经远远超出了从一开始就可以预期的程度，比如 Java 程序员。请尝试用 Java/C/whatever 解决这个问题，看看你能走多远。以我的经验，当学生说他们“太依赖于 Java 的思想”等时，他们也无法用 Java 解决问题。Prolog 是不同的，但没有那么不同，如果您对如何用 Java 解决它有一个清晰的想法，就无法将它直接翻译成 Prolog。我的解决方案使用 Prolog 的内置搜索机制，但您不必：您可以像在 Java 中一样自己实现搜索。

于 2010-10-06T14:12:25.933 回答
1

这是我的解决方案：

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

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

于 2010-10-06T12:30:51.593 回答
0

设法将垫子的代码转换为水银：

:- 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 进行编译以推断签名和确定性

于 2010-10-06T16:20:14.487 回答