论文部分内容阅读
[摘要]财产分配问题是一个NP完全问题，设计有效的算法成为计算机解决这一问题的关键。本文结合贪心策略和穷举策略提出了一种运算量可控、近似程度非常高的算法，为计算机有效解决这类NP问题提出了一种思考方向。
[关键词]贪心策略 财产分配 时间复杂度
一、引言
不管是日常生活中，还是计算机领域，我们都会经常碰到类似于财产分配的问题。例如，一批货物要尽可能均衡负载到几辆汽车或轮船上，“云计算”里一批分解出来的任务要均匀的分配到网络中其它计算机上完成，都可以看成是要将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组合计算时间比较
三、两种算法思路
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组合
从表中数据可以看出，分配的人数k越大，可以用来穷举的财产个数n-q越小。这种贪心算法与回溯算法结合的解决思路，可以在时间可控的情况下算出比贪心算法更准确的结果。由于算法并没有穷举到所有分配情况，其运算结果在有些数据上可能存在误差，笔者对每一种n，k取值下随机产生的100组测试数据（随机产生财产价值控制在1到100之间），对每一组数据控制合适q取值，保证微机在1秒钟内计算完，对其结果进行分析并统计出表3所示结果。
表3：测试结果
从测试结果中可以总结出如下规律：
①k固定时，财产数n越大，贪心算法结果越接近最优解。
②n固定时，分配人数k越大，贪心算法结果误差越大。
③在k≤7情况下，“贪心+穷举”算法结果与穷举算法得到的最优解几乎完全一致；而在k>=10情况下，“贪心+穷举”算法的结果误差比较大，准确率比贪心算法仅高出一点。
所以“贪心+穷举”算法的短板就是k较大时，由于要保证算法在1秒钟内结束使得穷举的财产个数n-q较小，从而使得穷举的部分对结果的影响变小。
五、结束语
本论文针对财产分配问题提出了一种融合各种算法进行“取长补短”式的解决思路，为这类NP难度问题提出一些有实用价值的解决办法。另外本文中的“贪心+穷举”算法，还可以与其它有某种特长的算法策略进行融合，这也是笔者正在研究的方向。
本文系2012年武汉大学珞珈学院教学研究项目（编号：武大珞珈教字[2011]118号）的研究成果之一）
[参考文献]
[1]王晓东.计算机算法设计与分析，北京，电子工业出版社
[2]高尚，候志远.集合划分问题的粒子群优化算法，江苏科技大学学报（自然科学版）
（作者单位：武汉大学珞珈学院）
[关键词]贪心策略 财产分配 时间复杂度
一、引言
不管是日常生活中，还是计算机领域，我们都会经常碰到类似于财产分配的问题。例如，一批货物要尽可能均衡负载到几辆汽车或轮船上，“云计算”里一批分解出来的任务要均匀的分配到网络中其它计算机上完成，都可以看成是要将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组合计算时间比较
三、两种算法思路
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组合
从表中数据可以看出，分配的人数k越大，可以用来穷举的财产个数n-q越小。这种贪心算法与回溯算法结合的解决思路，可以在时间可控的情况下算出比贪心算法更准确的结果。由于算法并没有穷举到所有分配情况，其运算结果在有些数据上可能存在误差，笔者对每一种n，k取值下随机产生的100组测试数据（随机产生财产价值控制在1到100之间），对每一组数据控制合适q取值，保证微机在1秒钟内计算完，对其结果进行分析并统计出表3所示结果。
表3：测试结果
从测试结果中可以总结出如下规律：
①k固定时，财产数n越大，贪心算法结果越接近最优解。
②n固定时，分配人数k越大，贪心算法结果误差越大。
③在k≤7情况下，“贪心+穷举”算法结果与穷举算法得到的最优解几乎完全一致；而在k>=10情况下，“贪心+穷举”算法的结果误差比较大，准确率比贪心算法仅高出一点。
所以“贪心+穷举”算法的短板就是k较大时，由于要保证算法在1秒钟内结束使得穷举的财产个数n-q较小，从而使得穷举的部分对结果的影响变小。
五、结束语
本论文针对财产分配问题提出了一种融合各种算法进行“取长补短”式的解决思路，为这类NP难度问题提出一些有实用价值的解决办法。另外本文中的“贪心+穷举”算法，还可以与其它有某种特长的算法策略进行融合，这也是笔者正在研究的方向。
本文系2012年武汉大学珞珈学院教学研究项目（编号：武大珞珈教字[2011]118号）的研究成果之一）
[参考文献]
[1]王晓东.计算机算法设计与分析，北京，电子工业出版社
[2]高尚，候志远.集合划分问题的粒子群优化算法，江苏科技大学学报（自然科学版）
（作者单位：武汉大学珞珈学院）