17

要するに:リストで最小値を見つける方法は? （アドバイスkaarelに感謝します）

長い話：

amzi プロローグで加重グラフを作成し、2 つのノードを指定すると、パスのリストを取得できます。ただし、このパスで最小値を見つける必要がありますが、これを行うためにリストをトラバースできません。リスト内の最小値を決定する方法についてアドバイスをお願いできますか?

私のコードは現在次のようになっています：

アーク(1,2)。
アーク(2,3)。
アーク(3,4)。
アーク(3,5)。
アーク(3,6)。
アーク(2,5)。
アーク(5,6)。
アーク (2,6)。

パス (X、Z、A) :-
 (arc(X,Y),path(Y,Z,A1),A は A1+1;arc(X,Z), A は 1)。

したがって、' キーイング findall(Z,path(2,6,Z),L)' です。リスナーでは、リスト [3,2,2,1] を取得できます。ここから最小値を取得し、それに金額を掛ける必要があります。誰かが最小値を取得する方法についてアドバイスできますか? ありがとう！

4

13 に答える 13

25

最初の引数のインデックス付けの恩恵を受けるために、いわゆる「遅延引数」を使用するのが一般的です。

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

あなたの例のようにintegersについて推論している場合は、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.
于 2010-10-19T07:30:43.927 に答える
16

これは私には正しいようです（ここから）。

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
于 2010-10-19T03:25:30.983 に答える
5 
%Usage: minl(List, Minimum).
minl([Only], Only).
minl([Head|Tail], Minimum) :-
    minl(Tail, TailMin),
    Minimum is min(Head, TailMin).

2 番目のルールは再帰を行います。英語では、「テールの最小値を取得し、最小値をそれとヘッドの小さい方に設定します」。最初のルールは、「1 つのリストの最小値がリスト内の唯一の値である」という基本ケースです。

テスト：

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

true ? 

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

X = 1 ? 

yes

これを使用して最初のケースで値をチェックするか、2 番目のケースでプロローグに値を計算させることができます。

于 2011-05-02T16:06:56.283 に答える
3

SWI-Prolog ではライブラリ(集合体)を提供しています。一般化され、パフォーマンスが向上します。

:- [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 はそれほど悪くないことがわかりました...

于 2011-12-07T11:30:03.677 に答える
2

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).
于 2010-10-19T06:26:14.643 に答える
2

これは私にとっては問題ありません：

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
于 2019-03-13T13:57:47.297 に答える
1

andersojに似ていますが、二重比較の代わりにカットを使用します。

min([X], X).

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

min([X, Y | R], Min) :-
   min([Y | R], Min).
于 2012-05-06T19:07:30.027 に答える
1

「である」のない解。

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).
于 2012-08-03T08:57:36.583 に答える
0

返信ありがとうございます。役に立ちました。私もさらに実験し、この答えを開発しました：

% if list has only 1 element, it is the smallest. also, this is base case.
min_list([X],X).

min_list([H|List],X) :-
min_list(List,X1), (H =< X1,X is H; H > X1, X is X1).

% recursively call min_list with list and value,
% if H is less than X1, X1 is H, else it is the same.

これがアルゴリズム的にどれだけ良い答えであるかを判断する方法はまだわかりませんが、うまくいきます! それにもかかわらず、フィードバックをいただければ幸いです。ありがとう！

于 2010-10-19T14:58:30.200 に答える
0

これは機能し、かなり効率的です。

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), !.
于 2016-03-08T02:01:21.547 に答える
0 
min([Second_Last, Last], Result):-
    Second_Last < Last
 -> Result = Second_Last
 ;  Result = Last, !.

min([First, Second|Rest], Result):-
    First < Second
 -> min([First|Rest], Result)
 ;  min([Second|Rest], Result).

動作するはずです。

于 2011-12-07T09:28:24.327 に答える
-1

% リスト内の最小値を見つける

min([Y],Y):-!.

min([H|L],H):-min(L,Z),H=<Z.

min([H|L],Z):-min(L,Z),H>=Z.

% じゃあどうしよう！

于 2013-05-18T07:41:53.930 に答える