0

我精通 Java 和 C#，因此在 Prolog 中进行编码对我来说是一项相当艰巨的任务，因为它似乎是一种完全不同的思维方式。

我需要解决的问题很简单，用 Java 十分钟就能搞定。老实说，即使从这里开始，我也遇到了麻烦。我得到了代表选民“投票”的十个数字的列表。投票是 0、-1 或 1。然后我还会得到一个列表列表，每个列表都是候选人的列表。每个候选人的名单包括一个名字，后面跟着十个与选民名单类似的分数。

我的目标是然后将选民名单与每个候选人名单进行比较，并根据相同的选票返回最佳匹配名单。

这是给我的：

?- best_candidates(
    [           0,   0,   0,   1,   1,   1,  -1,  -1,  -1,   1],
    [[adams     1,   1,   1,   1,   1,   1,   1,   1,   1,   1],
     [grant    -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1],
     [polk      1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1],
     [jackson   1,   0,   1,   0,   1,   0,   1,   0,   1,   0],
     [taft      0,  -1,   0,  -1,   0,  -1,   0,  -1,   0,  -1],
     [ford      1,   1,   1,   1,   0,   0,   0,   0,   0,   0],
     [madison   0,   0,   0,   1,  -1,   0,   0,  -1,   1,   1]],
    BestMatches).

这应该返回 BestMatches = [adams, Ford, madison]。

到目前为止，我没有太多。我只是想弄清楚我应该怎么做。我是否需要多种方法，或者我应该能够在 best_candidates 方法中完成这一切？

针对 Edmund 的建议，这是我目前所拥有的：

% match V1 and V2 and unify M with the match score
% match(V1, V2, M)
match([], [], 0).
match([H1|T1], [H2|T2], M) :-
    match_single_entry(H1, H2, M1),
    match(T1, T2, M2), 
    M is M1+M2.

% match_single_entry(I, J, M)
match_single_entry(X, Y, M) :-
    X =\= 0,
    Y =\= 0,
    I =:= J, 
    M is 1.
4

2 回答 2

1

似乎问题的症结在于一个函数，它接受两个 10 个数字的向量，并返回一个总匹配分数。

首先是 Prolog 没有功能；它有谓词。但是您可以通过提供可以绑定到“函数”输出的变量，轻松地将函数概念转换为谓词概念：

% Match V1 and V2, and unify M with the match score.
match(V1, V2, M) :- ...

目前尚不清楚向量是如何匹配的（但我认为这是相同条目的数量？还是每对条目之间的绝对差异之和？）。但是这个谓词可能会用一个基本情况（对于长度为 0 的列表）和一个为每个列表的头部计算它的一般情况以及列表尾部的递归来定义。

match([], [], 0).  % I'm assuming the match score for empty lists is 0.
match([H1|T1], [H2|T2], M) :-
    match_single_entry(H1, H2, M1),  % Somehow compute the score for two single entries.
    match(T1, T2, M2),  % Recurse on the tails.
    M is M1+M2.  % Combine the two scores and bind to the output variable M.

我没有match_single_entry定义。一旦你定义了它，你应该练习match使用各种候选人的向量来对抗选民的向量：

% Let's try getting the match score for adams:
?- match([1,1,1,1,1,1,1,1,1,1], [0,0,0,1,1,1,-1,-1,-1,1], AdamsScore).

AdamsScore = 3 ;

No

下一个挑战是编写另一个谓词best_candidates，该谓词采用选民的向量加上一组候选向量，对每个向量进行评分，然后返回 - 即绑定到对应于BestMatches得分最高的输出变量。同样，这个谓词可以通过定义一个基本案例（没有候选者，因此没有最佳案例）和一个一次处理一个候选者的递归案例来迭代候选向量集。

对每个候选向量进行评分

正如您所提到的，候选向量的名称后跟值。这意味着向量可以很容易地被 分割[Name|Values] = V，并且Values可以被传递以match与选民向量进行比较。

另一件事是将名称存储在BestMatches列表中。谓词必须对best_candidates每个候选向量进行评分，将这些分数保存在某个地方，然后它必须找到最佳分数，然后它必须遍历原始候选名称并添加与最佳分数一样好的那些。

建议添加一个谓词来完成第一部分：

% Score all vectors, returning a list of scores.
% score_vectors(VoterVector, AllVectors, AllScores)
score_vectors(V, [], []).
score_vectors(V, [H|T], [SH, ST]) :-
    ... score V against H, matching the result against SH.
    ... recurse on T and ST.

（用 填写两行...）然后使用一个简单的谓词从中找到最大分数AllScores（或者可能有一个内置的谓词来做到这一点）。

然后制作另一个谓词，它遍历所有向量和分数，并选择满足最佳分数的那些：

% Pick best candidates.
% pick_best(AllVectors, AllScores, BestScore, BestNames).
pick_best([], [], BS, []).
pick_best([H|T], [SH|ST], BS, [Name|NT]) :-
    H = [Name|Values],
    SH >= BS.
pick_best([H|T], [SH|ST], BS, NT) :-
    H = [Name|Values],
    SH < BS.

然后构建best_candidates出这三个步骤：

best_candidates(VoterVector, CandidateVectors, BestNames) :-
    score_vectors(VoterVector, CandidateVectors, Scores),
    maximum(Scores, BestScore),
    pick_best(CandidateVectors, Scores, BestScore, BestNames).
于 2012-11-19T02:03:39.060 回答
1

我将展示一个借助 SWI-Prolog 库（聚合）实现的解决方案。

:- [library(aggregate)].

best_candidates(Votes, Candidates, Best) :-
    maplist(count_matched(Votes), Candidates, NamesCounted),
    keysort(NamesCounted, BestDown),
    reverse(BestDown, Best).

count_matched(Votes, [Name|ThisVotes], MatchCount-Name) :-
    aggregate_all(sum(V * T),
        ( nth1(I, Votes, V),
          nth1(I, ThisVotes, T)
        ), MatchCount).

test(BestMatches) :-
    best_candidates(
         [           0,   0,   0,   1,   1,   1,  -1,  -1,  -1,   1],
        [[adams   ,  1,   1,   1,   1,   1,   1,   1,   1,   1,   1],
         [grant   , -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1],
         [polk    ,  1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1],
         [jackson ,  1,   0,   1,   0,   1,   0,   1,   0,   1,   0],
         [taft    ,  0,  -1,   0,  -1,   0,  -1,   0,  -1,   0,  -1],
         [ford    ,  1,   1,   1,   1,   0,   0,   0,   0,   0,   0],
         [madison ,  0,   0,   0,   1,  -1,   0,   0,  -1,   1,   1]],
        BestMatches),
    BestMatches = [_-A, _-B, _-C|_],
    writeln([A, B, C]).

测试输出：

?- test(L).
[madison,ford,adams]
L = [1-madison, 1-ford, 1-adams, -1-jackson, -1-grant, -2-taft, -3-polk].
于 2012-11-19T08:37:07.440 回答