試題、程序及解題報告樓天城

第13頁共13頁第12頁共1頁PAGE8淺談部分搜索+高效算法在搜索問題中的應用浙江省杭州第十四中學樓天城摘要：本文從有位置限制的匹配問題的搜索談起，通過對題目MilkBottleData的分析，提出了深度優(yōu)先搜索的一種非常規(guī)搜索——部分搜索+高效算法。然后通過部分搜索在TriangleConstruction和智破連環(huán)陣兩題中的應用，探討了部分搜索方法通用的主要優(yōu)化方法，并從此方法本質(zhì)分析其高效的原因所在和應用需要滿足的要求和限制。關鍵字：部分搜索、高效算法正文：很多題目，如果我們可以建立數(shù)學模型，應該盡量用解析法來處理，因為簡單的模型更清晰地反映了事物之間的關系。但是，并不是所有的題目都可以建立簡單的數(shù)學模型。我們這時必須使用搜索的方法，也就是枚舉所有可能情況來尋找可行解或最優(yōu)解。由于搜索建立在枚舉之上，所以搜索常常和低效是分不開的。有時搜索的運算量實在太大，實在是一件痛苦的事情。于是我們需要利用很多技巧來提高效率，可行性剪枝，最優(yōu)性剪枝和調(diào)整搜索順序等方法都很有用，在它們的幫助下，我們可以大大提高搜索的效率。而有些題目，這些常規(guī)的優(yōu)化方法很難有用武之地。這是我們必須使用一些非常規(guī)的搜索方法。本文中我們將討論非常規(guī)搜索中的一種——部分搜索+高效算法。引題：N個物品與N個位置，給定每個物品的可能放的位置集合，要求尋找一一對應的關系，但還給出物品位置之間的限制（例如：如果1放在3則2不能放在1），求一組可行解，或給每一種對應關系一個權(quán)，求滿足條件的最優(yōu)解。由于事物之間的限制關系非常復雜，很難建立簡單的二分圖關系，或者用網(wǎng)絡流來解決。面對這一系列類似的問題，我們一般只有搜索，如何搜索又如何優(yōu)化呢？簡單分析：如果我們枚舉每一個物品的位置，然后判斷，這樣的時間復雜度為O(N!)。好像似乎也只能這樣。進一步分析：我們看一個例子，N=6：其它限制有4條(a,b,c,d)表示如果a放在b則c不能放在d1356225331413262后來我們發(fā)現(xiàn)，如果我們一旦確定了3和5的位置，其它4個物品的位置之間已經(jīng)沒有限制關系了，這樣其它4個物品的位置可以通過匹配來解決。這時我們可以發(fā)現(xiàn)一個新的搜索模式：部分搜索。部分搜索：搜索一部分變量，使得余下的變量之間的關系簡化，然后通過一些高效算法（一般有匹配、解方程、貪心、動態(tài)規(guī)劃等）完成余下問題。就本題而言：先搜索一定數(shù)量（而不是全部）的物品的位置，使問題內(nèi)物品的關系簡化為二分圖關系，用二分圖匹配來解決余下的物品。本質(zhì)：其實，例如上面的例子，如果我們先知道了3和5的位置后，不用匹配，其實我們是在用搜索來求匹配，效率當然不會高。通過部分搜索為其它高效算法提供條件（例如上面的例子創(chuàng)造二分圖關系），而其它高效算法代替搜索，高效地完成余下的任務。部分搜索的方法充分發(fā)揮了搜索和其它高效算法的優(yōu)勢。搜索的優(yōu)勢在于應用性廣，可以克服復雜的情況，其他高效算法的優(yōu)勢在于效率高。兩者相互促進，同時也彌補對方的不足。這也是這個方法的成功的關鍵。部分搜索+其它高效算法已經(jīng)在很多題目中得到了應用。我們通過幾個例子來探討這種搜索方法的應用和優(yōu)化技巧。先看一個應用的例子。MilkBottleData(ACM/ICPCAsiaRegionalShanghai1996)【問題描述】一個被分為N*N個網(wǎng)格的盒子，每一格有可能包含一瓶牛奶或者什么都沒有。史密斯先生對每行從左到右記下牛奶的情況，同樣對每列從上到下記下牛奶的情況。每一條記錄包含N的數(shù)字，0表示沒有牛奶，1表示有牛奶。不幸的是，2*N條記錄的順序被打亂了，有些數(shù)字也模糊不清?，F(xiàn)在史密斯先生請你恢復原來盒子的牛奶情況。輸入：第一行：一個整數(shù)N，然后的2N行，每行有N個數(shù)字，0表示一定沒有牛奶，1表示一定有牛奶，2表示不能確定。樣例：input501210211202100112110121011210100011222221100110010output

