algorithm - 如何从列表中找到从 SWI-Prolog 中的某些查询中产生最大结果的输入？

Question

我现在刚开始学习 Prolog，所以我不熟悉做大多数事情的正常方法。

基本上我有一个规则，它从输入中给出一个值:

ScoreFromInput(Input, Score) :- ...

我有一个输入列表，它们只是数字。我无法弄清楚如何找到产生最高分数的输入。

这就是我现在所拥有的，但我认为它会无限递归:

bestInput(BestInput) :-
    %#Bind the list of valid inputs
    legalInputs(ValidInputs),
    %# -1000 is a dummy score, it should get replaced on the first call to bestInputHelper
    bestInputHelper(ValidInputs,-1000,BestInput).

%#I think this rule should work if the first input in the list is not the best one
bestInputHelper([Input|RestOfInputs],BestScore,BestInput):-
    bestInputHelper(RestOfInputs,RestBestScore,BestInput),
    ScoreFromInput(Input,BestScore),
    RestBestScore > BestScore.

%#And this one if it is the best input
bestInputHelper([Input|RestOfInputs],BestScore,Input):-
    bestInputHelper(RestOfInputs,RestBestScore,_RestBestInput),
    ScoreFromInput(Input,BestScore),
    RestBestScore =< BestScore.

这就是我目前所拥有的，但我想还有一种更直接的方法可以做到这一点。任何帮助表示赞赏!谢谢!

Answer 1

尽管 Chris 不熟悉 Prolog，但他概述的方法可能比 mat 的方法更有效地找到具有最大分数的输入。无需进行二次比较，可以采用像 Chris 的方法那样线性扫描可能的输入。

此处 ma​​xScoreOfList/3 将返回有效输入列表的最佳项目 Z 和最佳分数 B 作为第三个参数。谓词将在空列表上失败。

maxScoreOfList(Z,B,[H|T]) :-
    scoreFromInput(H,S),
    maxScoreOfListAux(Z,B,H,S,T).

下面需要一个“帮助”函数，它说明了添加一些额外参数的“技巧”，以便在到达输入列表的末尾时，输出 Z 和 B 可以绑定(bind)到最佳项目和分数找到“到目前为止”:

maxScoreOfListAux(Z,B,Z,B,[ ]).
maxScoreOfListAux(Z,B,X,S,[H|T]) :-
    scoreFromInput(H,Q),
    (   S >= Q
     -> ( Y = X, R = S )
     ;  ( Y = H, R = Q )
    ),
    maxScoreOfListAux(Z,B,Y,R,T).