Prolog实现原子拆分时为何重复返回相同正确解？

问题出在拆分逻辑的冗余设计，带来了大量无意义的回溯路径，最终同一个正确解会被多条不同的执行路径重复命中，和Prolog本身的回溯机制无关，是代码约束写漏了。

核心逻辑漏洞：子串匹配未限定前缀位置 #

看递归拆分的核心代码：

split_atoms(C, AtomsAccum, Atoms):- 
    basics( B ) ,
    member( SubAtom, B ) ,
    sub_atom( C, _, Length, _, SubAtom ) , 
    sub_atom( C, Length, _, 0, AtomRest ) , 
    split_atoms(AtomRest, [SubAtom|AtomsAccum], Atoms).

sub_atom/5的第二个参数是匹配子串的起始偏移量，这里用匿名变量_意味着只要基础原子在当前待拆分串的任意位置出现就算匹配成功，完全没有要求基础原子必须出现在待拆分串的最开头（也就是作为前缀）。

举个实际的例子：当待拆分串是aaaabcaaadef时，基础原子a可以在偏移0、1、2、3四个位置匹配成功：

• 偏移为0时，截掉长度1的前缀，剩余aaabcaaadef，这是符合拆分逻辑的正确路径
• 偏移为1、2、3时，代码会直接跳过前面的1~3个字符，从匹配位置的末尾截剩余串继续递归，这些路径本质上都是不符合“连续拼接”要求的错误路径

冗余校验让错误路径也能产出正确解 #

在拆分到空串的终止分支，你又加了一层拼接校验：

split_atoms( '', AtomsAccum, Atoms ) :-
    candidate(C) ,
    reverse( AtomsAccum, AtomsAccumR ) ,
    join_atoms( AtomsAccumR, C ) ,
    Atoms = AtomsAccumR .

本来如果每一步都严格拆分前缀，这层校验完全多余。现在因为前面放进来了大量跳步的错误路径，这层校验会把所有“最后拼起来刚好等于原串”的路径都判定为有效——而很多不同的跳步路径，最后收集到的原子序列是完全一样的，自然就会重复返回同一个解。
你看到的同一个解重复6次的现象，就是前3个字符拆分时，a的匹配偏移可选值组合出来的多条路径，最后都落到了同一个原子序列上。

直接从根源上剪掉无效路径，不需要靠最后sort/2去重：

• 把sub_atom的匹配起始偏移固定为0，强制每一步只匹配当前串的前缀，从根源上杜绝跳步的无效路径
• 删除终止分支里多余的拼接校验，因为严格按前缀拆分的路径，最后拼出来的结果必然和原串一致

修改后的拆分核心代码如下：

split_atoms( '', AtomsAccum, Atoms ) :-
    reverse( AtomsAccum, Atoms ) .
split_atoms(C, AtomsAccum, Atoms):- 
    basics( B ) ,
    member( SubAtom, B ) ,
    % 固定从起始位置0匹配前缀
    sub_atom( C, 0, Length, _, SubAtom ) , 
    sub_atom( C, Length, _, 0, AtomRest ) , 
    split_atoms(AtomRest, [SubAtom|AtomsAccum], Atoms).

改完后直接查询就不会出现重复解，执行效率也会提升几个数量级，不会再浪费算力跑那些最后会被校验过滤的无效分支。

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