c# - 在尊重偏好的情况下将人员分配到建筑物？

Question

今天有 friend 问我一个关于分配问题的问题。我找到了一个非常简单的解决方案，但我觉得它可以变得更简单、更快。您的帮助将不胜感激。

问题:假设我有N个人，我需要将他们分配到M栋楼，每栋楼可以容纳K人。并非所有人都愿意和对方住在一起，所以我有一个 N*N 单元格矩阵和一个 1，表示愿意和对方住在一起的人。如果一个单元格包含 1，则表示 I 和 J 可以住在一起。显然矩阵围绕主对角线对称。

我的解决方案如下(伪代码):

int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
    int[] freePeople = findFreePeople(people);
    if(freePeople) = 0 
    {
        return people;
    }

    foreach(int person in freePeople)
    {
        for(int buildingIndex=0 to numBuildings)
        {
            if( CheckIfPersonFitsInBuilding(...) )
            {
                int[] tempPeople = people.Copy();
                tempPeople[person] = buildingIndex;
                int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
                if(result != null)
                {
                    return result;
                }
            }
        }
    }
    return null;
}

我只是介绍了使用递归的所有可能安排。我觉得这可以大大优化，我不是在谈论启发式方法，而是一种复杂性要低得多的解决方案。

1. 是否有与此类似的正式的众所周知的问题？
2. 有没有更好的算法？

我认为这可能与 stable marriage problem 有关，虽然我不确定。

Answer 1

通过从 decomposing a graph into cliques 的 NP 完全问题减少，这个问题被认为是 NP 难的(集团掩护问题)。

首先，一些术语和讨论。 clique在一个图中是一组 k 个不同的节点，这样每个节点都连接到 clique 中的每个其他节点。一个independent set图中是一组 k 个不同的节点，使得没有两个节点相互连接。如果你采用任何图 G，然后在缺少边时引入边并删除以前存在的所有边，你会得到 complement graph的原始图形。这意味着在初始图中寻找团的问题等同于在补图中寻找独立集。

之所以有趣，是因为在您描述的问题中，您得到了一张人图，其中每条边都表示“这两个人不能住在一起”。因此，您可以将您所描述的问题视为试图找到一种方法将图形分解为 k 个子图，每个子图都是一个独立的集合。如果你构造这个图的补集，你会得到所有可以放在一起的人的图。在这种情况下，您希望将该组分成 k 个都是小集团的组。

已知下面的问题是NP完全的:

Given a graph and a number k, can you break the nodes in the graph apart into k cliques?

我们可以在多项式时间内将此问题简化为您的问题，表明您的问题是 NP-hard 问题。构造很简单——给定初始图 G 和数 k，首先构造 G 的补集。这意味着如果你可以将补集分解成 k 个独立的集合，那么原始图 G 可以分解成 k 个团(因为派系和独立集之间的二元性)。现在，将这个新图转换成一组人，每个节点一个，如果两个人的节点在原始图中连接，则不能将他们放在同一个房间里。现在，有一种方法可以将这些人分配到 k 个房子中，当且仅当 G 的补集可以分解为 k 个独立的集合，当且仅当 G 可以分解为 k 个派系。因此，已知的 NP-complete clique cover 问题可以在多项式时间内简化为您的问题，因此您的问题是 NP-hard。为了确保任何独立的集合都可以装进一个房子，只需将每个房间的最大容量设置为 n，即图中的节点数。这允许任何独立的集合被安置在任何房间。

由于您的问题是 NP 难的，因此除非 P = NP，否则不可能有多项式时间解。因此，众所周知，它没有多项式时间算法，您的回溯递归很可能是最佳解决方案。

希望这对您有所帮助!