久久婷婷久久精品视频,噜噜噜另类久久久,在线免费一区99

最優(yōu)二分搜索樹

二分搜索樹

是一棵空樹
具有下列性質(zhì)的二叉樹
- 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值
- 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
- 左、右子樹分別為二叉搜索樹

查詢操作

MEMBER(x,S)：若x在S中則返回”yes”，否則返回”no”
設(shè)有n個(gè)實(shí)數(shù) $a_1$ < $a_2$ <…< $a_n$ 構(gòu)成集合S
指令MEMBER(x,S)中的x可能是某個(gè) $a_i$ ，也可能不在S中。把不在S中的數(shù)按區(qū)間分為n+1類，以 $b_0$ ， $b_1$ ，…， $b_n$ 作為每一類數(shù)的代表（虛節(jié)點(diǎn)）

定義

$p_i$ 為MEMBER ( $a_i$ ,S)出現(xiàn)的頻率（i=1,2,…,n）
$q_j$ 為MEMBER ( $b_j$ ,S)出現(xiàn)的頻率（j=0,1,2,…,n）
$\sum_{i=1}^np_i$ + $\sum_{j=0}^nq_j$ =1
定義一棵二分搜索樹的總耗費(fèi)： $\sum_{i=1}^np_i(depth(a_i)+1)$ + $\sum_{j=0}^nq_j(depth(b_j))$
最優(yōu)二分搜索樹即耗費(fèi)最小的二分搜索樹

分析

若 $T_0$ 是最優(yōu)二分搜索樹，它的根是 $a_k$ （第k小的數(shù)）
則ak的左子樹中必然包含了{(lán) $a_1$ … $a_{k-1}$ }，ak的右子樹中必然包含了{(lán) $a_{k+1}$ … $a_n$ }。
考察一棵樹接到另一個(gè)結(jié)點(diǎn)之下構(gòu)成一棵新樹時(shí)耗費(fèi)的增加
設(shè)有一棵由結(jié)點(diǎn) $b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_j$ ， $b_j$ 構(gòu)成的樹
按定義該樹的耗費(fèi)為 $\sum_{l=i+1}^jp_l(depth(a_l)+1)$ + $\sum_{l=i}^jq_l(depth(b_l))$
把這棵樹接到到另一個(gè)結(jié)點(diǎn)之下構(gòu)成一棵新樹時(shí)，這棵子樹中的每個(gè)結(jié)點(diǎn)的深度在新樹中均
增加了1，則該子樹在新樹中的耗費(fèi)增加了 $\sum_{l=i+1}^jp_l$ + $\sum_{l=i}^jq_l$ = $q_i$ +( $p_{i+1}$ + $q_{i+1}$ )+...+( $p_j$ + $q_j$ )= $w_{ij}$
任何一顆子樹中結(jié)點(diǎn)的編號(hào)都是連續(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ì)算以 $a_1$ ， $a_2$ ，…， $a_n$ 為根的樹的耗費(fèi)來確定（使耗費(fèi)達(dá)到最小的）根 $a_k$ 并找出最優(yōu)二分搜索樹,在上述計(jì)算中，規(guī)模較?。?m≤n-1 ）的最優(yōu)子樹在計(jì)算中要多次被用到，因此，該問題具有高度重復(fù)性
$T_{ij}$ :有一棵由結(jié)點(diǎn) $b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_j$ ， $b_j$ 構(gòu)成的耗費(fèi)最小的樹
樹以 $a_k$ 作為根(i+1≤k≤j)
$b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_{k-1}$ ， $b_{k-1}$ 在左子樹
$b_k$ ， $a_{k+1}$ ， $b_{k+1}$ ，…， $a_j$ ， $b_j$ 在右子樹
這樣的樹中耗費(fèi)最小的必然是以 $T_{i,k-1}$ 為其左子樹，以 $T_{kj}$ 為其右子樹
記 $c_{ij}$ 是最優(yōu)子樹 $T_{ij}$ 的耗費(fèi)
樹 $T_{ij}$ 的總耗費(fèi)由三個(gè)部分組成
左子樹的耗費(fèi): $c_{i,k-1}$ + $w_{i,k-1}$
右子樹的耗費(fèi): $c_{kj}$ + $w_{kj}$
根的耗費(fèi): $p_k$
總耗費(fèi)= $c_{i,k-1}$ + $w_{i,k-1}$ + $c_{k,j}$ + $w_{k,j}$$c_{k,j}$ + $w_{k,j}$ = $c_{i,k-1}$ + $c_{kj}$ + $w_{ij}$
已知 ${p_i}$ （i=1,2,…,n）， ${q_i}$ （j=0,1,2,…,n）
若已知 $w_{i,j-1}$ ，則根據(jù) $w_{ij}$ = $w_{i,j-1}$ + ${p_j}$ + ${q_j}$ 的定義計(jì)算出 $w_{ij}$
所以，當(dāng) $c_{i,k-1}$ 和 $c_{kj}$ 已知，以 $a_k$ 為根的樹的最小總耗費(fèi)能在O(1)時(shí)間內(nèi)計(jì)算出來
綜上，分別計(jì)算以 $a_{i+1}$ , $a_{i+2}$ ,..., $a_j$ 為根，含有結(jié)點(diǎn) $b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_j$ ， $b_j$ 的樹的總耗費(fèi)，從中選出耗費(fèi)最小的樹，即為最優(yōu)子樹
$c_{ij}$ = $\min_{i<k≤j}$ { $c_{i,k-1}$ + $c_{kj}$ + $w_{ij}$ }
三層循環(huán)，Θ( $n^3$ )

