Реализация жадного алгоритма

Звучит как хорошее место для применения алгоритма графа.

Сформируйте граф людей, G. Для n человек в графе будет n узлов. Соедините узлы i и j, если человек i знает человека j.

Пусть первая итерация G будет называться G_0. Получите G_1, пройдя через G, и устраните любого, кто знает слишком много или слишком мало людей. (То есть исключить человека i, если количество ссылок на i равно < 5 или > n-5.)

Повторите процесс, получив G_2, G_3 до максимум n (или около того) итераций, получив G_n. Люди, оставшиеся на этом графике, — это люди, которых вы должны пригласить.

Каждый из n проходов требует проверки n людей против n других людей, поэтому алгоритм O(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

Я предполагаю следующую структуру данных для представления информации:

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

Дайте мне знать, если у вас возникнут трудности с пониманием этого алгоритма.