最長不下降序列動態(tài)規(guī)劃 4.ppt

1、動態(tài)規(guī)劃（四）,求最長不下降序列,問題描述： 設有一個正整數(shù)的序列：b1, b2, bn, 對于下標i1i2ih, 若有bi1bi2bih，則稱存在一個長度為h的不下降序列。 例如，下列數(shù) 13 7 9 16 38 24 27 38 44 49 21 52 63 15 對于下標 i1=1,i2=4,i3=5,i4=9,i5=13, 且滿足 13 16 38 44 63 則存在長度為5的不下降序列。 但是，我們看到還存在其它的不下降序列。如 7 9 16 18 19 21 22 63 則存在長度為8的不下降序列。 問題：當給定b1, b2, bn后，求出最長的不下降序列h及這個序列中的各個數(shù)。,

2、最長不下降序列-分析,動態(tài)規(guī)劃的難點之一：怎樣定義問題？你首先要能定義出問題是什么，才能進一步定義出子問題是什么，然后才能證明或者直觀地感覺問題與子問題之間是否存在最優(yōu)子結(jié)構(gòu)性質(zhì)。 從前往后分析。從序列長度為1開始，逐步放大序列長度，2，3，4看看要求的結(jié)果的變化規(guī)律。我們可能會很直接地想到，把問題定義成當前最長不下降序列。 序列長度序列 當前最長不下降序列長度 1131 213 71 313 7 92 413 7 9 163 513 7 9 16 384 613 7 9 16 38 244 （2438, 長度不增加） 713 7 9 16 38 24 27? (憑什么計算出當前值？) 由于當

3、前記錄的最長不下降序列是 7 9 16 38 ，而實際上應該有了更長的子序列 7 9 16 24 27。,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-分析,我們定義F(i) 為原始序列長度為I 的最長不下降序列，則F(I)只有一個子問題F(I-1)，即原始序列長度為I-1的最長不下降序列。而且我們無法得出問題與子問題之間的“最優(yōu)子結(jié)構(gòu)”性質(zhì)。 重新思考關(guān)于問題的定義。我們定義問題F(i)為以bi結(jié)束的最長不下降序列。則得到如下的分析結(jié)果： 下標I序列F(I)前趨結(jié)點下標 1311 13 7 12 13 7 922 13 7 9 1633 13

4、 7 9 16 3844 13 7 9 16 38 2444 13 7 9 16 38 24 2756 13 7 9 16 38 24 27 3867,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-分析,當我們定義問題F(i)為以bi結(jié)束的最長不下降序列時，則問題F(I)有I-1個子問題：F(1), F(2), F(I-1)。我們要使F(I)最大，則要找到一個F(j)最大的子問題，且同時滿足Bj Bi，這時F(I) := F(j) + 1 例如 F(4) 有3個子問題，分別是F(1), F(2), F(3), 它們都滿足bj bi的條件，而最大

5、的F(j)=2, 因此F(4) := F(3)+1=3, 而它的前趨結(jié)點下標是j,13 7 9 16 38 24 27 38 44 49 21 52 63 15,下標I序列F(I)前趨結(jié)點下標 1311 13 7 12 13 7 922 13 7 9 1633 13 7 9 16 3844 13 7 9 16 38 2444 13 7 9 16 38 24 2756 13 7 9 16 38 24 27 3867,最長不下降序列-分析,這樣定義問題，我們就看到了“最優(yōu)子結(jié)構(gòu)”性質(zhì)。因此可以應用動態(tài)規(guī)劃方法求解問題。 請你分析本問題的重疊子問題性質(zhì)。 請你遞歸地定義問題的解。 F(I) = Ma

6、xF(j)+1 | j I 且 bj = bi 本遞歸式的邊界條件是什么？ F(1) = 1, f(I)= 1 請你思考本題要求的結(jié)果是F(n)嗎？如果不是，那么最后要求的結(jié)果怎樣利用用動態(tài)規(guī)劃求得的問題和子問題的值得到？ 怎樣輸出顯示最長不下降序列的各個結(jié)點？,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-分析,寫出完整的求最長不下降序列的程序。上機調(diào)試。,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-討論,如果從后向前分析原始序列，會得到正確的結(jié)果嗎？又該怎樣定義問題？寫出從后向前求最長不下降序列的程序。,13 7 9 16 38 24 27 38 44 49 21 52 63 15,var f:array1.5000 of longint;a:array1.5000 of longint;i,n,j,k,l:longint;beginreadln(n);for i:=1 to n doread(ai);f1:=1;for i:=2 to n do beginfi:=1;for j:=1 t