下面是我个人的一些看法:
一、关于“尽量接近或相等”的判定
楼上的同志们看来都倾向于用“平均数的差的绝对值的和最小”的方法进行判定。在一般
情况下,这种做法似乎没有什么问题。但是,请看下面这组数据:
90, 10, 20, 30
如果我们想将它们“尽量平均”的分为三份,按照上面的判定方法就会出现几组最优解:
1. {90}, {10}, {20, 30}
2. {90}, {10, 20}, {30}
3. {90}, {10, 30}, {20}
它们距离平均数的差的绝对值之和分别为:
1. |90-50|+|10-50|+|(20+30)-50|=40+40+0=80
2. |90-50|+|(10+20)-50|+|30-50|=40+20+20=80
3. |90-50|+|(10+30)-50|+|20-50|=40+10+30=80
看起来,这几组解都是最优的——真的是这样吗?我们可以回忆一下中学学到的计算数据
误差大小的方法——求均方差。让我们用这个标准的统计学方法来检验一下这三组数据:
1. (40^2+40^2+0^2)/3=1066.67
2. (40^2+20^2+20^2)/3=800
3. (40^2+10^2+30^2)/3=866.67
现在我们可以得出结论——只有第2组结果才是三组答案中真正“最接近”的。
大家从中可以得到什么启发呢?...
二、关于算法的复杂性
如果将此问题简化,仅讨论“均分为两组”,完全可以用我在 lid=1016791 中提出的算法
圆满的解决(——请注意,此时算法的复杂度已经接近 O(N!) 了)。如果分组数量超过2,
该算法实际上已经成为一个NP复杂问题(如果再考虑均方差的话,就...不用说了吧)。我个
人认为,如果问题的数据量和分组数量均达到了一定程度,普通的算法就无法在可以接受的
时间内求出最优解(我估计在分组数>10,数据量>50的时候,普通的算法就招架不住了),
如果真的有这方面的需要,可以考虑使用人工神经网络求解,在一般情况下,它都可以在可
接受的时间内得到99.999999999999%满意的解。