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

Question

我有以下問題想解決。

我有2（或更多）矩陣; a和b。

每個矩陣都有列，行和值（利潤）。

我想使用prolog從2個不同的矩陣中找到2列的組合，這將給我最多的正面利潤。

I.E.矩陣A中的ColumnX +矩陣B中的ColumnY，然後計算結果列中具有正數的值的數量。 I.E.我添加在同一行上的值。

我把下面，到目前爲止，我已經嘗試的代碼（和一個鏈接），但我的功能count_profits（可樂，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：

下面是數據我想在我的樣本序言代碼工作的可視化表示：

Answer 1

我給你幾塊積木來解決這個任務。

首先，讓我們決定推理理性數字。請避免浮動 點數字，這會造成你無盡的問題。

來思考有理數序言中，檢查出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]).