0

私は Java と C# に堪能なので、Prolog でのコーディングは、まったく別の考え方のようで、これまでかなり苦労しました。

私が解決しなければならない問題は単純で、Java で 10 分で解決できました。正直なところ、ここで始めても問題があります。有権者の「投票」を表す 10 個の数字のリストが与えられます。投票は 0、-1、または 1 のいずれかです。次に、リストのリストも与えられます。各リストは候補者のリストです。各候補者のリストには名前が含まれ、その後に有権者リストと同様の 10 のスコアが続きます。

私の目標は、Voter リストを各 Candidate リストと比較し、同じ投票に基づいて最良の一致のリストを返すことです。

これは私が与えられたものです：

?- 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 = [アダムス、フォード、マディソン] が返されます。

これまでのところ、私はあまり持っていません。私はこれをどのように行うべきかを理解しようとしています。複数のメソッドが必要になるのでしょうか、それとも best_candidates メソッド内ですべて実行できるようにする必要がありますか?

エドマンドの提案に応えて、これまでのところ私が持っているものは次のとおりです。

% 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

SWIの助けを借りて実装されたソリューションを示します-Prologlibrary（aggregate）。

:- [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 に答える
1

問題の核心は、10 個の数値の 2 つのベクトルを取り、合計一致スコアを返す関数にあるようです。

まず、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ことです。つまり、最高のスコアに対応する出力変数にバインドします。繰り返しますが、この述語は、基本ケース (候補がないため、最良のケースもありません) と、一度に 1 つの候補を処理する再帰ケースを定義することにより、候補ベクトルのセットを反復処理できます。

各候補ベクトルのスコアリング

あなたが言及したように、候補ベクトルには名前とそれに続く値があります。これは、ベクトルを で簡単に分割でき[Name|Values] = V、Valuesに渡してmatch投票者ベクトルと比較できることを意味します。

BestMatchesもう1つは、名前をリストに保存することです。述語は、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.

(2 行を で埋め...ます) 次に、単純な述語を使用して最大スコアを見つけます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.

次に、次の 3 つのステップから構築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 に答える