prolog - 以声明方式解决汉诺塔(Prolog)

Question

我的教授给了 this作为 Prolog 的一个例子。这是一个解决汉诺塔难题的程序，您必须通过一个接一个地移动磁盘来将一堆磁盘移动到另一个钉子上，而不是将较大的磁盘放在较小的磁盘之上。

现在，我不喜欢那个节目。有人告诉我 Prolog 是用于声明式编程的。我不想编程如何解决问题，我想用Prolog写下问题是什么。然后让Prolog解决它。

到目前为止，我的努力可以在下面找到。我使用了两种类型的列表，一个 Action 序列表示如下:[[1,2],[3,1]] ;这将是“将顶部磁盘从 Hook 1 移动到 Hook 2，将磁盘从 Hook 3 移动到 Hook 1”。我的第二种列表是 状态 ，例如，如果有三个钉 [[1,2,3], [], []]这意味着第一个钉子上有三个磁盘。较小的磁盘具有较小的数字，因此内部列表的前面是堆栈的顶部。

% A sequence of actions (first argument) is a solution if it leads
% from the begin state (second argument) to the End state (third argument).

solution([], X, X).

solution([[FromIdx | ToIdx] | T], Begin, End) :-
    moved(FromIdx, ToIdx, Begin, X),
    solution(T, X, End).

% moved is true when Result is the resulting state after moving
% a disk from FromIdx to ToIdx starting at state Start

moved(FromIdx, ToIdx, Start, Result) :- 
    allowedMove(FromIdx, ToIdx, Start),
    nth1(FromIdx, Start, [Disk|OtherDisks]),
    nth1(ToIdx, Start, ToStack),
    nth1(FromIdx, Result, OtherDisks),
    nth1(ToIdx, Result, [Disk|ToStack]).

allowedMove(FromIdx, ToIdx, State) :- 
    number(FromIdx), number(ToIdx),
    nth1(FromIdx, State, [FromDisk|_]),
    nth1(ToIdx, State, [ToDisk|_]),
    ToDisk > FromDisk.

allowedMove(_, ToIdx, State) :- nth1(ToIdx, State, []).

上面的程序似乎可以工作，但是对于一切相当复杂的事情来说它太慢了。要求它解决经典的汉诺塔问题，将三个圆盘从第一个钉子移动到第三个和最后一个，如下所示:

?- solution(Seq, [[1,2,3], [], []], [[], [], [1,2,3]]).

我想对程序进行一些修改，使其适用于此查询。我该怎么做？分析时，我可以看到 nth1使用很多时间，我应该摆脱它吗？令我困扰的是 moved是完全确定的，应该只有一个结果。我怎样才能加快这个瓶颈？

Answer 1

河内的 Prolog 解决方案通常看起来像这样。该解决方案在遇到这些 Action 时将这些 Action 写出到屏幕上，并且不会将这些 Action 收集到列表中:

move_one(P1, P2) :-
    format("Move disk from ~k to ~k", [P1, P2]), nl.

move(1, P1, P2, _) :-
    move_one(P1, P2).
move(N, P1, P2, P3) :-
    N > 1,
    N1 is N - 1,
    move(N1, P1, P3, P2),
    move(1, P1, P2, P3),
    move(N1, P3, P2, P1).

hanoi(N) :-
    move(N, left, center, right).

这可以修改为收集列表中的移动，而不是通过在整个过程中添加列表参数并使用 append/3 :

move(0, _, _, _, []).
move(N, P1, P2, P3, Moves) :-
    N > 0,
    N1 is N - 1,
    move(N1, P1, P3, P2, M1),
    append(M1, [P1-to-P2], M2),
    move(N1, P3, P2, P1, M3),
    append(M2, M3, Moves).

hanoi(N, Moves) :-
    move(N, left, center, right, Moves).

我们能够在没有 write 的情况下使基本案例更简单. append/3完成这项工作，但它有点笨重。另外， is/2特别是使它成为非关系的。

通过使用 DCG 和 CLP(FD)， append/3可以被消除，它可以变得更加相关。这就是我所说的初始“天真”方法，它也更具可读性:

hanoi_dcg(N, Moves) :-
    N in 0..1000,
    phrase(move(N, left, center, right), Moves).

move(0, _, _, _) --> [].
move(N, P1, P2, P3) -->
    { N #> 0, N #= N1 + 1 },
    move(N1, P1, P3, P2),
    [P1-to-P2],
    move(N1, P3, P2, P1).

这导致:

| ?- hanoi_dcg(3, Moves).

Moves = [left-to-center,left-to-right,center-to-right,left-to-center,right-to-left,right-to-center,left-to-center] ? a

no
| ?- hanoi_dcg(N,  [left-to-center,left-to-right,center-to-right,left-to-center,right-to-left,right-to-center,left-to-center]).

N = 3 ? ;

(205 ms) no
| ?-

虽然它是相关的，但它确实有几个问题:

“双向”的无用选择点

终止问题，除非受到类似 N in 0..1000 的约束

我觉得有办法解决这两个问题，但还没有解决。 (我敢肯定，如果一些比我更聪明的 Prologers，例如 @mat、@false 或 @repeat 看到这一点，他们马上就会有一个很好的答案。)