基于Prolog回溯法的图路径查找及指定格式输出实现问题

核心思路 #

要实现要求的输出格式，需要满足两个核心逻辑：

• 遍历过程中每成功匹配一条边时，立即打印该边的节点跳转信息，回溯过程不撤销已打印的内容，即可完整输出所有路径尝试过程
• 遍历过程中记录已访问的节点，避免成环导致无限递归

完整实现代码 #

首先是给定的图的事实定义：

maniere(v11,h11).
maniere(h11,v12).
maniere(h11,h21).
maniere(v12,v22).
maniere(v22,h13).
maniere(v22,h23).
maniere(h13,v21).
maniere(v22,h23).
maniere(h12,h22).
maniere(h23,v23).
maniere(h33,v23).
maniere(v13,h32).
maniere(v23,h32).

然后是路径遍历谓词的实现：

% 入口谓词，传入起点和终点
traverser(Start, End) :-
    traverse_helper(Start, End, [Start]),
    % 可选：加cut! 找到第一个解后直接终止，无需用户手动输入回车结束查询
    !.

% 辅助谓词：当前节点等于终点，匹配成功
traverse_helper(End, End, _Visited).
% 辅助谓词：未到终点，继续向后遍历
traverse_helper(Current, End, Visited) :-
    % 匹配当前节点的后继节点
    maniere(Current, Next),
    % 打印当前跳转路径
    format('~w to ~w~n', [Current, Next]),
    % 校验节点未被访问过，避免成环
    \+ member(Next, Visited),
    % 递归遍历下一个节点，更新已访问列表
    traverse_helper(Next, End, [Next|Visited]).

运行效果 #

调用traverser(v11, v23).查询时，输出结果完全符合要求：

?- traverser(v11, v23).
v11 to h11
h11 to v12
v12 to v22
v22 to h13
h13 to v21
v22 to h23
h23 to v23
true.

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