基於卡爾多理論的宿舍分配算法

《基於卡爾多理論的宿舍分配算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基於卡爾多理論的宿舍分配算法综述首先要阐明几个概念：一个学生对另一个学生的满意度，是指后者的行为符合前者期望的程度，越符合期望，满意度越高；一个学生对其他所有学生的满意度从大到小的排名，称为偏好序列；一个分配方案中所有人在室友的偏好序列中的最低的排名，称为最差名次；寝室的和谐度，是指寝室中的所有学生两两之间满意度的和；所有寝室的和谐度的和，称为总和谐度。根据前文论述的人际关系理论，一个和谐的宿舍，不仅仅要让学生之间总的满意度最高，更要避免其中某两个人关系太差。所以，我们的宿舍分配策略是，优先保证最差名次最高，在此条件下使总和谐度最高。实现

2、思路首先把寝室分配问题抽象化。设学生数量为n,把每个学生当作顶点，满意度当作有向边，是一个有向完全图。寝室分配的过程就是从完全图中找出边，构成n/4个孤立的四阶完全图，在最差名次最高的情况下，总边权最大。不像组两人寝室，有带花树算法，可以用O(n4)时间求最大权匹配，这个问题没有现成的解法，需要我们创新。经过分析，我们觉得很难找到多项式时间的解，而且最朴素的指数算法——单纯的枚举所有组合再选出最优显然是不实际的。于是我们把目光投向了近似解法。有类似的论文使用贪心算法，从任意一个尚未被分配的学生出发，找出三个尚未被分配的学生里他最满意的，四

3、个人直接组成寝室。这样的解法显然是过于粗糙，既没考虑一个寝室里另外三名同学之间的关系，也没考虑全局的最优。不值得我们借鉴。求近似解的问题还有一类通用的解法，就是人工智能算法。以遗传算法为例，可以随机生成一系列的分配方案，对这些方案进行反复的选择，交叉，变异，多代后会有很好的近似解。遗传算法的优点是效果比较好，缺点是编程复杂度高，调试和维护困难，所以我们也先不考虑。我们之中有擅长经济学的同学，她向我们推荐了一个经济学中的理论——卡尔多改进。如果一种变革使受益者所得足以补偿受损者的所失，这种变革就叫卡尔多改进。如果一种状态下，已经没有卡尔多－

4、希克斯改进的余地，那么这种状态就达到了卡尔多效率。在宿舍分配问题中，如果其中两个人交换寝室后，最差名次提高了，或者总和谐度增大了，那么就是卡尔多改进，说明这个交换是合理的。经过不断地交换，当再也没有合理的交换，那么就达到了卡尔多效率。我们将达到卡尔多效率的分配方案称为一个极优解。我们设想，这样的极优解会是最优解的很好的近似。更进一步，我们可以从多个不同的初始状态求出多个极优解，再从中找到最好的那一个，那么就可以更好地逼近最优解。算法的思路概括如下：1.随机一个分配方案，为一个初始状态。2.从当前状态，枚举一次交换所能得到的各种状态，选取其

5、中最好的状态，如果它比当前状态好，则实施对应的一次交换。（注：状态A>状态B定义：A最差名次更高

6、

7、最差名次相等&&A总和谐度更高）3.重复步骤2，直到一次交换后任何一种状态都不比当前状态好。至此得到极优解。4.重复1-3步骤T次，从T个极优解中选取最好的解，为最终解答。组织结构1.数据结构：总人数的最大值constintMaxN=60总人数intn满意度矩阵intgraph[MaxN+1][MaxN+1]每个宿舍人数constintDormLimit=4宿舍数最大值constintMaxDCnt=(MaxN/DormLimit)+(bo

8、ol)(MaxN%DormLimit)宿舍数intdcnt每个人所在宿舍intinDrm[MaxN+1]classPlan{/*宿舍分配方案类*/public:总和谐度ints;最差排名intrmax;分配方法intdorm[MaxDCnt+1][DormLimit+1];public:构造函数Plan();析构函数voidclear();};2.主要函数：intread()读入总人数和满意度矩阵voidcalc_max_roommate_rank(Plan&pl)计算方案p1的最差名次voidrandom_divide(Plan&pl)

9、随机初始方案boolisBetterPlan(constPlan&p1,constPlan&p2)判断一个方案是否优于另一个方案voidchief()多次实施交换，得到极优解，并选取最好的解voidwrite()输出宿舍分配方案性能分析理论分析算法的时间复杂度为：T*k*n3其中T是初始方案的个数，k是尝试交换的总次数，n是总人数。T个初始方案，每个初始方案尝试k次交换，每次交换验证是否更优需要3层循环，复杂度是n3，故总时间复杂度为三者相乘其中k是n的指数函数。k最大是总状态数，即Cn4*Cn-44*…*C44。平均未知。实际测试分析测

10、试环境：cpu:IntelCorei5-3230M操作系统：windows7内存：4MIDE：Dev-cpp输入数据：满意度矩阵由随机数计算生成。考虑到实际问题当中，三个人之间应满足三角不等式