前言：中文期刊網精心挑選了動態(tài)規(guī)劃思想范文供你參考和學習，希望我們的參考范文能激發(fā)你的文章創(chuàng)作靈感，歡迎閱讀。

動態(tài)規(guī)劃思想范文1

關鍵詞：物流產業(yè)；動態(tài)規(guī)劃；資源優(yōu)化

中圖分類號：F259.22 文獻標識碼：A

Abstract： Dynamic programming is the way to improve the allocation of logistics resources. The theory and method should be regarded as the key to solve the optimization problem of logistics resources for the industry supply chain and enterprise cost and efficiency. This paper classified the research on the dynamic programming of the logistics industry in China into several types and did an overall analysis of the relative research results in this area from two perspectives： one is the macro logistics industry， and the other is the designated link in the process. In addition， an review was given on the research contents， methods and characteristics after consulting a large quantity of related literature with the hope to facilitate the future studies.

Key words： logistics industry； dynamic programming； resource optimization

0 引 言

現代物流業(yè)是支撐國民經濟發(fā)展的基礎性、戰(zhàn)略性產業(yè)[1]，具有巨大的市場空間和發(fā)展?jié)摿ΑＮ锪鳂I(yè)是融合倉儲、配送、運輸、貨代、信息等的復合型服務業(yè)，隨著國家“一帶一路”戰(zhàn)略的實施，物流業(yè)也迎來重大的發(fā)展機遇。動態(tài)規(guī)劃是運籌學中一種研究多階段決策問題的理論和方法[2]，無論是對于物流行業(yè)中供應鏈的優(yōu)化，還是對于企業(yè)內部物流成本和效率的優(yōu)化，這種理論和方法都為企業(yè)的管理決策提供了不同層面的支持。因此，動態(tài)規(guī)劃理論和應用研究成為當前物流領域解決供應鏈效率低下、保障資源有效配置的熱點。本文通過對相關文獻的研究，分析了動態(tài)規(guī)劃在我國物流產業(yè)的應用研究現狀，為學者的進一步研究探索提供便利。

1 國內外動態(tài)規(guī)劃在物流產業(yè)的研究概況

近年來，動態(tài)規(guī)劃在物流產業(yè)的研究呈現上升趨勢，本文采用文獻檢索的方法對國內外公開發(fā)表的動態(tài)規(guī)劃在物流產業(yè)研究的相關文獻進行統計整理。

通過ELSEVIER公司的Science Direct數據庫，使用“Dynamic programming of goods”、“Logistics dynamic programming”和“Transportation dynamic programming”三個檢索詞進行檢索，檢索情況見表1。

使用清華同方數據庫和萬方數據庫，利用“物流動態(tài)規(guī)劃”、“運輸動態(tài)規(guī)劃”、“貨物動態(tài)規(guī)劃”、“物流資源優(yōu)化”、“交通運輸優(yōu)化”和“貨物倉儲優(yōu)化”六個關鍵詞進行檢索，檢索情況見表2。

由表1、表2統計的結果可以看出，國內對動態(tài)規(guī)劃在物流產業(yè)的研究要多于國外，這與當前國內物流業(yè)的快速發(fā)展是分不開的。從以上的研究文獻來看，主要可以將研究分為兩個主要部分，一是動態(tài)規(guī)劃在宏觀物流產業(yè)的研究；二是針對物流過程中某個環(huán)節(jié)，如庫存采購、物流配送、倉庫選址過程中的物流資源進行配置優(yōu)化研究。

2 動態(tài)規(guī)劃在宏觀物流產業(yè)的應用研究

針對動態(tài)規(guī)劃在宏觀物流產業(yè)的問題進行研究主要分為：企業(yè)物流資源研究、行業(yè)物流資源研究、特定背景物流資源研究三個方面。

（1）企業(yè)物流資源研究。天津大學的趙雙記[3]以寶碩化工供應鏈系統為研究對象，從采購、庫存、生產三個方面入手，解決寶碩化工現存生產與庫存之間的矛盾問題。無錫商業(yè)職業(yè)技術學院的潘珩[4]對企業(yè)生產物流進行了研究，運用動態(tài)規(guī)劃的方法，針對企業(yè)的生產物流和多種產品，提供了優(yōu)化的分析和運算方法。哈爾濱理工大學的劉虹等人[5]根據企業(yè)的物流優(yōu)化模型，提出一種新的矩陣運算的動態(tài)規(guī)劃算法，更好地解決了企業(yè)對單個用戶的供應鏈優(yōu)化。

（2）行業(yè)物流資源研究。大連海事大學的邊展[6]通過分析海運行業(yè)港口集裝箱堆場的相關操作事宜，以提高裝卸效率為目標優(yōu)化了集裝箱的裝船順序。黃岡職業(yè)技術學院的張孝忠、周慧蘭，北京交通大學的董祥俊等[7]針對鐵路行業(yè)的物資管理的特點，提出通過建立動態(tài)規(guī)劃模型來變更存儲設施選址的方法，降低了鐵路施工企業(yè)物資運輸和其他相關成本。華中科技大學的馬士華等[8]通過考察公路運輸行業(yè)中供應鏈物流運作能力的多項指標，對達到最優(yōu)物流能力的最小物流成本進行了研究。

（3）特定背景物流資源研究。物流行業(yè)的特定背景非常多樣，本文針對其中的應急物流、回收物流和不同生命周期物流進行簡要總結。

北京交通大學的英升賀等人[9]針對應急物流的物資配送特征，建立了受災地區(qū)接收點和非受災地區(qū)發(fā)送點之間的配送網絡。武漢理工大學的余浩然[10]利用多周期動態(tài)規(guī)劃理論對再制造物流的設施選址和流量分配進行了著重研究，實現了節(jié)約和環(huán)保的生產理念。上海交通大學的佘小川等人[11]分析了產品在不同生命周期情況下采取的不同市場戰(zhàn)略，并在此基礎上利用動態(tài)規(guī)劃方法對物流成本最小化問題進行了研究。

從這些角度進行研究的文獻來看，對于動態(tài)規(guī)劃在宏觀物流產業(yè)的研究呈現了以下特征：一是研究側重于定性分析，對物流產業(yè)進行理論研究探索；二是側重于定量分析，運用運籌學中的動態(tài)規(guī)劃方法和計算機模擬仿真技術來建立優(yōu)化模型。隨著計算機和物聯網技術的快速發(fā)展，第二個特征日益突出。

3 動態(tài)規(guī)劃在物流環(huán)節(jié)的應用研究

對物流過程中某個環(huán)節(jié)的動態(tài)規(guī)劃研究主要是通過庫存采購環(huán)節(jié)、物流配送環(huán)節(jié)和倉庫選址環(huán)節(jié)三個方面進行了研究。

（1）庫存采購環(huán)節(jié)。長春理工大學的王景恒[12]建立了配送中心的貨物裝卸搬運模型，利用動態(tài)規(guī)劃方法求解，并通過實例證明了模型的可行性及實用性。常州輕工職業(yè)技術學院的施新平[13]通過分析汽車動態(tài)庫存服務方法，構造了以時間為函數的動態(tài)物流庫存管理模型，促進了企業(yè)庫存管理能力和創(chuàng)新服務能力。曲阜師范大學的徐健騰[14]利用組合最優(yōu)化理論分別對單一產品多斷點、單斷點和易腐產品的經濟批量問題進行研究。

