資源分配算法的比較和研究

摘要：許多領域都涉及資源分配問題，怎樣合理的把各種有限的經濟資源分配給企業內各生產部門，使得本企業在相對較低的成本投入下得到較大利潤是每一個企業所追求的目標。于是就產生了如何分配以使工程目標或生產目的達到最優的問題。本文針對這一類資源分配問題，闡述了用動態規劃方法和多段圖方法的求解思想，并通過實例比較了兩種算法。

關鍵詞：資源分配，動態規劃，多段圖

中圖分類號：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項工程可獲利潤Ｎ(i，j).把資源分配給這n個項目，要求使總利潤達最大的方法 ．問題可用一個(n+1)段圖來表示．以段i對應工程項目i（1≤i≤n )，源點S＝V(0，0)，匯點t＝Ｖ（n+1，m），每段有m+1個頂點Ｖ(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格式閱讀原文?！?/p>