Prolog, finden mindestens in einer Liste

kurz: Wie finden Sie min Wert in einer Liste? (vielen Dank für die Beratung kaarel)

lange Geschichte:

Habe ich einen gewichteten Graphen in Amzis prolog und 2 Knoten, ich bin in der Lage, zum abrufen einer Liste von Pfaden. Ich muss jedoch finden Sie den minimalen Wert in diesem Pfad aber nicht in der Lage bin zum Durchlaufen der Liste, um dies zu tun. Kann ich bitte suchen Sie Ihren Rat auf wie um zu bestimmen, die minimalen Wert in der Liste?

mein code sieht derzeit ungefähr so aus:

Bogen(1,2). 
arc(2,3). 
arc(3,4). 
arc(3,5). 
arc(3,6). 
arc(2,5). 
arc(5,6). 
arc(2,6). 

Pfad(X,Z,A) :- 
(arc(X,Y),Pfad(Y,Z,A1),A is A1+1;arc(X,Z), A ist 1).

so, "keying" - Funktion findall(Z), Pfad(2,6,Z),L).' im Hörer ermöglicht es mir, Sie zu erreichen, Sie auf eine Liste [3,2,2,1].
Ich brauche zum abrufen der Mindestwert von hier aus und multiplizieren Sie mit einem Betrag. Kann mir bitte jemand raten, wie das abrufen der minimal-Wert? danke!

Bitte ersetzen Sie den text Ihrer Frage mit einem Satz, "gewusst Wie: bestimmen der kleinsten Zahl in einer Liste?" 😉

InformationsquelleAutor Roy | 2010-10-19

  1. 18

    Ist es üblich, eine so genannte "verzögerte argument" zum Wohle von first-argument-indexing:

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

    Dieses Muster heißt ein Falten (von Links), und foldl/4 zur Verfügung, das in den letzten SWI-Versionen, können Sie dies schreiben als:

    list_min([L|Ls], Min) :- foldl(num_num_min, Ls, L, Min).

num_num_min(X, Y, Min) :- Min is min(X, Y).

    Aber feststellen, dass diese nicht verwendet werden, in alle Richtungen, zum Beispiel:

    ?- list_min([A,B], 5).
is/2: Arguments are not sufficiently instantiated

    Wenn Sie die Argumentation über Ganzzahlen, wie scheint der Fall in deinem Beispiel, daher empfehle ich Sie verwenden CLP(FD) constraints natürlich verallgemeinern das Prädikat. Statt (is)/2 einfach (#=)/2 und profitieren Sie von einer mehr deklarative Lösung:

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

    Dies kann verwendet werden, als eine echte Beziehung, die funktioniert in alle Richtungen, zum Beispiel:

    ?- list_min([A,B], 5).

    nachgeben:

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

    InformationsquelleAutor mat

  2. 13

    Das sieht mir Recht sein (von hier aus).

    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
    Dank andersoj. Ich sah wirklich diesen code während der online-Suche vor dem Absenden meiner qn hier. Irgendwie schaffte ich es nicht verstehen, jetzt weiß ich, danke!
    Es ist schon Jahre da ich gedacht habe, im Prolog, aber ich vermute, @Matte hat die Lesbarkeit Rand, an was ich gepostet...
    Das problem mit deiner Lösung ist auch, dass Sie vergleichen Sie H und K zweimal, die min-Funktion wahrscheinlich nicht tun...

    InformationsquelleAutor andersoj

  3. 3

    SWI-Prolog bietet Bibliothek(aggregieren). Generalisierte und Leistung Weise.

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

    InformationsquelleAutor CapelliC

  4. 2

    Lösung ohne "ist".

    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).
    min([1,1],X). erfolgreich sein sollte, aber es funktioniert nicht.
    Vielen Dank, jetzt funktioniert es.

    InformationsquelleAutor Daniel Libanori

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

    Die zweite Regel gilt die Rekursion, in Englisch "erhalten Sie den kleinsten Wert in den Schwanz, und die Mindestanforderungen festzulegen, um die kleineren und den Kopf". Die erste Regel ist die Basis-Fall", der Minimalwert einer Liste mit einer, ist nur der Wert in der Liste".

    Test:

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

true ? 

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

X = 1 ? 

yes

    Können Sie es verwenden, um zu überprüfen, ein Wert in dem ersten Fall, oder Sie können prolog berechnen Sie den Wert des zweiten Fall.

    InformationsquelleAutor Joe Flynn

  6. 1

    SWI-Prolog hat min_list/2:

    min_list(+List, -Min)
    True if Min is the smallest number in List.

    Seine definition ist in 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).

    InformationsquelleAutor Kaarel

  7. 0

    Ähnlich andersoj, aber mit einem Schnitt statt Doppel-Vergleich:

    min([X], X).

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

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

    InformationsquelleAutor Adam Stelmaszczyk

  8. 0

    danke für die Antworten. nützlich gewesen. Ich experimentierte auch furthur und entwickelt diese Antwort:

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

    Nicht sicher, wie Sie zu beurteilen, wie gut eine Antwort dies ist algorithmisch noch nicht, aber es funktioniert! würde schätzen jedes feedback dennoch. danke!

    InformationsquelleAutor Roy

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

    Tätig werden sollte.

    InformationsquelleAutor Js Lim

  10. 0

    Das funktioniert und scheint halbwegs effizient. 

    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), !.
    prolog-cut hat Ihren code verlieren, Standhaftigkeit, was bedeutet, dass der code verhält sich logisch Klang mit "genau der richtigen Menge der Instanziierung", wird aber im logisch inkorrekt beim arbeiten mit Bedingungen, die zu viel Instanziierung. Dies ist der Grund, warum ?- min_in_list([1,2,3],2). gelingt—sollte es scheitern!

    InformationsquelleAutor Neil H

  11. -1

    % finden mindestens in einer Liste

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

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

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

    % so whattaya denken!

    Es mag elegant auf den ersten Blick - aber es ist leider nicht deterministisch, und kann sogar Rendite mehr Lösungen, als es Elemente in der Liste. Versuchen Sie es zum Beispiel: ?- min([1,1,1,1], Min)., das ergibt 8 Lösungen. Oder probieren Sie ?- numlist(1, 1000, Ls), min(Ls, Min). in SWI-Prolog ein, und drücken Sie PLATZ für weitere Lösungen nachdem Sie strahlt Min = 1 und bereit sein, zu warten. Auch, es ist nicht tail-rekursiv, und somit weniger geeignet für lange Listen: Versuchen Sie es zum Beispiel ?- numlist(1, 10_000_000, Ls), min(Ls, Min)., das ergibt einen lokalen stack-überlauf während andere Versionen, die hier gepostet nicht.

    InformationsquelleAutor MZee

Schreibe einen Kommentar