贪婪算法实现
贪婪算法实现
提问于 2012-04-01 16:52:17
你知道谁知道你想参加聚会的人中有谁。假设“知道”是对称的:如果我认识你，你就了解我。你进一步要求每个人至少有5个新人在聚会上见面，所以没有人觉得太孤立了，每个人都应该已经认识至少5个人了。您的原始列表可能不满足这些额外的两个条件，因此您可能需要将一些人从邀请列表中删除(或者您可能根本不能有这些限制的聚会)。找到您可以邀请的n个人的最大可能子集，并满足另外两个需求。对于这个基本问题，找出一个O(n^3)算法，并解释它的顺序和逻辑。
我要求的不是答案，而是关于从哪里开始的指导。
回答 2
Stack Overflow用户
发布于 2012-04-01 18:55:28
听起来是应用图形算法的好地方。
组成一个人的图表，G。对于n用户，图中将有n节点。链接节点i和j，如果person i知道person j。
让G的第一次迭代称为G_0。通过通过G_1来获得G，并消除任何认识太多或太少人的人。(也就是说，如果指向i的链接数为< 5或> n-5，则删除person > 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 =
8Stack Overflow用户
发布于 2012-04-01 18:15:37
我假设信息的表示形式为数据结构：
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个人化“中。
排在第一位的聚会的主人。
我可能需要的一个子程序，用于algo：
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如果你在理解这封信时遇到任何困难，请告诉我。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9966249
复制相关文章
相似问题
腾讯云开发者
