基于動態規劃的最優二叉搜索樹算法的改進

摘要：基于動態規劃的最優二叉搜索樹構造算法，選擇子問題的劃分時，r值的循環范圍過大，存在不足。本文對此改進，縮小了r值的范圍，算法時間復雜度由O(n3)減小至O(n2)，并對兩個算法的優劣進行了比較。

關鍵詞：動態規劃；最優二叉搜索樹；算法改進

中圖分類號：TP318文獻標識碼：A文章編號：1009-3044(2008)35-2176-02

A Better Algorithm of Setting up Optimal Binary Trees Based on Dynamic Programming

LIU Yan

(College of Information Science and Engineering，Xinjiang University， Urumqi 830046， China)

Abstract: The algorithm of setting up optimal binary trees based on dynamic programming occurs some faults.The r′s value has some faults that the range of selecting subproblems is too wide.This paper improved the algorithm by the point which diminished the range of r's value and decreased a great number of time complexity from O(n3) to O(n2)，and compared the advantages and disadvantages between the two algorithms.

Key words: dynamic programming; optimal binary search trees; a better algorithm

1 引言

高等教育出版社影印版《INTRODUCTION TO ALGORITHMS》（第二版）中，基于動態規劃法思想，建立最優二叉搜索樹算法，選擇子問題的劃分，r值的循環范圍過大。當二叉樹結點較多時，算法的時間復雜度較大，造成程序運行時較多開支。

2 經典最優二叉搜索樹算法分析

原最優二叉搜索樹算法時間復雜度為：

本文引用《INTRODUCTION TO ALGORITHMS》（第二版）第363頁例題15.5-2作為實例分析：

Determine the cost and structure of an optimal binary search tree for a set of n=7 keys with the following probabilities.

表1 概率值表

原算法計算結果：

e[1，0]=0.06

e[1，1]=0.28 e[2，1]=0.06

……

e[1，7]=3.12 e[2，7]=2.61 e[3，7]=2.13 e[4，7]=1.55 e[5，7]=1.20 e[6，7]=0.78 e[7，7]=0.34 e[8，7]=0.05

w[1，0]=0.06

w[1，1]=0.16 w[2，1]=0.06

……

w[1，7]=1.00 w[2，7]=0.90 w[3，7]=0.78 w[4，7]=0.64 w[5，7]=0.56 w[6，7]=0.41 w[7，7]=0.24 w[8，7]=0.05

root[1，1]=1

root[1，2]=2 root[2，2]=2

……

root[1，7]=5 root[2，7]=5 root[3，7]=5 root[4，7]=6 root[5，7]=6 root[6，7]=7

root[7，7]=7

（e陣列為建立兩個結點之間的二叉搜索樹的時間期望值花費，w陣列為兩個結點之間查找成功與否的概率和，root陣列為兩個結點間最優二叉搜索樹的最優化劃分方法。）

e， w， root陣列各個計算順序為：

e[1，0]→e[2，1]→…→e[8，7]→e[1，1]→…→e[1，7];

w[1，0]→…→w[8，7]→w[1，2]→…→w[6，7];

root[1，1]→…→root[7，7]→root[1，3]→…→root[1，7];

經分析，原算法r值的范圍可再次縮小，原r范圍為從i～j，如實際情況i與j值較大，循環次數較多，算法時間復雜度較大。

3 算法的改進及可靠性證明

3.1 算法的改進

計算r時，root陣列記錄e陣列的最優劃分方法。例如e[1，7]，e陣列公式e[i，j]=e[i，r-1]+e[r+1，j]+w[i，j]，r循環范圍1～7，計算以下式子：

e[1，0]+e[2，7]+w[1，7]=3.67 ①

…

e[1，6]+e[8，7]+w[1，7]=3.49 ⑦

7次，計算e[1，6]的式子為：

e[1，0]+e[2，6]+w[1，6]=2.73 ⑴

…

e[1，5]+e[7，6]+w[1，6]=2.59 ⑹

共6次。

e[1，6]是e[1，7]子問題。動態規劃特點：若子問題最優，則主問題也最優。則root[1，6]=3就保證計算e[1，7]時，r循環1~3時，一定是r=3，e[1，7]最小。則計算e[1，7]時可從r=3開始計算。即計算e[1，7]時，原算法重復了①～②式的計算。

