寻求一个均分算法 (如能解决高分奉送) (100分)

感谢大家出谋划策,小弟第一次在大富翁中提问题,
没想到大富翁的气氛真的太好了,比其他论坛强多了,
而且有那么多热心的网友,无私的帮助,真的令我感动。
谢谢大家。
问题已经更正了,是我表达不周,应该是:
“把不定量的一组随机数分成n份,使每份的累加和尽量接近或相等,请高手指教”。
 
呵呵,就是不均分了,看来我老了
 
SS2000:还是有问题哦!
你把11换成15!
然后再看看你的分组是不是还可以优化?
你分组是12+28+119+105=264/////115+43+37+32+19+15=261
是不是可以把119+12 和115+15交换一下??
 
下面是我个人的一些看法:
一、关于“尽量接近或相等”的判定
楼上的同志们看来都倾向于用“平均数的差的绝对值的和最小”的方法进行判定。在一般
情况下,这种做法似乎没有什么问题。但是,请看下面这组数据:
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%满意的解。
 
step1,排序
step2,用贪心获取次优解,
一般获得的解已经比较符合要求了
step3,分支定界,以2的次优解为临界条件
 
中午想了一下,觉得这个问题似乎可以用遗传算法来解决,而不是神经网络,因为本问题
的解决思路和遗传算法中的“基因”非常的接近。
算法的大致实现思路:
1.将全部数据随机的分成N份,形成N个子集(每个子集的元素数量都要大于0);
2.对目前的数据分配方案进行均方差计算,并将所得结果与已获得的均方差的最小值进行
比较,按照一定的规律进行方案淘汰(比如:小于等于最小值的将被保留,剩下的比值越大
被淘汰的概率就越高),如果当前方案没有被淘汰,则接着进行下一步操作;
3.对当前方案进行“变异”操作——即在原方案的基础上,让几个集合之间进行少量随机
性的数据交换(注意,“交换”在此并不单指1个换1个,可以是1换多甚至0换多,但要保证
交换之后每个子集中都有元素),并最终形成4-20个子代方案;
4.返回并等待,直到当前层的所有子代生成完毕;
5.将所有子代方案分别送入2号过程进行处理。
注意到本算法中没有终止机制,我们在具体操作中可以通过限制递归深度或总运算时间达
到停止运算的目的。
容易看出,使用本算法,并不能保证一定能求出最优解,但是对于NP复杂问题,我们能够
在可接受的时间内得到一个可接受的、非常接近最优值的解就可以了。

>>如能解决高分奉送
嗯,像我这样的“职业杀手”最欣赏的就是这一点了,嘿嘿...
Working...
 
收藏并努力试验中。
 
to creation-zy:1.你的分析实际上不了解数学上面其实对“尽量接近或相等”的探讨
非常深入,比如残差分析法 而这些只不过是初步。所以我才尽量简化成绝对值最小。
而且请注意的最小方差实际在数学上说效果是和绝对值相似的,并没有本质上的改善;
其中的原因比较复杂,我无法一下说清楚。
2.我的复杂度没有那么高:我的是m<<n,所以找最优解是有意义的。不过你的淘汰机制还是
非常可取的,可以看出你的水平还是比较高的,很荣幸和你讨论。
to lldhz:我无法确定取接近某个平均值的就是一定是最优解中的一个集合,
所以不能以最接近来作为一个约束条件。
 
关注,听课[:D]
 
zjczxd:
>>必须设法找到第一组数;糟糕的是我们必须逐一扫描,获得第一组数,
>>然后才可以用n=2的办法找出一个方案,记录三个数差的绝对值和进行比较,得到最优解。
如果取接近某个平均值的组不一定是最优解中的一个集合的话,在获得第一组数据的时候的
可能就有非常的多(∑C(n.i),i=1..n/2+1)事实上:分2组时,取出的一个是最接近平均值时
也就已经得到答案。现在就看能不能推广到N上。
Working......
 
