使用Prolog查找无向无环图路径：遗漏路径且结果重复

核心问题拆解 #

1. 路径遗漏原因 #

• 错误的递归限制条件：原程序第三个子句中的not(adj(X,Y,Weight))会阻止程序寻找「X和Y存在直接边，但存在更长间接路径」的情况。比如a→b→c这条路径，因为a和c有直接边，该条件会导致递归分支被跳过，无法生成这条路径，进而遗漏依赖它的a→b→c→d→e。
• 倒推逻辑的局限性：原程序从终点倒推时仅使用edge(A,Y,Weight1)（仅匹配原edge的正向定义），没有利用无向图的双向邻接关系，导致部分路径无法被遍历到。

2. 重复输出原因 #

• 未记录已访问节点：无向图中，Prolog的回溯机制会通过不同推导顺序生成相同路径（比如同一路径的反向推导分支），但原程序没有节点去重逻辑，导致重复输出。
• 邻接关系定义错误：原adj/3的第二个子句adj(Y,X,W) :- edge(Y,X,W)完全冗余，且没有正确表示无向图的双向邻接，间接导致匹配冗余。

修正后的代码 #

% 定义无向图的边
edge(a,b,1). 
edge(a,c,6). 
edge(b,c,4). 
edge(b,d,3). 
edge(b,e,1). 
edge(c,d,1). 
edge(d,e,1).

% 正确表示无向图的邻接关系：X与Y相邻，只要存在任意方向的边
adj(X, Y, W) :- edge(X, Y, W).
adj(X, Y, W) :- edge(Y, X, W).

% 主谓词：findpath(起点, 终点, 总权重, 路径)
% 基础情况：到达终点，路径仅包含终点，权重为0
findpath(End, End, 0, [End]).

% 递归情况：从当前节点出发，遍历未访问的邻居，递归生成路径并累加权重
findpath(Current, End, TotalWeight, [Current|PathRest]) :-
    adj(Current, Next, Weight),
    \+ member(Next, [Current|PathRest]),  % 防止重复访问节点，避免循环和重复路径
    findpath(Next, End, RestWeight, PathRest),
    TotalWeight is Weight + RestWeight.

修正说明 #

1. 正向搜索逻辑：改为从起点出发遍历路径，逻辑更直观，避免倒推带来的局限性。
2. 节点去重：通过\+ member(Next, [Current|PathRest])确保每个节点仅被访问一次，彻底解决重复路径问题，同时防止无向图中的循环遍历。
3. 正确的邻接关系：修正adj/3定义，完整覆盖无向图的双向邻接，确保所有可能的路径分支都能被遍历。
4. 移除错误限制：去掉not(adj(X,Y,Weight))条件，允许程序寻找所有合法路径，包括存在直接边的间接路径。

测试结果 #

执行查询findpath(a, e, W, P).会输出所有合法路径，无重复、无遗漏：

W = 2, P = [a, b, e] ;
W = 5, P = [a, b, d, e] ;
W = 7, P = [a, b, c, d, e] ;
W = 8, P = [a, c, d, e] ;
W = 11, P = [a, c, b, e] ;
W = 14, P = [a, c, b, d, e] ;
false.

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