9862741011010

1

0

0

1

010

1

1

1

030

1

0

0

15

1

1

1

0

1數(shù)據(jù)范圍：1<=N<=10初步分析：行列之間的限制關系非常復雜，很難找到多項式算法。（網(wǎng)絡流?。浚┛梢杂?2N)!的深度優(yōu)先搜索，依次枚舉每行和每列的記錄編號，然后判斷是否產(chǎn)生了矛盾。判斷方法：設：第i條記錄的第j個數(shù)字為A[i,j]。如果第a行選擇第x條記錄，第b列選擇第y條記錄，那么矛盾的條件就是：((A[x,b]<>2)and(A[y,a]<>2)and(A[x,b]<>A[y,a]))性能分析（1）：因為N<=10，(20)!*10高達24329020081766400000。試一試幾個基本的優(yōu)化：可行性剪枝：除了提前判斷，也沒有什么別的優(yōu)化。最優(yōu)性剪枝：不是最優(yōu)性問題。調(diào)整搜索順序：如果每次搜索可能性最少的，效果還是不錯的。但是最壞情況需要計算(20)!的運算量，實在不能說是個好的可行算法。部分搜索＋匹配算法我們可以發(fā)現(xiàn)行與行之間和列與列之間不存在約束關系，所有的約束關系都在行列之間。我們可不可以只搜索行呢？答案是肯定的。如果我們已經(jīng)知道了每行的值，列與列之間已經(jīng)沒有約束關系。我們當然可以用匹配來求出一組可行解。建圖方法：二分圖左邊N個點表示N個沒有被選擇的N條記錄，右邊N個點表示N列。如果將左邊第i個結(jié)點對應編號的記錄放入第j列，在第j列的每一行都不會產(chǎn)生矛盾,就在左邊第i個結(jié)點和右邊第j結(jié)點之間添一條邊。二分圖匹配可以在O(N3)的時間內(nèi)解決，比盲目搜索的效果好很多。性能分析（2）：這樣N=10時的運算量為P(20,10)*(20*10*10)=13408850145600000。效率與簡單搜索相比已有很大的提高。因為只要找到一組解就可以結(jié)束程序，所以可以很快地通過所有測試數(shù)據(jù)?？偨Y(jié)：我們可以這樣比較兩個算法，如果普通的搜索是先搜索行再搜索列，那么在搜索完行以后，它是在用搜索來找匹配。搜索的復雜度為O(N!)，而匹配的復雜度為O(N3)。搜索的效率不言而喻.本搜索算法依然可以使用幾個常規(guī)優(yōu)化。特殊的搜索方法和常規(guī)的優(yōu)化還是不矛盾的。本算法還有很多獨特優(yōu)化，我們結(jié)合兩個例子講起。例一：TriangleConstruction(ZJUMonthlyContest)【問題描述】一個邊長為N的等邊三角形可以被分為N*N個邊長為1的小的等邊三角形，如圖：

