Matrix chain Multiplication in prolog

Question

I have the following solution to matrix multiplication problem.

matMul([X], os(0, X)).
matMul(L, os(A, m(a, d(D1, D2)))) :-
     append([L1|L1s], [L2|L2s], L),
     matMul([L1|L1s], os(A1, m(_, d(D1, C1)))),
     matMul([L2|L2s], os(A2, m(_, d(_, D2)))),
     A is A1 + A2 + (D1 * C1 * D2).

This program gives me all the possible solutions.

?- matMul([m(a,d(5,4)), m(a,d(4,6)), m(a,d(6,2)), m(a,d(2,7))], A).
A = os(392, m(a, d(5, 7))) ;
A = os(244, m(a, d(5, 7))) ;
A = os(414, m(a, d(5, 7))) ;
**A = os(158, m(a, d(5, 7))) ;**
A = os(250, m(a, d(5, 7))) ;
false.

As we can see, one of them is optimal one. What I would like to do is modify this one to get just one solution the optimal one.

If anyone can provide any pointer/suggestion to achieve it, that would be really helpful.

Thanks.

lurker lurker · Accepted Answer · 2015-03-17T12:54:42

The quick way to do this would be to use setof/3 since it sorts in ascending order:

optimum_solution(Matrix, A) :-
    setof(os(X,M), matMul(Matrix, os(X,M)), S),
    S = [A|_].   % Select the first element, which has lowest X

setof/3 will use a standard ordering of terms when doing the sort.

Then query it as:

| ?- optimum_solution([m(a,d(5,4)), m(a,d(4,6)), m(a,d(6,2)), m(a,d(2,7))], A).

A = os(158,m(a,d(5,7)))

yes

Matrix chain Multiplication in prolog

1 Answers