>>分2组时,取出的一个是最接近平均值时也就已经得到答案。现在就看能不能推广到N上。
这是一个全局优化的问题,局部的优化并不能一定导致整体的最优化。以我在上面给出的
90,10,20,30 为例,平均值为50,但是方案1显然要比方案2差。除此之外,还有相当多的难
以把握的因素(比如:在分为多组时,最接近平均值的解可能有很多组,每种情况对应的剩
余组的分配情况又是不同的)。
另外,即使实际问题中满足m<<n的条件,仍然很可能成为NP复杂问题(比如m=8,n=50)。
 
to lldhz:您现在终于明白我的意思了!实际上我现在就是在想能不能找到他们更为内在的
联系,从而改善算法的效率。不过我现在还没有找到进一步的办法。
to creation-zy: 均方根算法实际上是在绝对值算法上加上一个权,
也就是说权等于它本身,这个权这样加上去是否合理呢?不一定。
就那你的例子来说吧:
1. {90}, {10}, {20, 30}
2. {90}, {10, 20}, {30}
3. {90}, {10, 30}, {20}
你不能说第2组就一定是最优秀的解,
比如有些应用可能会以为第一组是最优秀的解,
因为它认为:(90)和(20,30)这一组非常接近,而(10)仅仅是一组,
综合考虑,还是第一组比较好,等等。
当然,道理实际上没有这么简单,实际上远比这要复杂。
另外,求乘法的时间消耗的时间比求和差长得多,而这一运算又是在算法的最底端,
所以没有必要牺牲速度而改进判断法则呢?我想我们无法在这里讨论,
这需要根据实际情况来决定。
另外:确实,当n过大的时候,比如n>100,m>10时,这个问题基本上无法解出最优解了,
我这时就要想办法找较优解。你讲的方法确实是一个考虑。但是另外一方面当规模
进一步扩大,比如n>1E10,m>1E9 的时候,可能任何算法都无能为力了。
请您注意我的“可能”的措词,表示是有不确定性的,我并没有完全否定的意思。
 
首先要把“尽量接近或相等”的概念量化,否则无从下手。
 
与zjczxd%creation_zy讨论:关于最优解的判断方法

1. {90}, {10}, {20, 30}
2. {90}, {10, 20}, {30}
3. {90}, {10, 30}, {20}
到底哪个是最优解,应该有一个科学的定义,我认为《数理统计》早已解决了这个问题
那就是“方差”,三组数中,哪一组方差最小,就是最优解。
barton的冒泡法在只分两组的情况下可以得到最优解,但在n组的情况下,可能使方差
很大。
我认为creation_zy的算法可行,但对如何结束可做以下判断:
每计算一次结果计算一次方差,两次方差之差小于某一个设定值时终止计算。
方差判断法还可以作为衡量某一个算法是否可行的手段,如果经过n次循环后
方差趋于增大,说明这个算法不可行。
 
Creation_zy,抱歉,昨晚没有认真看您的方案,对您的评论实属多此一举。
至此,我认为Creation_zy的方法最优。
下面想对其他可能的方法进行粗略讨论:
典型的是Barton的方法,其结果是:
V1..Vn从小到大离平均值越来越大。
| ‘
| 。
| 。
| 。
|。
。-------------------------------------------
zjczxd的方法说是解决了这个问题,但从其文字表达中,我没有看出解决的方法。
我的想法是,不管用什么方法,每次循环得到的中间方案的客观效果必定如
上图,所以我们必须在递归计算中以上一个计算结果为基础,计算意图是使
下一个计算结果的方差比上一个方案小,手段是强制排在前面组中的某些元素不在
组内(我非计算机科班,不通数据结构,请其他高手解决)。方差之差小于某值后
退出到递归上一个循环。
上面所说的计算意图对每次次计算结果有随机性,但趋势必须是缩小的(收敛的)
我们可以后( n次计算的平均方差-前n次的平均方差)〈指定值 作为退出计算的
条件
这事实上是统计学问题,所以不能回避统计学方法和经验值上述公式的
n 和“指定值”就必须作为经验值。
方差走势图:
|。
| 。
| 。
| 。
| 。 。
| 。 。
。-------------------------------------------
 
接受答案了.
 

Similar threads

S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
D
回复
0
查看
892
DelphiTeacher的专栏
D
I
回复
0
查看
708
import
I
顶部