财产分配问题的一种算法策略

摘要 财产分配问题是一个NP完全问题，设计有效的算法成为计算机解决这一问题的关键。本文结合贪心策略和穷举策略提出了一种运算量可控、近似程度非常高的算法，为计算机有效解决这类NP问题提出了一种思考方向。
关键词：贪心策略；财产分配；时间复杂度
Abstract Distribution of property is a typical Non-deterministic Polynomial problem, an efficient algorithm is key to solve such problem for computer. This paper integrate backtrack strategy into greed strategy to produce an algorithm with can-be-controled time complexity and super approximant, so as to solve similar problems.
Keywords: greed strategy; distribution of property; time complexity
一 引言
不管是日常生活中，还是计算机领域，我们都会经常碰到类似于财产分配的问题。例如，一批货物要尽可能均衡负载到几辆汽车或轮船上，"云计算"里一批分解出来的任务要均匀的分配到网络中其它计算机上完成，都可以看成是要将n项不能再分割的财产尽可能均匀分配给k个人的问题，这就是我们要讨论的财产分配问题。
财产分配问题是一个NP完全复杂难度的组合数学问题【1】，其分配方案的个数为kn, 对人和计算机而言，这很容易产生一个天文数字。例如在财产数量n很大和分配人数k也很大的情况下，如果没有设计出有效的算法，即使用现在速度最快的巨型计算机运算，也可能导致几万亿年都无法计算出满意的结果。
因此，设计出有效的算法是解决这一问题的关键，本文结合贪心算法速度快和穷举算法精度高的特性，设计出一种速度快、精确程度高的实用算法策略，为解决这类NP完全问题提出一种实用有效的算法策略。
二 问题分析
问题描述：将n项价值分别为a1,a2,…,an的不可分割财产尽可能均匀分配给k个人，设k个人获得总价值分别为V1,V2,…,Vk，分配结果要求Vmax-Vmin最小。
这个问题的本质是把一个具有n个元素的集合尽可能均匀的划分成k个子集，并找到符合问题要求的子集划分结果【2】。显然，每一项财产都可以分给k个人的其中一个，有k种分法，那么n项财产全部分配完有kn种分法。k越大，这个数增长的越快，如果采用一般的穷举算法，并假设人1秒钟可以算1种分配情况，而微机1秒钟能算出109种分配情况，则不同n,k组合，所需要运算时间如表1所示。
从表中我们可以看出，要将100项财产均匀分配给5个人，没有经过优化的穷举算法会让微机运行远远超过1万亿年。
运用常规的分治算法、贪心算法、概率算法等高效算法求解此问题时，其得到结果的精确性往往难以满足要求。而运用穷举算法，虽然理论上一定可以得到最好的解，但是运算量却远远超过了计算机的运算能力。因此，如果能够将时间高效的算法和结果精确的算法进行结合，各取所长，将是一个不错的思考方向。
表1 不同n,k组合计算时间比较
穷举运算量kn人计算所需时间微机计算所需时间
n=10 k=210241024秒1.02微秒
n=20 k=33.49×109111年3.49秒
n=30 k=41.15×1018366亿年36.6年
n=100 k=57.89×10692.5×1062年2.5×1053年
n=500 k=101×103003.17×10292年3.17×10283年
三 两种算法思路
a．贪心算法
用Xi=t表示将第i（1≤i≤n）项财产分配给第t（1≤t≤k）个人,则分配过程中X向量记住了分配结果。其贪心算法思路如下：
①对n项财产进行递减排序，假设排序后财产价值分别为a1,a2,…,an，置i=1。
②选择财产ai,找出V1~Vk中最小者（假设为Vt,1≤t≤k），将相应财产ai分给第t个人，且置Vt=Vt+ai, Xi=t。
③i=i+1;如果i≤n，则继续②，否则算法结束。
上述算法思路用类C语言表达如下贪心算法。

