序言中的矩阵链乘法

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.

正如我们所见，其中之一是最优的。我想做的是修改这个，只得到一个最佳解决方案。

如果有人可以提供任何 pointer/suggestion 来实现它，那将非常有帮助。

谢谢。

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

序言中的矩阵链乘法

Matrix chain Multiplication in prolog

prolog