（2）物流配送環(huán)節(jié)。對外經濟貿易大學的周森[15]利用自然數序列來編碼，以遺傳算法為依托來解決車輛的路徑優(yōu)化問題，得到了低于案例成本的方案。山東經濟學院的袁杰[16]提出了先分配車輛后指派車輛的處理思路，利用動態(tài)規(guī)劃方法和蟻群算法為目標分配車輛，實現了將最短車輛路徑問題向最優(yōu)客戶問題的轉化。重慶大學的陶波[17]通過研究B2C電子商務企業(yè)的物流配送，建立整數規(guī)劃的最短路徑模型，并利用動態(tài)規(guī)劃法為理論求解并得到質量較高的解。重慶郵電大學的任志霞[18]利用運籌學方法和計算機技術分別對0-1規(guī)劃問題、背包問題和路線優(yōu)化問題進行研究，為配送環(huán)節(jié)提供幫助。

（3）倉庫選址環(huán)節(jié)。南昌大學的胡章云[19]通過考慮供應商的供應量、客戶的需求量及配送時間等因素，建立了不確定環(huán)境下配送中心的動態(tài)選址模型，利用動態(tài)規(guī)劃思想來支持長期的動態(tài)選址決策。武漢理工大學的徐利民等人[20]針對不考慮時間因素的靜態(tài)選址，提出了運用動態(tài)規(guī)劃求解的思想，并結合實例分析了加入時間變量后企業(yè)如何做出選址決策。東北大學的陳冰冰[21]利用一個企業(yè)的數據進行實例分析，建立了雙層規(guī)劃和動態(tài)規(guī)劃相結合的物流中心選址模型。浙江師范大學的卓婧婧等人[22]基于樹型動態(tài)規(guī)劃來簡化配送網絡，提出較之傳統動態(tài)規(guī)劃、層次分析法等更有優(yōu)勢的選址算法。

以上三個研究方向的研究成果各有特點：庫存采購環(huán)節(jié)的研究主要集中在庫存管理能力、裝卸搬運方法和經濟批量等問題的優(yōu)化；物流配送環(huán)節(jié)的研究主要是針對最短路徑的優(yōu)化和計算；倉庫選址環(huán)節(jié)的研究則集中于在考慮不同因素情況下對最佳選址模型的建立。這些研究主要采用動態(tài)規(guī)劃和其他輔助方法來建立模型或者求解，部分利用計算機技術進行仿真或者以實例驗證。理論指導性較強，但實踐指導性較弱。

4 國內動態(tài)規(guī)劃在物流產業(yè)的研究展望

通過以上對國內動態(tài)規(guī)劃在物流產業(yè)研究的相關文獻綜述可以看出，研究既有理論方法的探索、配置模型的構建，也有與特定背景結合的探討，研究態(tài)勢多元化。本文認為，動態(tài)規(guī)劃在物流產業(yè)的研究可以重點從以下幾個方面進一步展開：

（1）結合我國供應鏈體系，將動態(tài)規(guī)劃運用到生產、倉儲、銷售、配送等整個供應鏈中，以供應鏈整體優(yōu)化為目標，促進物流資源的整合優(yōu)化。

（2）結合我國信息技術的發(fā)展情況，研究物聯網、云計算、大數據、移動互聯網等先進的信息技術在物流領域的應用，利用信息技術手段進行動態(tài)規(guī)劃整合。

（3）結合我國“一帶一路”的發(fā)展戰(zhàn)略，按照我國物流業(yè)的發(fā)展狀況、物流基礎設施水平以及市場需求等，在戰(zhàn)略層面對我國物流環(huán)境進行規(guī)劃研究。

5 結束語

綜上所述，動態(tài)規(guī)劃在物流產業(yè)的應用是現代物流管理研究的重點，對該問題的研究具有理論價值和現實意義。希望本文對動態(tài)規(guī)劃在我國物流產業(yè)應用研究的相關文獻的總結分析，能夠為我國物流行業(yè)和物流企業(yè)提供幫助，為相關研究人員提供參考。

參考文獻：

[1] 國務院. 物流業(yè)發(fā)展中長期規(guī)劃（2014―2020年）[Z]. 2014.

[2] 黃立君. 動態(tài)規(guī)劃在企業(yè)運輸物流中的應用研究[J]. 赤峰學院學報，2009（3）：98-100.

[3] 趙雙記. 基于動態(tài)供應鏈管理的寶碩化工流程分析與研究[D]. 天津：天津大學（碩士學位論文），2005.

[4] 潘珩. 動態(tài)規(guī)劃方法在企業(yè)生產物流控制中的應用研究[J]. 物流技術，2004（4）：72-73.

[5] 劉虹，孫金梅，陳德運. 一種基于供應鏈的動態(tài)規(guī)劃算法[J]. 哈爾濱理工大學學報，2003（2）：122-124.

[6] 邊展. 基于混合動態(tài)規(guī)劃的集裝箱裝船順序優(yōu)化[D]. 大連：大連海事大學（碩士學位論文），2012.

[7] 張孝忠，周慧蘭，董祥俊，等. 動態(tài)選址在鐵路施工企業(yè)物資管理中的應用[J]. 經營管理，2007（7）：49-51.

[8] 馬士華，申文. 供應鏈物流運作能力計劃模型與分析[J]. 中國管理科學，2007（8）：83-88.

[9] 英升賀，李毅鑫. 動態(tài)規(guī)劃和整數規(guī)劃在應急物流物資配送優(yōu)化中的應用研究[J]. 物流技術，2009（8）：80-83.

[10] 余浩然. 再制造物流網絡多周期動態(tài)規(guī)劃模型研究[D]. 武漢：武漢理工大學（碩士學位論文），2012.

[11] 佘小川，季建華. 基于產品生命周期的物流系統動態(tài)規(guī)劃研究[J]. 科技進步與對策，2006（5）：102-104.

[12] 王景恒. 物流中心貨物最優(yōu)配裝問題的動態(tài)規(guī)劃解法[J]. 長春理工大學學報，2004（3）：9-11.

[13] 施新平. 基于動態(tài)汽車庫存管理的物流企業(yè)創(chuàng)新服務分析[J]. 物流技術，2014（5）：316-318.

[14] 徐健騰. 組合最優(yōu)化在庫存管理中的應用[D]. 曲阜：曲阜師范大學（碩士學位論文），2007.

[15] 周森. 基于遺傳算法的物流運輸中的車輛路徑研究[D]. 北京：對外經濟貿易大學（碩士學位論文），2006.

[16] 袁杰. 基于蟻群算法的多車場車輛路徑問題研究[D]. 濟南：山東經濟學院（碩士學位論文），2010.

[17] 陶波. 基于最短路徑算法的物流配送車輛優(yōu)化調度的研究[D]. 重慶：重慶大學（碩士學位論文），2009.

[18] 任志霞. 物流配送系統中的運籌學問題及方法研究[J]. 物流科技，2007（3）：10-12.

[19] 胡章云. 不確定環(huán)境下的城市配送中心動態(tài)選址研究[D]. 南昌：南昌大學（碩士學位論文），2013.

[20] 徐利民，馬良成，方芳. 倉儲中心的動態(tài)規(guī)劃選址及應用[J]. 武漢理工大學學報，2003（4）：256-259.

