2

我尝试在 Prolog 中编写一个程序来解决众所周知的 Wolf Goat Cabbage 谜题。假设一个农民想带着他的狼、山羊和卷心菜过河。船只能同时容纳两个，他不能让狼和山羊或山羊和白菜一起离开。

我知道 Stackoverflow 上有针对此问题的有效解决方案。但我想在我的代码中找到错误以用于学习目的。这是我的代码。它导致所谓的本地堆栈溢出，我猜逻辑中存在错误。由于我对每个块都进行了评论，因此应该很容易理解。

% Helper function to check if first list
% is fully contained in second one.
subset([], []).
subset([E|Tail], [E|NTail]):-
    subset(Tail, NTail).
subset([_|Tail], NTail):-
    subset(Tail, NTail).

% There is space for two objects on the
% boat, but one of them must be the farmer.
crew(farmer).
crew(farmer, wolf).
crew(farmer, goat).
crew(farmer, cabbage).

% The riverside is safe if either the
% farmer is there, or not both wolf and
% goat or both goat and cabbage are there.
safe(Side) :-
    member(farmer, Side).
safe(Side) :-
    not(member(wolf, Side)),
    not(member(goat, Side)).
safe(Side) :-
    not(member(goat, Side)),
    not(member(cabbage, Side)).

% To embark, objects from one riverside,
% the crew must be valid an the riverside
% must stay safe. Disembarking is easy.
embark(Crew, Side, New) :-
    subset(Crew, Side),
    crew(Crew),
    safe(Side),
    delete(Side, Crew, New).
disembark(Crew, Side, New) :-
    append(Side, Crew, New).

% Crossing the river from one or the other side.
cross(Left, Right, Nextleft, Nextright) :-
    embark(Left, Crew, L),
    disembark(Right, Crew, R),
    cross(L, R, Nextleft, Nextright).
cross(Left, Right, Nextleft, Nextright) :-
    embark(Right, Crew, R),
    disembark(Left, Crew, L),
    cross(L, R, Nextleft, Nextright).

% Find solution to bring all objects from left
% riverside to right. Run this after consulting
% the file.
% cross([farmer, wolf, goat, cabbage], [], [], [farmer, wolf, goat, cabbage]).

这段代码有什么问题？我只是尝试更深入地了解 Prolog。

4

2 回答 2

4

基于 SWI-Prolog 外部参照的编辑器突出显示了第一个问题：从不使用 Crew/2：

在此处输入图像描述

那么你可能想要这个定义：

crew([farmer]).
crew([farmer, wolf]).
crew([farmer, goat]).
crew([farmer, cabbage]).

编辑我认为下一个问题在你调用crew/1的方式中很明显：

embark(Crew, Side, New) :-
    subset(Crew, Side),
    crew(Crew),
    safe(Side),
    delete(Side, Crew, New).

您正在传递一个已经形成的工作人员，而不是由子集/2 生成的工作人员。如果进入调试模式

?- leash(-all),trace.
true.
[trace] 3 ?- cross([farmer, wolf, goat, cabbage], [], [], L).
Call: (6) stackoverflow:cross([farmer, wolf, goat, cabbage], [], [], _G1474)
...

Exit: (8) stackoverflow:subset([farmer, wolf, goat, cabbage], [farmer, wolf, goat, cabbage])
Call: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Fail: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Redo: (11) stackoverflow:subset([cabbage], _G1560)
...
Exit: (8) stackoverflow:subset([farmer, wolf, goat, cabbage], [farmer, wolf, goat])
Call: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Fail: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Redo: (10) stackoverflow:subset([goat, cabbage], _G1557)
...

也就是说，船员总是失败......

于 2014-01-16T17:23:19.903 回答
1

事实证明，该程序存在几个问题，主要与不限制深度优先搜索和允许循环如 ([F,G,W,C], [])-->([W,C], [F,G])-->([F,G,W,C], [])，会无限下降。在安全等方面也存在一些小的逻辑错误（不允许山羊或狼几乎没有选择）。

作为一次学习经历，我经历并得到了这种工作方法。我喜欢它所捕捉的思维过程，并希望看到它得到发展。在处理过程中，我对它进行了一些重新组织，但它应该仍然可以识别。我添加了一个带有 prev 的“no undo”移动检查和一个“no empty right side”检查，以切断对骨头路径的搜索。我还为更简单的 prolog 解释器添加了一些原语。但也许看到这一点会有所帮助。

最后在 SWI-Prolog 上测试。

member(X, [X|_]).
member(X, [_|Tail]) :- member(X, Tail).

subset([],_).
subset([X|L],Set):-
    member(X,Set),
    subset(L,Set).

delete([], _, []).
delete(List, [], List).
delete([X|Tail], [X|STail], Res) :- 
    delete(Tail, STail, Res).
delete([X|Tail], Sublist, Res) :- 
    member(X, Sublist),
    delete(Tail, Sublist, Res).
delete([X|Tail], Sublist, [X|Res]) :-
    not(member(X, Sublist)),
    delete(Tail, Sublist, Res).

append([],L,L).
append([H|T],L,[H|TL]) :- append(T,L,TL).

crew([farmer]).
crew([farmer, wolf]).
crew([farmer, goat]).
crew([farmer, cabbage]).

safe([]).
safe(Side) :-
    member(farmer, Side).
safe(Side) :-
    not(subset([goat, wolf], Side)),
    not(subset([goat, cabbage], Side)).

embark(Side, Crew, Remain, Prev) :-
    crew(Crew),
    subset(Crew, Side),
    not(Crew = Prev),
    delete(Side, Crew, Remain),
    safe(Remain).
disembark(Side, Crew, Remain) :-
    append(Side, Crew, Remain),
    safe(Remain).

cross([], Right, [], _) :-
    subset([farmer, wolf, goat, cabbage], Right).
cross(Left, Right, Move, Prev) :-
    embark(Left, Crew, NewLeft, Prev),
    disembark(Right, Crew, NewRight),
    cross(NewLeft, NewRight, Othermoves, Crew),
    Move = [[toright|Crew]|Othermoves].
cross(Left, Right, Move, Prev) :-
    embark(Right, Crew, NewRight, Prev),
    not(NewRight = []),
    disembark(Left, Crew, NewLeft),
    cross(NewLeft, NewRight, Othermoves, Crew),
    Move = [[toleft|Crew]|Othermoves].

solve(Left, Right, Moves) :-
    cross(Left, Right, Moves, []).
于 2014-10-29T17:19:15.090 回答