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

вкратце: как найти минимальное значение в списке? (спасибо за рекомендацию 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).

таким образом, 'keying findall (Z, путь (2,6, Z), L).' в прослушивателе позволяет мне получить список [3,2,2,1]. Мне нужно получить минимальное значение отсюда и умножить его на сумму. Кто-нибудь может посоветовать, как получить минимальное значение? спасибо!

Ответы

Ответ 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.

Ответ 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

Ответ 3

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

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

Ответ 4

%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

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

Ответ 5

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

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

Ответ 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).

Ответ 7

спасибо за ответы. были полезны. Я также экспериментировал с furthur и разработал этот ответ:

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

Не уверен, как оценить, насколько хорошо ответ это алгоритмически, но он работает! тем не менее, будет признательна за любую обратную связь. спасибо!

Ответ 8

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

Должен работать.

Ответ 9

Похож на andersoj, но с использованием разреза вместо двойного сравнения:

min([X], X).

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

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

Ответ 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), !.

Ответ 11

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

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

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

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

% так что думаешь!