動態(tài)規(guī)劃思想范文2

關鍵詞：動態(tài)規(guī)劃；編程；技巧

中圖分類號：J954 文獻標識碼：A 文章編號：1007-9599 （2012） 16-0000-02

首先，第一類動態(tài)規(guī)劃的題目。這類問題往往直接采用遞推的方式從前往后一步步記錄下每一步的結果，最后得出問題的解就可以了。我們來看一個例子：

“數字三角形問題”。問題的大意是：給定一個由n行數字組成的數字三角形，如下面所示。試設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。

5（行數）

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

這道題很明顯要用動態(tài)規(guī)劃算法求解。假設我們要求第i行的最大值，怎么求呢？可能有的人會找每一行最大的數，但這樣是行不通的，因為我們要找到一條路徑，也就是上一行與下一行選的數必須不能隔數字。那怎么辦呢？我們如果要找第i行的最大值，可以從第i-1行來找。對于第i行的每一個數字，通過選第i-1行中符合題目要求的數字，求出到該數的路徑的最大值。我們最后求出的第n行的最大值中求出最大的即可。

附上代碼（c語言）：

#include

int main（）

{

int n，i，j，max；

int num[120][120]；

int sum[120][120]；

scanf（"%d"，&n）；

for（i=1；i

{

for（j=1；j

{

scanf（"%d"，&num[i][j]）；

}

}

sum[1][1]=num[1][1]；

for（i=2；i

{

for（j=1；j

{

if（j==1）

{

sum[i][j]=sum[i-1][j]+num[i][j]；

}

else if（j==i）

{

sum[i][j]=sum[i-1][j-1]+num[i][j]；

}

else

{

if（sum[i-1][j-1]>sum[i-1][j]）

{

sum[i][j]=sum[i-1][j-1]+num[i][j]；

}

else

{

sum[i][j]=sum[i-1][j]+num[i][j]；

}

}

}

}

max=0；

for（i=1；i

{

if（sum[n][i]>max）

{

max=sum[n][i]；

}

}

printf（"%d＼n"，max）；

return 0；

}

其次，第二類動態(tài)規(guī)劃算法。這類動態(tài)規(guī)劃算法往往不像第一種那么直接往后遞推就可以了。這類問題往往要借助于前面求解過的子問題，而且不一定是剛剛求解過的子問題。其實這類問題有點分治法的意思，但是可以記錄下已經求解過的子問題的結果，不必再在后面的問題中求解一遍。我們來看一個典型的例子——“0-1背包問題”：

題目大意是，有一個背包容量為v，還有若干個寶物，第i個寶物的價值為v[i]，容量為w[i]。試設計一個算法，在背包容量范圍內，把總價值最大的寶物總和加入到背包內。數據輸入實例：

4（寶物個數） 6（背包容量）

1 4 （第一個寶物的容量和價值，下同）

2 6

3 12

2 7

這個問題怎么分析呢？我們假設已經裝到第i個寶物了，容量為m時最大價值為f[m]。那么這時最大的價值為多少呢？如果第i個寶物裝到了背包中，那么這時價值為f[m—w[i]]+v[i]，如果不裝呢，價值仍為f[m]。取其中最大值。這里求數組f的各個元素時，我們可能需要前面求過的子問題。

附上代碼（c語言）：

#include

int main（）

{

int dp[13000]，n，m；

int w[3500]，d[3500]，i，j；

scanf（"%d%d"，&n，&m）；

for（i=1；i

{

scanf（"%d%d"，&w[i]，&d[i]）；

}

memset（dp，0，sizeof（dp））；

for（i=1；i

{

for（j=m；j>=w[i]；j--）

{

if（dp[j]

{

dp[j]=dp[j-w[i]]+d[i]；

}

}

}

printf（"%d＼n"，dp[m]）；

return 0；

}

最后，我們來看第3類動態(tài)規(guī)劃問題。這類動態(tài)規(guī)劃牽涉到了數據結構的內容，對我們這部分的學習以及抽象出算法模型的能力有比較大的要求。我們必須先對這部分的數據結構有自己的理解和體會，然后才能用算法的知識求解這類問題。我們來看一個問題：

“加分2叉樹”。 設一個n個節(jié)點的二叉樹tree的中序遍歷為（l，2，3，…，n），其中數字1，2，3，…，n為節(jié)點編號。每個節(jié)點都有一個分數（均為正整數），記第j個節(jié)點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：

subtree的左子樹的加分× subtree的右子樹的加分+subtree的根的分數

若某個子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數。不考慮它的空子樹。

試求一棵符合中序遍歷為（1，2，3，…，n）且加分最高的二叉樹tree。要求輸出；

（1）tree的最高加分

（2）tree的前序遍歷

【輸入格式】

多組測試數組，對于每組：

第1行：一個整數n（n

第2行：n個用空格隔開的整數，為每個節(jié)點的分數（分數

【輸出格式】

第1行：一個整數，為最高加分（結果不會超過4，000，000，000）。

第2行：n個用空格隔開的整數，為該樹的前序遍歷。

【輸入樣例】

5

5 7 1 2 10

【輸出樣例】

145

3 1 2 4 5

這個問題就用到了2叉樹的知識。我們首先得對樹有一定的了解，必須了解樹的各種遍歷方式，先序遍歷，中序遍歷，后序遍歷。

先序遍歷，也叫先根遍歷，遍歷的順序是，根，左子樹，右子樹

中序遍歷，也叫中根遍歷，遍歷的順序是，左子樹，根，右子樹

后序遍歷，也叫后跟遍歷，遍歷的順序是，左子樹，右子樹，根

然后我們來分析這道題。

設節(jié)點d為最優(yōu)的根節(jié)點，那么可以把這棵樹分成[1，d-1]和[d+1，n]，這顆樹的加分為子樹[1，d-1]的加分與子樹[d+1，n]加分的乘積與d的加分的和，而[1，d-1]和[d+1，n]的加分也可也一定是最優(yōu)加分，所以這個題具有最優(yōu)子結構，那么可以用動態(tài)規(guī)劃。

設f[k，j]為子樹k到j的最高加分，求f[k，j]的最優(yōu)值，就要求f[1，d-1]和f[d+1，n]的最優(yōu)加分，那么枚舉根節(jié)點p，則有

f[k，j]的最優(yōu)值=f[k，p-1]*f[p+1，j]+v[p]（k

規(guī)劃方程為f[k，j]=max{f[k，p-1]*f[p+1，j]+v[p]}（k

動態(tài)規(guī)劃思想范文3

關鍵詞：管理運籌學; 生產管理; 戰(zhàn)略規(guī)劃; 利潤最大化

The Application of Management and Operations Research

In Enterprise Management of Business Operators

Abstract: With the development of enterprises and the extensive application of computers, management and operations research is playing an important role in production management and strategic planning of enterprise. The implementation of management and operations research in enterprise can reasonably arrange the allocation of human resources, material resources, capital resources and achieve the maximum profit for enterprise.

Key words: management and operations research; production management; strategic planning; maximum profit

1 管理運籌學概述

運籌學的思想在古代就已經產生了。敵我雙方交戰(zhàn)，要克敵制勝就要在了解雙方情況的基礎上，做出最優(yōu)的對付敵人的方法，這就是“運籌帷幄之中，決勝千里之外”的說法。

