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

基於卡爾多理論的宿舍分配算法综述首先要阐明几个概念：一个学生对另一个学生的满意度，是指后者的行为符合前者期望的程度，越符合期望，满意度越高；一个学生对其他所有学生的满意度从大到小的排名，称为偏好序列；一个分配方案中所有人在室友的偏好序列中的最低的排名，称为最差名次；寝室的和谐度，是指寝室中的所有学生两两之间满意度的和；所有寝室的和谐度的和，称为总和谐度。根据前文论述的人际关系理论，一个和谐的宿舍，不仅仅要让学生之间总的满意度最高，更要避免其中某两个人关系太差。所以，我们的宿舍分配策略是，优先保证最差名次最高，在此条件下使总和谐度最高。实现思路首先把寝室分配问题抽象化。设学生数量为n ,把每个学生当作顶点，满意度当作有向边，是一个有向完全图。寝室分配的过程就是从完全图中找出边，构成n/4个孤立的四阶完全图，在最差名次最高的情况下，总边权最大。不像组两人寝室，有带花树算法，可以用O(n4)时间求最大权匹配，这个问题没有现成的解法，需要我们创新。经过分析，我们觉得很难找到多项式时间的解，而且最朴素的指数算法单纯的枚举所有组合再选出最优显然是不实际的。于是我们把目光投向了近似解法。有类似的论文使用贪心算法，从任意一个尚未被分配的学生出发，找出三个尚未被分配的学生里他最满意的，四个人直接组成寝室。这样的解法显然是过于粗糙，既没考虑一个寝室里另外三名同学之间的关系，也没考虑全局的最优。不值得我们借鉴。求近似解的问题还有一类通用的解法，就是人工智能算法。以遗传算法为例，可以随机生成一系列的分配方案，对这些方案进行反复的选择，交叉，变异，多代后会有很好的近似解。遗传算法的优点是效果比较好，缺点是编程复杂度高，调试和维护困难，所以我们也先不考虑。我们之中有擅长经济学的同学，她向我们推荐了一个经济学中的理论卡尔多改进。如果一种变革使受益者所得足以补偿受损者的所失，这种变革就叫卡尔多改进。如果一种状态下，已经没有卡尔多希克斯改进的余地，那么这种状态就达到了卡尔多效率。在宿舍分配问题中，如果其中两个人交换寝室后，最差名次提高了，或者总和谐度增大了，那么就是卡尔多改进，说明这个交换是合理的。经过不断地交换，当再也没有合理的交换，那么就达到了卡尔多效率。我们将达到卡尔多效率的分配方案称为一个极优解。我们设想，这样的极优解会是最优解的很好的近似。更进一步，我们可以从多个不同的初始状态求出多个极优解，再从中找到最好的那一个，那么就可以更好地逼近最优解。算法的思路概括如下：1.随机一个分配方案，为一个初始状态。2.从当前状态，枚举一次交换所能得到的各种状态，选取其中最好的状态，如果它比当前状态好，则实施对应的一次交换。（注：状态A状态B定义：A最差名次更高|最差名次相等&A总和谐度更高）3.重复步骤2，直到一次交换后任何一种状态都不比当前状态好。至此得到极优解。4.重复1-3步骤T次，从T个极优解中选取最好的解，为最终解答。组织结构1.数据结构：总人数的最大值 const int MaxN = 60总人数 int n满意度矩阵 int graphMaxN+1MaxN+1每个宿舍人数 const int DormLimit = 4宿舍数最大值 const int MaxDCnt = (MaxN / DormLimit) + (bool)(MaxN % DormLimit)宿舍数 int dcnt每个人所在宿舍 int inDrmMaxN+1class Plan /* 宿舍分配方案类 */public:总和谐度 int s;最差排名 int rmax;分配方法 int dormMaxDCnt+1DormLimit+1;public:构造函数 Plan();析构函数 void clear();2.主要函数：int read() 读入总人数和满意度矩阵void calc_max_roommate_rank(Plan &pl) 计算方案p1的最差名次void random_divide(Plan &pl) 随机初始方案bool isBetterPlan(const Plan &p1, const Plan &p2) 判断一个方案是否优于另一个方案void chief() 多次实施交换，得到极优解，并选取最好的解void write() 输出宿舍分配方案性能分析理论分析算法的时间复杂度为：T*k*n3其中T是初始方案的个数，k是尝试交换的总次数，n是总人数。T个初始方案，每个初始方案尝试k次交换，每次交换验证是否更优需要3层循环，复杂度是n3，故总时间复杂度为三者相乘其中k是n的指数函数。k最大是总状态数，即Cn4* Cn-44* C44。平均未知。实际测试分析测试环境： cpu: Intel Core i5-3230M 操作系统：windows7内存：4M IDE：Dev-cpp输入数据：满意度矩阵由随机数计算生成。考虑到实际问题当中，三个人之间应满足三角不等式关系，所以我们没有直接随机满意度矩阵的元素，而是先随机出n个点的横纵坐标，再计算两两之间的曼哈顿距离，以最大距离减去每对的距离作为两两之间的满意度。实际问题当中相互满意度可以不同，但与上述方法生成的数据没有本质区别。单次测试时，设置随机种子为1，rand()%1000000得出数据点的横纵坐标。多次测试时，设置随机种子分别为1,2,3N，rand()%1000000得出数据点的横纵坐标。首先分析时间性能，令 T=100，作时间t与n的关系图如下：横坐标n,纵坐标t(s)再令n=40，作时间t与T的关系如下：横坐标T,纵坐标t(s)我们分配寝室是以班级为单位的，一个班级大概40-50人，可以从上图中看出，n50,T=100时，运行时间在4秒以内，可以满足实际需要。当n增大时，运行速度会快速下降，n=100,T=1时，运行时间约为1秒。当T增大时，时间近似是线性增加的。在实验过程中，我们观察到一个反常现象。当n=40， T=100时，按照概率统计的规律，因为初始状态是随机的，所以我们找到的最优的解应该平均出现在第50次。然而实际测试中，最优的解平均出现的位置往往比较靠前。这让我们非常疑惑。于是我们做了一个统计，令n=40,T=100,随机不同的输入，重复测试500次，统计我们能找到的最优的解（以下简称最优的解）出现的位置，作图如下。横坐标是频数，纵坐标是最优的解出现位置平均出现位置为32.432，印证了我们的观察结果。后来我们想到一个可能的解释，那就是最优的解可能会重复出现多次，而在原先的程序中，后几次出现没有被记录下来。所以没有发现这种重复。想到这里，我们加上计数功能。令n=40,T=100, 随机不同的输入，重复测试500次，统计最优的解出现的频数，作图如下：横坐标是最的优解重复出现次数，纵坐标是频数这表明我们找到的最优的解有时多次重复出现。进而说明，从不同的随机初始状态，可以求出同一个极优解。这暗示了这个问题的一个特性，那就是虽然它的状态空间很大，但是极优解的数量却远比状态空间的数量少。如果极优解足够少，那么我们通过多次运算，就有很大把握穷尽所有的极优解，继而让我们得到的最优的解就是最优解。那么极优解到底有多少呢？我们不能准确地求出来，但是可以从极优解的重复情况中看出趋势。我们令n=40,T=5000，统计我们找到的极优解的出现频数。横坐标是频数，纵坐标是总和谐度这个图标揭示了很多信息。首先一个坏消息是，5000次重复计算求出的极优解就有905个，这说明极优解的数量还是比较多，我们通过有限时间的计算没有把握穷尽所有极优解。其次，极优解的频数是有规律的。有几个极优解出现上百次，有一部分极优解频数达到20次，与大部分极优解只出现1次形成鲜明对比。这说明极优解出现的概率差别较大。不过，从图中可以看出，极优解出现的概率与它自己的总和谐度呈正相关关系，也就是说，越好的极优解出现的概率越大。这可以解释为，差的解各有各的差，但是好的解却是公认的好，所以在求最优解时更容易被构造出来。这是一个好消息，尽管我们定义的最优并不是和谐度最大的解，但至少说明我们能找到的最优的解在某种意义上是很好的。另外还有一个好消息，那就是这些极优解的总和谐度比较接近，极差只有6%-7%，这说明它们的近似效果都比较好。所以，就算