我正在为我工作的英语语言学校编写程序。我没有工资，这只是一种爱好，可以改善/自动化我的工作流程。
这是一所寄宿学校，我正在研究自动化的一个方面是我们为学生分配房间的方式，虽然我不想要一个完整的解决方案，但我希望有人能给我指出正确的方向……你可能处理这个问题的方法的建议，或者通过建议算法来查看等。
基本上在学校我们有一大堆不同的房间，从单人房到8人宿舍。我们有很多来自世界各地的不同国籍的人，我们总是努力确保每个房间都有不同国籍的人。在不止一个民族的地方，我们试图平衡他们。年龄也很重要，我们总是把年龄相近的学生放在一起，同时也在努力混合国籍，而我们不寻常的是有学生分享超过两年的时间。
我想更一般地说，我感兴趣的是如何根据两个参数对给定的一组学生进行排序，以获得带有一些规则的最佳结果。
我希望我已经清楚地解释了我想要实现的目标……在某种程度上，这听起来很简单，但我一直在努力思考如何用一种简单的方式来做到这一点，即按国籍和年龄排序，但这并不合适，我知道一定有更好的方法来解决这个问题。当我在excel表格上"手工"做时，确实感觉很直观。
感谢任何提供帮助/建议的人。
这是一个有趣的问题，但不容易回答。不知何故，它与细分、装箱或库存削减问题有关。你可能也想找一个拓扑排序。您可以寻找允许您定义此类规则的业务逻辑平台Drools。
首先你可能会发现这个有趣的问题:稳定的室友问题(维基百科)。遗憾的是，它没有回答你的问题。
试试遗传算法。
使用遗传算法有三个主要标准:
-
将解决方案表示为可变数组的能力。我们可以有一个整数数组，其中a[i]是第i个学生的房间。
-
状态的突变应该产生可预测的结果。在我们的例子中，这是真的。改变数组可以预见地将打乱学生在房间之间的顺序。
-
方便编写的快速适应度函数。写一个O(n)适应度函数应该不会太难
不如这样，你把一个房间想象成一种东西，它排斥已有国籍的学生，而吸引与已有国籍相近的学生。年龄越接近平均年龄，它就越吸引它，房间里X国籍的男人越多，它就越排斥X国籍的男人。
然后，对于每增加一个新学生，迭代遍历每个房间，看看哪个更吸引它。我想如果房间是空的，你可以把所有的力都设为0。此外，你会有几个常数来乘以这两种"力量"，这样你就可以根据年龄相同和国籍不同的重要性来校准它。
我会分析每个学生，并根据他/她的年龄创建一个"个性"向量;国籍。然后我会对向量进行排序，排序后可能会对结果进行一些混乱，以鼓励多样性。
"在优化某些数量的同时根据约束将x分配给y"的一般主题属于运筹学，或者更具体地说http://en.wikipedia.org/wiki/Mathematical_optimization。通常的方法是正式指定问题，并使用通用的优化求解器，例如http://en.wikipedia.org/wiki/List_of_optimization_software中列出的其中一个。
尝试一下，使用现有求解器的正式规范语言相当容易学习，您可能无需调试复杂的算法即可获得最佳解决方案。
作为一般优化问题的公式
形式化约束和参数将是有用的。我们假设对于1 <= i <= 8，我们有n_i个房间大小为i，现在让我们施加一个硬性约束，在特定的房间S中，每两个学生a, b 在S中，我们有:
|Grade(a) - Grade(b)| <= 2 (1)
现在我们感兴趣的是优化"多样性"功能，直观地代表了我们希望房间尽可能混合的想法。所以我们可以将这个目标表示为:
max over all arrangements {{ Sum over all rooms S of DiversityScore(S) }}
where we have DiversityScore(S) = # of Different Nationalities in the Room
作为图问题的公式
这是最一般的设置，但是很明显max在所有的安排上在计算上是不可行的。现在让我们把它作为一种带有硬等级约束的图形问题。将所有学生表示为图g中的一个顶点，如果学生满足约束条件(1)，则连接两个顶点。现在，图中的clique表示可以将所有学生放在同一个房间中的一组学生。现在以贪婪的方式继续。选择规模为4且多样性得分最高的最大集团。然后把它们放在一个房间里，直到所有的房间都被填满。这种小团体搜索方法也可以纳入性别约束，这是有用的，但不是小团体搜索是NP困难问题。
现在，在尝试提出可能更快的东西之前，让我们考虑一下如何削弱硬约束(1)。我们可以通过在图片中包含边权来按摩我们的图公式。如果硬约束满足，表示从i到j的边权值为1。如果两个学生i和j的年龄相差超过2，则表示边缘权重为1/(年龄差)^2或其他东西。那么，小集团的得分应该是小集团边缘权重与某种多样性得分的乘积。然而，很明显，现在的问题是在一个完整的图上，这正是我们希望避免的一般优化，所以我们需要施加一些硬限制来减少图的连通性。
一个基本的排序近似算法
对所有学生按年龄排序，因此我们有一个排序数组，其中a[i]中的所有学生年龄相同，并且a[i]中的所有学生年龄都大于a[j]中的所有学生，对于所有j <我。现在考虑每一对i,><= 2。找到最多的不同国籍的学生，把他们放在一个房间里。我们依次迭代O(n^2)对满足硬约束的索引对，并取任意有国籍差异的学生(通过对索引对进行预处理和哈希可以找到)。仔细执行此操作(例如在接近之前查看分散的索引i j)进一步提高了运行时间。感觉应该是多工时，但我认为在这么说之前有一些微妙之处需要先解决。