狼山羊甘蓝拼图求解器中的堆栈溢出
狼山羊甘蓝拼图求解器中的堆栈溢出
提问于 2014-01-16 16:54:42
我试着用Prolog编写一个程序来解决众所周知的狼山羊卷心菜难题。给了一个想和他的狼，山羊和卷心菜过河的农民。这条船同时只能装两个，他不能把狼和山羊丢在一起，也不能丢下山羊和卷心菜。
我知道这里有解决这个问题的有效方法。但是，为了学习的目的，我想在代码中找出错误。这是我的密码。它导致所谓的本地堆栈溢出，我猜逻辑中有一个错误。因为我评论了每一个街区，这应该很容易理解。
% 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。
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-01-16 17:23:19
基于SWI xref的编辑器强调了第一个问题: crew/2从未被使用过：
那么您可能需要这样的定义：
crew([farmer]).
crew([farmer, wolf]).
crew([farmer, goat]).
crew([farmer, cabbage]).编辑我认为下一个问题是显而易见的方式，你叫船员/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)
...也就是说船员总是失败..。
Stack Overflow用户
发布于 2014-10-29 17:19:15
结果表明，该程序存在几个问题，大多数问题与深度优先搜索和允许循环(F，G，W，C，[]) ->( W，C，F，G，C，C，[])->(F，G，W，C，C，[])等问题有关。在诸如安全的事情上也有一些小的逻辑错误(不允许山羊或狼只剩下很少的选择)。
作为一次学习的经历，我经历了这种方法并开始工作。我喜欢它捕捉到的思想过程，并希望看到它的发展。在事情的过程中，我对它进行了一些重新组织，但它仍然是可以辨认的。我增加了一个“不撤销”移动检查与prev，和“没有空的右侧”检查，以切断对骨头头路径的搜索。我还为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, []).页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21167969
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号