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

《财产分配问题的一种算法策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、财产分配问题的一种算法策暁［摘要］财产分配问题是一个NP完全问题，设计有效的算法成为计算机解决这一问题的关键。本文结合贪心策略和穷举策略提出了一种运算量可控、近似程度非常高的算法，为计算机有效解决这类NP问题提出了一种思考方向。［关键词］贪心策略财产分配时间复杂度一、引言不管是口常生活中，还是计算机领域，我们都会经常碰到类似于财产分配的问题。例如，一批货物要尽可能均衡负载到几辆汽车或轮船上，“云计算”里一批分解出来的任务要均匀的分配到网络屮其它计算机上完成，都可以看成是耍将n项不能再分割的财产尽可能均匀分配给k个人的问题，这就是我们要

2、讨论的财产分配问题。财产分配问题是一个NP完全复杂难度的组合数学问题［1］,其分配方案的个数为kn,对人和计算机而言，这很容易产生一个天文数字。例如在财产数量n很大和分配人数k也很大的情况下，如果没有设计出有效的算法，即使用现在速度最快的口型计算机运算，也可能导致几万亿年都无法计算出满意的结果。因此，设计出有效的算法是解决这一问题的关键，本文结合贪心算法速度快和穷举算法精度高的特性，设计出一种速度快、精确程度高的实用算法策略，为解决这类NP完全问题提出一种实用有效的算法策略。二、问题分析问题描述：将n项价值分别为el,a2,…，em的

3、不可分割财产尽可能均匀分配给k个人，设k个人获得总价值分别为VI,V2,…，Vk,分配结果要求Vmax-Vmin最小。这个问题的本质是把一个具有n个元素的集合尽可能均匀的划分成k个子集，并找到符合问题要求的子集划分结果［2］。显然，每一项财产都可以分给k个人的其中一个，冇k种分法，那么n项财产全部分配完有kn种分法。k越大，这个数增长的越快，如果采用一般的穷举算法，并假设人1秒钟可以算1种分配情况，而微机1秒钟能算出109种分配情况，则不同n,k组合，所需要运算时间如表1所示。从表中我们可以看出，要将100项财产均匀分配给5个人，没有

4、经过优化的穷举算法会让微机运行远远超过1力亿年。运用常规的分治算法、贪心算法、概率算法等高效算法求解此问题时,其得到结果的精确性往往难以满足要求。而运用穷举算法，虽然理论上一定可以得到最好的解，但是运算量却远远超过了计算机的运算能力。因此,如果能够将时间高效的算法和结果精确的算法进行结合，各取所长，将是一个不错的思考方向。表1：不同n,k组合计算时间比较三、两种算法思路a.贪心算法用Xi二t表示将第i(lWiWn)项财产分配给第t(lWtWk)个人,则分配过程中X向量记住了分配结果。其贪心算法思路如下：%1对n项财产进行递减排序，假设

5、排序后财产价值分别为al,a2,…,an,置i二1。%1选择财产ai,找出VI〜Vk中最小者(假设为Vt,lWtWk),将相应财产ai分给第t个人，且置Vt=Vt+ai,Xi=to%1i二i+1；如果iWn,则继续②，否则算法结束。上述算法思路用类C语言表达如下贪心算法。贪心算法在分配过程中，总是将价值越來越小的财产分配给当前最少的人，即用价值越来越小的财产去填补这k个人之间的差距，其时间复杂度为0(k*n)ob.穷举算法穷举算法中可以不用进行排序的预处理，其算法的最终实质就是计算财产的所冇可能分配情况，其算法思路用类C语言递归表达如

6、上穷举算法。穷举算法必定可以找出所有分配方案中最符合要求的结果，但是其运算时间复杂度为O(kn),当k、n达到一定数值时，机器无法运算出结果,即使算法中还可以大量优化，但是仍然无法解决根本问题。两种算法对比，贪心算法运算量小速度快，只是结果可能存在误差，而穷举算法结果准确，但是运算量大速度慢，所以如果能够将两种算法冇机的结合起来，将给这个问题带来非常实用的解决思路。四、“贪心+穷举”算法“贪心+穷举”的算法思想是：一部分财产采用贪心策略分配，另外一部分财产在贪心算法结果的基础上采用穷举算法。具体过程思路如下：%1对n项财产进行递减排序

7、，假设排序后财产价值分别为al,a2,…,an,置i二1。%1对财产al~aq依次进行贪心策略分配，即每一项分配给当前VI〜Vk中最小者。%1对财产aq+1〜an进行穷举分配，即在al〜aq已经分配的基础上,穷举aq+l~an所有可能的分配情况，找出最符合问题要求的结果。其中步骤②可以直接调用上面贪心算法函数，即treed(q)；步骤③直接调用上面穷举算法函数，即f(q+1)。用类C语言表达如下“贪心+穷举”算法。此算法时间复杂度取决于这两个调用函数的时间复杂度，为()(k*q+k(n-q))=0(k(n-q))o可以看出此算法的时间

8、复杂度取决于f(q+1)的函数调用，它对最后n-q项财产进行穷举分配。假设微机的速度为109,对于一个k已知的问题，只要控制好穷举分配的礼物个数n-q大小，即可控制该算法在1秒钟内算出结果，表2数据是1秒钟可算出结果的k