Prolog,在列表中找到最小值

Question

简而言之:如何在列表中找到最小值？(感谢kaarel的建议)

很长的故事:

我在amzi prolog中创建了一个加权图并给出了2个节点,我能够检索路径列表.但是,我需要在此路径中找到最小值,但无法遍历列表来执行此操作.我可以请您就如何确定清单中的最小值寻求建议吗？

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

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).

因此,"键入findall(Z,路径(2,6,Z),L)." 在听众中允许我获得一个列表[3,2,2,1].我需要从这里检索最小值并将其乘以一个数量.有人可以建议如何检索最小值？谢谢!

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).

此模式称为折叠(从左侧开始),并且foldl/4在最近的SWI版本中可用,可以将其写为:

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).

收益:

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

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

Answer 3

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

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

测试：

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

true ? 

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

X = 1 ? 

yes

您可以使用它来检查第一种情况下的值，也可以让 prolog 计算第二种情况下的值。