同理，e[2，7]是e[1，7]的子問題，root[2，7]=5就可保證一定是r=5時，e[1，7]最小。原算法重復⑥～⑦式的計算。整個算法中，這兩種情況重復出現，使原算法運行時間開支較大。

經分析，r值范圍改為root[i，j-1]～root[i+1，j]。

3.2 改進算法的可靠性證明

根據動態規劃思想，若子問題劃分最優，則主問題最優，而計算e[i，j]時，根據原算法，知root[i，j-1]已計算。即i～j-1結點最優化劃分已選，計算e[i，j]時，只需r從root[i，j-1]值開始。

同理，root[i+1，j]也算出。即i+1～j結點最優化劃分已選，計算e[i，j]時，r取值上限為root[i+1，j]值。其它循環同理。

3.3 改進算法的實現

改進算法，應注意root陣列初始值，root[1，1]，…，root[7，7]沒對應取值范圍，需要在計算前，先初始化root[i，i](i=1，2，…，7)。

改進算法如下。

Optimal-Adv-BST(p，q，n)

1. for i←1 to n+1/1~3步的時間復雜度為O(n+1)/

2. do e[i，i-1]←qi-1

3. w[i，i-1]←qi–1

4. for i←1 to n/4~5步的時間復雜度為O(n)/

5. do root[i，i]←i/root[i，i]初始化/

6. for l←1 to n

7. do for i←1 to n–l+1

8. do j←i+l-1

9. e[i，j]←∞

10. w[i，j]←w[i，j-1]+pj+qj

11. if i=j /i=j時是root[i，i]初始值/

12. then {t←e[i，i-1]+e[i+1，]+w[i，j]/i=j時，r只能選i-1/

13. if t

14. then e[i，j]←t}

15. else for r←root[i，j-1] to root[i+1，j]

16. do t←e[i，r-1]+e[r+1，j]+w[i，j]

17. if t

18. then e[i，j]←t

19. root[i，j]←r

20. return e and root/時間復雜度為1/

改進算法的6~19行時間復雜度：

改進算法的最壞時間復雜度為：

注意，原算法時間復雜度是確定的，而改進算法15行時間復雜度隨著問題不同而不同，給出改進算法的時間復雜度T(n2)是最壞情況的時間復雜度。改進算法比原算法節省時間是因為15行語句。改進算法雖然有3個for語句循環，但經過計算，其時間復雜度為O(n2)。因為root陣列的值會相互影響，即若root[i，j-1]與root[i+1，j]值相差較大，則root[i+1，j]與root[i+2，j+1]值相差較小，所以此句循環次數遠小于n，使改進整體算法的時間復雜度整體減小。

4 兩種算法的優越性比較

現在比較兩種算法的優越性。

從表2、表3可以看出，理論上改進算法比原算法運行時間減少14%，實際例題中，改進算法比原算法節省時間36%。n值較大時，改進算法的效果將更加理想。

5 總結

本文在最優二叉搜索樹構造算法中，主要改進了子問題的劃分時r值的循環范圍，減小了算法的時間復雜度，由原來的O(n3) 減小為O(n2)，并討論改進算法的優越性。

文中輸出格式與教材中格式不相同，但不影響理解和閱讀。改進算法雖然在表面上與原算法有較大改動，其實只是為了讓改進算法適應更好的環境，例如考慮到root的初始值，增加的語句并不會增加程序的開支；相反，當n值越大時，改進算法節省的時間將更顯著。

參考文獻：

[1] Cormen T H，Leiserson C E，Rivest R L，et al. Introduction to Algorithms[M]. 2nd ed. The Massachusetts Institute of Technology Press，2001.

[2] Knuth D E. Optimum binary search trees，Acta Informatica，1971，1:14-25.

[3] Hu T C，Tucker A C.Optimal computer search trees and variable-length alphabetic codes[J]. SIAM Journal on Applied Mathematics，1971，21(4):514-532.

[4] 譚浩強. C程序設計[M]. 2版. 北京：北京清華大學出版社，1999.