Minimum Value of a Predicate?

Appeared in Volume 10/2, May 1997

Keywords: minimum.

mslamm@pluto.cc.huji.ac.il
Zvi Lamm
4th January, 1997

I want to write a predicate which will produce the minimal X for which p(a,b,X) is true.

nick@maproom.demon.co.uk
Nick Wedd
5th January, 1997

How about:

dis_min( X, Y, Z ) :-
  dis( X, Y, Z ),
  not((
        dis( X, Y, Other ),
        Other < Z
     )).

This is horribly inefficient, but might work.

John Fletcher
john.fletcher@dial.pipex.com
5th January 1997

The above is code is 'quadratic': it finds the 'N' solutions of dis/3 'N' times!.

To find the minimum value more efficiently we can collect every value, and then take the minimum of the collection. The following code should work for any non-deterministic generator supplied as Goal:

minimum_value( Value, Goal, MinimumValue ):-
    findall( Value, Goal, Values ),
    minimum( Values, MinimumValue ).

findall/3 should be a built-in predicate, and you probably have code for minimum/2.

So, given the example above:

dis_min( X, Y, Z ) :-
    minimum_value( Value, dis(X, Y, Value), Z ).

rwab1@cl.cam.ac.uk
Ralph Becket
6th January 1997

Or even...

min_dis(X, Y, Z) :-
    findall(D, dis(X, Y, D), Ds),
    sort(Ds, [Z | _]).

odin@cs.uq.oz.au
Dan
6th January 1997

My "(don't try this)" solution:

min_dis(X, Y, Z) :-
    setof(D, dis(X, Y, D), [Z|_]).

ok@goanna.cs.rmit.edu.au
Richard A. O'Keefe
7th January 1997

% np
NU-Prolog 1.6.0
1?- man min.
min(Term, Formula, Result)

Declaratively: same as solutions(Term, Formula, Set), minimum(Set, Result), where minimum/2 finds the minimum element of Set.

The scope of variables in Term is the call to min/3. Result is the minimum (via the non-logical standard ordering) instantiation of Term by Formula.

Operationally: min/3 delays until the global variables in Formula are ground. Each instantiation of Term may contain local variables (this is non-logical).

Or, if you have Quintus Prolog, look up library(aggregate):
aggregate(min(Term), Formula, Result)

It does pretty much the same things.

The classical method is simply:

?- bagof(X, Formula, Xs),
   min(Xs, Result)

where:

min([X|Xs], Min) :-
    min_1(Xs, X, Min).

min_1([], Min, Min)
min_1([X|Xs], Min0, Min) :-
    ( X @< Min0 -> Min1 = X ; Min1 = Min0 ),
    min_1(Xs, Min1, Min).

Assume that the cost of finding all the solutions is BIG, and that the number of solutions is N, and that your Formula has no free variables other than X, and that you have a reasonably smart bagof/3, then this costs:

O(BIG + N)

time and O(N) space. If the Formula has free variables, then there is an extra O(N.lgN) to consider.

The classic method of doing this without setof is

min_p(A, B, Min_X) :-
    once((
        p(A, B, Min_X),
        \+ ( p(A, B, Y), Y @< Min_X )
    )),

This finds each solution, and for each solution finds each solution again to see if it is smaller, and stops as soon as it finds a minimal solution. The worst case cost is:

O(BIG * BIG + N * N)

with the first bit coming from the calls to p/3 and the second bit coming from @< .

Ralph Becket wrote:
min_dis(X, Y, Z) :- findall(D, dis(X, Y, D), Ds), sort(Ds, [Z | _]).

This has O(BIG + N.lgN) cost thanks to the sort. Using bagof/3 or findall/3, followed by min/3 has O(BIG + N) cost, which is an obvious improvement if N is non-trivial.

Dan writes:
min_dis(X, Y, Z) :- setof(D, dis(X, Y, D), [Z|_]).

This too has O(BIG + N.lgN) cost, because of the internal sort. There are times not to use setof/3, and this is one of them.

Here is some simple code that finds the minimum by using the same technique as findall:

find_min(X, Query) :-
    asserta('find min'(_)),
    (   call(Query),
         'find min update'(X),
         fail
    ;    retract('find min'(Y))
    ),
    !,
    nonvar(Y),
    X = Y.

find min update'(X) :-
    retract('find min'(Y)),
    (  nonvar(Y), Y < X -> Z = Y ; Z = X ),
    !,
    asserta('find min'(Z)).

Indeed, one reason that library(aggregate) exists in Quintus Prolog is that I intended to do something very like this, only more efficiently. I abandoned that plan when I realised how very limited it is; just like findall/3, it cannot solve for other free variables in the Query.

Another issue is whether there is only one minimum or more. In typical databasey stuff, there may be a different minimum for each binding for the free variables of the query.

aggregate(min(X), p(X, Y), Min_X)    % Quintus Prolog
min(X, p(X, Y), Min_X)               % NU Prolog

both enumerate a set of {Y, Min_X} bindings.

anewman@epidigm.geg.mot.com
M. Alan Newman
7th January 1997

Richard A. O'Keefe wrote:
'find min update'(X) :- ...

My version of 'find min update'/1' avoids uninstantiated query results, and improves its efficiency by avoiding the retraction and reassertion of an unchanged 'find min'/1 value. However, it is less efficient if the query results occur in sorted order.

'find min update'(X) :-
    var(X) , !
    ;
         'find min'(Y) , Y =< X , !
    ;
         retract('find min'(_)) ,
         asserta('find min'(X)) .