4

所以我被分配了一个任务来尝试在 Prolog 中解决这个问题，尽管老师只介绍了基础知识，这基本上是 Prolog 中唯一的项目。我觉得我想多了，而且他对第一次 Prolog 程序的期望太高了。

下面列出了问题，我应该如何解决这个问题？

编写一个 Prolog 程序来解决下面的单词问题。作为解决方案的一部分，它应该打印所有的交叉点，首先列出桨手。

汤姆、杰克、比尔和吉姆不得不使用只能容纳两个人的独木舟过河。
在河的左岸到右岸的三个渡口中，独木舟都有两个人，从右到左岸的两个渡口中，独木舟的每个人都有一个人。当其他人在独木舟中时，汤姆无法划桨。
当除比尔以外的其他人在独木舟中时，杰克无法划桨。每个人至少划过一个路口。

这是我到目前为止所拥有的，虽然它“有效”，但它并不能确保每个人都至少划一次。

state(tom(Side),jim(Side),jack(Side),bill(Side),c(Side)).
initial(state(tom(l),jim(l),jack(l),bill(l),c(l))).
final(state(tom(r),jim(r),jack(r),bill(r),c(r))).

canoe(P):-P=p.
canoe(P,C):-P=p,C=c.

bad(state(tom(W),jim(X),jack(Y),bill(Z),c(C))):-
    C=l,(W=c;X=c;Y=c;Z=c).

move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z),c(C1))):-
    ((canoe(W1),W=r,W=C,C1=m);(canoe(W),W1=l,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1),X=r,X=C,C1=m);(canoe(X),X1=l,X1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z),c(C1))):-
    ((canoe(Y1),Y=r,Y=C,C1=m);(canoe(Y),Y1=l,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1),Z=r,Z=C,C1=m);(canoe(Z),Z1=l,Z1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1,W1),W=l,W=X,W=C,C1=m);
    (canoe(X,W),W1=r,W1=X1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,W1),W=l,W=Z,W=C,C1=m);
    (canoe(Z,W),W1=r,W1=Z1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y1),bill(Z),c(C1))):-
    ((canoe(X1,Y1),Y=l,Y=X,Y=C,C1=m);
    (canoe(X,Y),Y1=r,Y1=X1,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,X1);canoe(X1,Z1)),
     Z=l,Z=X,Z=C,C1=m);
    ((canoe(Z,X);canoe(X,Z)),Z1=r,Z1=X1,Z1=C1).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z1),c(C1))):-
    ((canoe(Y1,Z1);canoe(Z1,Y1)),
     Y=l,Y=Z,Y=C,C1=m);
    ((canoe(Y,Z);canoe(Z,Y)),Y1=r,Y1=Z1,Y1=C1).

find(Path):-initial(S),rez(S,Path).
bkt(State,Path,[Path|State]):-final(State).
bkt(State,Path,Sol):-move(State,Next),not(bad(Next)),
    not(member(Next,Path)),bkt(Next,[Path|Next],Sol).
rez(State,Sol):-bkt(State,[State],Sol).
start:-find(D),writef('%w\n',D).
4

1 回答 1

2

（这个答案可能为时已晚，但由于这是一个相当经典的问题/谜题，有很多变体，我认为尝试将问题分解一下可能仍然有用。）

正如上面的答案中所述，我认为进行一些重构并尝试为这个问题编写一个更简单、更易于管理的模型可能是一个好主意。我的意思是，如果有人要求你“快速修改”你的代码以集成让我们说第五个人参与这个难题，那么重构上面的代码就不会很有趣。

你可以开始 - 这只是给你一个想法的一种方法 - 通过在列表中编码 4 个人的配置，我们使用“l”或“r”来指定某人是位于左侧还是右侧的河岸。这会给我们一个像这样的初始状态：

% Tom, Jack, Bill, and Jim are all on the left side
[l,l,l,l]

我们想要达到目标状态：

% Tom, Jack, Bill, and Jim are all on the right side
[r,r,r,r]

这为我们提供了一个更容易阅读/理解的模型（imo）。

然后我们可以更多地考虑我们将如何编码河岸之间的实际运输。我们编写了列表配置来指定哪个人位于哪里，所以现在我们需要一个 Prolog 谓词，可以将一种配置转换为另一种配置。比方说：

transport(StartState,[Persons],EndState)

现在，对于实现，而不是显式匹配所有可能的动作（就像您在当前代码中所做的那样），尝试概括到底发生了什么总是一个好主意（Prolog 中有趣的部分:)）。

无需立即编写太复杂的代码，我们将问题分解为小块：

% Facts defining a crossing of the river
cross(l,r).
cross(r,l).

% Transport example for Tom
transport([X,Jack,Bill,Jim],[tom],[Y,Jack,Bill,Jim]) :- cross(X,Y).

如您所见，我们现在以一种非常简单的方式定义了“运输”：众所周知，汤姆只会自己过河，所以我们使用交叉事实来改变他的位置。（请注意，Jack、Bill 和 Jim 只是用“l”或“r”表示这些人位于哪个河岸的变量。由于 Tom 只是自己过河，这些变量不会改变！）。我们可以把它写得更抽象，不要专门匹配“tom”，但我试图在这个例子中保持简单。

当然，我们仍然需要表达哪些交叉是有效的，哪些不是。从你的问题：“在河的左岸到右岸的三个渡口中，独木舟都有两个人，而从右岸到左岸的两个渡口中，独木舟都有一个人。” 这些条件可以很容易地使用我们的“运输”谓词进行编码，因为初始状态（第一个参数）告诉我们是从左到右穿越，反之亦然，我们的第二个参数指定了哪些人正在穿越的列表。换句话说，人行横道的方向和乘客的数量是已知的，在这里写下这些条件似乎有点微不足道。

接下来：“当除了比尔以外的其他人在独木舟上时，杰克无法划桨。” 同样，这已经很容易在我们的“传输”中一起编写（请注意，我使用通配符省略了我们在此特定条件下不关心的信息，但是当然，最终结果可能会有所不同代码。只是举例）：

% Transport example for Jack (Persons length = min 1 - max 2)
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    ( member(jack,Persons) ->
      member(bill,Persons)
    ;
      * other condition(s) *
    ).

% Alternative with pattern matching on Persons
transport([_,_,_,_],[A,B],[_,_,_,_]) :-
    * if jack is A or B, then bill is the other one *

另一个简单的例子：“当别人和他一起划独木舟时，汤姆无法划桨。”

% Tom cannot peddle in a team of 2
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    \+ member(tom,Persons).

正如您可能已经注意到的那样，我们现在几乎将问题完全分解为可以在我们的模型中非常容易地表达的点点滴滴，并且我们离编写实际求解器不远了。然而，网上可以找到足够多的代码示例，我认为没有必要在这里编写更多代码。

通过搜索经典的Fox-Goose-Beans/Cabbage拼图可以找到更多灵感。

祝大家好运！

于 2016-03-19T14:34:34.657 回答