優(yōu)化

可以證明：若最小耗費(fèi)樹 $T_{i,j-1}$ 和 $T_{i+1,j}$ 的根分別為 $a_p$ 和 $a_q$ ，則必有⑴p≤q；⑵最小耗費(fèi)樹 $T_{ij}$ 的根 $a_k$ 滿足p≤k≤q
因此，求 $\min_{i<k≤j}$ { $c_{i,k-1}$ + $c_{kj}$ + $w_{ij}$ }時(shí)，無需在 $a_{i+1}$ ~ $a_j$ 間一一嘗試，只需要從 $a_p$ 和～ $a_q$ 找一個(gè)根即可

流水作業(yè)調(diào)度

問題

n個(gè)作業(yè)，m項(xiàng)任務(wù)，m臺(tái)機(jī)器
設(shè)有n個(gè)任務(wù)，每一個(gè)作業(yè)i均被分解為m項(xiàng)任務(wù)： $T_{i1}$ , $T_{i2}$ , $T_{im}$ (1≤i≤n，故共有n×m個(gè)任務(wù))，要把這些任務(wù)安排到m臺(tái)機(jī)器上進(jìn)行加工
需要滿足條件：

每個(gè)作業(yè)i的第j項(xiàng)任務(wù) $T_{ij}$ (1≤i≤n, 1≤j≤m) 只能安排在機(jī)器 $P_j$ 上進(jìn)行加工
作業(yè)i的第j項(xiàng)任務(wù) $T_{ij}$ (1≤i≤n, 2≤j≤m)的開始加工時(shí)間均安排在第j-1項(xiàng)任務(wù) $T_{i,j-1}$ 加工完畢之后
任何一臺(tái)機(jī)器在任何一個(gè)時(shí)刻最多只能承擔(dān)一項(xiàng)任務(wù)
設(shè)任務(wù) $T_{ij}$ 在機(jī)器 $P_j$ 上進(jìn)行加工需要的時(shí)間 $t_{ij}$ ，如果所有 $t_{ij}$ (1≤i≤n, 1≤j≤m)均已給出，要找出一種安排任務(wù)的方法，使得完成這n個(gè)作業(yè)的加工時(shí)間為最少，這個(gè)安排稱之為最優(yōu)流水作業(yè)調(diào)度
流水作業(yè)調(diào)度一般均指的是非優(yōu)先調(diào)度，即任何任務(wù)一旦開始加工，就不允許被中斷，直到該任務(wù)被完成

分析

當(dāng)機(jī)器數(shù)m≥3時(shí)，流水作業(yè)調(diào)度問題是一個(gè)NP-hard問題。當(dāng)m=2時(shí)，該問題可有多項(xiàng)式時(shí)間的算法。
記 $t_{i1}$ 為 $a_i$ （作業(yè)i在 $P_1$ 上加工所需時(shí)間）, $t_{i2}$ 為 $b_i$ （作業(yè)i在 $P_2$ 上加工所需時(shí)間）
當(dāng)機(jī)器 $P_1$ 空閑時(shí)，則任何一個(gè)作業(yè)的第一個(gè)任務(wù)都可以立即在 $P_1$ 上執(zhí)行
必有一個(gè)最優(yōu)調(diào)度使得在 $P_1$ 上的加工是無間斷的
必有一個(gè)最優(yōu)調(diào)度使得在 $P_2$ 上的加工空閑時(shí)間（從0時(shí)刻起算）為最小，同時(shí)還滿足在 $P_1$ 上的加工是無間斷的
若在 $P_2$ 上的加工次序與在 $P_1$ 上的加工次序不同，則只可能增加加工時(shí)間。所以僅需要考慮在 $P_1$ 和 $P_2$ 上加工次序完全相同的調(diào)度
最優(yōu)調(diào)度具有如下性質(zhì)：
在所確定的最優(yōu)調(diào)度的排列中去掉第一個(gè)執(zhí)行作業(yè)后，剩下的作業(yè)排列仍然還是一個(gè)最優(yōu)調(diào)度，即該問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)
在計(jì)算規(guī)模為n的作業(yè)集合的最優(yōu)調(diào)度時(shí)，該作業(yè)集合的子集合的最優(yōu)調(diào)度會(huì)被多次用到，即該問題亦具有高度重復(fù)性