運籌學主要研究經濟活動和軍事活動中能用數量來表達的有關策劃、管理方面的問題。當然，隨著客觀實際的發(fā)展，運籌學的許多內容不但研究經濟和軍事活動，有些已經深入到日常生活當中去了。運籌學可以根據問題的要求，通過數學上的分析、運算，得出各種各樣的結果，最后提出綜合性的合理安排，已達到最好的效果[1]。

隨著科學技術和生產的發(fā)展，運籌學已滲入很多領域里，發(fā)揮了越來越重要的作用。運籌學本身也在不斷發(fā)展，現在已經是一個包括好幾個分支的數學部門了。比如：數學規(guī)劃（又包含線性規(guī)劃；非線性規(guī)劃；整數規(guī)劃；組合規(guī)劃等）、圖論、網絡流、決策分析、排隊論、可靠性數學理論、庫存論、對策論、搜索論、模擬等等[2]。

按照我過的學科分類，管理學下面分管理科學、工商管理學和宏觀管理與政策，而運籌學歸于管理科學里面。但是按照國際學界的觀點，有人認為運籌學是管理科學的一個分支，也有人則認為管理科學是運籌學的一個分支。按照大多數學者的觀點，我們這里將兩者作對等的概念來看待。但是為了不與工商管理混淆和簡便起見，我們用管理運籌學一詞代替管理科學和運籌學[3]。

在企業(yè)管理的領域中，運籌學發(fā)揮了其重要的作用，可以說，管理運籌學的產生，為企業(yè)實現其最終目標提供了最直觀可行的數學模型和理論指導。管理運籌學的主要研究內容包括：線性規(guī)劃的圖解法、線性規(guī)劃的計算機求解、線性規(guī)劃在工商管理中的應用、單純形法、單純形法的靈敏度分析與對偶、運輸問題、整數規(guī)劃、動態(tài)規(guī)劃、圖與網絡模型、排序與統籌方法、存儲論、排隊論、決策分析、預測等[4]。

運籌學的思想貫穿了企業(yè)管理的始終，它在企業(yè)戰(zhàn)略管理、生產計劃、市場營銷、運輸問題、庫存管理、人事管理、財務會計等各個方面都具有重要的作用[5]。

2 管理運籌學的研究方法

運籌學的研究方法有：1.從現實生活場合抽出本質的要素來構造數學模型，因而可尋求一個跟決策者的目標有關的解；2.探索求解的結構并導出系統的求解過程；3.從可行方案中尋求系統的最優(yōu)解法。

傳統的管理運籌學解決問題的方法一般可分為以下幾個步驟：確定目標、制定方案、建立模型、制定解法[6]。而現代管理運籌學的內容討論可以從以下幾個步驟著手：問題產生背景的分析―決策者的目標分析―確定決策目標―決策者可控要素分析―確定決策變量―決策者所受環(huán)境的限制（不可控要素分析）約束條件研究―建立運籌學模型[7]。

運籌學發(fā)展到今天，內容已相當豐富，研究方面也相當深入。其研究問題主要有以下特點[8]：

面向實際，從全局追求總體效益最優(yōu)；

借助于模型，用定量分析的方法，合理解決實際問題；

多學科專家集體協作研究；

計算機技術的發(fā)展為管理運籌學提供了新的契機,運籌學與計算機技術相結合,在現代管理信息系統的開發(fā)和應用中發(fā)揮著重要的作用,而管理信息系統是現代化管理不可或缺的組成部分。因此，運籌學在現代管理中具有相當重要的地位和作用，它是企業(yè)及公共事業(yè)機構管理者應當了界和掌握的一門科學[9]。在計算機參與的管理運籌學中，決策的過程可以分為：發(fā)現問題、分析問題、找出問題的關鍵點；羅列可供選擇的方案；確定解決問題的方案；建立模型，確定目標函數及約束條件；把所有數據轉換成計算機可識別的符號，輸入計算機；對答案進行修正；得到需要的符合實際的最優(yōu)解[4]。

在進行決策的分析時,可以運用兩種基本的分析方式：定性分析和定量分析。定性分析主要依賴于管理者的主管判斷和經驗，靠的是管理者的直覺，這種分析與其說是科學不如說是藝術。在進行決策時，如果管理者有相似的經歷，或遇到的問題比較簡單，也許應該首推這種分析方法。但是，如果管理者缺乏經驗或問題很復雜，定量分析方式就顯得非常重要，所以管理者在進行決策時應該予以充分重視。在運用定量分析的方法時，分析員應首先從問題中提取量化資料和數據，對其進行分析，再運用數學表達式的形式把問題的目標、約束條件和其他關系表達出來。最后，分析員依靠一種或多種定量的方法，提出建議，這種建議應該是建立在定量分析的基礎上的[10]。

3 多階段決策-動態(tài)規(guī)劃法闡述

經常會遇到復雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地采用把大問題分解成子問題，并綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規(guī)模呈冪級數增加。 為了節(jié)約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存于該數組中，這就是動態(tài)規(guī)劃法所采用的基本方法。這種方法主要研究計劃管理工作中有關有限資源的分配的問題，一般可以歸納為在滿足即定條件限制下，按某一衡量指標來尋求最優(yōu)方案的問題[11]。

在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實質是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產生一個全局最優(yōu)解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結果保存起來，避免每次碰到時都要重復計算。因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現大量的重復。動態(tài)規(guī)劃法的關鍵就在于，對于重復出現的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。

4 管理運籌學的實際應用舉例

在本例中，主要針對企業(yè)管理中的資源分配問題進行討論和研究，目標為實現企業(yè)資源分配的合理化和最優(yōu)化，為企業(yè)節(jié)省資源的同時，創(chuàng)造企業(yè)利潤的最大化。

4.1 模型知識點介紹

本例中的建立的模型屬于多階段決策，所采用的研究方法為動態(tài)規(guī)劃法。首先，對多階段決策所涉及到的理論知識作以介紹[12]。

① 階段：若干相互獨立的可排列的部分，一般用變量K來表示（K=1、2、3、4、5……….）。

② 狀態(tài)：在K階段初始時刻可能出現的客觀情況，用變量來表示。

③ 決策與策略：策略指單階段的策略集。若次階段為第K階段，那么第K階段的決策用V（）來表示。

④ 狀態(tài)轉移律：=T[，V（）] （其中，T是一個函數）。一般用表格、公式、函數（傳遞函數）來表示。

指標函數：（第K個階段的指標函數，一般可以指距離、效益等指標），=（，）。

過程指標函數：從第K個階段開始，一直到最終產生的結果（疊加），。

全過程指標函數：是最優(yōu)的。

過程指標函數的類型： 或

基本方程：，其中，或為min或為max

4.2 模型建立與求解

某公司下設有甲、乙、丙三個生產車間，現為完成一個特定目標，在一定的期限內生產出盡可能多的產品，爭創(chuàng)最大利潤，特新進5臺同樣的生產設備。現在要將這5臺生產設備根據各車間的生產情況進行分配，若將一臺分配給甲車間，可創(chuàng)造利潤3萬元，將一臺分配給乙車間，可創(chuàng)造利潤5萬元，將一臺分配給丙車間，可創(chuàng)造利潤4萬元；若將兩臺設備分配給甲車間，可創(chuàng)造利潤7萬元，將一臺分配給乙車間，可創(chuàng)造利潤10萬元，將一臺分配給丙車間，可創(chuàng)造利潤6萬元......依次類推，現將設備分配和相應所創(chuàng)造的利潤情況制成下表：

