Prolog中DFS与状态空间实现水壶问题的故障排查求助

1. 倒水动作逻辑错误（核心问题） #

你写的pour1to2和pour2to1动作逻辑完全错误——当前代码强制将倒出水的水壶直接置空，这不符合实际倒水规则：

• 从水壶1倒向水壶2时，只有当水壶1的水量≤水壶2的剩余容量时，才会倒空水壶1；否则水壶1会剩余部分水量，水壶2被倒满。
• 同理，从水壶2倒向水壶1时也需要计算实际转移的水量，而非直接清空水壶2。

修正后的动作定义：

action(pour1to2, jug(X,Y), jug(X1,Y1)) :- 
    X > 0, Y < 3,
    Transfer is min(X, 3 - Y),  % 计算实际能转移的水量
    X1 is X - Transfer,
    Y1 is Y + Transfer.

action(pour2to1, jug(X,Y), jug(X1,Y1)) :- 
    Y > 0, X < 4,
    Transfer is min(Y, 4 - X),
    Y1 is Y - Transfer,
    X1 is X + Transfer.

2. 冗余状态判断（非致命，可优化） #

代码中的State1 \= State是冗余判断——所有动作定义都会产生与原状态不同的新状态，完全可以移除，不影响逻辑且能提升一点效率。

修正后的完整代码 #

% Water Jug problem using DFS in Prolog

% Define the initial state
start(jug(0,0)).

% Define the goal state
goal(jug(_,2)).

% Define the actions that can be taken
action(fill1, jug(_,Y), jug(4,Y)).
action(fill2, jug(X,_), jug(X,3)).
action(empty1, jug(_,Y), jug(0,Y)).
action(empty2, jug(X,_), jug(X,0)).
action(pour1to2, jug(X,Y), jug(X1,Y1)) :- 
    X > 0, Y < 3,
    Transfer is min(X, 3 - Y),
    X1 is X - Transfer,
    Y1 is Y + Transfer.
action(pour2to1, jug(X,Y), jug(X1,Y1)) :- 
    Y > 0, X < 4,
    Transfer is min(Y, 4 - X),
    Y1 is Y - Transfer,
    X1 is X + Transfer.

% Define the DFS algorithm
dfs(State, [], _) :- goal(State).

dfs(State, [Action|Actions], Visited) :- 
    action(Action, State, State1),
    \+ member(State1, Visited),
    dfs(State1, Actions, [State1|Visited]).

验证结果 #

运行指令start(State), dfs(State, Actions, [State]).，会得到正确的动作序列，例如：

Actions = [fill2, pour2to1, fill2, pour2to1]

对应的状态流转为：
(0,0) → (0,3) → (3,0) → (3,3) → (4,2)，最终状态(4,2)满足目标要求（水壶2装有2单位水）。

内容的提问来源于stack exchange，提问作者Ni No