algorithm - 貪欲なアルゴリズムの実装

Question

n 人の中で誰がパーティに来てほしいか知っています。「知っている」が対称であると仮定します。私があなたを知っている場合、あなたは私を知っています。さらに、各人がパーティーで少なくとも 5 人の新しい人に会う必要があるという要件を作成します。また、誰も孤立していると感じないように、各人はパーティーで少なくとも 5 人を既に知っている必要があります。元のリストは、これらの追加の 2 つの条件を満たさない可能性があるため、招待リストから一部の人を削除する必要がある場合があります (または、これらの制限によりパーティーをまったく開催できない場合があります)。招待して他の 2 つの要件を満たすことができる n 人の可能な最大のサブセットを見つけます。基本的な問題について、O(n^3) アルゴリズムを見つけ、その順序と論理を説明します。

答えを求めるのではなく、どこから始めるべきかについてのガイダンスを求めます。

score 6 · Accepted Answer

グラフアルゴリズムを適用するのに適した場所のように思えます。

人のグラフを作成しGます。n人の場合、グラフにノードnがあります。iノードとjif person iknow personをリンクしjます。

の最初の繰り返しをとしGますG_0。G_1パススルーを行うことで入手し、G知っている人が多すぎたり少なすぎたりする人を排除します。(つまり、iへのリンク数iが< 5またはの場合、 person を除外します> n-5。)

を取得するプロセスを繰り返してG_2、G_3最大n(またはその程度) の反復まで、を取得しG_nます。このグラフに残っている人は、招待する必要がある人です。

パスごとに、他の人に対する人をnチェックする必要があるため、アルゴリズムは.nnO(n^3)

これを実現するための MATLAB コード (要求されませんでしたが、興味深いと思い、とにかく書きました):

% number of people on original list
N = 10

% number of connections to (attempt) to generate
% may include self-links (i,i) or duplicates
M = 40

% threshold for "too few" friends
p = 3

% threshold for "too many" friends
q = 3

% Generate connections at random
G = zeros(N);
for k = 1:M
    i = randi(N);
    j = randi(N);
    G(i,j) = 1;
    G(j,i) = 1;
end

% define people to not be their own friends
for i = 1:N
    G(i,i) = 0;
end

% make a copy for future comparison to final G
G_orig = G

% '1' means invited, '0' means not invited
invited = ones(1,N);

% make N passes over graph
for k = 1:N
    % number of people still on the candidate list
    n = sum(invited); 
    % inspect the i'th person
    for i = 1:N 
        people_known = sum(G(i,:));
        if invited(i) == 1 && ((people_known < p) || (people_known > n-q))
            fprintf('Person %i was eliminated. (He knew %i of the %i invitees.)\n',i,people_known,n);
            invited(i) = 0;
            G(i,:) = zeros(1,N);
            G(:,i) = zeros(1,N);
        end
    end
end

fprintf('\n\nFinal connection graph')
G

disp 'People to invite:'
invited

disp 'Total invitees:'
n

サンプル出力 (10 人、40 接続、少なくとも 3 人を知っている必要があります、少なくとも 3 人を知っている必要はありません)

G_orig =

     0     0     1     1     0     0     0     0     1     0
     0     0     0     0     0     1     0     0     0     1
     1     0     0     1     1     1     0     0     0     1
     1     0     1     0     0     1     0     1     1     0
     0     0     1     0     0     0     1     0     1     1
     0     1     1     1     0     0     0     1     0     1
     0     0     0     0     1     0     0     0     1     0
     0     0     0     1     0     1     0     0     0     1
     1     0     0     1     1     0     1     0     0     1
     0     1     1     0     1     1     0     1     1     0

Person 2 was eliminated. (He knew 2 of the 10 invitees.)
Person 7 was eliminated. (He knew 2 of the 10 invitees.)


Final connection graph
G =

     0     0     1     1     0     0     0     0     1     0
     0     0     0     0     0     0     0     0     0     0
     1     0     0     1     1     1     0     0     0     1
     1     0     1     0     0     1     0     1     1     0
     0     0     1     0     0     0     0     0     1     1
     0     0     1     1     0     0     0     1     0     1
     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     0     1     0     0     0     1
     1     0     0     1     1     0     0     0     0     1
     0     0     1     0     1     1     0     1     1     0

People to invite:

invited =

     1     0     1     1     1     1     0     1     1     1

Total invitees:

n =

     8

score 3 · Accepted Answer

情報の表現のために次のデータ構造を想定しています。

Person
    name : string, if this is empty or null, the person isnt not invited to party
    knows: array of pointers to type Person. Indicates whom this person 'knows'
    knows_cnt : size of "knows" array

全員（ホストを含む）の詳細は、「人物個人[n]」に格納できます。

パーティーのホストが最初の位置にあります。

アルゴに必要なサブルーチン:

RemovePerson (individuals, n, i)
// removes i'th person from individuals an array of n persons

    set individuals[i].name to empty so that this person is discarded

    For j from 1 to individuals[i].knows_cnt
    // as knows is symmetric, we can get the persons' contact right away
        Person contact = individuals[i].knows[j]

        if contact.name is empty, 
            continue

        modify contact.knows to remove i'th person. 
        modify corresponding contact.knows_cnt
    end for

end RemovePerson

提案されたアルゴリズム:

change = true 
invitees = n

while [change == true]
    change = false

    for i = 2 to n do
    // start from 2 to prevent the host getting discarded due to condition #2

        if individuals[i].name is empty, 
            continue

        // condition #1,
        // check if the person knows atleast 5 people
        if individuals[i].knows_cnt < 5
            change = true 
            invitees = invitees  - 1
            RemovePerson(individuals, n, i)

        // condition #2
        // check to find out if the person will get to know 5 new people
        if (invitees - individuals[i].knows_cnt) < 5
            change = true 
            invitees = invitees  - 1
            RemovePerson(individuals, n, i)

    end for

end while   

return invitees

このアルゴリズムを理解するのが難しい場合はお知らせください。

algorithm - 貪欲なアルゴリズムの実装

2 に答える 2

Related

Reference