在尊重偏好的同时将人分配到建筑物？

Question

一位朋友今天问了我一个关于转让问题的问题.我找到了一个非常简单的解决方案,但我觉得它可以变得更简单,更快捷.非常感谢您的帮助.

问题:假设我有N个人,我需要将它们分配到M个建筑物中,每个建筑物都可以容纳K个人.并非所有人都愿意相互生活,所以我有一个N*N细胞矩阵和一个标志着愿意相互生活的人的1.如果一个单元格包含1,则意味着我和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. 有更好的算法吗？

我认为这可能与稳定的婚姻问题有关,尽管我不确定.

Answer 1

通过从将图分解为集团的NP完全问题(集团覆盖问题)的减少,已知该问题是NP难的.

首先,一些术语和讨论.图中的clique是一组k个不同的节点,使得每个节点连接到clique中的每个其他节点.图中的独立集是一组k个不同的节点,使得没有两个节点彼此连接.如果您获取任何图形G,然后在缺少边缘时引入边缘并移除先前存在的所有边缘,则会得到原始图形的补图.这意味着在初始图中找到一个团的问题等同于在补图中找到一个独立的集.

这很有趣的原因在于,在你所描述的问题中,你会得到一个人物图表,每个边缘都表示"这两个人不能被安置在一起".因此,您可以将您所描述的问题视为试图找到将图形分解为k个子图的方法,每个子图都是一个独立的集合.如果您构建此图的补充,您将获得所有可以放在一起的人的图表.在这种情况下,您希望将组分成k组,这些组都是派系.

众所周知,以下问题是NP完全的:

给定一个图形和一个数字k,你能否将图形中的节点分成k个集团？

我们可以在多项式时间内将此问题减少到您的问题,表明您的问题是NP难的.构造很简单 - 给定初始图G和数k,首先构造G的补数.这意味着如果你可以将补数分解为k个独立集,那么原始图G可以分解为k个集团(因为集团与独立集之间的二元性).现在,使用这个新图并将其转换为一组人,每个节点一个,如果他们的节点在原始图中连接,则两个人不能放在同一个房间.现在,有一种方法可以将这些人分配到k个房屋中,如果G的补充可以分解为k个独立集合,如果G可以分解为k个集团.因此,已知的NP-complete clique cover问题可以在多项式时间内减少到你的问题,所以你的问题是NP难的.要确保任何独立集合适合房屋,只需将每个房间的最大容量设置为n,即图表中的节点数量.这允许任何独立的装置容纳在任何房间中.

由于你的问题是NP难的,除非P = NP,否则不能有多项式时间解决方案.因此,就像任何人都知道的那样,没有多项式时间算法,你的回溯递归可能是最佳解决方案.

希望这可以帮助!

Answer 2

templatetypedef 非常好地证明了为什么问题是NP难的并且没有(已知的)多项式时间解决方案.

然而,与许多NP难问题一样,这并不意味着你无法在实践中有效地解决它,或者你无法改进蛮力解决方案.

特别是,您应该研究约束满足问题.它们是一类更为通用的问题,它们准确描述了您要解决的问题:给定一组约束条件,满足所有约束条件的值是什么？

AIMA这本书有一个关于如何解决这些类型问题的非常好的章节.我建议你阅读一下,因为那里有很多很好的信息,因为这本书是为本科生设计的,所以很容易理解.我会在这里给你一些重要的想法:

主要问题是:

• 你的递归中应该分配哪个学生？
• 该学生应该按照什么顺序考虑建筑物？

以下是两个启发式方法:

• 最小剩余值(MRV)启发式:当您选择在递归中接下来分配给建筑物的学生时,选择剩下最少选择的学生.
• 最小约束值(LCV)启发式:在确定要查看的学生后,指定排除剩余学生最少选择的建筑物

对于MRV启发式,通过选择对其他学生具有最多约束的学生来打破联系.这些启发式背后的想法是,您希望选择最有可能成功的搜索路径(LCV).但是考虑到特定的搜索路径,您希望尽早失败以减少在该路径上花费的时间(MRV).

此外,您应该使用更先进的搜索算法,如AC-3,而不是基本前向检查的天真递归.

看到约束满足问题在许多软件工程应用中非常普遍,已经有大量的开放式库可以解决这些问题,从而有效地解决它们.当然,这是因为您尝试解决的问题是实际应用程序而不是各种类型的家庭作业.