Пролог, найдите минимум в списке

Question

короче: как найти минимальное значение в списке?(спасибо за совет kaarel)

длинная история:

Я создал взвешенный граф в прологе amzi и, имея 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), л) «.в слушатель позволяет мне получить список [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).

Этот шаблон называется 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.

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

SWI-Prolog предлагает библиотеку (агрегат).Обобщенный и по производительности.

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

Answer 4

%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

Вы можете использовать его для проверкизначение в первом случае, или вы можете прологом вычислить значение во втором случае.

Answer 5

Это нормально для меня:

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

Answer 6

Решение без "есть".

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

Answer 7

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

Answer 8

Эта программа может быть медленной, но мне нравится писать явно правильный код, когда я могу.

наименьший (List, Min): - sort (List, [Min | _]).

Answer 9

Это работает и кажется достаточно эффективным.

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

Answer 10

% найти минимум в списке

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

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

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

%, так что подумай!