8

你知道谁知道你想参加聚会的 n 个人中的谁。假设“知道”是对称的：如果我认识你，你就认识我。你提出了进一步的要求，你希望每个人至少有 5 个新人在聚会上见面，而且，没有人会感到太孤立，每个人应该已经认识至少 5 个聚会上的人。您的原始列表可能不满足这两个额外的条件，因此您可能需要从邀请列表中删除一些人（或者您可能根本无法在这些限制下举办派对）。从您可以邀请的 n 个人中找出一个最大可能的子集，并满足其他两个要求。对于基本问题，找到一个 O(n^3) 算法并解释其顺序和逻辑。

我要求的不是答案，而是从哪里开始的指导。

4

2 回答 2

6

听起来是应用图算法的好地方。

形成一个人的图表，G。对于n人来说，图中会有n节点。链接节点i，j如果 personi知道 person 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
于 2012-04-01T18:55:28.620 回答
3

我假设以下数据结构用于表示信息：

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

每个人（包括主机）的详细信息可以存储在“Person individual[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

如果您在理解此算法时遇到任何困难，请告诉我。

于 2012-04-01T18:15:37.833 回答