Умножение матричной цепочки в прологе

Question

У меня есть следующее решение проблемы матричного умножения.

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

Эта программа дает мне все возможные решения.

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

Как мы видим, один из них является оптимальным. Что я хотел бы сделать, это изменить этот вариант, чтобы получить только одно решение, оптимальное.

Если кто-либо может предоставить любой указатель/предложение для его достижения, это будет действительно полезно.

Спасибо.

Answer 1

Быстрый способ сделать это было бы использовать setof/3, поскольку он сортирует в порядке возрастания:

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 будет использовать standard ordering of terms при выполнении сортировки.

Тогда запрос как:

| ?- 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