邯郸学步2之学有所成：随机优化分班

aoe1981

　　下图是详尽分析：
　　
　　分析附件如下：
　　 代码运行时间分析.rar (7.7 KB, 下载次数: 24)

2014-8-8 14:42 上传

点击文件名下载附件

aoe1981

　　刚想到了，在上楼时间分析附件中增加了一列：
　　
　　发现，运行时间完全取决于实际交换次数，二者完全正相关！
　　只是对比理论次数，这个实际次数多了随机的特点，不太可控……
　　如果每次交换时，第一个“方差变小学生”出现的早，则后面的循环便不再进行，这样循环的次数就会少一些……

aoe1981

　　最后再上一张图：
　　
　　此图为前楼稍大数据测试截图的一部分。
　　可见，人数＋性别＋语文单科＋数学单科＋综合单科的均衡并没有使四大分数段变得均衡！
　　我上图圈起来的地方，往往是老师很在意的地方……
　　呵呵，继续保留我的“分数段均衡”的猜想……哈哈哈……

aoe1981

　　引用一句：“我自横刀仰天笑 笑完之后去睡觉！”

香川群子

aoe1981 发表于 2014-8-8 11:06
　　香川曾说：
　　“这个不是随机交换了，而是遍历交换。
　　当然，我的算法遍历次数会少 ...

这当然仍然是遍历的算法，而不是随机的算法。

应该描述为：
1. 两层遍历循环 （外层为主动班学生、内层为被动班交换学生）
2. 内层循环择优交换、终止退回上一层继续遍历
3. 1-2的算法反复多次进行


…………
而随机，则可能是两种情况：
1. 全随机：
按一定次数、任意选择2个学生进行比较，择优交换。

2. 半随机：
外层主动班进行循环遍历
内层剩余班进行一定次数的随机比较、择优交换。


…………
一般随机算法的目的，在于：
针对人数增长导致计算量平方级倍增的问题，
以随机方式进行不完全的检查交换，提高计算效率。
但可能会牺牲一定的准确性（可能无法得到最优解）
但一般仍能较快得到次优解。

呵呵。

aoe1981

香川群子 发表于 2014-8-8 15:39
这当然仍然是遍历的算法，而不是随机的算法。

应该描述为：

　　您说得也在理……不过，我这样1次1次的遍历下去，当提示框显示“实际替换较小方差状态为0”时是否就是得到了最优结果呢？这个我不太敢断定，但是我倾向于认为是这样的……
　　我说随机主要还是针对海量的分班方案：h!，我觉得把这个试到了，才算是遍历吧，而不只是“数据两两对换”的遍历……

aoe1981

　　再上两张关于运行时间的图：
　　
　　
　　可见，均是“实际替换0次较小方差状态”，我猜测：这就是最优方案！

aoe1981

　　关于上楼所上运行时间，总结两点：
　　1.与21楼测试时间对比，遍历2次时间由563秒延长为1097秒；遍历1次时间由58秒延长为553秒。这说明，越往后，寻找“方差较小方案“越困难，所需的找寻时间越长，如果实在找不到，就会遍历所有数据，故而，我猜测是最优状态！
　　2.上楼中遍历1次基础数据时，实际尝试交换426615人次，与21楼公式计算的理论次数426616.875次非常接近，出入是由于各班人数并不是完全相等带来的！
　　当然以上仍然以954人分16班为测试标准。

aoe1981

　　均衡分班做到下图这样，算是到了极致了吧……
　　

aoe1981

　　关于极端情况疑问的测试与回应：
　　170人分25班、27班、29班。