0

我想使用任何类型的深度优先搜索来解决 SWI-Prolog 中的 7 升和 5 升到 4 升的难题

我不知道我该如何开始..

最后我想在一个罐子里装 4 升

solve(JUG1, JUG2) :- fill(JUG1, JUG2), swap(JUG1, JUG2).
fill(JUG1,JUG2) :- JUG1 = 7, JUG2 = 5.
%i dont know about that
swap(JUG1, JUG2) :- JUG1 = JUG2.
4

1 回答 1

1

我有完全相同的问题要解决，我在我的电脑上找到了我的代码：

我们正在使用迭代加深深度优先搜索来结合呼吸和深度搜索的优点。使用以下代码，我们正在尝试可能的组合以达到我们的目标，即在一个水壶中最终达到 4 升。如果我们找到解决方案，我们将相应地打印出来。

% Iterative deepening depth-first search
dlDfs(Node, Path, DepthLimit, ReturnPath) :-
    goal(Node), reverse(Path, ReturnPath);
    DepthLimit > 0,
    adj(Node,NewNeighbor), not(member(NewNeighbor,Path)),
    L is DepthLimit-1,
    dlDfs(NewNeighbor, [NewNeighbor|Path], L, ReturnPath).

idDfsLoop(Start, D, ReturnPath) :-
    dlDfs(Start, [Start], D, ReturnPath)
    ;
    L is D+1,
    idDfsLoop(Start, L, ReturnPath).

idDfs(Start, ReturnPath) :- idDfsLoop(Start, 1, ReturnPath).

% [L,R] L is 7 liter, R is 5 liter
goal([_,4]).
goal([4,_]).

adj(X,Y) :- adj0(X,Y).

%fill up
adj0([X,Y],[7,Y]).
adj0([X,Y],[X,5]).

%Swap over to another canister
adj0([X,Y],[Z,U]) :- X+Y =< 5, Z is 0, U is X+Y ; X+Y > 5, Z is (X+Y) mod 5, U is 5.
adj0([X,Y],[Z,U]) :- X+Y =< 7, Z is X+Y, U is 0 ; X+Y > 7, Z is 7, U is (X+Y) mod 7.

%empty the cansiter
adj0([X,Y],[0,Y]).
adj0([X,Y],[X,0]).

solution(Start, Return) :- idDfs(Start, Return).

您可以调用解决方案谓词，如下所示：

solution([0,0], R)

例如，解决方案之一应该是

R = [[0, 0], [7, 0], [2, 5], [2, 0], [0, 2], [7, 2], [4, 5]]

如果您有任何问题，请随时回答。

于 2019-08-27T08:15:30.980 回答