SWI Prolog路径重复输出问题及最短路径实现方案咨询

我来帮你拆解这个问题——在SWI-Prolog里遇到路径重复输出，还有最短路径求解的需求，这俩其实是紧密相关的，咱们一步步来：

• 双向边的回溯特性：你定义的touching/2事实是双向的（比如touching(2,1)和touching(1,2)同时存在），Prolog的回溯机制会顺着两条边分别搜索，导致同一段路径的往返、或者同一路径的反向被当成不同解重复输出。
• 未跟踪已访问节点：如果你的路径搜索规则没有记录已经走过的节点，Prolog会反复遍历同一个节点，生成大量包含循环的重复路径（比如1→2→1→2...），或者不同遍历顺序但本质相同的路径。

核心思路是在搜索过程中维护一个已访问节点的列表，确保每个节点只被访问一次。假设你要找从起点Start到终点End的路径，可以这样定义规则：

% 基础情况：起点就是终点，路径只有起点本身
path(Start, Start, [Start]).
% 递归情况：找到相邻节点Next，且Next不在已访问路径里
path(Start, End, [Start|Rest]) :-
    touching(Start, Next),
    \+ member(Next, [Start|Rest]),  % 关键：排除已访问的节点
    path(Next, End, Rest).

这里的\+ member(Next, [Start|Rest])是核心——它确保不会重复访问已经在当前路径中的节点，从根源上避免了循环和重复路径的生成。

最短路径最适合用广度优先搜索（BFS），因为BFS是按层级遍历的，第一个找到的从起点到终点的路径就是最短的（不会像深度优先搜索那样先钻进长路径里）。

下面是一个SWI-Prolog的BFS实现示例：

% 初始化BFS队列：队列元素是(当前节点, 已走路径)
bfs_shortest_path(Start, End, Path) :-
    bfs_queue([(Start, [Start])], End, Path).

% 终止条件：队列头部的节点就是终点，直接返回对应路径
bfs_queue([(End, Path)|_], End, Path).
% 递归扩展队列：处理头部节点，把未访问的相邻节点加到队列尾部
bfs_queue([(Current, CurrentPath)|Rest], End, Path) :-
    findall(
        (Next, [Next|CurrentPath]),  % 路径暂时反向存储，最后反转即可
        (touching(Current, Next), \+ member(Next, CurrentPath)),
        NextPaths
    ),
    append(Rest, NextPaths, NewQueue),  % 新节点加到队列尾部，保证层级顺序
    bfs_queue(NewQueue, End, Path).

% 可选：把反转的路径调整为从起点到终点的正常顺序
shortest_path(Start, End, FinalPath) :-
    bfs_shortest_path(Start, End, ReversedPath),
    reverse(ReversedPath, FinalPath).

简单解释下：

• 队列里的每个元素绑定了当前节点和到达该节点的路径，初始队列只有起点和包含起点的路径。
• 每次处理队列头部的节点，扩展所有未访问过的相邻节点，把新节点和新路径加到队列尾部——这样能保证先处理路径更短的节点（层级更浅的）。
• 当第一次遇到终点时，对应的路径就是最短路径，直接返回即可。

如果图的规模很小，你也可以用findall/3收集所有合法路径，再用min_list/2筛选出最短的，但这种方法效率极低，BFS是最优选择。

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