表1 設備分配及利潤表

從表中可以看出以下信息：

階段：3個

狀態(tài)變量：=5， 0＜≤5， 0＜≤5

策略和決策變量： ,

指標函數：（指結果，這里就是利潤）

狀態(tài)轉移：

基本方程具體求解步驟如下：

本算法遵循的原則是：算的時候倒著算，分的時候正著分。

由此，我們可以得出該資源分配模型的分配結果為：

第一種分配方法，給甲車間0臺設備，乙車間2臺設備，丙車間3臺設備，共為公司創(chuàng)造利潤為21萬元；

第二種分配方法，給甲車間2臺設備，乙車間2臺設備，丙車間1臺設備，共為公司創(chuàng)造利潤為21萬元。

5 結論

從以上的具體模型舉例可以看出，管理運籌學在企業(yè)管理中發(fā)揮著很大的作用，為企業(yè)的管理時間分配、人力資源分配、資金分配、資源分配等制定最合理的分配方式，從而企業(yè)可以根據這些計算出來的數據，并結合企業(yè)自身的實際情況制定企業(yè)管理戰(zhàn)略和生產規(guī)劃，以及對企業(yè)的市場營銷策劃都具有一定的指導作用。

動態(tài)規(guī)劃思想范文4

【關鍵詞】算法分析與設計 比較教學法 課程教學

【中圖分類號】G642 【文獻標識碼】A 【文章編號】2095-3089（2016）11-0111-02

一、引言

“算法分析與設計”是計算機科學與技術、軟件工程、信息管理與信息系統、醫(yī)學信息工程等計算機相關專業(yè)一門重要的專業(yè)課[1]，是計算機科學和計算機應用的核心課程之一。“算法分析與設計”是一門兼具理論性和實踐性的課程，其中部分教學內容具有一定的難度，需要在教學過程中適當引入一些先進和高效的教學方法。

比較教學法是一種對具有可比性的教學內容通過橫向和縱向比較，找出它們具有的相同點和不同點，讓學生在對比分析中學習和掌握所學內容的教學方法，它通過在教學活動中比較兩個或兩個以上的認識對象，分析它們存在異同，達到辨識、了解和把握認識對象的目的[2-3]。比較教學法有助于加深學生對知識的理解，建立相關知識之間的聯系，培養(yǎng)學生知識遷移應用和自主學習的能力。比較教學法在計算機類專業(yè)課程的教學中得到了較為廣泛的應用[4-5]。通過多年的教學實踐，我們發(fā)現比較教學法也可以很好地應用到“算法分析與設計”課程的教學過程中。

二、比較教學法的應用

在“算法分析與設計”課程中，可以從多個角度對教學內容進行比較，下面介紹幾種較為典型的應用情況。

1.同一算法求解不同問題的比較

對于某一種算法通常會有大量的應用實例，例如我們在動態(tài)規(guī)劃算法的教學過程中主要講解五個實例，包括最長公共子序列、矩陣鏈連乘、01背包問題、數字三角形和最長遞增子序列，通過使用動態(tài)規(guī)劃法求解這些問題，對比分析這幾個問題的解決步驟，很容易歸納總結出動態(tài)規(guī)劃求解問題的基本步驟，即分析最優(yōu)解結構、建立遞歸關系、計算最優(yōu)值和構造最優(yōu)解。動態(tài)規(guī)劃算法在求解問題時通常需要采用表格來保存子問題的解，不同的問題其表格的構造存在不同，但是都蘊含了自底向上求解問題的思想，通過對比分析不同問題的遞歸關系和算法結構，便于總結和整理動態(tài)規(guī)劃的特點，有助于學生更好地理解動態(tài)規(guī)劃算法。同時，通過比較教學法，可以更加深入理解動態(tài)規(guī)劃算法的基本步驟和原理，在比較分析的同時尋找這些問題的共同之處，更好地理解最優(yōu)子結構和重疊子問題這兩個動態(tài)規(guī)劃的基本要素。

在開展“算法分析與設計”教學時，我們還發(fā)現對于一些具體問題，使用同一種算法思想從不同的角度考慮可以設計出不同的算法，例如在講解分治算法時，快速排序和歸并排序都基于遞歸和分治思想，但是這兩種算法的實現過程完全不同，可以將二者結合一些經典的排序算法，例如冒泡排序、選擇排序和插入排序等進行比較，對比項包括時間復雜度、空間復雜度、排序的穩(wěn)定性等。通過比較，學生可以理解每一種排序算法的優(yōu)缺點，便于根據待解決問題的特點選擇合適的算法進行求解。

2.不同算法求解同一問題的比較

對于某些實際問題，有時候可以使用多種算法來求解，例如對于最長公共子序列問題，可以采用窮舉搜索法、備忘錄法、動態(tài)規(guī)劃法等多種方法，且不同的方法具有不同的特點，其實現過程也不盡相同。因此，針對某一問題，在教學過程中對比分析不同算法的特點，有助于學生更好地理解和掌握相關算法的原理。

在“算法分析與設計”課程教學中，主要講解分治算法、動態(tài)規(guī)劃算法、貪心算法、回溯法和分支限界法這五大算法。對于某些具體問題而言，可以采用這些算法中的兩種或多種來求解。以經典的背包問題為例，可以使用多種算法來求解背包問題，但是不同的算法在求解問題時存在較大的區(qū)別。例如采用最簡單的不考慮跳躍點的動態(tài)規(guī)劃法求解01背包問題時，要求物品的重量為整數，其適用性不強，可以通過跳躍點來改進;如果采用貪心算法，則不能求解01背包問題，因為得到的不一定是最優(yōu)解，貪心算法可以用于處理連續(xù)背包問題，對于01背包問題而言不適用;采用回溯法來求解雖然時間復雜度不及動態(tài)規(guī)劃，但是它是一種萬能解題法;也可以使用分支限界法來求解01背包問題，與回溯法的相同點在于都需要使用剪枝函數來刪除部分子樹，區(qū)別在于分支限界法采用廣度優(yōu)先搜索來搜索問題的解空間，而回溯法采用的是深度優(yōu)先搜索，因此在算法實現時回溯法和分支限界法需要使用不同的數據結構和代碼結構。

3.同一算法求解同一問題中不同實現方式的比較

有時候針對某一問題采用同一算法有不同的具體實現方案，例如在講解使用回溯法求解01背包問題時，重點在于教學生如何高效剪枝，在設計剪枝函數時引導學生主動思考，首先利用約束函數剪去左子樹，但時間復雜度仍然很高，然后設計限界函數剪去右子樹，最簡單的限界函數是直接將剩余物品的總價值與當前獲得的價值相加再與當前最優(yōu)值比較，如果小于當前最優(yōu)值，則剪去右子樹，更好的限界函數是計算得到右子樹的上界，如果將當前獲得的價值與右子樹價值的上界相加小于當前最優(yōu)值，則剪去右子樹，通過計算可以得到右子樹的精確上界，進一步對算法進行優(yōu)化。此外，在講解回溯法時，通過比較教學法，在分析具體實例時可以讓學生理解兩種典型的解空間樹的異同，遇到新的問題時根據問題的性質來確定是排列數還是子集樹，對于不同的解空間樹，有不同的算法框架。使用回溯法對解空間進行深度優(yōu)先搜索時，可以采用遞歸回溯，也可以采用迭代回溯，通過對代碼實例進行比較讓學生更好地理解和掌握兩種回溯方法的異同。