求解

N={1，2，┅，n}是全部作業(yè)的集合，作業(yè)集S是N的子集合即有S?N
對(duì)機(jī)器 $P_2$ 需等待t個(gè)時(shí)間單位以后才可以用于S中的作業(yè)加工（t也可以為0即無須等
待）
記g(S,t)為在此情況下完成S中全部作業(yè)的最短時(shí)間
g(S,t)= $min_{i∈S}$ { $a_i$ + g(S-{i}, $b_i$ +max{t- $a_i$ ,0})}
當(dāng)S=N即全部作業(yè)開始加工時(shí)，t=0
g(N,0)= $min_{1≤i≤n}$ { $a_i$ + g(N-{i}, $b_i$ )}
該算法的時(shí)間復(fù)雜度為指數(shù)量級(jí)，因?yàn)樗惴ㄖ袑?duì)N的每一個(gè)非空子集都要進(jìn)行一次計(jì)算，而N的非空子集共有 $2^n$ -1個(gè)，因此不能直接使用動(dòng)態(tài)規(guī)劃方法來求解該問題

進(jìn)一步求解

Johnson不等式：min{ $a_j$ , $b_i$ } ≥ min{ $a_i$ , $b_j$ }
當(dāng)min{ $a_i$ , $a_j$ , $b_i$ , $b_j$ }為 $a_i$ 或者 $b_j$ 時(shí)，Johnson不等式成立，此時(shí)把i排在前j排在后的調(diào)度用時(shí)較少；反之，若min{ $a_i$ , $a_j$ , $b_i$ , $b_j$ }為 $a_j$ 或者 $b_i$ 時(shí)，則j排在前i排在后的調(diào)度用時(shí)較少
推廣：當(dāng)min{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }= $a_k$ 時(shí)，則對(duì)任何i≠k，都有min{ $a_i$ , $b_k$ } ≥ min{ $a_k$ , $b_i$ }成立，故此時(shí)應(yīng)將作業(yè)k安排在最前面，作為最優(yōu)調(diào)度的第一個(gè)執(zhí)行的作業(yè);當(dāng)min{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }= $b_k$ 時(shí)，則對(duì)任何i≠k，都有min{ $a_k$ , $b_i$ } ≥ min{ $a_i$ , $b_k$ }成立，故此時(shí)應(yīng)將作業(yè)k安排在最后面，作為最優(yōu)調(diào)度的最后一個(gè)執(zhí)行的作業(yè)
n個(gè)作業(yè)中首先開工（或最后開工）的作業(yè)確定之后，對(duì)剩下的n-1個(gè)作業(yè)采用相同方法可再確定其中的一個(gè)作業(yè),應(yīng)作為n-1個(gè)作業(yè)中最先或最后執(zhí)行的作業(yè)；反復(fù)使用這個(gè)方法直到最后只剩一個(gè)作業(yè)為止，即可確定最優(yōu)調(diào)度
為O(nlgn)

總結(jié)

滿足1）高度重復(fù)性 2）最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，一般采用動(dòng)態(tài)規(guī)劃法，但偶爾也可能得不到高效的算法
若問題本身不是NP-hard問題，進(jìn)一步分析后就有可能獲得效率較高的算法
若問題本身就是NP-hard問題，與其它的精確算法相比，動(dòng)態(tài)規(guī)劃法性能一般不算太壞，但有時(shí)需要對(duì)動(dòng)態(tài)規(guī)劃法作進(jìn)一步的加工

備忘錄LCS

備忘錄方法

