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

Question

我有以下问题我想解决.

我有2个(或更多)矩阵; a和b.

每个矩阵都有列,行和值(利润).

我想用prolog找到2个不同矩阵中2列的组合,这将给我最多的正利润.

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

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

 count_profits(66,65.5,P).

现在我正在为每个要使用的矩阵提供列索引.最终我想要一个名为best_profit(C​​olA,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:

以下是我在示例prolog代码中尝试使用的数据的直观表示:

Answer 1

我给你几个构建块来解决这个任务.

首先,让我们决定推理有理数.请避免乱七八糟的浮点数,这会给你带来无穷无尽的问题.

为了推理Prolog中的有理数,请查看CLP(Q),对有理数进行约束求解.

在您的情况下,您从涉及浮点数的矩阵开始.让我们首先使用更方便的表示形式,例如:

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获取有理数列的列表:

:- 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)约束来定义列表的元素添加.它可以在所有方向使用!

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

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