Prolog中Cut算子未按预期丢弃选择点的原因探究

免责声明：这确实是一项作业任务，但我已有替代解决方案。我只是想弄明白最初的尝试为何失败，因为我无法理解它为何未按预期运行。

我正在编写一个path/2谓词（path(+Node1, +Node2)），它接收两个节点，若Node1到Node2存在通过单独定义的edge/2谓词（语义上，edge(A, B).表示从A到B的有向边）的有效路径，则返回true。

我的代码如下：

%    WRAPPER
path(N1, N2) :- 
    pathHelper(N1, N2, []).

%    HELPER
pathHelper(N1, N2, Checked) :- 
    \+ member(N1, Checked),
    (
        (N1 = N2, !); % sort of a base case?
        NewChecked = [N1 | Checked],
        (
            edge(N1, Next),
            pathHelper(Next, N2, NewChecked)
        )
    ).

给定以下知识库：

%    KNOWLEDGE BASE
edge(a,b).
edge(b,c).
edge(c,d).
edge(d,a).
edge(d,e).
edge(b,a).

当执行查询?- path(b, d).时，程序会先针对路径b->c->d返回true.（已通过跟踪模式验证），但随后会回溯到b节点检查其他相连节点，找到a并再次检查，最终返回false.。

我的理解是，当程序执行到(N1 = N2, !);且N1与N2成功合一后，!（cut算子）应丢弃所有之前的选择点，跳过后续语句，不再寻找其他可形成路径的节点。但实际结果并非如此，我对cut算子的理解存在哪些误区？

你的核心误区在于cut算子的作用范围：cut仅能删除其所在子句内的当前选择点，以及该子句中cut左侧的选择点，无法影响上层调用栈中的选择点。

具体执行流程拆解 #

1. 当pathHelper(d, d, [c,b])执行时，N1 = N2匹配成功，随后的!只会删除当前pathHelper子句中;分隔的两个分支的选择点（也就是不会再尝试执行;右侧的分支），但不会影响上层pathHelper(c, d, [b])中edge(c, Next)的选择点，更不会影响最上层pathHelper(b, d, [])里edge(b, Next)的选择点。
2. 第一个有效路径b->c->d返回true后，Prolog会默认尝试回溯寻找其他可能的解，于是回到pathHelper(b, d, [])中edge(b, Next)的选择点，尝试edge(b,a)这条边，进入pathHelper(a, d, [b])的调用。由于这条路径最终无法到达d，所以返回false，这就是你看到的最终结果。

修正方案 #

要让cut阻止上层回溯，需要把cut放在能覆盖上层选择点的位置，比如直接在path谓词中：

path(N1, N2) :- 
    pathHelper(N1, N2, []), !.

pathHelper(N1, N2, _Checked) :- 
    N1 = N2.
pathHelper(N1, N2, Checked) :-
    \+ member(N1, Checked),
    edge(N1, Next),
    pathHelper(Next, N2, [N1|Checked]).

这里的cut放在path子句中，一旦pathHelper找到第一个有效路径，cut就会切断所有后续回溯，确保只返回true。

另一种更符合Prolog风格的写法是拆分子句，避免嵌套的;结构，这样逻辑更清晰，cut的作用也更明确。

总结：cut的作用范围是当前子句，它只能消除该子句内左侧的选择点和备选分支，不能影响上层调用的选择点。你之前误以为cut会删除所有上层选择点，这是核心错误。

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