當(dāng)某個(gè)問題可以用動(dòng)態(tài)規(guī)劃法求解,但二維數(shù)組中有相當(dāng)一部分元素在整個(gè)計(jì)算中都不會(huì)被用到
因此，不需要以遞推方式逐個(gè)計(jì)算二維數(shù)組中元素，而采用備忘錄方法：數(shù)組中的元素只是在需要計(jì)算時(shí)才去計(jì)算，計(jì)算采用遞歸方式，值計(jì)算出來之后將其保存起來以備它用
若有大量的子問題無需求解時(shí)，用備忘錄方法較省時(shí)

求解

當(dāng) $x_i$ = $y_j$ 時(shí)，求C[i,j]只需知道C[i-1,j-1]，而無需用到C[i,0]～C[i,j-1]及C[i-1,j]～C[i-1,n]，所以只需求出一個(gè)LCS時(shí)，可能有一些C[p,q]在整個(gè)求解過程中都不會(huì)用到
將C[i,0]與C[0,j] 初始化為0，其余m×n個(gè)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] 兩者中有一個(gè)等于-1（尚未計(jì)算出來），或兩者均等于-1，就遞歸調(diào)用LCS將其計(jì)算出來，然后再把max{ C[i-1,j], C[i,j-1]} 賦給C[i,j]

最長(zhǎng)遞增子序列問題（LIS）

問題

假設(shè)A =< $a_1$ , $??_2$ , … , $??_??$ >為由n個(gè)不同的實(shí)數(shù)組成的序列
遞增子序列?? =< $a_{??_1}$ , $a_{??_2}$ , … , $a_{??_m}$ >
其中 $??_1$ < $??_2$ <…< $??_??$ 并且 $a_{??_1}$ < $a_{??_2}$ < … < $a_{??_m}$
求最大的??值

最大子段和問題

問題

n個(gè)整數(shù)序列 $a_1$ … $a_n$ ，求該序列形如 $\sum_{k=i}^ja_k$ 的子段和的最大值
當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0

分治解法

如果將所給的序列a[1..n]分為長(zhǎng)度相等的兩段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]的最大子段和為 $\sum_{k=i}^ja_k$ ，1≤ i ≤ n/2，n/2+1 ≤ j ≤ n
對(duì)于1、2可以遞歸求解
對(duì)于3:
a[n/2]、a[n/2+1]在最優(yōu)子序列中
可以在a[1:n/2]中計(jì)算出 $s_1$ = $max_{1≤ i ≤ n/2}\sum_{k=i}^ja_k$
可以在a[n/2+1:n]中計(jì)算出 $s_2$ = $max_{n/2+1 ≤ i ≤ n}\sum_{k=n/2+1}^ia_k$
$s_1$ + $s_2$ 即為最優(yōu)

代碼

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ì)算時(shí)間T(n)滿足典型的分治算法遞歸式：

$T(n)=\left\{ \begin{aligned} O(1) && n≤c \\ 2T(n/2)+O(n) && n>c \\ \end{aligned} \right.$

基于主方法和主定理，T(n)=O(nlogn)

動(dòng)態(tài)規(guī)劃解法

記b[j]= $max_{1≤i<j}\sum_{k=i}^ja_k$ ，1≤j≤n，則
$max_{1≤i≤j≤n}\sum_{k=i}^ja[k]$ = $max_{1≤j≤n}max_{1≤i≤j}\sum_{k=i}^ja[k]$ = $max_{1≤j≤n}b[j]$
因此，當(dāng)b[j-1]>0,b[j]=b[j-1]+a[j]；否則，b[j]=a[j]。得出
b[j]= $max_{1≤j≤n}{b[j-1]+a[j],a[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)

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

動(dòng)態(tài)規(guī)劃例題

動(dòng)態(tài)規(guī)劃例題

最優(yōu)二分搜索樹

二分搜索樹

查詢操作

定義

分析

優(yōu)化

流水作業(yè)調(diào)度

問題

分析

求解

進(jìn)一步求解

總結(jié)

備忘錄LCS

備忘錄方法

求解

最長(zhǎng)遞增子序列問題（LIS）

問題

最大子段和問題

問題

分治解法

代碼

分析

動(dòng)態(tài)規(guī)劃解法

代碼

分析

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

動(dòng)態(tài)規(guī)劃例題

最優(yōu)二分搜索樹

二分搜索樹

查詢操作

定義

分析

優(yōu)化

流水作業(yè)調(diào)度

問題

分析

求解

進(jìn)一步求解

總結(jié)

備忘錄LCS

備忘錄方法

求解

最長(zhǎng)遞增子序列問題（LIS）

問題

最大子段和問題

問題

分治解法

代碼

分析

動(dòng)態(tài)規(guī)劃解法

代碼

分析

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av