我們注意到相鄰的兩條邊必須是同一種顏色，現(xiàn)在給出這n*n個三角形的三條邊的顏色，請你判斷是否可以用這n*n個三角形構(gòu)成一個邊長為n的等邊三角形。這里只考慮n=4的情況。分析：直接搜索運算量達16!=20922789888000，實在太高了。其實，這個問題也就是一個16個物體的有位置限制的匹配問題。與引題的區(qū)別就是：位置之間的限制是確定的，我們必須充分利用這一特點。使用部分搜索＋匹配的算法，我們?nèi)绾嗡阉髂兀课覀儺斎粦撨x擇效率最高的方法。假設枚舉的三角形的數(shù)量為T，則運算量為P(16,T)*256*(16-T)。T運算量T運算量0409697439214182400161440104463528509440028601601122317642547200031118208012892705701888000413418496013267811710566400051476034560145356234211328000614760345600155356234211328000713284311040016?81062744883200結(jié)論：運算量隨T的增加而遞增。此類問題，一般情況下，枚舉的變量數(shù)量越少越好。優(yōu)化：選擇好的枚舉變量，使枚舉的變量數(shù)量盡可能少。對于此題，我們可以枚舉陰影部分的6塊，其它10塊都可以建立簡單的二分圖關系。運算量為P(16,6)*256*10加上常規(guī)的優(yōu)化效率有了很大的提高?？偨Y(jié)：搜索變量的選擇：一般以搜索變量的數(shù)目盡可能少為原則，因為高效算法的效率是多項式級別的，但是搜索是NP的。選擇方法：有時可以通過分析，例如上述兩題；但有的題目需要程序來確定搜索的變量。例二：智破連環(huán)陣(NOI2003)（一個部分搜索法優(yōu)化的經(jīng)典例子。）【問題描述】B國在耗資百億元之后終于研制出了新式武器——連環(huán)陣(ZenithProtectedLinkedHybridZone)，并聲稱這是一種無敵的自發(fā)性智能武器。但A國經(jīng)偵察發(fā)現(xiàn)，連環(huán)陣其實是由M個獨立武器組成的。這M個武器編號為1，2，…，M。每件武器有兩種狀態(tài)：無敵自衛(wèi)狀態(tài)和攻擊狀態(tài)。最初，1號武器處于攻擊狀態(tài)，其他武器都處在無敵自衛(wèi)狀態(tài)。以后，一旦第I(1i<M）號武器被消滅，1秒鐘以后第i+1號武器就自動從無敵自衛(wèi)狀態(tài)變成攻擊狀態(tài)。當?shù)贛號武器被消滅以后，這個造價昂貴的連環(huán)陣就被徹底摧毀了。為了打敗B國，A國軍事部長打算用最廉價的武器——炸彈來消滅連環(huán)陣。經(jīng)過長時間的精密探測，A國的軍事家們掌握了連環(huán)陣中M個武器的平面坐標，然后依此選擇了n個點，并在這些點上安放了特殊的定時炸彈。這n個炸彈編號為1，2，…，n。每個炸彈的作用半徑均為k，且會持續(xù)爆炸5分鐘。在這5分鐘內(nèi)，每枚炸彈都可以在瞬間消滅離它直線距離不超過k的、處在攻擊狀態(tài)的B國武器。和連環(huán)陣類似，最初a1號炸彈持續(xù)引爆5分鐘時間，然后a2號炸彈持續(xù)引爆5分鐘時間，接著a3號炸彈引爆……以此類推，直到連環(huán)陣被摧毀。在每個炸彈爆炸的時候，其它尚未引爆的炸彈都處于地下隱蔽處，不會被己方的炸彈摧毀。顯然，選好a1、a2、a3...十分重要。好的序列可以在僅使用較少炸彈的情況下就能將連環(huán)陣摧毀；壞的序列可能在使用完所有炸彈后仍無法將連環(huán)陣摧毀?，F(xiàn)在，請你決定一個序列a1、a2、a3…使得在第ax號炸彈引爆的時間內(nèi)連環(huán)陣被摧毀。這里的x應當盡量小?！据斎胛募枯斎胛募plhz.in第一行包含三個整數(shù)：M、n和k（1M,n100，1k1000），分別表示B國連環(huán)陣由M個武器組成，A國有n個炸彈可以使用，炸彈攻擊范圍為k。以下M行，每行由一對整數(shù)xi，yi（0xi，yi10000）組成，表示第i（1iM）號武器的平面坐標。再接下來n行，每行由一對整數(shù)ui，vi(0ui，vi10000)組成，表示第i（1in）號炸彈的平面坐標。輸入數(shù)據(jù)保證無誤和有解。測試數(shù)據(jù)中的xi、yi、ui、vi是隨機生成的?！据敵鑫募枯敵鑫募plhz.out的第一行包含一個整數(shù)x，表示實際使用的炸彈數(shù)。第二行包括x個整數(shù)，依次表示a1，a2，…，ax。初步分析：A國炸彈I可以炸到B國武器J的條件:(u[i]-x[j])2+(v[i]-y[j])2<=r2結(jié)論：很難找到求最優(yōu)解的多項式算法。面對此類問題，一般只有搜索策略。進一步分析：每一顆炸彈必定炸掉B國武器中編號連續(xù)的一段。5分鐘只是表明每一顆炸彈可以炸掉任意多個編號連續(xù)的B國武器。部分搜索：此題使用部分搜索的算法需要一些轉(zhuǎn)化：如果已經(jīng)將B國武器根據(jù)編號分為x段，[Si,Ti](S1=1,Ti>=Si,Ti+1=Si+1)。然后判斷是否可以從A國的N顆炸彈中選出x顆，分別可以炸掉其中的一段。其實我們把搜索分為了兩部分，先通過搜索將B國武器根據(jù)編號分為x段，再通過搜索判斷是否可以從A國的N顆炸彈中選出x顆，分別可以炸掉其中的一段。其實第二部分可以用匹配來解決。C[S][T][I]表示A國炸彈I是否可以炸到B國武器S,S+1..T-1,T。C[S][S][I]=((u[I]-x[S])2+(v[I]-y[S])2<=R2)C[S][T][I]=C[S][T-1][I]&C[T][T][I](S<T)求C的時間復雜度為O(N3)。建圖：左邊x個點，表示B國武器根據(jù)編號分為的x段，右邊N個點，表示A國的N顆炸彈。左邊第i個點到右邊第j個點有邊的條件即：C[Si][Ti][j]。搜索的任務就是將B國武器根據(jù)編號劃分為若干段+二分圖匹配判斷。性能分析（1）：搜索的基本框架已經(jīng)建立，雖然數(shù)據(jù)是隨機生成的，但是M個B國武器的劃分方案還是非常多的，有時可能高達2m。時間上很難承受，如果使用卡時，正確性受到影響，效果不會很好。只有4個數(shù)據(jù)可以在時限內(nèi)出解，另外6個如果卡時，有1個也可以得到最優(yōu)解。優(yōu)化：優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。優(yōu)化一（最優(yōu)性）：如果A國炸彈可以重復使用，設：Dist[i]=炸掉B國武器i－m的最少使用炸彈數(shù)。可以用動態(tài)規(guī)劃計算Dist值，狀態(tài)轉(zhuǎn)移方程如下：Dist[m+1]=0。Dist[i]=Min(Dist[j]+1|Can[i][j-1][k](1<=k<=n))(1<=i<=n)(i<j<=n+1)求Dist的時間復雜度為O(N3)。從而產(chǎn)生了一個最優(yōu)性剪枝條件：if當前已經(jīng)使用的炸彈數(shù)+Dist[當前已經(jīng)炸掉的B國武器數(shù)+1]>=當前找到的最優(yōu)解then剪枝；優(yōu)化二（可行性）：此搜索方法一般都可以用兩個效果很好的可行性優(yōu)化：(1)提前判斷是否可以匹配成功，避免多余的搜索。(2)每次匹配可以從以前的匹配開始擴展，不需要重新開始。如果當前的劃分方法已經(jīng)無法匹配成功，就沒有搜索下去的必要了，只要每搜索新的一段時立即通過匹配判斷即可。每次求匹配只要從原來的基礎上擴展就可以了。通過上述兩個優(yōu)化，程序的效率有了很大的提高。性能分析（2）：雖然通過上述兩個優(yōu)化，程序的效率較原來的搜索有了很大的提高。10個測試數(shù)據(jù)中有8個可以在時限內(nèi)出解，另外2個如果卡時，有1個也可以得到最優(yōu)解。進一步優(yōu)化：優(yōu)化二雖然排除了許多不必要的劃分，但是在判斷時浪費了不少時間。因此，在枚舉劃分長度時，可以通過以前的劃分和匹配情況（被匹配的邊），用O(n2)的時間復雜度的寬度優(yōu)先搜索計算出下一個劃分的最大長度maxL，顯然下一個劃分的長度在[1，maxL]都一定可以找到可行的匹配。這樣既節(jié)省了判斷的時間，又可以使每次劃分長度從長到短枚舉，使程序盡快逼近最優(yōu)解，同時增強了剪枝條件一的效果。這一部分的實現(xiàn)，首先需要求MaxT。MaxT[I][S]=炸彈i，從S開始炸，可以炸到的最大編號。如果，炸彈i炸不到S，則MaxT[I][S]=S-1。求MaxT[I][S]可以用動態(tài)規(guī)劃的方法解決。狀態(tài)轉(zhuǎn)移方程為：MaxT[I][S]=炸彈i炸不到SS-1炸彈i炸得到SMaxT[i][S+1]MaxT[i][m+1]=m求MaxT的時間復雜度為O(N2)。具體實現(xiàn)方法，考慮二分圖右邊的n個結(jié)點（n顆炸彈），如果結(jié)點i沒有匹配，i被認為可以使用。對于一個已經(jīng)匹配的結(jié)點i，如果從任何一個沒有匹配的結(jié)點出發(fā)存在一條到達i，而且i為外點的交錯路，i也被認為可以使用。計算所有從沒有匹配點出發(fā)的交錯路（沒有匹配點i出發(fā)的交錯路沒有被匹配點i一定為外點）所能到達的匹配的結(jié)點，只要從每一個沒有匹配的結(jié)點出發(fā)，寬度優(yōu)先搜索，只要O(N2)的時間。注意判斷重復（如果一個已經(jīng)匹配的結(jié)點已經(jīng)被確定為可以使用，那么不需要對它再擴展一次，因為當把這個已經(jīng)匹配的結(jié)點確定為可以使用的結(jié)點的時候，已經(jīng)從這個結(jié)點擴展過，如果再擴展必將產(chǎn)生無謂的重復）所以MaxL=Max(MaxT[I][S]|i可以使用)；性能分析（3）：通過以上的優(yōu)化，所有數(shù)據(jù)都是瞬間出解，并且所有結(jié)果都是最優(yōu)解。甚至對n=200的隨機數(shù)據(jù)，也可以在瞬間出解，可見程序的效率有了很大的提高。精益求精：另外，還有兩個優(yōu)化，但是有時效果不好，但也值得一提。優(yōu)化三：分支定界。這樣可以增強剪枝條件一的效果，但是當最優(yōu)解與Dist[1]相差比較遠的時候，會浪費一定的時間。優(yōu)化四：優(yōu)化一中Dist[i]的值有時并不是最優(yōu)的，通過測試，發(fā)現(xiàn)如果Dist[i]的值與最優(yōu)值相差1，特別是當i小的時候，程序的速度都會有明顯的影響。所以，可以通過同樣的搜索來計算Dist[i]，（本題的答案就是Dist[1]）。這樣做可以增強剪枝條件一的效果，但是同時對每個i都要搜索也浪費了一定的時間。程序結(jié)果比較：12345678910最簡單的搜索0.000.000.50TimeOver0.65TimeOverTimeOverTimeOverTimeOverTimeOver優(yōu)化的搜索0.010.010.10TimeOver0.500.80TimeOver0.550.300.80進一步優(yōu)化的搜索0.010.010.020.030.000.020.020.010.020.02此搜索方法一般都可以用兩個效果很好的可行性優(yōu)化：(1)提前判斷是否可以成功，避免多余的搜索。(2)每次判斷盡量多利用以前的判斷結(jié)果?？偨Y(jié)：本文中的幾個例子都可以應用部分搜索的方法高效解決，它們在思想上有著明顯的相同點。一般的思維過程如下：一般的優(yōu)化包括：（1）選擇好的枚舉變量，使枚舉的變量數(shù)量盡可能少。（2）盡可能充分利用以前的結(jié)果，提前判斷，避免多余的搜索。部分搜索同樣可以和解方程、貪心、動態(tài)規(guī)劃等高效算法結(jié)合。部分搜索＋高效算法體現(xiàn)了搜索與其他方法的有機結(jié)合，充分發(fā)揮兩者的長處，相互彌補對方的不足，這就是其高效的主要原因所在。因此，在搜索問題中靈活地應用部分搜索的方法，往往可以創(chuàng)造出奇效。值得注意的是，部分搜索來解決搜索問題作為一種非常規(guī)的搜索方法。雖然在本文的例子中，部分搜索有著很多的過人之處，但是并不能認為常規(guī)方法一定不如非常規(guī)方法。大多數(shù)的搜索問題還是適合用常規(guī)的搜索方法的，所以只有充分把握部分搜索的特點，使之與常規(guī)的搜索融會貫通，才能真正得到高效的搜索算法。參考文獻：ACM/ICPCAsiaRegionalShanghai1996(MilkBottleData)ZJUMonthlyContest(TriangleConstruction)NOI2003(智破連環(huán)陣)感謝：ZhejiangUniversityOnlineJudge提供(MilkBottleData)和(TriangleConstruction)的題目描述。附錄：智破連環(huán)陣參考程序：#include<stdio.h>#include<stdlib.h>#include<string.h>constintmaxm=100+2;constintmaxn=100+2;intn,m,dist[maxm],MaxT[maxm][maxn];boolreachable[maxm][maxn],*can[maxm][maxm];/*m=B國武器數(shù)。n=A國炸彈數(shù)。dist[i]=如果A國炸彈可以重復使用，炸掉B國武器I~m的最少使用炸彈數(shù)。MaxT[s][i]=炸彈I，從S開始炸，可以炸到的最大編號，如果炸彈I炸不到S，則MaxT[I][S]=S-1。reachable[i][j]=A國炸彈i是否可以炸到B國炸彈j。can[s][t][i]=表示A國炸彈I是否可以炸到B國武器S,S+1..T-1,T。*/intanswer,bestv[maxn];/*answer=最少需要的A國炸彈數(shù)。bestv=記錄取最優(yōu)解A國炸彈的使用序列。*/inta[maxm],b[maxn];boolvis[maxn],*g[maxm];/*a[i],b[i]用于匹配，分別記錄左（右）第i個點的匹配邊的另一個點的編號，如果沒有匹配則為0。vis[i]用于匹配和寬度優(yōu)先搜索時判重。g[i][j]=左邊第i個點到右邊第j個點是否有邊。*/voidinit(){ //讀入數(shù)據(jù)并計算reachable。 intx1[maxm],y1[maxm],x2[maxn],y2[maxn],i,j,R; scanf("%d%d%d",&m,&n,&R); for(i=1;i<=m;i++) scanf("%d%d",&x1[i],&y1[i]); for(i=1;i<=n;i++) scanf("%d%d",&x2[i],&y2[i]); for(i=1;i<=m;i++) for(j=1;j<=n;j++) reachable[i][j]=((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j])<=R*R);}voidpreprocess(){ //初始化，計算can,MaxT。 ints,t,i; for(i=1;i<=m;i++) g[i]=newbool[maxn]; for(s=1;s<=m;s++) for(t=s;t<=m;t++) can[s][t]=newbool[maxn]; for(s=1;s<=m;s++) { for(i=1;i<=n;i++) can[s][s][i]=reachable[s][i]; for(t=s+1;t<=m;t++) for(i=1;i<=n;i++) can[s][t][i]=can[s][t-1][i]&&reachable[t][i]; for(i=1;i<=n;i++) { MaxT[s][i]=s-1; for(t=s;t<=m;t++) if(can[s][t][i]) MaxT[s][i]=t; } } //計算dist dist[m+1]=0; for(s=m;s>=1;s--) { t=s-1; for(i=1;i<=n;i++) if(MaxT[s][i]>t) t=MaxT[s][i]; dist[s]=1+dist[t+1]; }}boolfind(intv){ //匈牙利算法找可增廣路。 for(inti=1;i<=n;i++) if(g[v][i]&&!vis[i]) { vis[i]=true; if(b[i]==0||find(b[i])) { a[v]=i; b[i]=v; returntrue; } } returnfalse;}voidsearch(intused,ints){ //狀態(tài)：已經(jīng)使用了used個A國炸彈，編號在s之前的B國武器都已經(jīng)炸毀。 if(used+dist[s]>=answer)//優(yōu)化一：最優(yōu)性剪枝 return; if(s==m+1) { //如果B國武器已經(jīng)全部炸毀，