matrix - 如何在 Prolog 中找到列表的最佳组合

Question

我有以下问题想要解决。

我有 2 个(或更多)矩阵； a 和 b。

每个矩阵都有列、行和值(利润)。

我想使用 prolog 从 2 个不同的矩阵中找到 2 列的组合，这将为我带来最多的正利润。

即矩阵 A 中的 ColumnX + 矩阵 B 中的 ColumnY，然后计算结果列中具有正数的值的数量。 IE。我添加同一行上的值。

我将迄今为止尝试过的代码(及其链接)放在下面，但我的函数 count_profits(ColA, ColB, P) 没有返回预期结果。以下查询应返回 P = 2，但它返回了 P = 1。

 count_profits(66,65.5,P).

现在我提供每个矩阵使用的列索引。最终我想要一个名为 best_profit(ColA, ColB) 的函数，它应该为我提供矩阵 A 中的列和矩阵 B 中的列，组合起来会产生最多数量的正结果。根据我拥有的测试数据，如果我是正确的，这应该导致 ColA = 66 和 ColB = 65.5。

https://pastebin.com/rKG8twE1

    % Data sets 
    % a(Column, Row, Profit)
    % b(Column, Row, Profit)    

    a(65, 66, -0.82).
    a(65, 65.5, -1.32).
    a(65, 65, -1.82).

    a(65.5, 66, -1.07).
    a(65.5, 65.5, -1.57).
    a(65.5, 65, -1.57).

    a(66, 66, -1.3).
    a(66, 65.5, -1.3).
    a(66, 65, -1.3).

    b(65, 66, -1).
    b(65, 65.5, -0.5).
    b(65, 65, 1.72).

    b(65.5, 66, -0.5).
    b(65.5, 65.5, 1.48).
    b(65.5, 65, 1.48).

    b(66, 66, 1.25).
    b(66, 65.5, 1.25).
    b(66, 65, 1.25).

    min_row(Row) :-
        a(Col, Row, _),
        \+ (a(_,Row2,_), Row2 < Row),!.

    max_row(Row) :-
        a(Col, Row, _),
        \+ (a(_,Row2,_), Row2 > Row),!.

    is_profit(ColA, ColB, Row, P) :-
        a(ColA, Row, Profit1),
        b(ColB, Row, Profit2),
        Profit is Profit1 + Profit2,
        ( Profit > 0 -> P is 1 ; P is 0),!.

    count_profits(ColA, ColB, Row1, P) :-
        max_row(Row),
        Row1 =:= Row,
        is_profit(ColA, ColB, Row1, P).

    count_profits(ColA, ColB, Row1, P) :-
        a(ColA,Row2,_),
        Row2 > Row1,
        count_profits(ColA, ColB, Row2, P2),
        is_profit(ColA, ColB, Row1, P1),
        P is P1+P2.

    count_profits(ColA, ColB, P) :-
        min_row(Row1),
        count_profits(ColA, ColB, Row1, P),!.

更新1:

这是我在示例序言代码中尝试使用的数据的直观表示:

Answer 1

我为您提供了一些构建 block 来解决此任务。

首先，让我们决定推理有理数。请避免使用困惑的 float ，它会给你带来无穷无尽的问题。

要在 Prolog 中推理有理数，请查看 CLP(Q)，即有理数约束求解。

就您而言，您从涉及 float 的矩阵开始。让我们首先对它们使用更方便的表示，例如:

matrix(a, [[-0.82,-1.07,-1.3],           [-1.32,-1.57,-1.3],           [-1.82,-1.57,-1.3]]).matrix(b, [[-1,-0.5,1.25],           [-0.5,1.48,1.25],           [1.72,1.48,1.25]]).

您可以使用所有解决方案谓词，例如 setof/3 和 findall/3 将您当前的演示文稿转换为这样的列表行。

正如已经提到的，我们应该首先将其转换为有理数，以消除后续步骤中的许多问题。顺便说一句，即使是您当前拥有的数字也不能保证准确表示!另外，在您的情况下，我们主要对列感兴趣，因此我们可以转置矩阵，并使用rationalize/1来获得< em>有理数列列表:

:- use_module(library(clpq)).:- use_module(library(clpfd)).to_rational(F, R) :- R is rationalize(F).rational_columns(Name, Cols) :-        matrix(Name, Rows),        transpose(Rows, Cols0),        maplist(maplist(to_rational), Cols0, Cols).

让我们看看到目前为止我们有什么:

?- rational_columns(a, Cols).Cols = [[-41 rdiv 50, -33 rdiv 25, -91 rdiv 50], [-107 rdiv 100, -157 rdiv 100, -157 rdiv 100], [-13 rdiv 10, -13 rdiv 10, -13 rdiv 10]].

继续，让我们定义添加列的含义:

column_column_plus(As, Bs, Ps) :-        maplist(addition, As, Bs, Ps).addition(A, B, Sum) :- { Sum = A + B }.

这使用 CLP(Q) 约束来定义列表的按元素添加。它可以在各个方向使用!

使用这些构建 block ，我们已经可以描述我们感兴趣的列的组合:

combination_number(A-B, N) :-        rational_columns(a, ACs),        rational_columns(b, BCs),        member(A, ACs),        member(B, BCs),        column_column_plus(A, B, Ps),        include(<(0), Ps, Gs0),        Gs0 = [_|_],        length(Gs0, N).

回溯找到解决方案:

?- combination_number(Cs, N).Cs = [-41 rdiv 50, -33 rdiv 25, -91 rdiv 50]-[-1 rdiv 2, 37 rdiv 25, 37 rdiv 25],N = 1 ;Cs = [-41 rdiv 50, -33 rdiv 25, -91 rdiv 50]-[5 rdiv 4, 5 rdiv 4, 5 rdiv 4],N = 1 ;Cs = [-107 rdiv 100, -157 rdiv 100, -157 rdiv 100]-[-1, -1 rdiv 2, 43 rdiv 25],N = 1 ;Cs = [-107 rdiv 100, -157 rdiv 100, -157 rdiv 100]-[5 rdiv 4, 5 rdiv 4, 5 rdiv 4],N = 1 ;Cs = [-13 rdiv 10, -13 rdiv 10, -13 rdiv 10]-[-1, -1 rdiv 2, 43 rdiv 25],N = 1 ;Cs = [-13 rdiv 10, -13 rdiv 10, -13 rdiv 10]-[-1 rdiv 2, 37 rdiv 25, 37 rdiv 25],N = 2 ;false.

要选择最佳组合，您可以将findall/3与keysort/2结合使用:

?- findall(N-Cs, combination_number(Cs, N), NCs0),   keysort(NCs0, NCs),   last(NCs, Best).

产量:

Best = 2-([-13 rdiv 10, -13 rdiv 10, -13 rdiv 10]-[-1 rdiv 2, 37 rdiv 25, 37 rdiv 25]).