最優(yōu)二分搜索樹
二分搜索樹
- 是一棵空樹
- 具有下列性質(zhì)的二叉樹
- 若左子樹不空参咙，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值
- 若右子樹不空院崇，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
- 左霜旧、右子樹分別為二叉搜索樹
查詢操作
MEMBER(x,S)：若x在S中則返回”yes”压汪，否則返回”no”
設(shè)有n個實(shí)數(shù)<
<…<
構(gòu)成集合S
指令MEMBER(x,S)中的x可能是某個，也可能不在S中。把不在S中的數(shù)按區(qū)間分為n+1類，以
，
贤徒，…，
作為每一類數(shù)的代表（虛節(jié)點(diǎn)）
定義
為MEMBER (
,S)出現(xiàn)的頻率（i=1,2,…,n）
為MEMBER (
,S)出現(xiàn)的頻率（j=0,1,2,…,n）
+
=1
定義一棵二分搜索樹的總耗費(fèi)：+
最優(yōu)二分搜索樹即耗費(fèi)最小的二分搜索樹
分析
- 若
是最優(yōu)二分搜索樹汇四，它的根是
（第k小的數(shù)）
則ak的左子樹中必然包含了{(lán)…
}接奈，ak的右子樹中必然包含了{(lán)
…
}。
- 考察一棵樹接到另一個結(jié)點(diǎn)之下構(gòu)成一棵新樹時耗費(fèi)的增加
設(shè)有一棵由結(jié)點(diǎn)通孽，
序宦，
，…背苦，
互捌，
構(gòu)成的樹
按定義該樹的耗費(fèi)為+
把這棵樹接到到另一個結(jié)點(diǎn)之下構(gòu)成一棵新樹時，這棵子樹中的每個結(jié)點(diǎn)的深度在新樹中均
增加了1行剂，則該子樹在新樹中的耗費(fèi)增加了+
=
+(
+
)+...+(
+
)=
- 任何一顆子樹中結(jié)點(diǎn)的編號都是連續(xù)的秕噪，而且，最優(yōu)樹中的任何一棵子樹厚宰，也必然
是關(guān)于子樹中結(jié)點(diǎn)的最優(yōu)樹腌巾，因此最優(yōu)二分搜索樹具有最優(yōu)子結(jié)構(gòu)性質(zhì) - 若規(guī)模為m≤n-1的最優(yōu)子樹均已知，就可以通過逐一計(jì)算以
壤躲，…城菊，
-
:有一棵由結(jié)點(diǎn)
樹以
在左子樹
目胡，
链快，…誉己，
這樣的樹中耗費(fèi)最小的必然是以為其左子樹域蜗，以
為其右子樹
記是最優(yōu)子樹
- 樹
左子樹的耗費(fèi):+
右子樹的耗費(fèi):+
根的耗費(fèi):
總耗費(fèi)=+
+
+
=
- 已知
（i=1,2,…,n）巨双，
（j=0,1,2,…,n）
若已知，則根據(jù)
=
+
的定義計(jì)算出
所以霉祸，當(dāng) - 綜上，分別計(jì)算以
,...,
{
- 三層循環(huán)茵典，Θ(
)
優(yōu)化
- 可以證明：若最小耗費(fèi)樹
和
的根分別為
和
湘换，則必有⑴p≤q；⑵最小耗費(fèi)樹
- 因此，求
流水作業(yè)調(diào)度
問題
n個作業(yè)，m項(xiàng)任務(wù)帆离，m臺機(jī)器
設(shè)有n個任務(wù)蔬蕊，每一個作業(yè)i均被分解為m項(xiàng)任務(wù)：,
,
(1≤i≤n，故共有n×m個任務(wù))哥谷，要把這些任務(wù)安排到m臺機(jī)器上進(jìn)行加工
需要滿足條件：
- 每個作業(yè)i的第j項(xiàng)任務(wù)
上進(jìn)行加工
- 作業(yè)i的第j項(xiàng)任務(wù)
- 任何一臺機(jī)器在任何一個時刻最多只能承擔(dān)一項(xiàng)任務(wù)
設(shè)任務(wù)岸夯，如果所有
流水作業(yè)調(diào)度一般均指的是非優(yōu)先調(diào)度，即任何任務(wù)一旦開始加工监婶，就不允許被中斷旅赢，直到該任務(wù)被完成
分析
- 當(dāng)機(jī)器數(shù)m≥3時，流水作業(yè)調(diào)度問題是一個NP-hard問題惑惶。當(dāng)m=2時煮盼，該問題可有多項(xiàng)式時間的算法。
- 記
為
（作業(yè)i在
上加工所需時間）,
為
上加工所需時間）
- 當(dāng)機(jī)器
- 必有一個最優(yōu)調(diào)度使得在
- 必有一個最優(yōu)調(diào)度使得在
- 若在
- 最優(yōu)調(diào)度具有如下性質(zhì)：
在所確定的最優(yōu)調(diào)度的排列中去掉第一個執(zhí)行作業(yè)后喉祭，剩下的作業(yè)排列仍然還是一個最優(yōu)調(diào)度，即該問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)
在計(jì)算規(guī)模為n的作業(yè)集合的最優(yōu)調(diào)度時雷绢，該作業(yè)集合的子集合的最優(yōu)調(diào)度會被多次用到泛烙，即該問題亦具有高度重復(fù)性
求解
- N={1，2翘紊，┅蔽氨，n}是全部作業(yè)的集合，作業(yè)集S是N的子集合即有S?N
- 對機(jī)器
待） - 記g(S,t)為在此情況下完成S中全部作業(yè)的最短時間
g(S,t)={
- 當(dāng)S=N即全部作業(yè)開始加工時帆疟，t=0
- g(N,0)=
{
- 該算法的時間復(fù)雜度為指數(shù)量級鹉究，因?yàn)樗惴ㄖ袑的每一個非空子集都要進(jìn)行一次計(jì)算，而N的非空子集共有
-1個踪宠，因此不能直接使用動態(tài)規(guī)劃方法來求解該問題
進(jìn)一步求解
- Johnson不等式：min{
- 當(dāng)min{
- 推廣：當(dāng)min{
,
,┅,
}=
- n個作業(yè)中首先開工（或最后開工）的作業(yè)確定之后允坚，對剩下的n-1個作業(yè)采用相同方法可再確定其中的一個作業(yè),應(yīng)作為n-1個作業(yè)中最先或最后執(zhí)行的作業(yè)；反復(fù)使用這個方法直到最后只剩一個作業(yè)為止蛾号，即可確定最優(yōu)調(diào)度
- 為O(nlgn)
總結(jié)
- 滿足1）高度重復(fù)性 2）最優(yōu)子結(jié)構(gòu)性質(zhì)時稠项，一般采用動態(tài)規(guī)劃法，但偶爾也可能得不到高效的算法
- 若問題本身不是NP-hard問題鲜结，進(jìn)一步分析后就有可能獲得效率較高的算法
- 若問題本身就是NP-hard問題展运，與其它的精確算法相比，動態(tài)規(guī)劃法性能一般不算太壞精刷， 但有時需要對動態(tài)規(guī)劃法作進(jìn)一步的加工
備忘錄LCS
備忘錄方法
- 當(dāng)某個問題可以用動態(tài)規(guī)劃法求解,但二維數(shù)組中有相當(dāng)一部分元素在整個計(jì)算中都不會被用到
- 因此拗胜，不需要以遞推方式逐個計(jì)算二維數(shù)組中元素，而采用備忘錄方法：數(shù)組中的元素只是在需要計(jì)算時才去計(jì)算怒允，計(jì)算采用遞歸方式埂软，值計(jì)算出來之后將其保存起來以備它用
- 若有大量的子問題無需求解時，用備忘錄方法較省時
求解
- 當(dāng)
=
時纫事，求C[i,j]只需知道C[i-1,j-1]勘畔，而無需用到C[i,0]～C[i,j-1]及C[i-1,j]～C[i-1,n]，所以只需求出一個LCS時丽惶，可能有一些C[p,q]在整個求解過程中都不會用到
- 將C[i,0]與C[0,j] 初始化為0炫七，其余m×n個C[i,j]全部初始化為-1
- 若x[i]=y[j]，則去檢查C[i-1,j-1]：若C[i-1,j-1]> -1（已經(jīng)計(jì)算出來）钾唬，就直接把C[i-1,j-1]+1賦 給C[i,j]万哪，返回；若C[i-1,j-1]=-1（尚未計(jì)算出來）抡秆，就遞歸調(diào)用LCS(X,Y,i-1,j-1,C) 計(jì)算出C[i-1,j-1]奕巍，然后再把C[i-1,j-1]+1賦給C[i,j]，返回
- 若x[i]不等于y[j]儒士，則檢查C[i-1,j]和C[i,j-1]：若兩者均 > -1（已經(jīng)計(jì)算出來）的止，則把max{ C[i-1,j], C[i,j-1]} 賦給C[i,j]，返回乍桂；若C[i-1,j], C[i,j-1] 兩者中有一個等于-1（尚未計(jì)算出來）冲杀， 或兩者均等于-1，就遞歸調(diào)用LCS將其計(jì)算出來睹酌，然后 再把max{ C[i-1,j], C[i,j-1]} 賦給C[i,j]
最長遞增子序列問題（LIS）
問題
假設(shè)A =< ,
, … ,
>為由n個不同的實(shí)數(shù)組成的序列
遞增子序列?? =< ,
, … ,
>
其中<
<…<
并且
<
< … <
求最大的??值
最大子段和問題
問題
n個整數(shù)序列 …
权谁，求該序列形如
的子段和的最大值
當(dāng)所有整數(shù)均為負(fù)整數(shù)時定義其最大子段和為0
分治解法
如果將所給的序列a[1..n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n],分別求出這兩段最大子段和，則a[1..n]的最大子段和有三種情形：
- a[1:n]的最大子段和與a[1:n/2]的最大子段和相同憋沿；
- a[1:n]的最大子段和與a[n/2+1:n]的最大子段和相同旺芽；
- a[1:n]的最大子段和為
，1≤ i ≤ n/2辐啄，n/2+1 ≤ j ≤ n
對于1采章、2可以遞歸求解
對于3:
a[n/2]、a[n/2+1]在最優(yōu)子序列中
可以在a[1:n/2]中計(jì)算出=
可以在a[n/2+1:n]中計(jì)算出=
代碼
void MaxSubSum(int *a壶辜，int left悯舟，int right)
{
int sum=0;
if (left==right) sum=a[left]>0?a[left]:0;
else{
int center=(left+right)/2;
int leftsum=MaxSubSum(a,left,center);
int rightsum=MaxSubSum(a,center+1,right);
int s1=0; int lefts=0;
for(int i=center;i>=left;i--){
lefts+=a[i];
if (lefts>s1) s1=lefts;
}
int s2=0; int rights=0;
for (int i=center+1; i<=right; i++){
rights+=a[i];
if (rights>s2) s2=rights;
}
sum=s1+s2;
if (sum<leftsum) sum=leftsum;
if (sum<rightsum) sum=rightsum;
}
return sum;
}
分析
算法所需的計(jì)算時間T(n)滿足典型的分治算法遞歸式：
基于主方法和主定理，T(n)=O(nlogn)
動態(tài)規(guī)劃解法
記b[j]=砸民，1≤j≤n抵怎，則
=
=
因此，當(dāng)b[j-1]>0,b[j]=b[j-1]+a[j]岭参；否則反惕，b[j]=a[j]。得出
b[j]=
代碼
int MaxSum(int n演侯，int *a)
{
int sum=0, b=0;//初始化最大子段和為0姿染，b[0]=0
for (int i = 1; i <= n; i++){
if (b>0) b+=a[i];
else b=a[i];
if (b>sum) sum=b;//更新當(dāng)前找到的最大子段和
}
return sum;
}
分析
O(n)