贪心算法在分配过程中，总是将价值越来越小的财产分配给当前最少的人，即用价
值越来越小的财产去填补这k个人之间的差距，其时间复杂度为O（k*n）。
b．穷举算法
穷举算法中可以不用进行排序的预处理，其算法的最终实质就是计算财产的所有可能分配情况，其算法思路用类C语言递归表达如上穷举算法。
穷举算法必定可以找出所有分配方案中最符合要求的结果，但是其运算时间复杂度
为O（kn），当k、n达到一定数值时，机器无法运算出结果，即使算法中还可以大量优化，但是仍然无法解决根本问题。

两种算法对比，贪心算法运算量小速度快，只是结果可能存在误差，而穷举算法结果准确，但是运算量大速度慢，所以如果能够将两种算法有机的结合起来，将给这个问题带来非常实用的解决思路。
四 "贪心+穷举"算法
"贪心+穷举"的算法思想是：一部分财产采用贪心策略分配，另外一部分财产在贪心算法结果的基础上采用穷举算法。
具体过程思路如下：
①对n项财产进行递减排序，假设排序后财产价值分别为a1,a2,…,an，置i=1。
②对财产a1~aq依次进行贪心策略分配，即每一项分配给当前V1~Vk中最小者。
③对财产aq+1~an进行穷举分配，即在a1~aq已经分配的基础上，穷举aq+1~an所有可能的分配情况，找出最符合问题要求的结果。

其中步骤②可以直接调用上面贪心算法函数，即treed(q)；步骤③直接调用上面穷举
算法函数，即f(q+1)。用类C语言表达如下"贪心+穷举"算法。
此算法时间复杂度取决于这两个调用函数的时间复杂度，为O(k*q + k(n-q))=O(k(n-q))。可以看出此算法的时间复杂度取决于f(q+1)的函数调用，它对最后n-q项财产进行穷举分配。
假设微机的速度为109，对于一个k已知的问题，只要控制好穷举分配的礼物个数n-q大小，即可控制该算法在1秒钟内算出结果，表2数据是1秒钟可算出结果的k, n-q组合。
表2 微机1秒钟可算出的k, n-q组合
k235671013193263
n-q301913121198765
从表中数据可以看出，分配的人数k越大，可以用来穷举的财产个数n-q越小。这种贪心算法与回溯算法结合的解决思路，可以在时间可控的情况下算出比贪心算法更准确的结果。由于算法并没有穷举到所有分配情况，其运算结果在有些数据上可能存在误差，笔者对每一种n,k取值下随机产生的100组测试数据（随机产生财产价值控制在1到100之间），对每一组数据控制合适q取值，保证微机在1秒钟内计算完，对其结果进行分析并统计出表3所示结果。
表3 测试结果
n取值k取值贪心算法得到最优解的
百分比"贪心+穷举"算法得到最优解的百分比
30234%100%
30517%97%
60292%100%
100298%100%
100365%99%
100548%98%
200562%99%
1001035%42%
从测试结果中可以总结出如下规律：
①k固定时，财产数n越大，贪心算法结果越接近最优解。
②n固定时，分配人数k越大，贪心算法结果误差越大。
③在k≤7情况下，"贪心+穷举"算法结果与穷举算法得到的最优解几乎完全一致；而在k>=10情况下，"贪心+穷举"算法的结果误差比较大，准确率比贪心算法仅高出一点。
所以"贪心+穷举"算法的短板就是k较大时，由于要保证算法在1秒钟内结束使得穷举的财产个数n-q较小，从而使得穷举的部分对结果的影响变小。
五 结束语
本论文针对财产分配问题提出了一种融合各种算法进行"取长补短"式的解决思路，为这类NP难度问题提出一些有实用价值的解决办法。另外本文中的"贪心+穷举"算法，还可以与其它有某种特长的算法策略进行融合，这也是笔者正在研究的方向。
参考文献：
【1】 王晓东，计算机算法设计与分析，北京，电子工业出版社
【2】 高尚，候志远，集合划分问题的粒子群优化算法，江苏科技大学学报（自然科学版）
作者简介：刘芳，1982年生，女，武汉大学珞珈学院，讲师，主要研究电子商务应用问题。