首页 文章

Prolog河流穿越

提问于
浏览 次
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).
prolog river-crossing-puzzle

1 回答

  • 0

    （这个答案可能为时已晚，但由于这是一个非常经典的问题/难题，有很多变种，我认为尝试将问题稍微解决可能仍然有用 . ）

    至于上面的答案，我认为做一些重构并尝试为这个问题编写一个更简单，更易于管理的模型可能是一个好主意 . 我的意思是，如果有人要求你“快速修改”你的代码以整合让我们说第五个人来解决这个难题，重构上面的代码并不是很有趣 .

    你可以开始 - 这只是一种给你一个想法的方法 - 通过在列表中编码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).

    正如你所看到的，我们现在以一种非常简单的方式定义了“运输”：众所周知，汤姆只能自己过河，因此我们使用交叉事实来改变他的位置 . （请注意，杰克，比尔和吉姆只是变量，说明'l'或'r'表示这些人所在的河岸 . 由于汤姆只是自己穿越，所以这些变量不会改变！） . 我们可以写这个更抽象，并且在'tom'上没有特别匹配，但我试图在这个例子中保持简单 .

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

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

    % 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拼图可以找到更多灵感 .

    祝大家好运！

    回复于

相关问题