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