使用失败，回溯 Prolog 查找列表的最小值

Question

我想计算列表的最小值，使用失败导致回溯。我如何更改 min(Min, X, Min)，使其工作。

%min(X, A, B) X is the min of A, B
min(X, X, Y) :- X =< Y.
min(Y, X, Y) :- Y < X.

member(X, [X|_]).
member(X, [_|Ys]) :-
  member(X,Ys).

program :-
  Min is 1000,
  (member(X, [1, 2, 3, 4]),
  writeln(X),
  min(Min, X, Min), %This is wrong !
  fail;
  writeln(Min),
  true).

我以前计算最小值的工作代码

solve([Head|Rest], Ans) :-
   solve(Rest, Till),
   min(Ans, Head, Till).

但我不想这样做，至于调用解决，我正在做这样的事情

program :-
   findall(X, solve(List, X), Z).

这导致找到 X 的所有解并存储在内存中。此方法不适用于大量输入，会被杀死。

因此，我想即时计算每个求解调用的最小值，而不是像使用 findall 那样存储。

Answer 1

如果您担心内存使用情况，则不应使用猜测和检查比喻（使用失败意味着您正在使用）。有一个 O(n) 算法根本不需要失败。

minlist(Min, [X|Xs]) :- minlist(X, Xs, Min).

minlist(Min, [], Min).
minlist(MinSoFar, [X|Xs], Min) :-
    min(NextMin, MinSoFar, X),
    minlist(NextMin, Xs, Min).

使用失败，回溯 Prolog 查找列表的最小值

Find min of list using fail, backtracking Prolog

prolog

backtracking