對于分支限界法，根據從活結點表中選擇下一個擴展結點的不同方式也存在不同的分支界限法的實現方式，最常見的有隊列式分支限界法和優(yōu)先隊列式分支限界法。在講解裝載問題等具體實例時，通過比較兩種不同的實現方法可以加深對這兩種實現方式的理解。

三、結語

比較教學法通過對比分析，尋找事物之間的聯系，分析待比較對象之間存在的異同，采用求同比較、求異比較、相似比較等形式，讓教學內容更加系統化、綜合化和條理化。在“算法分析與設計”課程教學過程中，通過對某些教學內容采用比較教學法，有助于培養(yǎng)學生整理和總結所學知識的能力，讓學生在面對新知識的學習時擺脫陌生感，增加學習的主動性，提高學習效率，優(yōu)化學習效果。正確運用比較教學法可以讓學生更為深刻、更為全面地理解和掌握所學知識，從而獲得更好的教學效果。

參考文獻：

[1] 王曉東. 算法分析與設計（第3版）[M]. 北京：清華大學出版社， 2014.

[2] 李運模. 比較教學法論略[J]. 中南民族學院學報：人文社會科學版，2000，20（3）：125-127.

[3] 肖敏. 比較教學法在現代設計方法課程教學中的應用[J]. 高教論壇，2006（6）：120-121.

動態(tài)規(guī)劃思想范文5

文章在介紹了傳統的基于遍歷樹的方法的基礎上重點討論了基于路徑分解的查詢處理算法，并對選擇連接順序算法提出了基于動態(tài)規(guī)劃思想的改進。

關鍵詞：XPath；XML；查詢優(yōu)化；動態(tài)規(guī)劃

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)28-0020-04

XML Query Optimization Based on XPath

XU Yi

(School of Software Engineering,Tongji University,Shanghai 201804,China)

Abstract: With the advent of XML as a standard for data representation and exchange on the Internet, querying XML data becomes more and more important. Several XML query Language have been proposed, and the common feature of the languages is the use of regular path expression based on XPath Data Model to query XML data. Research shows that the current relational database technology often inefficient when deal with the regular path expression.

This paper first introduce the traditional traversing tree algorithm, and then discuss the query parse algorithm which based on regular path expression, and optimize the structural join order by dynamic programming.

Key words: XPath; XML; query optimization; dynamic programming

1 引言

XML是由W3C開發(fā)的，主要目的是為了克服HTML缺乏結構和元數據信息的缺點，為Web信息的集成、交換建立一種新的靈活的機制。

它在以下幾個領域正改變著Web：

1) 簡化了數據交換。使用XML，每個實體可以創(chuàng)建單一的實用程序，該實用程序將該實體的內部數據格式轉換成XML，反之亦然。

2) XML支持智能代碼。因為可以使XML文檔結構化以標識每個非常重要的信息片段以及這些片段之間的關系，所以可以編寫無需人工干預就能處理這些XML文檔的代碼。

3)XML支持智能搜索。盡管搜索引擎這些年在穩(wěn)步改進，但從搜索中得到錯誤的結果仍很常見。搜索 XML文檔會給一個好得多的結果集。

隨著XML數據的增多，如何對其進行高效的查詢時非常重要的，本文從XML的基本概念入手，著重對當前XML數據查詢的處理方法進行分析研究，并加以改進和優(yōu)化，來進一步提高查詢處理效率。

2 XPath

談及XML數據查詢，就不得不談到XPath。作為XML數據查詢語言的核心部分，XPath用來對XML文檔的內容進行定位、檢索。XQuery和XPath公用的數據模型提供了XML文檔的樹形表示―節(jié)點樹。節(jié)點有七類，包括根節(jié)點、元素節(jié)點、屬性節(jié)點、文本節(jié)點、命名空間節(jié)點、處理指令節(jié)點、注釋節(jié)點。XPath的最主要構件路徑表達式就是通過這樣的節(jié)點樹來跟蹤路徑，識別出所有被路徑表達式檢索的節(jié)點。下面給出的是一個簡單的定位表達式：

/pub/book/author

定位路徑有兩種，分別是相對定位路徑和絕對定位路徑。每個定位路徑表達式都由一個或者多個定位步組成，每個定位步之間用正斜杠分開。絕對路徑以正斜杠開始，它從文檔的根節(jié)點開始定位路徑；而相對路徑則直接從某個定位步開始定位路徑。

XPath中用上下文節(jié)點集來描述定位路徑的求值過程是如何進行的。上下文節(jié)點集定義為：表達式中給定集確定的當前節(jié)點集。上下文定義為：正在處理的當前節(jié)點。

定位路徑表達式是求值過程是由定位步驟決定。定位步驟按順序(從左到右)一次一個地求值。每一個定位步驟都是對照上下文節(jié)點集中的節(jié)點進行求值的。第一個定位步驟是把上下文節(jié)點集中的每個節(jié)點當作上下文節(jié)點進行求值。 然后結果節(jié)點集被合并為新的節(jié)點集，這個節(jié)點集成為下一步操作的上下文節(jié)點集。這樣的處理在路徑的每一個定位步驟中持續(xù)進行。最后的定位步驟產生的節(jié)點集就是這個表達式的結果。

定位步包含三部分：

一個軸，它指定了定位步選擇節(jié)點與上下文節(jié)點之間的樹狀關系。XPath定義了13個軸。每個軸都有個方向，向前或者向后。

一個節(jié)點測試，它指定了定位步選擇的節(jié)點類型或者節(jié)點名。如果給定點的節(jié)點測試為真，則它保留在結果節(jié)點集中，否則將它從結果節(jié)點集中刪除。

零個或多個謂詞，它使用專有的謂詞表達式來進一步篩選定位步選擇的節(jié)點集合。

3 XML數據查詢處理方法

利用路徑表達式導航XML查詢是XML查詢語言的共同特點.目前對XML路徑表達式的計算有兩種方法:一種是基于樹遍歷的方法,另外一種是路徑連接方法。

3.1 基于遍歷樹的方法

基于遍歷樹的方法有兩種次序：top-down和bottom-up。下面以查詢表達式Q1:/city/school/class/student[@name=”Tom”]為例來說明。按top-down的次序來處理時，要順著所有開始于city節(jié)點的路徑，去查找是否有school的節(jié)點作為后代，這一步要對XML數據庫中的所有的city節(jié)點來執(zhí)行， 這就意味著在XML樹中要遍歷從city節(jié)點到葉節(jié)點的每一條可能的路徑，如果city節(jié)點是根節(jié)點，那么整棵XML樹都必須被遍歷。按bottom-up的次序來遍歷可以降低遍歷的成本,對于同樣的查詢Q1來講，所有帶有屬性name值為”Tom”的student節(jié)點都要被搜索，從每一個這樣的student節(jié)點開始向上遍歷來確定是否存在class節(jié)點，然后再從每一個這樣的class節(jié)點向上遍歷來確定是否存在school節(jié)點作為祖先， 依次類推… 這種向上遍歷的方法在一般情況下較簡單、耗時較小，但對于符合條件的student節(jié)點數目很大，而class節(jié)點、school節(jié)點或city節(jié)點數目較小的情況，這種遍歷方式的成本可能會高于top-down方式。

