Prolog，查找列表中的最小值

Question

简言之：如何在列表中找到最小值？（感谢Kaarel的建议）

详细情况：

我在Amzi Prolog中创建了一个加权图，并给定两个节点，我能够检索到路径列表。然而，我需要找到该路径中的最小值，但无法遍历列表来完成。请问如何确定列表中的最小值？

我的代码目前看起来像这样：

arc(1,2).
arc(2,3).
arc(3,4).
arc(3,5).
arc(3,6).
arc(2,5).
arc(5,6).
arc(2,6).

path(X,Z,A) :- 
 (arc(X,Y),path(Y,Z,A1),A is A1+1;arc(X,Z), A is 1).

因此，在listener中输入'findall(Z,path(2,6,Z),L).' 可以得到一个列表 [3,2,2,1]。我需要从中检索最小值并乘以一个数值。请问如何检索最小值？谢谢！

- Roy

---

请用一句话“如何确定列表中的最小数？”替换您的问题文本？;) - Kaarel

Answer 1

通常使用所谓的“滞后参数”从第一个参数索引中受益：

list_min([L|Ls], Min) :-
    list_min(Ls, L, Min).

list_min([], Min, Min).
list_min([L|Ls], Min0, Min) :-
    Min1 is min(L, Min0),
    list_min(Ls, Min1, Min).

这个模式称为从左折叠（fold），而最新版本的 SWI 中提供了 foldl/4，它使您可以将其编写为：

list_min([L|Ls], Min) :- foldl(num_num_min, Ls, L, Min).

num_num_min(X, Y, Min) :- Min is min(X, Y).

请注意，这并不适用于所有方向，例如：

?- list_min([A,B], 5).
is/2: Arguments are not sufficiently instantiated

如果你在考虑整数，正如你的例子中所示，我建议你使用CLP(FD)约束来自然地推广谓词。不要使用(is)/2，而是直接使用(#=)/2，从中获得更具有声明性的解决方案：

:- use_module(library(clpfd)).

list_min([L|Ls], Min) :- foldl(num_num_min, Ls, L, Min).

num_num_min(X, Y, Min) :- Min #= min(X, Y).

这可以被用作一个真实的关系，适用于所有方向，例如：

?- list_min([A,B], 5).

yielding:

稍作让步或屈服的意思。

A in 5..sup,
5#=min(B, A),
B in 5..sup.

- mat

Answer 2

我认为这看起来是正确的（来自此处）。

min_in_list([Min],Min).                 % We've found the minimum

min_in_list([H,K|T],M) :-
    H =< K,                             % H is less than or equal to K
    min_in_list([H|T],M).               % so use H

min_in_list([H,K|T],M) :-
    H > K,                              % H is greater than K
    min_in_list([K|T],M).               % so use K

- andersoj

---

谢谢andersoj。在提交问题之前，我在网上搜索时看到了这段代码。不知何故，我当时没有理解它，现在我明白了，谢谢！ - Roy

我多年没有想过Prolog了，但我猜@mat的可读性比我发布的要好... - andersoj

你的解决方案问题在于你比较了两次 H 和 K，而 min 函数可能并不会这样做... - Kaarel

Answer 3

%Usage: minl(List, Minimum).
minl([Only], Only).
minl([Head|Tail], Minimum) :-
    minl(Tail, TailMin),
    Minimum is min(Head, TailMin). 

第二条规则进行递归，即“获取尾部中最小的值，并将Minimum设置为该值和头部中较小的值”。第一条规则是基本情况，“一个列表的最小值是列表中唯一的值”。

测试：

| ?- minl([2,4,1],1).

true ? 

yes
| ?- minl([2,4,1],X).

X = 1 ? 

yes

你可以在第一种情况下使用它来检查一个值，或者在第二种情况下让Prolog计算该值。

- Joe Flynn

Answer 4

SWI-Prolog提供library(aggregate)，在通用性和性能上都表现优异。

:- [library(aggregate)].
min(L, M) :- aggregate(min(E), member(E, L), M).

编辑

最近增加了library（solution_sequences），现在我们可以编写以下代码：

min(L,M) :- order_by([asc(M)], member(M,L)), !.
max(L,M) :- order_by([desc(M)], member(M,L)), !.

现在，准备好惊喜了吗 :) ?

