有一个朋友今天问我一个问题有关的分配问题。我发现了一个很简单的解决办法，但我觉得它可以更简单，更快捷。 您的帮助将是AP preciated。

A friend asked me a question today about an assignment problem. I found a quite straightforward solution, but I feel that it can be made simpler and faster. Your help would be appreciated.

问题： 假设我的 N 的人，我需要将其分配到的 M 建筑，每栋建筑可容纳的 K 的人。并非所有的人都愿意住对方，所以我有N个* N单元的矩阵和1这标志着愿意忍受彼此的人。如果单元格中包含1就意味着我和J可以住在一起。显然基质是围绕主对角线对称。

The problem: Assuming that I have N people, I need to assign them into M buildings, each building can house K people. Not all people are willing to live with each other, so i have a matrix of N*N cells and a 1 that marks the people that are willing to live with each other. If a cell contains 1 it means that I and J can live together. Obviously the matrix is symmetrical around the main diagonal.

我的解决方案如下（伪code）：

My solution is as follows (pseudo Code):

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;
}

我只是介绍如何使用递归所有可能的安排。我觉得这可能是极大的优化了，我说的不是启发式，但远较小的复杂性的解决方案。

I just cover all the possible arrangements using recursion. I feel this could be optimized greatly, and I'm not talking about heuristics but a solution with far lesser complexity.

我认为，这可能会涉及到稳定的婚姻问题，虽然我不敢肯定。

I think that this might be related to the stable marriage problem, though I'm not sure.

推荐答案

这个问题被称为是NP难通过从的分解图分成派系（中的集团覆盖问题的）。

This problem is known to be NP-hard by a reduction from the NP-complete problem of decomposing a graph into cliques (the clique cover problem).

首先，一些术语和讨论。在一个曲线A 集团是一组k个不同的节点，使得每个节点都连接到彼此节点在集团。图中的一条独立集是一组k个不同的节点这样的，没有两个节点连接到一个另一个。如果你采取任何图G，然后介绍每当边缘缺失的边缘，并删除previously存在的所有边缘，你得到的补原图的图表。这意味着，找到一个集团在初始图表的问题是等价于求一个独立的组中的补图。

First, some terminology and discussion. A clique in a graph is a set of k different nodes such that each node is connected to each other node in the clique. An independent set in the graph is a set of k different nodes such that no two nodes are connected to one another. If you take any graph G and then introduce edges whenever an edge is missing and remove all edges that previously existed, you get the complement graph of the original graph. This means that the problem of finding a clique in an initial graph is equivalent to finding an independent set in the complement graph.

究其原因，这是有趣的是，在你所描述的问题，您将得到人们的图，每个边表示这两种人不能住在一起。因此，你可以把你描述为试图找到一种方法，打破了该图分成k子图，每一个都是独立设置的问题。如果您构建此图的补充，你会得到所有的人谁也还行被放在一起的图形。在这种情况下，要向上打破组成k团的所有派系

The reason this is interesting is that in the problem you're describing, you are given a graph of people where each edge indicates "these two people can't be housed together." Consequently, you can think of the problem you're describing as trying to find a way to break the graph up into k subgraphs, each of which is an independent set. If you construct the complement of this graph, you get the graph of all people who are okay being placed together. In that case, you want to break the group up into k groups that are all cliques.

已知的是，存在以下问题是NP完全

It is known that the following problem is NP-complete:

给定图和一个数k，你能打破在图中的节点分开成k派系？

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

我们可以减少这个问题，您的问题在多项式时间内，显示出你的问题是一个NP难。施工简便 - 定的初始图G和数k，首先构造G的补这意味着，如果你能掰开补为k独立集，那么原来的图G可以断开分开为k派系（因为拉帮结派和独立组之间的对偶）。现在，利用这个新的图形，并把它转换成一组人，每个节点之一，这里两个人不能置于同一房间，彼此如果他们的节点被连接在原来的曲线图。现在，有一种方法对这些人分配成k房屋当且仅当的G的补体可以被分解成k个独立的集IFFģ可以分解成k小集团。因此，集团覆盖已知的NP完全问题可以简化为在多项式时间内您的问题，所以你的问题是一个NP难。以确保任何独立集可以是配合到一所房子，只是设置每个房间的最大容量为n，图中的节点的数目。这允许被容纳在任何房间内的任何独立的设定。

We can reduce this problem to your problem in polynomial time, showing that your problem is NP-hard. The construction is simple - given the initial graph G and number k, first construct the complement of G. This means that if you can break apart the complement into k independent sets, then the original graph G can be broken apart into k cliques (because of the duality between cliques and independent sets). Now, take this new graph and convert it into a set of people, one per node, where two people cannot be placed into the same room as one another if their nodes were connected in the original graph. Now, there is a way to distribute these people into k houses iff the complement of G can be broken down into k independent sets iff G can be broken down into k cliques. Consequently, the known NP-complete problem of clique cover can be reduced to your problem in polynomial time, so your problem is NP-hard. To ensure that any independent set can be fit into a house, just set the maximum capacity of each room to n, the number of nodes in the graph. This allows any independent set to be housed in any room.

由于您的问题是NP难的，不可能有一个多项式时间的解决方案，除非P = NP。因此，作为最好的，任何人都知道，没有多项式时间算法，它和你的回溯递归很可能是最佳的解决方案。

Since your problem is NP-hard, there cannot be a polynomial-time solution to it unless P = NP. Consequently, as best as anyone knows, there is no polynomial time algorithm for it and your backtracking recursion very well might be the optimal solution.

希望这有助于！