IBM经典算法求解：房间分配

IBM本月提出的求解算法问题，挺有意思：

房间分配

问题描述：
假定有若干间宿舍，每个房间住两名学生，要对学生兴趣进行调查，根据学生兴趣来安排志趣相投的学生同住，以尽量使所有学生能够和睦相处。

对学生进行一次包含 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 评估值，然后将最终分配的标识
字符串（一行一个标识）打印到输出文件。此处显示的具体函数名或变量名并非必需。

算法限制：由于解决此类问题的直接方法可能不可靠，并且随着学生人数的增加，各种分配组合的数量将呈几何级剧增，因此程序代码必须使用一些


模拟退火算法：
模拟退火算法描述

模拟退火算法求解tsp问题

文章来自: 本站原创
标签: 算法 ibm 房间分配 模拟退火算法