狼山羊白菜拼圖解算器中的堆棧溢出

我試圖在Prolog中編寫程序來解決衆所周知的狼山羊白菜拼圖。鑑於一個想用狼，山羊和捲心菜過河的農民。船隻同時舉行兩次，他不能與山羊或山羊一起離開狼。狼山羊白菜拼圖解算器中的堆棧溢出

我知道這裏有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。

來源

2014-01-16 danijar

一個肯定的錯誤就是你稱之爲船員（船員）的方式，或者更確切地說你如何定義船員。我想你想製作一份名單：「船員（[農夫，狼]）'。 –

在運行之前，請使用'trace。'，這將允許您逐步執行並查看它開始在循環中運行的點 - 這是非常有用的學習工具。 – magus

@Amicable好吧，我不知道代碼評論中沒有工作代碼是關於主題的。 – danijar

SWI-Prolog的基於外部參照編輯器突出了第一個問題：船員/ 2是從未使用過：

enter image description here

那麼你也許想這樣的定義：

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) 
...

也就是說，船員總是失敗......

來源

2014-01-16 17:23:19 CapelliC

好吧，將'crew'字段定義在列表上，程序爲輸入的cross（[farmer，wolf，goat，cabbage]，[]，[]，[farmer，wolf，goat，cabbage]]輸出'no' ）.'。 – danijar

感謝您的更新。你有一個想法如何解決這個問題？ – danijar

你嘗試過「船員（側）」嗎？也許跟蹤這個改變可能會提示如何解決問題 – CapelliC

原來有幾個問題與程序，最做不侷限於深度優先搜索，並允許（[F，G，W，C]，[]） - >（[W，C]，[F，G]） - >（[F，G，W，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, []).

來源

2014-10-29 17:19:15 jspencer

狼山羊白菜拼圖解算器中的堆棧溢出

回答

相關問題