Search code examples
prolog

In Prolog, how can I check condition B only if condition A is not satisfied?


I am trying to solve this optimization problem with Prolog. A person can only drive a car if his/her ability is higher than the car's difficulty. Additionally, if possible, each person should get one of the cars in their wishlist (favcar).

I tried doing this using the *-> operator and conditions g1, g2 as shown below, but it doesn't work. The script simply checks g1 and if it is not satisfied, as in the example below, it returns false.

If I change line 7 to favcar(a, [1,3]), for example, it works. But I also wanted to cover cases in which that is not possible.

car(1).
car(2).
car(3).
person(a).
person(b).
person(c).
favcar(a, [1]).
favcar(b, [1]).
favcar(c, [1,2]).
ability(a,0).
ability(b,1).
ability(c,2).
diff(1,0).
diff(3,0).
diff(2,1).
candrive(X,Y) :- ability(X,H1),diff(Y,H2),person(X),car(Y),H1>=H2.
wants(X,Y) :- favcar(X, L), member(Y,L), person(X),car(Y).
g1(X,Y) :- person(X),car(Y),candrive(X,Y),wants(X,Y).
g2(X,Y) :- person(X),car(Y),candrive(X,Y).
gen(X,Y) :- g1(X,Y) *-> g1(X,Y); g2(X,Y).
unique([]).
unique([X|Xs]) :-
    \+ memberchk(X, Xs),
    unique(Xs).
solve(C1,C2,C3) :- gen(a,C1),gen(b,C2),gen(c,C3),unique([C1,C2,C3]).


Solution

  • The construct ( Condition *-> Action ; Else ) implements a soft-cut. The problem is that, when Condition succeeds at least once, Else is never executed. This can be observed with the following query:

    ?- (g1(X,Y) *-> g1(X,Y) ; g2(X,Y)).
    X = a,
    Y = 1 ;
    X = b,
    Y = 1 ;
    X = c,
    Y = 1 ;
    X = c,
    Y = 2 ;
    false.
    

    According to predicate g1/2, car 1 should be assigned to both a and b. However, as this is not allowed by predicate unique/1, no solution is found.

    So, a possible solution would be to define a predicate to assign a car to each person (according to candrive/2) and to compute how many of them were satisfied (according to wants/2). The use of the predicate select/3 guarantees that a same car will not be assigned to different people.

    assignment([], _, [], 0).
    assignment([P|Ps], Cs, [P-C|A], N) :-
        candrive(P, C),
        select(C, Cs, R),
        assignment(Ps, R, A, N0),
        (   wants(P, C)
        ->  N is N0 + 1      % satisfied!
        ;   N is N0 ).
    

    Feasible solutions:

    ?- assignment([a,b,c], [1,2,3], A,  N).
    A = [a-1, b-3, c-2],
    N = 2 ;
    A = [a-1, b-2, c-3],
    N = 1 ;
    A = [a-3, b-1, c-2],
    N = 2 ;
    A = [a-3, b-2, c-1],
    N = 1 ;
    false.
    

    Finally, using this predicate, an optimal assignment can be obtained as follows:

    best_assignment(A) :-
        findall(P, person(P), Ps),
        findall(C, car(C), Cs),
        assignment(Ps, Cs, A, W),         % A is a solution and
        \+ ( assignment(Ps, Cs, _, W1),   % there is no better one!
             W1 > W ).
    

    Optimal solutions:

    ?- best_assignment(A).
    A = [a-1, b-3, c-2] ;
    A = [a-3, b-1, c-2] ;
    false.