贪心算法实现 [英] Greedy Algorithm Implementation
问题描述
您知道谁知道谁中n个人，你想都来参加一个聚会。假设知道是对称的：如果我知道你，你认识我。你让你想每个人至少有5个新的人，以满足在党进一步的要求，而且，所以没有人感觉太孤立的，每个人都应该已经知道至少有5人在党。您的原始清单可能无法满足这些额外的两个条件，所以你可能需要消除一些人的邀请名单（也许你不能有一个党在所有这些限制）。找了N人，你可以邀请和满足另外两个要求的最大可能的子集。对于基本的问题，找到一个为O（n ^ 3）算法并解释其秩序和它的逻辑。
You know who knows who among n people that you would like to have come to a party. Assume "knows" is symmetric: If I know you, you know me. You make further requirements that you want each person to have at least 5 new people to meet at the party, and also, so nobody feels too isolated, each person should already know at least 5 people at the party. Your original list may not satisfy these extra two conditions, so you may need to eliminate some people from the invitation list (or maybe you cannot have a party at all with these restrictions). Find a largest possible subset of the n people that you could invite and satisfy the the other two requirements. For the basic problem, find an O(n^3) algorithm and explain its order and its logic.
我不问的答案，但就从哪里开始指导。
I ask not for the answer, but for guidance on where to start.
推荐答案
听起来像是应用的图形算法的好地方。
Sounds like a good place to apply a graph algorithm.
形式的人的图表， N 人会有 N 图中的节点。链接节点我和Ĵ如果人我知道的人Ĵ。
Form a graph of people, G. For n people there will be n nodes in the graph. Link nodes i and j if person i knows person j.
让 G_0 。获取 G_1 通过我如果链接数我是小于5 或＆GT; N-5 ）
Let the first iteration of G be called G_0. Obtain G_1 by making a pass through G and eliminate any person who knows too many or too few people. (That is, eliminate person i if the number of links to i is < 5 or > n-5.)
重复上述过程，获得 G_2 ， G_3 最多正（左右）的迭代，获得 G_N 。留在这个图中的人是人，你应该邀请。
Repeat the process, obtaining G_2, G_3 up to a maximum of n (or so) iterations, obtaining G_n. The people remaining in this graph are the people you should invite.
每个 N 通过要求 N 人对证 N 其他人，所以算法是为O（n ^ 3）。
Each of the n passes requires a check of n people against n other people, so the algorithm is O(n^3).
MATLAB code来完成这个（你没有问，但我觉得这很有趣，反正写的）：
MATLAB code to accomplish this (you didn't ask for it, but I thought it was interesting and wrote it anyway):
% 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人）
Sample output (10 people, 40 connections, must know at least 3 people, must not know at least 3 people)
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
这篇关于贪心算法实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
