问题描述:假定有若干间宿舍,每个房间住两名学生,要对学生兴趣进行调查,根据学生兴趣来安排志趣相投的学生同住,以尽量使所有学生能够和睦相处。
对学生进行一次包含 50 个问题的调查。每个问题的答案都有五种同意程度,其分值范围从强烈反对(0 分)到强烈同意(4 分)。评估任意一对学生间不和谐程度的计算方法是:比较两人对 50 个调查问题的答案,并汇总不同答案所对应的同意程度分值差的绝对值。然后将得到的总和统一除以 200.0(即可能的最大差异分值总和)。所有假定房间分配的总不和谐程度(TD)值是所有学生对之间的不和谐程度值总和。因此,这个程序的目的就是通过测试宿舍中学生的不同配对来最小化 TD 值。
这个问题的输入内容将是一个文本文件。这个文件的第一行将是要分配宿舍的学生总数(N),后面跟有 N 个学生行。文件中的学生数N将是一个小于 2^28 - 1 的偶数,并且所有输入数据将装入目标平台的主内存中。文件中学生行的格式将是:由 10 个字符组成的标识字符串,1 个空格,再加一个 50 位的调查字符串。调查字符串的元素值范围为 0 到 4。
这些行的初始排列将决定初始的室友配对。最前面的两名学生将被视为分配到同一个房间,接下来的两名学生也分配到另一个房间,依此类推。
输入文件示例:
2
ChukECheez 01230230420314203422301230230420332023410123023042 Clyde Ruth 20342230123023042031420342230123042031420342233042此示例文件的总不和谐程度(TD)临界值为 0.305。
代码限制:主程序必须采用以下结构:
InputDataFromFile(Rooms, N);
first = EvaluateRooms(Rooms, N); print("The initial Disharmony is", first); start = GetTime; ComputeRoomAssignments(Rooms, N); end = GetTime; print("Time to compute room assignments is ", end - start, "seconds"); final = EvaluateRooms(Rooms, N); print("Final Disharmony is", final); PrintRoomAssignmentToFile(Rooms, N); 亦即:输入数据,计算并打印初始总不和谐程度(TD)评估值,开始计时,计算 TD 评估值较低的房间分配,停止计时,打印计算所用的时间,计算并打印最终分配所对应的 TD 评估值,然后将最终分配的标识字符串(一行一个标识)打印到输出文件。此处显示的具体函数名或变量名并非必需。算法限制:由于解决此类问题的直接方法可能不可靠,并且随着学生人数的增加,各种分配组合的数量将呈几何级剧增,因此程序代码必须使用一些迭代的全局优化技巧,例如模拟退火算法(Simulated Annealing)。
时间限制:运行时的执行时间将限制在 2 分钟以内。亦即:假如运行时间超过120秒,应用程序无法向接收点报告。
输入文件:Students.in
输出文件:Assignments.out