黃曉愉《深度優(yōu)先搜索問題的優(yōu)化技巧》.ppt

深度優(yōu)先搜索問題的優(yōu)化技巧,重慶一中 黃曉愉,深度優(yōu)先搜索的優(yōu)化技巧,在深度優(yōu)先搜索中如何運(yùn)用題目中的約束條件為我們提供剪枝是影響程序效率的關(guān)鍵。而搜索的順序和搜索的對象對于這一點(diǎn)是十分重要的。,搜索順序的選擇,我們先來看一道比較簡單的題目： (zju1937) 已知一個數(shù)列a0,a1am其中 a0 = 1 am = n a0 a1 a2 . am-1 am 對于每個k(1=k=m),ak=ai+aj (0 = i, j = k-1)，這里i與j可以相等?，F(xiàn)給定n的值，要求m的最小值,簡單的分析,依次搜索是很容易想到的方法，而對于每個數(shù)的取值，我們顯然可以采用從小到大搜索和從大到小搜索兩種搜索方法。,由于題目要求的是m的最小值，也就是需要我們盡快構(gòu)造出n，所以每次構(gòu)造的數(shù)應(yīng)當(dāng)是盡可能大的數(shù) 。,不同搜索順序效率比較,兩種搜索順序比較：,N,時間/s,顯然，不同的順序?qū)е铝顺绦蛐实牟煌?1、從小到大搜索每個數(shù)值,2、從大到小搜索每個數(shù)值,以往比賽中的情況,IOI2000中的BLOCK,NOI2005中的智慧珠,將木塊從大到小經(jīng)過旋轉(zhuǎn)和反轉(zhuǎn)后，依次放入進(jìn)行搜索,滿分！,將珠子從大到小進(jìn)行搜索，不加任何其他剪枝,90分！,搜索對象的選擇,(USACOweight) 已知原數(shù)列a1，a2an中前1項,前2項,前3項前n項的和,以及后1項,后2項,后3項后n項的和,但是所有的數(shù)據(jù)都已經(jīng)被打亂了順序,還知道數(shù)列中的數(shù)存在集合中，求原數(shù)列。當(dāng)存在多組可能數(shù)列的時候求左邊的數(shù)最小的數(shù)列。 其中n=1000,S1500,一個例子,假如原數(shù)列為1 1 5 2 5，S=1，2，4，5那么知道的值就是 ：,1 = 1 2 = 1+1 7 = 1+1+5 9 = 1+1+5+2 14 = 1+1+5+2+5,5 = 5 7 = 2+5 12 = 5+2+5 13 = 1+5+2+5 14 = 1+1+5+2+5,(1 2 7 9 14 5 7 12 13 14),一般方法,從左往右依次搜索原數(shù)列每個數(shù)可能的值，然后與所知道的值進(jìn)行比較。,如何改進(jìn)？,太慢了,但是這個算法最壞的情況下擴(kuò)展的節(jié)點(diǎn)為5001000，這個算法,從已知入手分析,s2,s0,s1,s3,s4,t4,t3,t2,t1,t0,我們用 Si表示前I個數(shù)的和 Ti表示后I個數(shù)的和,對題目中數(shù)據(jù)分類,s0,s1,s2,s3,s4,t4,t3,t2,t1,t0,集合A,集合B,任意I滿足：Si+Tn-I=Sn=Tn,分析,在集合A和集合B中：,S0S1S2Sn,T0T1T2Tn,XiS,Si-Si-1,Ti-Ti-1,猜想？,在搜索中從小到大搜索每個Si和Ti的位置。,由具體分析,對于原數(shù)列：1 1 5 2 5，S=1,2,4,5 由它得到的值為： 1 2 7 9 14 5 7 12 13 14,排序后為：,1 2 5 7 7 9 12 13,14 14,13,12,9,7,7,5,2,1,原數(shù)列：,1,1,這樣，對于這個數(shù)據(jù)，我們已經(jīng)構(gòu)造出了原數(shù)列。,改變搜索對象,題目的約束條件集中在Si和Ti中，我們改變搜索的對象，不再搜索原數(shù)列中每個數(shù)的值，而是搜索給出的數(shù)中出現(xiàn)在Si或者Ti中的位置。又由于Si+1與Si的約束關(guān)系，提示我們在搜索中按照Si中i遞增或者遞減的順序進(jìn)行搜索。,推而廣之,當(dāng)我們已經(jīng)搜索出原數(shù)列的a1，a2ai和an,an-1aj，此時搜索排序后第k小的數(shù)Wk,只可能有兩種存在的可能：,Try(I,j),Wk,WkSiS?,WkTjS?,Try(I+1,j),Try(I,j-1),else,Exit,AI+1=Wk,Aj-1=Wk,這個算法在最壞情況下擴(kuò)展的節(jié)點(diǎn)為21000(實際中遠(yuǎn)遠(yuǎn)小于這個數(shù))，在搜索的同時可以利用Si+Tn-I=Sn=Tn這個約束條件進(jìn)行剪枝。程序效率得到顯著的提高。兩個程序效率對比：,小結(jié),原始的搜索方法搜索量巨大，我們通過分析，選擇適當(dāng)?shù)乃阉鲗ο?，在搜索量減少的同時充分利用了題目的約束條件，成為了程序的一個有利的剪枝，