资源分配算法的比较和研究

摘要：许多领域都涉及资源分配问题，怎样合理的把各种有限的经济资源分配给企业内各生产部门，使得本企业在相对较低的成本投入下得到较大利润是每一个企业所追求的目标。于是就产生了如何分配以使工程目标或生产目的达到最优的问题。本文针对这一类资源分配问题，阐述了用动态规划方法和多段图方法的求解思想，并通过实例比较了两种算法。

关键词：资源分配，动态规划，多段图

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)12-20ppp-0c

Comparison and Research for Resource Allocation Algorithm

FAN Chao, ZHU Zhan-li

(School of Computer Science, Xi'an Shiyou University, Xi'an 710065, China)

Abstract: Many fields involving the allocation of resources, how to allocate various kinds of limited economic resources reasonably to production department, and making enterprises get higher profit at lower input costs is the goal for every enterprise.So,the problem of how to allocate recourse to make the project target or the aim of production optimization was brought out. This paper focuses attention on this kind of resource allocation ,and discusses the method of using Dynamic Programming and Multistage Graph., Then, using examples compare these two algorithms.

Key words: resource allocation; Dynamic Programming; Multistage Graph

1 引言

资源分配问题是现实中存在的一种决策问题，例如各类工程预算、自然科学基金资助项

目的评审都可以看作资源分配问题来求解。本文定义的资源分配问题是将一定量的资源分配给若干工程以获得最大效益，这类分配问题满足一定的条件：待分配的资源是有限的；资源分配给不同的工程所创造的效益是不同的。

动态规划和多段图是解决资源分配的两种方法。动态规划将活动过程划分为若干个阶段，每一阶段的决策，依赖于前一阶段的状态，由决策所采取的动作，使状态发生转移，成为下一阶段的决策依据。最优性原理：无论过程的初始状态和初始决策是什么，其余决策都必须相对于初始决策所产生的状态，构成一个最优决策序列。

令最优状态为S(2,22)，由此倒推：S(2,22)―>p(2,22)―>S(1,2)―>p(1,2)―>S0，最优决策序列，p(1,2)―> p(2,22)，状态转移序列：S0―>S(1,2)―> S(2,22)，赖以决策的策略或目标，称为动态规划函数。整个决策过程，可以递归地进行，或用循环迭代的方法进行。动态规划函数可以递归地定义，也可以用递推公式来表达。最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；而决策的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向后递归或迭代，直到最终结果。

有向连通赋权图G=(V,E,W)，顶点集合V划分成k个不相交的子集Vi，1≤i≤k，k≥2，使得 中的任一边(u,v)，必有u∈Vi，V∈Vi+m，m≥1。称为多段图。令|V1|=|Vk|=1，称S∈V1为源点，t∈Vk为收点。多段图的最长路径问题，是求从源点S到达收点t的最大花费的通路。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点S的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。

下面将分别用上述两种方法解决一个资源分配问题。

2 动态规划法

资源r划分为m个相等的部分，每份资源为t/m，m为整数。利润函数Gi(x),1≤i≤n,0≤x≤m： x份资源分配给第i个工程所得到的利润，已知分配m份资源给所有工程，所得到的利润总额为：

fc03.tif

使G(m)最大的xi分配方案：(x1,x2,…,xn) 各个工程按顺序编号，fi(x)：把x份资源分配给前i个工程时，所得到的最大利润，di(x)：使fi(x)最大时，分配给第i个工程的资源份额。

在第一阶段，只把x份资源分配给第一个工程，有：

在第二阶段，只把x份资源分配给前面两个工程，有：

一般的，在第i阶段，把x份资源分配给前面i个工程，有：

令第i阶段的最大利润为gi，则：

gi=max{fi(1),…,fi(m)} （3）

设qi是使gi达最大时，分配给前面i个工程的资源份额，则：

qi=使fi(x)达最大的x （4）

在每个阶段，把所得到的所有局部决策值fi(x), di(x),gi,qi保存起来。最后，在第 阶段结束之后，令全局的最大利润为optg，则：

optg=max{gi ,…,gn} （5）

在全局最大利润下，所分配工程项目的最大编号（即所分配工程项目的最大数目）为k，则：

k=使gi达最大的i （6）

分配给前面k个工程的最优份额为：

optx=与最大的gi相对应的qi （7）

分配给第k个工程的最优份额为：

optqk=dk(optx)

分配给其余k-1个工程的剩余的最优份额为：

optx=optx-dk(optx)

由此回溯，得到分配给前面各个工程的最优份额的递推关系式：

由上面的决策过程，可以把求解资源分配问题，划分为下面四个步骤：①按(1)(2)式，对各个阶段i，各个不同份额x的资源，计算fi(x)及di(x)；②按(3)(4)式，计算各个阶段的最大利润gi，及获得此最大利润的分配份额qi；③按(5)(6)(7)式，计算全局的最大利润optg，总的最优分配份额optx,及编号最大的工程项目k；

