草庐IT

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

coder 2023-07-14 原文

今天有 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 有关，虽然我不确定。

最佳答案

通过从 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，否则不可能有多项式时间解。因此，众所周知，它没有多项式时间算法，您的回溯递归很可能是最佳解决方案。

希望这对您有所帮助!

关于c# - 在尊重偏好的情况下将人员分配到建筑物？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11172756/

c#偏好图中的sectionalgorithmoptimizationcomplexity-theorycombinatorics

有关c# - 在尊重偏好的情况下将人员分配到建筑物？的更多相关文章

  1. ruby - 默认情况下使选项为 false - 2

    这是在Ruby中设置默认值的常用方法:classQuietByDefaultdefinitialize(opts={})@verbose=opts[:verbose]endend这是一个容易落入的陷阱:classVerboseNoMatterWhatdefinitialize(opts={})@verbose=opts[:verbose]||trueendend正确的做法是:classVerboseByDefaultdefinitialize(opts={})@verbose=opts.include?(:verbose)?opts[:verbose]:trueendend编写Verb

  2. Ruby Koans about_array_assignment - 非平行与平行分配歧视 - 2

    通过ruby​​koans.com，我在about_array_assignment.rb中遇到了这两段代码你怎么知道第一个是非并行赋值，第二个是一个变量的并行赋值？在我看来，除了命名差异之外，代码几乎完全相同。4deftest_non_parallel_assignment5names=["John","Smith"]6assert_equal["John","Smith"],names7end45deftest_parallel_assignment_with_one_variable46first_name,=["John","Smith"]47assert_equal'John

  3. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  4. ruby - 模块嵌套代码风格偏好 - 2

    我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

  5. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  6. ruby - 在 Ruby 中重新分配常量时抛出异常？ - 2

    我早就知道Ruby中的“常量”(即大写的变量名)不是真正常量。与其他编程语言一样，对对象的引用是唯一存储在变量/常量中的东西。(侧边栏:Ruby确实具有“卡住”引用对象不被修改的功能，据我所知，许多其他语言都没有提供这种功能。)所以这是我的问题:当您将一个值重新分配给常量时，您会收到如下警告:>>FOO='bar'=>"bar">>FOO='baz'(irb):2:warning:alreadyinitializedconstantFOO=>"baz"有没有办法强制Ruby抛出异常而不是打印警告？很难弄清楚为什么有时会发生重新分配。 最佳答案

  7. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  8. ruby - 在不使用 RVM 的情况下在 Mac 上卸载和升级 Ruby - 2

    我最近决定从我的系统中卸载RVM。在thispage提出的一些论点说服我:实际上，我的决定是，我根本不想担心Ruby的多个版本。我只想使用1.9.2-p290版本而不用担心其他任何事情。但是，当我在我的Mac上运行ruby--version时，它告诉我我的版本是1.8.7。我四处寻找如何简单地从我的Mac上卸载这个Ruby，但奇怪的是我没有找到任何东西。似乎唯一想卸载Ruby的人运行linux，而使用Mac的每个人都推荐RVM。如何从我的Mac上卸载Ruby1.8.7？我想升级到1.9.2-p290版本，并且我希望我的系统上只有一个版本。 最佳答案

  9. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  10. ruby - 在什么情况下会使用 Sinatra 或 Merb？ - 2

    我正在学习Rails，对Sinatra和Merb知之甚少。我想知道您会在哪些情况下使用Merb/Sinatra。感谢您的反馈! 最佳答案 Sinatra是一个比Rails更小、更轻的框架。如果你想让一些东西快速运行，只需发送几个URL并返回一些简单的内容，就可以使用它。看看Sinatrahomepage;这就是启动和运行“Hello,World”所需的全部内容，而在Rails中，您需要生成整个项目结构、设置Controller和View、设置路由等等(我还没有有一段时间写了一个Rails应用程序，所以我不知道“Hello,World

随机推荐