?- test_performance([clpfd_max,slow_max,member_max,rel_max,agg_max]).
clpfd_max:99999996
% 1,500,000 inferences, 0.607 CPU in 0.607 seconds (100% CPU, 2470519 Lips)
slow_max:99999996
% 9,500,376 inferences, 2.564 CPU in 2.564 seconds (100% CPU, 3705655 Lips)
member_max:99999996
% 1,500,009 inferences, 1.004 CPU in 1.004 seconds (100% CPU, 1494329 Lips)
rel_max:99999996
% 1,000,054 inferences, 2.649 CPU in 2.648 seconds (100% CPU, 377588 Lips)
agg_max:99999996
% 2,500,028 inferences, 1.461 CPU in 1.462 seconds (100% CPU, 1710732 Lips)
true 

with these definitions:

```erlang
:- use_module(library(clpfd)).

clpfd_max([L|Ls], Max) :- foldl([X,Y,M]>>(M #= max(X, Y)), Ls, L, Max).

slow_max(L, Max) :-
   select(Max, L, Rest), \+ (member(E, Rest), E @> Max).

member_max([H|T],M) :-
    member_max(T,N), ( \+ H@<N -> M=H ; M=N ).
member_max([M],M).

rel_max(L,M) :-
    order_by([desc(M)], member(M,L)), !.

agg_max(L,M) :-
    aggregate(max(E), member(E,L), M).

test_performance(Ps) :-
    test_performance(Ps,500 000,_).
test_performance(Ps,N_Ints,Result) :-
    list_of_random(N_Ints,1,100 000 000,Seq),
    maplist({Seq}/[P,N]>>time((call(P,Seq,N),write(P:N))),Ps,Ns),
    assertion(sort(Ns,[Result])).

list_of_random(N_Ints,L,U,RandomInts) :-
    length(RandomInts,N_Ints),
    maplist({L,U}/[Int]>>random_between(L,U,Int),RandomInts).

clpfd_max毫无疑问是最佳选择，而令我惊讶的是，slow_max/2也不错...

- CapelliC

Answer 5

虽然这个程序可能运行缓慢，但当可以时，我喜欢编写明显正确的代码。

smallest(List,Min) :- sort(List,[Min|_]).

- Bill McEnaney

---

是的，但是对于包含逻辑变量的输入列表怎么办？ - repeat

Answer 6

SWI-Prolog有min_list/2函数：

min_list(+List, -Min)
    True if Min is the smallest number in List.

它的定义在 library/lists.pl 中。

min_list([H|T], Min) :-
    min_list(T, H, Min).

min_list([], Min, Min).
min_list([H|T], Min0, Min) :-
    Min1 is min(H, Min0),
    min_list(T, Min1, Min).

- Kaarel

Answer 7

这对我来说没问题：

minimumList([X], X).        %(The minimum is the only element in the list)

minimumList([X|Q], M) :-    % We 'cut' our list to have one element, and the rest in Q
 minimumList(Q, M1),         % We call our predicate again with the smallest list Q, the minimum will be in M1
 M is min(M1, X).            % We check if our first element X is smaller than M1 as we unstack our calls

- TomaDeLosTacos

Answer 8

与andersoj类似，但使用切割而不是双重比较：

min([X], X).

min([X, Y | R], Min) :-
    X < Y, !,
    min([X | R], Min).

min([X, Y | R], Min) :-
   min([Y | R], Min).

- Adam Stelmaszczyk

Answer 9

没有“是”的解决方案。

min([],X,X).
min([H|T],M,X) :- H =< M, min(T,H,X).
min([H|T],M,X) :- M < H, min(T,M,X).
min([H|T],X) :- min(T,H,X).

- Daniel Libanori

---

min([1,1],X) 应该成功，但是失败了。 - false

Answer 10

这个代码可以正常运行，而且效率相当高。

min_in_list([M],M).    
min_in_list([H|T],X) :-
    min_in_list(T,M),
    (H < M, X = H; X = M).   

min_list(X,Y) :- min_in_list(X,Y), !.

- Neil H

---

[tag:prolog-cut] 使您的代码失去了坚定性，这意味着代码在逻辑上表现得很好，具有“恰到好处的实例化”，但在处理具有过多实例化的术语时会变得不合逻辑。这就是为什么 ?- min_in_list([1,2,3],2). 成功了 - 它本应该失败！ - repeat