一千萬個為什麽

搜索

Prolog,在列表中找到最小值

簡而言之:如何在列表中找到最小值? (感謝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]。 我需要從這裏檢索最小值並將其乘以一個數量。有人可以建議如何檢索最小值?謝謝!

最佳答案

通常使用所謂的“滯後論證”來從第一個參數索引中受益:

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 (從左側開始), 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.

轉載註明原文: Prolog,在列表中找到最小值