一種折衷的處理方法是同時按照top-down 和bottom-up的次序進行遍歷，最終會在路徑的某個中間位置相遇，從而得出查詢結果。這種方法結合了top-down和bottom-up的優(yōu)點，但它的高效性并不總能得到保證，下面改進的方法中采用了路徑分解和連接算法來處理，避免了多次遍歷樹。

3.2 基于路徑分解的查詢處理算法

Quanzhongli和Bongki Moon將規(guī)則路徑查詢表達式分解為以下五種基本表達式的組合。

1) 只由單一元素或單一屬性組成的表達式,如author、@year;

2) 由一個元素和一個屬性組成的表達式，如book[@year=2007];

3) 由兩個元素組成的的表達式，如chapter//title、book/@isbn;book[descendant::section]、book[chapter];

4) 一個子表達式的kleene閉包

5) 兩個子表達式的并集

對第1種情況可利用元素或屬性的索引直接得到結果，對第2、3、4種情況需分別需要采用EA-Join、EE-Join和KC-Join三個算法來進行中間結果的連接合并；第5 種情況可通過組合兩個中間結果或直接按文件分組來處理。

三個算法如下：

1) EA-Join算法 ( 用于元素集合和屬性集合的合并，對應于由一個元素和一個屬性組成的子表達式) :

輸入:{E1,…,Em}, Ei表示擁有相同文件標示符(did)的元素集

{A1,…,An}, Aj表示擁有相同文件標示符(did)的元素集

輸出:元素為(e,a)的集合，要求滿足a是e的屬性

//據文件標示符來分類合并集合{Ei} 和{Aj}

l :for each Ei and Aj with the same did do

//據孩子父母關系分類合并Ei和Aj

2 : for each e∈Ei and a∈Aj do

3 : if(e is a parent of a) then output(e,a)

end

end

2) EE-Join算法 ( 用于元素集合和屬性集合的合并，對應于由一個元素和一個屬性組成的子表達式)：

輸入:{E1,…,Em}和{F1,…,Fn}, Ei和Fj表示擁有相同文件標示符(did)的元素集

輸出:元素為(e,f)的集合，要求滿足e是f的屬性

//據文件標示符來分類合并集合{Ei} 和{Fj}

l :for each Ei and Fj with the same did do

//據孩子父母關系分類合并Ei和Fj

2 : for each e∈Ei and f∈Fj do

3 : if(e is an ancestor of f) then output(e,f)

end

end

3) kleene closure算法 ( 對應于求一個子表達式的kleene閉包) :

輸入:{E1,…,Em}, Ei表示一個XML文檔的一組元素

輸出: {E1,…,Em}的kleene閉包

//重復執(zhí)行EE-Join算法

1:set i=1

2:set Kci ={E1,…,Em};

3:repeat

4:set I =i+1

5:set Kci=EE-Join(Kci-1, Kc1)

until (Kci is empty)

6:output union of Kc1 ,Kc2, ……, Kci-1;

4 XML數據查詢處理優(yōu)化

路徑分解算法（見3.2節(jié)）在合并中間結果集時，由于各個集合中元素的個數不同，在采用不同的連接合并的次序的情況下，執(zhí)行的開銷有很大不同。如果能夠選擇恰當的結構連接順序，將使原算法得到進一步的優(yōu)化。因此如何應用動態(tài)規(guī)劃算法，使得在盡量小的搜尋空間里找到最好的方案是本節(jié)的主題。

4.1 動態(tài)規(guī)劃的基本思想

動態(tài)規(guī)劃算法的基本思路是用一個表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中，在需要時再找出，這樣就可避免大量的重復計算。

動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質的問題。這類問題中，可能會有許多可行解，每個解都對應一個值，我們希望找到最優(yōu)值 ( 最大值或最小值)的那個解。設計一個動態(tài)規(guī)劃算法，通常可按以下幾個步驟進行:

1) 找出最優(yōu)解的性質，并刻畫其結構特征。

2) 遞歸地定義最優(yōu)值。

3) 以自底向上的方式計算出最優(yōu)值。

4) 根據計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。

用動態(tài)規(guī)劃算法通常只需要多項式時間，從而獲得較高的解題效率。

4.2 動態(tài)規(guī)劃算法的設計

一個XPath語句通常被建模成為一個樹，這種查詢也被稱為樹模式查詢。一個查詢的求解過程為：從初始查詢數開始，每次處理樹中的一條邊，即將相連的兩個節(jié)點進行連接，連接的結果用一個新的節(jié)點表示，并替代原樹中的2個節(jié)點。每次連接的時候都會減少一個節(jié)點，產生一個新的樹。當最后的樹只包含一個節(jié)點的時候，整個求解過程便告結束。圖1給出了一個查詢樹求解的例子。

■

圖1 使用動態(tài)規(guī)劃時的查詢樹求解圖

查詢數的求解圖實際上是一個有向無環(huán)圖。圖中所有類似于AB的聚集點成為狀態(tài)節(jié)點，每個查詢數稱為一個狀態(tài)，從一個查詢樹變換到另一個查詢樹的過程稱為移動。從初始狀態(tài)開始經過k步移動后到達的狀態(tài)被稱為k層狀態(tài)。只有當第k層所有狀態(tài)產生后才能移動到第k+1層。因而查詢樹的求解過程就是從初始狀態(tài)出發(fā)，經過n次移動到達結束狀態(tài)的過程，n為初始查詢樹中邊的數目。在這n次移動過程中經過的路徑就給出了連接的計劃即連接的順序。比如：S00-S10-S24-S31表示連接的順序為：先連接節(jié)點A和B，在將中間結果和D連接，最后與C連接。現在的問題是，要選擇一條路徑，使得按照該順序連接的總體代價最小。

如果將每一步的連接代價作為狀態(tài)樹每個邊的權，則這個問題上實際就是經典的求最小路徑問題。把最短路徑問題的動態(tài)規(guī)劃算法應用到這里，就變成了連接順序求解的動態(tài)規(guī)劃策略。其過程為：從初始狀態(tài)出發(fā)，每次進行一步移動。移動到第k層時，可能得到多個狀態(tài)，而且每個狀態(tài)又可能從多個路徑轉換而來。這些路徑的代價不一樣，只保留其中代價最小的那條路徑。然后從第k層狀態(tài)出發(fā)，移動到下一層，并按同樣的方法選擇最佳路徑。這樣到最后得到的路徑便是最短路徑，也是最優(yōu)的連接順序。

DijkstraShortestPathes算法:

輸入:具有非負權值的簡單無向加權圖G，以及G的一個特殊頂點v：

輸出:對于G中每個頂點u,輸出標記D[u],滿足D[u]是G中從v到u的距離

//初始化

1:set D[v]=0;

2:for G中每個頂點u ≠ v do

set D[u]=+ ∞;

//設優(yōu)先隊列Q包含G中所有的頂點，利用D標記作為關鍵字

