贪心算法实现

Question

您想邀请n个人参加聚会，但是您不知道这些人之间的相互认识情况。假设“认识”是对称的：如果我认识你，你也认识我。您还有进一步的要求，即每个人在聚会上至少要认识5个新人，同时为了避免任何人感到孤立，每个人应该已经认识聚会上的至少5个人。您原来的名单可能无法满足这两个额外的条件，因此您可能需要从邀请名单中剔除一些人（或者根本无法举办聚会）。找到一个最大的可能邀请的人数，并满足另外两个要求。对于基本问题，找到一个O(n^3)的算法并解释它的顺序和逻辑。

我不要答案，只是想知道从哪里开始。

- Peter Weglarz

---

第一步始终是绘制（或生成）几个图形（比如10-20个顶点），并尝试手动找到解决方案。这给你一个大致的想法，任务是什么，难点在哪里。 - biziclop

算法需要输入什么？ - Tejas Patil

Answer 1

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

将人们形成一个图G。对于n个人，图中将有n个节点。如果人i认识人j，则连接节点i和j。

让G的第一次迭代称为G0。通过G进行一次遍历，消除任何认识过多或过少人的人。 （也就是说，如果与i相连的链接数小于5或大于n-5，则消除人i。）

重复此过程，获得G2、G3等最多n（左右）次迭代，获得Gn。剩下在此图中的人就是你应该邀请的人。

每个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

- Li-aung Yip

---

有趣的是，我一开始用Python写这个程序，但后来转用MATLAB。用MATLAB写起来要容易得多。 - Li-aung Yip

非常好，解释清晰。一个小改进是在交替传递中消除每种类型的人。第一次可以消除认识人太少的人，但同样可以是“过于友好”的人；两者都无法参加，它们的消除可能会导致一些其他人的状态发生变化。在我看来，在算法中这并不是必要的，但可能会使它更容易看到大O符号。只是一个小想法。 - gbulmer

@gbulmer：感谢您的赞美（我以易读的代码为傲）。关于您的建议：我考虑过，但决定它需要跟踪额外的状态，所以我选择了最简单的解决方案。您还会注意到我没有进行任何优化-在这个例子中，第一次通过后解决方案就已经完成了。我本可以检测到并停止，但再次增加了额外的逻辑。;) - Li-aung Yip

Answer 2

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

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 individuals[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

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

- Tejas Patil

---

谁给这个点踩了：我很好奇为什么。这个算法基本上是正确的（即使由于Java而有点冗长）。 - Li-aung Yip