在尊重偏好的情况下将人员分配到建筑物？今天有朋友问我关于转学的问题。我找到了一个非常简单的解决方案，但我觉得它可以变得更简单、更快。感谢您的帮助。问题：假设我有N个人，我需要将他们分布在M栋楼，每栋楼可以容纳K人。并不是所有的人都愿意同居，所以我有一个N*N单元格的矩阵和一个标记愿意同居的人的1。如果一个单元格包含1，则表示I和J可以共存。显然，矩阵围绕主对角线对称。我的解决方案如下（伪代码）：int[]Match(int[]people,int[][]pairs,intnumBuildings,intbuildingsSize){int[]freePeople=findFreePeople(people);if(freePeople)=0{返回人；}foreach(intpersoninfreePeople){for(intbuildingIndex=0tonumBuildings){if(CheckIfPersonFitsInBuilding(...)){int[]tempPeople=people.Copy();tempPeople[person]=buildingIndex;int[]result=Match(tempPeople,pairs,numBuildings,buildingsSize);如果（结果！=null）{返回结果；}}}}返回空；我只是使用递归来涵盖所有可能的安排。我觉得这可以大大优化，我不是在谈论启发式方法，而是一个不太复杂的解决方案。是否有与此类似的官方已知问题？有更好的算法吗？我认为这可能与稳定的婚姻问题有关，尽管我不确定。通过将图分解为团（团覆盖问题）的NP完全问题归约，已知该问题是NP难的。首先，一些术语和讨论。图中的团是一组k个不同的节点，这样每个节点都连接到团中的每个其他节点。图中的独立集是一组k个不同的节点，使得没有两个节点相互连接。如果您采用任何图G，然后在缺少边时引入边并删除任何预先存在的边，您将得到原始图的补集。这意味着在初始图中寻找团的问题等同于在补图中寻找独立集。这很有趣的原因是，在你描述的问题中，你得到一个人图，每条边都说“这两个人不能放在一起”。所以你可以把你描述的问题想成是想办法把一个图分解成k个子图，每个子图都是一个独立的集合。如果你为这张图构建一个补充图，你将得到一张包含所有你可以放在一起的人的图。在这种情况下，您想将组分成k个组，这些组都是cliques。众所周知，以下问题是NP完全问题：给定一个图和一个数字k，你能否将图中的节点划分为k个团？我们可以在多项式时间内将此问题简化为您的问题，表明您的问题是NP-hard问题。构造很简单——给定一个初始图G和一个数k，首先构造G的补集。这意味着如果你可以将补集分解成k个独立的集合，那么原始图G可以分解成k个团（因为cliques和independentsets之间的二元性）。现在，将这个新图转换为一组人，每个节点一个人，如果他们的节点在原始图中连接，则不能将两个人放在同一个房间里。现在，如果G的补集可以分解成k个独立的集合，如果G可以分解成k个团，有没有办法将这些人分配到k个房子里。因此，已知为NP完全的集团覆盖问题可以在多项式时间内简化为您的问题，因此您的问题是NP难的。为了确保任何独立的集合都适合一个房子，只需将每个房间的最大容量设置为n，即图中的节点数。这允许任何独立单元容纳在任何房间中。由于您的问题是NP-hard，因此除非P=NP，否则不可能有多项式时间解。所以，众所周知，它没有多项式时间算法，你的回溯递归可能是最好的解决方案。希望这可以帮助！templatetypedef很好地演示了为什么问题是NP-hard并且没有（已知的）多项式时间解决方案。然而，与许多NP-hard问题一样，这并不意味着您无法在实践中有效地解决它，或者您无法改进蛮力解决方案。特别是，您应该研究约束满足问题。它们是一类更普遍的问题，可以准确描述您要解决的问题：给定一组约束，满足所有约束的值是多少？AIMA书中有一个非常好的章节介绍了如何解决这些类型的问题。我推荐你去读一读，因为那里有很多很好的信息，而且由于这本书是为本科生设计的，所以很容易理解。我将在这里给你一些重要的想法：主要问题是：这里有两个启发式：对于MRV启发式，通过选择对其他学生有最大限制的学生来打破平局。这些试探法背后的想法是您要选择最有可能成功的搜索路径(LCV)。但是给定一个特定的搜索路径，您希望尽早失败以减少在该路径上花费的时间(MRV)。此外，与具有基本前向检查的朴素递归不同，您应该使用更高级的搜索算法，如AC-3，它看起来更远。在许多软件工程应用程序中看到约束满足问题是如此普遍，以至于已经有大量的开放库可以有效地解决这些问题。当然，这是因为你要解决的问题是真实的应用，而不是各种作业。解决这些问题的一个好方法是对有限域使用约束求解器。例如，使用GNU-Prolog：solve(Out):-People=[Jon,Mary,Alice,Smith,Dick,George,Betty,Lucy],fd_domain(People,0,3),%peoplelivesinbuildings0to3.fd_atmost(4,People,0),%最多，4人可能住在0号楼fd_atmost(3,People,1),%最多，3人可能住在1号楼fd_atmost(2,People,2),%等fd_atmost(1,People,3),Jon#=Mary,%JonhatesMaryAlice#=Smith,%etc.Betty#=Lucy,Jon#=Alice,Dick#=George,fd_labeling(People),%迭代直到找到可接受的组合。人=出去。:-解决（O），写（O），nl。从复杂性的角度来看，这仍然是NP完全的。但是约束求解器可以重新排序在标记步骤上执行分配的方式，以便更早地找到死胡同，从而导致更小的搜索树。以上是C#学习教程：在尊重偏好的情况下分配人员到建筑物？如果所有分享的内容对你有用，需要进一步了解C#学习教程，希望大家多多关注。本文收集自网络，不代表立场。如涉及侵权，请点击右侧联系管理员删除。如需转载请注明出处：
