SWI-Prolog中如何低内存开销实现原子的最值求解？

问题背景 #

现有谓词生成多个解，例如：

solution(1).
solution(2).
solution(3).
solution(4).
solution(5).
solution(6).

常规使用findall/3或setof/3收集所有解后再找最优的方式会占用大量内存，期望实现一种无需存储所有解、仅在遍历过程中维护当前最优的方案，类似接口形式：

findmin(MinAtom, Solution, (predicate(MinAtom, Solution))).

SWI-Prolog原生实现方案 #

SWI-Prolog自带的library(aggregate)模块专门解决这类聚合统计问题，其中aggregate/3或aggregate_all/3可以在遍历解的过程中直接计算最大值/最小值，无需存储所有结果：

求最大值示例 #

:- use_module(library(aggregate)).

find_max_solution(Max) :-
    aggregate(max(X), solution(X), Max).

调用find_max_solution(Max)会直接返回Max=6，内部仅维护当前最大值，内存占用极低。

求最小值示例 #

find_min_solution(Min) :-
    aggregate(min(X), solution(X), Min).

调用后返回Min=1。

手动实现最优解遍历（含取巧的fail用法） #

如果需要自定义逻辑，可通过回溯+状态维护实现，以下是两种常见方式：

方式1：使用非回溯变量（nb_setval/2） #

利用SWI-Prolog的非回溯变量存储当前最优值，遍历所有解时更新：

find_max_solution(Max) :-
    nb_setval(current_opt, -inf),  % 初始化最优值为负无穷
    % 遍历所有解，更新最优值
    forall(solution(X), (
        nb_getval(current_opt, Curr),
        (X > Curr -> nb_setval(current_opt, X) ; true)
    )),
    nb_getval(current_opt, Max),
    nb_delete(current_opt).  % 清理临时变量

方式2：滥用fail谓词触发回溯 #

通过fail强制遍历所有解，配合动态谓词记录当前最优值：

:- dynamic current_opt/1.

find_max_solution(Max) :-
    retractall(current_opt(_)),
    assert(current_opt(-inf)),  % 初始化
    % 遍历所有解，更新最优后触发fail回溯
    (solution(X),
     current_opt(Curr),
     (X > Curr -> retract(current_opt(Curr)), assert(current_opt(X)) ; true),
     fail
    ; current_opt(Max)),  % 所有回溯结束后，取最终最优值
    retractall(current_opt(_)).

这里fail会迫使Prolog回溯所有solution(X)的可能，每次迭代都更新当前最优值，直到没有更多解时，执行第二个分支返回结果。

图搜索场景下的优化思路（类似ILP） #

如果是图搜索类问题（如路径规划、组合优化），需避免重复搜索无效分支，可采用以下策略：

• 分支定界剪枝：维护当前最优值，在搜索每个分支前判断该分支的理论最优下界是否能超过当前最优值，若无法超过则直接剪枝，跳过该分支的探索。
• 启发式优先搜索：优先搜索更可能得到优解的分支（如估值更高的节点），快速找到较优解后，后续剪枝的效率会大幅提升。
• 状态记录：用动态谓词或哈希表记录已访问过的状态，避免重复探索相同状态。

内容的提问来源于stack exchange，提问作者Seán Healy