3:while Q 非空 do

//把一個新頂點u從Q中加入到初始化為空集的集合C中

set u = Q.removeMin();

for u 的每個鄰接頂點Z且Z在Q中 do

//對邊(u,z)進行松弛過程

if D[u] + w(u,z) < D[z] then

set D[z] = D[u] + w(u,z);

改變Q中頂點Z的關鍵字

算法運行時間分析：

反復向Q中插入帶有初始關鍵字的所有頂點，所需時間為O（nlogn），如果利用自底向上的構造堆，則所需時間為O(n)在while循環(huán)中，從頂點Q中刪除頂點u所需時間為O（nlogn）,對于依附于頂點u的邊，執(zhí)行松弛過程的時間為O(dev(v)logn)總時間為Σv∈G（1+dev（v））logn即：總運行時間為O（（n+m）logn）

4.3 幾種查詢處理算法的比較

基于遍歷樹的處理方法比較直觀，但祖先后代關系的判斷需要多次對樹進行遍歷，特別對查詢路徑較長的情況將耗費較多時間，效率不高。路徑分解法處理時將長的查詢表達式分成五種基本子表達式，處理完每個子表達式后，再將中間結果集合按照具體算法進行合并，得出原查詢表達式的結果，此方法節(jié)省了時間，提高了效率。在此基礎上，動態(tài)規(guī)劃算法對此路徑分解法進一步優(yōu)化，在進行合并中間結果集前先確定出合并的最優(yōu)次序，減少了計算量，提高了效率。

5 小結

隨著XML作為Internet上數據表示和交換的標準，如何高效地進行XML數據的查詢己經變得越來越重要，本文對規(guī)則路徑表示下XML數據的查詢處理算法進行了分析研究，其中重點討論了基于XPath的查詢表達式的分解、中間結果集的合并算法等，主要工作如下:基于動態(tài)規(guī)劃的思想，設計出具體算法，在進行中間結果集合并之前，先求出合并的最優(yōu)次序，大大降低了合并結果集的計算量，提高了查詢處理效率，實現了對路徑分解算法的進一步優(yōu)化。

事實上，對于一個復雜的查詢來說，上述算法的搜索空間依然很大，還有進一步優(yōu)化的空間，這也是后續(xù)的研究方向。

參考文獻：

[1] Li Q,Moon B.Indexing and Querying XML Data for Regular Path Expression[A].In: Apers PMG et al Eds. Proceedings of the 27th VLDB International Conference on Very Large Database.[C] Rome, Italy. September 11-14,2001.San Francisco: Morgan Publishers,2001:361-370.

動態(tài)規(guī)劃思想范文6

關鍵詞：RNA二級結構預測; 假結; 最小自由能; 布谷鳥搜索

中圖分類號： R857.3 文獻標識碼：A

1概述

假結結構是一類二級結構子結構，在兩個或多個莖區(qū)出現交叉嵌套時形成，存在于多種RNA分子二級結構中。其中莖區(qū)是一種二級結構子結構，通過連續(xù)的三對或三對以上堿基配對形成。研究發(fā)現，假結結構對于RNA結構的作用具有重要的意義。

RNA分子結構對于其作用有重要影響，其測定可通過X光測定、核磁共振成像等物理方法進行。但物理方法存在耗時長、財力物力開銷大等缺點，限制了其使用。

目前的研究主要通過軟件計算方式預測RNA二級結構。早期的RNA結構預測算法主要是動態(tài)規(guī)劃類型算法。這些算法具有不適用于較長的RNA序列、算法復雜預測計算耗時長等缺點。近期研究熱點轉向基于啟發(fā)式算法的預測研究。

2 研究現狀

目前主要預測算法采用最小自由能量模型作為建模基礎。此模型認為在所有可能結構中自由能量最低的預測結構最有可能是給定序列的實際結構。通過實驗及統計估算，可以指定出一系列自由能量計算規(guī)則，以計算出任何給定結構的自由能量。

目前的主要算法分為動態(tài)規(guī)劃和啟發(fā)式兩種。動態(tài)規(guī)劃算法能夠在理論上保證搜索到具有全局最小自由能量的結構，但時間復雜度高。啟發(fā)式算法收斂速度明顯比動態(tài)規(guī)劃算法快，但不能保證得到具有全局最小自由能的結構是其主要缺點。

目前主要的動態(tài)規(guī)劃算法包括Reeder和Generics提出的pknotsRG-mfe算法 和Dirks和Pierce提出的NUPACK的算法。pknotsRG-mfe通過限制假結類型將時間復雜度低至 。

Van Batenburg等人通過引入遺傳算法思想提出名為STAR的啟發(fā)式算法，將問題轉化為莖區(qū)組合優(yōu)化進行搜索。Ren和Rastegari提出名為HotKnots的啟發(fā)式算法，通過迭代添加可能的子結構建立候選結構。

3 CSRNA算法

布谷鳥搜索算法（Cuckoo Search， CS）是由Yang等于2009年提出的一種啟發(fā)式優(yōu)化算法，用以解決函數優(yōu)化、最值搜索等問題。算法受布谷鳥在其他鳥類的巢中下蛋并由他人代為孵化這一繁殖行為啟發(fā)。

3.1 目標函數

CSRNA算法定義RNA結構自由能量函數作為算法的目標函數，使用最鄰近能量模型進行計算。

一個結構的自由能通過將非假結子結構、H假結、復雜假結三者能量求和得到。

非假結子結構包含莖區(qū)、發(fā)夾環(huán)、內環(huán)、凸環(huán)、多分支環(huán)、懸掛堿基和終端錯配等二級結構子結構。CSRNA采用Mathews小組提出的能量參數計算上述子結構的能量。

針對H型假結能量，CSRNA引入由Gultyaev和Batenburg、Dirk和Pierce[3]以及Cao和Chen 提出的三組能量參數進行計算。針對復雜假結能量，CSRNA采用了將其拆分為多個非假結結構方式計算能量。

3.2 初始化處理

初始化處理包括構造莖區(qū)池、構造初始解并排序兩個步驟。

首先定義兩個莖區(qū)兼容指相互不包含重復的堿基位。

莖區(qū)池是一個存儲給定RNA序列所有可能存在的莖區(qū)的線性表，表中每個莖區(qū)被賦予全局唯一的序號。每個解都是莖區(qū)池中相互兼容莖區(qū)的組合。

4 實驗結果

定義TP表示預測結構堿基對中出現在實際結構中的堿基對個數，FP表示預測結構堿基對中未出現于實際結構中的堿基對個數，FN表示真實結構堿基對中未出現在預測結構中的堿基對的個數。

則可定義用于評價結果的敏感性指標為TP除以TP與FN的和，而確定性敏感性指標為TP除以TP與FP的和。

表2 確定性指標實驗結果表

結語

在本文中，以解決帶假結RNA二級結構預測問題，我們基于布谷鳥搜索提出了一種名為CSRNA的預測算法。通過與目前主要預測算法進行對比實驗，證明了CSRNA算法的有用性和有效性。

在后續(xù)研究中，計劃通過完善自由能量計算模型以提高預測準確率。此外，還計劃針對構造領域解進行搜索和按比例淘汰部分解兩項機制進行改造，以加強算法搜索能力，優(yōu)化預測結果。

參考消息