水壶问题最短路径求解：如何无需全遍历获取最短路径P

以下是我实现的水壶问题求解方案：

:- use_module(library(clpfd)).

initial(state(8, 0, 0)).
final(state(4, 4, 0)).

constraint(A0, A1, B0, B1, C0, C1, V) :-
  A0 #< A1,
  ( B0 #> 0, T #= min(V - A0, B0), A1 #= A0 + T, B1 #= B0 - T, C1 #= C0
  ; C0 #> 0, T #= min(V - A0, C0), A1 #= A0 + T, C1 #= C0 - T, B1 #= B0
  ).

transition(state(A0, B0, C0), state(A1, B1, C1)) :-
  ( constraint(A0, A1, B0, B1, C0, C1, 8)
  ; constraint(B0, B1, A0, A1, C0, C1, 5)
  ; constraint(C0, C1, A0, A1, B0, B1, 3)
  ).

solve(A, A, _, [A]).
solve(A, B, P, [A|Q]) :-
  transition(A, A1),
  \+ member(A1, P),
  solve(A1, B, [A|P], Q).

path(P) :-
  initial(S0),
  final(S),
  solve(S0, S, [], P).

请问是否存在无需遍历所有可选路径，即可找到长度最短的路径P的方法？

当然存在。你当前的实现用的是无长度限制的深度优先搜索，回溯时会优先探索更长的分支，第一次返回的路径不一定是最短的，要找到最短路径完全不需要遍历所有可选路径，常见的实现方案有三种：

• 广度优先搜索（BFS）：BFS按路径长度逐层扩展状态，第一次到达目标状态时得到的路径天然就是最短的，找到第一个解就可以直接终止搜索，不需要遍历剩余的状态空间。
• 迭代加深深度优先搜索（IDDFS）：从小到大设定路径的最大允许长度，每次用DFS搜索不超过该长度的路径，第一次找到符合要求的路径时就是最短路径。这个方案不需要额外维护BFS的层级队列，内存开销远低于BFS，非常适配水壶问题这类小状态空间的场景。
• CLPFD长度约束搜索：利用Prolog的特性，先声明路径长度变量L，让L从1开始逐次递增，约束求解路径的长度等于L，第一次求解成功得到的就是最短路径，代码改动量极小。

可以参考下面的最短路径实现，只需要对你的原有代码做少量修改：

% 带长度限制的搜索谓词
solve_limit(A, A, _, 1, [A]).
solve_limit(A, B, Visited, L, [A|Path]) :-
  L > 1,
  NextL is L - 1,
  transition(A, NextState),
  \+ member(NextState, Visited),
  solve_limit(NextState, B, [A|Visited], NextL, Path).

shortest_path(P) :-
  initial(Start),
  final(Target),
  length(P, PathLen), % 从小到大生成路径长度
  solve_limit(Start, Target, [], PathLen, P),
  !. % 找到第一个最短路径后直接截断，停止搜索

调用shortest_path(P)就能直接得到最短路径，不需要遍历所有可能的路径。

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