0

这是一个问题的第三次迭代，这个问题从纯粹的算法角度开始，现在已经变成了寻找我能理解的代码示例的绝望任务。

我正在尝试做的是创建一组人员列表，试图满足尽可能多的偏好。每个人都给出了一个未排名的列表，列出了他们希望分配到的列表中的前n 个其他人。它（我的程序）需要将相互请求视为比单向更具影响力，并且应该（希望）找到接近最佳解决方案的东西。

我想要某种代码示例（实际上，任何基于 C 的语言或详细的伪代码），以便我能够理解所需的算法并编写我的程序。在我的第一个问题之后，我已经确定这可能需要稳定婚姻问题的某种变体，但我无法找到伪代码或我能理解的实际语言的完整示例。

我已经问过有关算法的先前问题HERE和HERE的先前问题，但没有提出任何问题（我认为这是由于那些 SE 论坛上的用户数量极少）。现在我在这里问一个问题，希望更高的观看率加上面向编程的问题能给我一个答案。

是的，我确实意识到以前有人问过这样的问题，但没有一个既适用又得到回答。

有谁知道我该怎么做？

添加更多细节（回应评论）：我有一个人员列表。对于每个人，我都有一个他们最喜欢的其他人的列表，其中仅包括主列表中的其他人。没有列表以任何方式排序。偏好列表中的姓名意味着请求者希望与被请求的人在一起。我正在寻找一种方法来创建指定数量的组，每个组只包含我的主列表中的人。我希望分组包含首选项列表。如果他们都在他们的列表中互相请求，它应该尝试将人们放在同一组中。它还应该包含一个人（在此示例中为人 A）请求其他人（人 B）但 B 不请求 A 的请求。在这种情况下，尽管它仍应计算请求，

编辑：再次，根据要求，这是一个 JS 函数，它（希望）有助于解释我的目标：

/*
Scores a possible grouping
group would be an object, where the keys are names and the values are arrays of preferences. Ex:

    {
        "Person 1": ["Person 2"],
        "Person 2": ["Person 1"],
        "Person 3": ["Person 4"],
        "Person 4": ["Person 2"]
    }

*/
function getGroupScore(group) {
    var totalPoints = 0;

    //Add a point for each request
    for (var person in group) {
        for (var request in group[person]) {
            if(request != undefined && request.length > 0)
                totalPoints++;
        }
    }

    //Add two points for each two-way request
    for (var person in group) {
        for (var request in group[person]) {
            if (group[person][request] != undefined //String validation
                && group[person][request].length > 0 //More string validation
                && group[group[person][request]] != undefined //Array validation
                && group[group[person][request]].indexOf(person) != -1) //Check mutual request
                    totalPoints += 2;
        }
    }

    return totalPoints;
}

/*
Compares two possble groupings
*/
function compareGroups(groupA, groupB) {
    var scoreA = getGroupScore(groupA),
        scoreB = getGroupScore(groupB);

    if (scoreA > scoreB)
        return 1;
    else if (scoreA == ScoreB)
        return 0;
    else
        return -1;
}
4

1 回答 1

2

好的我一直在考虑你的问题，我想我可以给你一些方向，虽然我不能完全解决它。

首先，我将尝试重新表述您的问题，如果我错了，请纠正我。

假设有一组 P 个人，以及一个偏好表，例如：

名为 ABCD 的 4 个人的偏好：
   A B C D
 +----------+
一个| XX |
乙| X |
C| XX |
D| X |
 +----------+

在此示例中，“A”更喜欢“C”，“B”更喜欢“D”等。对角线是否更喜欢自己将变得无关紧要。

现在你的问题是将 P 人分成 G 个大小为 N 的不同集合，假设 P=G*N。对于 N=2 示例：

  生物多样性公约
 +-------|
一个|xx| |
C| x| x|
 +---+----
乙| | x|
D| |x |
 +---+---+
这里的分区是 {A, C} 和 {B, D}

满足划分的程度是对角块中X的数量之和，在上面的例子中是3+2=5。

AFAIK，与您要解决的问题最相似的问题是构建一个块对角矩阵，或者尽可能接近一个。在您的情况下，对角线块之外的值不会对您不利。

如果你蛮力解决问题，那么你有 P!/N! 要检查的分区。对于较小的 P 值和较大的 N 值，这可能值得直接实施，尽管在 JS 中这样做会受到伤害。如果您的解决方案必须是最佳结果，那么您可能不得不求助于这样的方法。

如果您可以允许“相当不错”的解决方案，那么随机方法可能会接近。只需进行贪婪的重新排列，直到重新排列不再有帮助，然后重复该过程几次。

我还在另一个论坛上找到了这个帖子，这可能会对你有所帮助。与此相关的大多数问题都假设存在满足每个偏好的解决方案，这归结为广度优先搜索。显然，如果这是真的，那么结果将是您的最佳解决方案，但由于一般情况下并非如此，您可能需要做一些繁重的研究来修改已知的算法。

最美好的祝愿~

于 2013-09-26T03:12:08.743 回答