例：有4个份额的资源，分配给3个工程，其利润函数如下：

求资源的最优分配方案。

解：在第一阶段，只把资源的份额分配给第一个工程，由(1)式，有：

其次，把资源的份额分配给前面两个个工程

同样，计算出f3(x)及d3(x)的值，有：

第二步，按(3)(4)式，求各个阶段的最大利润，及在此利润下的分配份额，有：fc12.tif

第三步，按(5)(6)(7)式，计算全局的最大利润optg，最大的工程数目、及总的最优分配份额，有：optg=46, optx=4, k=3。

第四步，按(8)式计算各个工程的最优分配份额，有：fc13.tif

最后的决策结果：分配给第2、3工程各1个份额，第1个工程2个份额，可得最大利润46。

3 多段图法

如果把j个资源分配给第i项工程可获利润N(i,j).把资源分配给这n个项目,要求使总利润达最大的方法 ．问题可用一个(n+1)段图来表示．以段i对应工程项目i（1≤i≤n )，源点S＝V(0,0)，汇点t＝V（n+1，m），每段有m+1个顶点V(i,j),0≤j≤m，表示共把j个资源分配给了前i个工程的利润，图中所有的边都具有的形式(1≤i≤n,0≤j≤m),边表示N(i+1,j)的利润给工程V(i,j)获得的利润，最佳分配方案是从图中S到T的一条最大路径所确定。

数组元素cost[i]：存放顶点i到达收点t的最小花费数组元素path[i]：存放顶点i到达收点t的最小花费通路上的前方顶点编号数组route[n]：存放从源点S出发，到达收点t的最长通路上的顶点编号第一阶段，确定第k-1段的所有顶点到达收点t的花费最大的通路。

第二阶段，用第一阶段的信息，确定第k-2段的所有顶点到达收点t的花费最大的通路。

如此依次进行，直到最后确定源点S到达收点 的花费最大的通路。最后，从源点S的path信息中，确定它的前方顶点编号p1，从p1的path信息中，确定p1的前方顶点编号p2，如此递推，直到收点r。

path[i]=使Cij+cost[j]最小的j,i

算法步骤：①对所有的i,0≤i≤n，把cost[i]初始化为最大值，path[i]初始化为-1；cost[n-1]初始化为0；②令i=n-2；③根据（1）式和（2）式计算cost[i]和path[i]；④ i=i-1，若i≥0，转3；否则，转5；⑤令i=0，route[i]=0；⑥如果route[i]=n-1，算法结束；否则，转7；⑦i=i+1，route[i]=path[route[i-1]]；转6；

由于没有第4个工程，所以给第4个工程分几份资源所创造的利润都是0。

最后，得到最大利润的路径a,d,j,p,q，利润为46，分配个第1个工程2个份额，分配给第2,3工程各1个份额。

4 结束语

动态规划法和多段图法是是解决资源分配问题的两种算法，经过实例计算，两种算法均可得到资源分配的最优解。动态规划算法先计算各个阶段在各种不同份额下的利润，然后计算各个阶段的最大利润gi，及获得此最大利润的分配份额qi；最后计算全局的最大利润optg，总的最优分配份额optx,及编号最大的工程项目k。若工程数为n,资源数为m，资源分配算法的时间复杂性是O(nm2)，空间复杂性是O(nm)。多段图算法在初始化后进行分段决策，分别计算各个顶点到收点的最大利润，确定各个顶点到收点的最大利润路径的前方顶点，因为顶点根据多段图的不相交子集顺序预先按照字母编号，字母顺序靠后的顶点首先计算，保证了在对每一个顶点进行决策和计算时，其到收点路径上的所有前方顶点都已计算和决策完毕，所以可直接利用前方顶点的信息，进行全局的最优决策时，首先从源点开始，递推的确定其前方顶点，直到收点为止，多段图算法时间复杂性：O(n+M)，空间复杂性是O(n)。动态规划算法在工程数和资源数比较小的情况下可以较快的得到最优解，在工程数和资源数都较大的情况下，动态规划算法在空间和时间复杂性上都比多段图算法复杂，利用多段图算法求解资源的最佳分配可以较快的获得结果。

参考文献：

[1] 郑宗汉,郑晓明.算法分析与设计[M].北京:清华大学出版社,2005.

[2] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社,2007.

[3] 朱站立.数据结构[M].西安：西安交通大学出版社，2005.

[4] 霍红卫.算法设计与分析[M].西安：西安电子大学出版社,2005.

[5] 魏宝刚,陈越,王申康.数据结构与算法分析（C语言版）[M].浙江：浙江大学出版社,2006.

[6] （美）塞奇威克.算法分析导论[M].北京：机械工业出版社,2006.

收稿日期：2008-01-12

作者简介：樊超（1983-），男，陕西西安人，在读研究生，研究方向：人工智能与专家系统。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”