國家集訓隊作業(yè)ltc

1、匹配算法在搜索問題中的巧用 浙江省杭州第十四中學 樓天城 很多的題目，如果我們可以建立數(shù)學模型，應該盡量用解析法來處理，因為簡單的模型更清晰地反映了事物之間的關系。但是，并不是所有的題目都可以建立簡單的數(shù)學模型。我們這時必須使用搜索的方法，也就是枚舉所有可能情況來尋找可行解或最優(yōu)解。前言由于搜索一般建立在枚舉之上，所以搜索常常和低效是分不開的。有時搜索的運算量實在太大，實在是一件痛苦的事情。于是我們需要利用很多技巧來提高效率：可行性剪枝， 最優(yōu)性剪枝， 調(diào)整搜索順序， 等方法都很有用，在它們的幫助下，我們可以大大提高搜索的效率。而有些題目，這些常規(guī)的優(yōu)化方法很難有用武之地。這是我們必須使用一些

2、非常規(guī)的搜索方法。本文中我們將討論非常規(guī)搜索中的一種部分搜索+匹配算法引題：N個物品與N個位置，給定每個物品的可能放的位置集合，要求尋找一一對應的關系。但還給出物品位置之間的限制（例如：如果1放在3則2不能放在1）。求一組可行解，或給每一種對應關系一個權，求滿足條件的最優(yōu)解。由于事物之間的限制關系非常復雜，很難建立簡單的二分圖關系，或者用網(wǎng)絡流來解決。面對這一系列類似的問題，我們一般只有搜索，如何搜索又如何優(yōu)化呢？簡單分析：如果我們枚舉每一個物品的位置，然后判斷。這樣的時間復雜度為O(N!)。好像似乎也只能這樣。進一步分析：我們看一個例子，N=6：其它限制有4條(a,b,c,d)表示如果a放在

3、b則c不能放在d1 3 5 62 2 5 33 1 4 13 2 6 2我們發(fā)現(xiàn)，如果我們一旦確定了3和5的位置，其它4個物品的位置之間已經(jīng)沒有限制關系了，這樣其它4個物品的位置可以通過匹配來解決。這時我們發(fā)現(xiàn)一個新的搜索方法：部分搜索+匹配。 1 3 5 62 2 5 33 1 4 13 2 6 2部分搜索+匹配： 搜索一部分變量，使得余下的變量之間的關系簡化，然后通過一些高效算法（匹配）完成余下問題。就本題而言就是：先搜索一定數(shù)量（而不是全部）的物品的位置，使問題內(nèi)其它物品的關系簡化為二分圖關系，用二分圖匹配來解決余下的物品。通過部分搜索為匹配算法提供條件（例如上面的例子創(chuàng)造二分圖關系），

4、而匹配算法代替搜索，高效地完成余下的任務。部分搜索+匹配的方法充分發(fā)揮了搜索和匹配算法的雙重優(yōu)勢。搜索的優(yōu)勢在于應用性廣，可以克服復雜的情況，匹配算法的優(yōu)勢在于效率高。兩者相互促進，同時也彌補對方的不足。這也是這個方法的成功的關鍵。例如上面的例子，如果我們先知道了3和5的位置后，不用匹配，其實我們是在用搜索來求匹配，效率當然不會高。部分搜索+匹配的方法已經(jīng)在很多題目中得到了應用。一個部分搜索+匹配算法的經(jīng)典例子。智破連環(huán)陣題目簡述(NOI2003二試第三題)B國的連環(huán)陣由M個武器組成。最初，1號武器處于攻擊狀態(tài)，其他武器都處在無敵自衛(wèi)狀態(tài)。以后，一旦第i（1 iM）號武器被消滅，1秒鐘以后第i

5、+1號武器就自動從無敵自衛(wèi)狀態(tài)變成攻擊狀態(tài)。 A國有N個炸彈，每個炸彈的作用半徑均為k，且會持續(xù)爆炸5分鐘。在這5分鐘內(nèi)，瞬間消滅離它直線距離不超過k的、處在攻擊狀態(tài)的B國武器，不會炸毀本國炸彈。任務：決定一個序列a1、a2、a3使得在第ax號炸彈引爆的時間內(nèi)連環(huán)陣被摧毀。這里的x應當盡量小。輸入：N,M及武器和炸彈的坐標。測試數(shù)據(jù)中的坐標是隨機生成的。 初步分析：A國炸彈I可以炸到B國武器J的條件： (uI-xJ)2+(vI-yJ)2=Si,Ti+1=Si+1)。然后的任務就是判斷是否可以從A國的N顆炸彈中選出x顆，分別可以炸掉其中的一段。其實我們把搜索分為了兩部分，（）將B國武器根據(jù)編號分

6、為x段。（）判斷是否可以從A國的N顆炸彈中選出x顆，分別可以炸掉其中的一段。其實第二部分可以用匹配來解決。建圖：CSTI 表示A國炸彈I是否可以炸到B國武器S,S+1.T-1,T。CSSI=(uI-xS)2+(vI-yS)2=R2)CSTI=CST-1I & CTTI (ST)求C的時間復雜度為O(N3)。建圖：左邊x個點，表示B國武器根據(jù)編號分為的x段，右邊N個點，表示A國的N顆炸彈。左邊第i個點到右邊第j個點有邊的條件即：CSiTij。下面任務就是將B國武器根據(jù)編號劃分為若干段+二分圖匹配判斷。樣例1：4 3 60 6 6 6 6 0 0 01 5 0 3 1 1如果的劃分方法是：x=3，

7、3段分別為1-2,3-3,4-4最大匹配=x，滿足如果的劃分方法是：x=4，4段分別為1-1,2-2,3-3,4-4最大匹配x，不滿足性能分析（1）：搜索的基本框架已經(jīng)建立，雖然數(shù)據(jù)是隨機生成的，但是m個B國武器的劃分方案還是非常多的，有時可能高達2m。時間上很難承受，如果使用卡時，正確性受到影響，效果不會很好。只有4個數(shù)據(jù)可以在時限內(nèi)出解，另外6個如果卡時，有2個也可以得到最優(yōu)解。優(yōu)化： 優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。優(yōu)化一（最優(yōu)性）：如果A國炸彈可以重復使用，設：DistI=炸掉B國武器Im的最少使用炸彈數(shù)?？梢杂脛討B(tài)規(guī)劃計算Dist值，狀態(tài)轉(zhuǎn)移方程如下：Distm+1=0。Dis

8、tI=Min(DistJ+1 | CanIJ-1K(1=K=n) (1=I=N) (IJ=當前找到的最優(yōu)解)then 剪枝；優(yōu)化二（可行性）：部分搜索匹配的方法一般都可以用兩個效果很好的可行性優(yōu)化：(1)提前判斷是否可以匹配成功，避免多余的搜索。(2)每次匹配可以從以前的匹配開始擴展，不需要重新開始。如果當前的劃分方法已經(jīng)無法匹配成功，就沒有搜索下去的必要了，只要每搜索新的一段時立即通過匹配判斷即可。每次求匹配只要從原來的基礎上擴展就可以了。沒有必要從頭開始。性能分析（2）：通過上述兩個優(yōu)化，程序的效率有了很大的提高。 10個測試數(shù)據(jù)中有8個可以在時限內(nèi)出解，另外2個如果卡時，也可以得到最優(yōu)解

9、。進一步優(yōu)化：優(yōu)化二雖然排除了許多不必要的劃分，但是在判斷時浪費了不少時間。因此，在枚舉劃分長度時，可以通過以前的劃分和匹配情況（被匹配的邊），用O(n2)的時間復雜度的寬度優(yōu)先搜索計算出下一個劃分的最大長度maxL，顯然下一個劃分的長度在1，maxL都一定可以找到可行的匹配。這樣既節(jié)省了判斷的時間，又可以使每次劃分長度從長到短枚舉，使程序盡快逼近最優(yōu)解，從而同時增強剪枝條件一的效果。這一部分的實現(xiàn)，首先需要求MaxT。MaxTIS=炸彈I，從S開始炸，可以炸到的最大編號。 如果，炸彈I炸不到S，則MaxTIS=S-1。求MaxTIS可以用動態(tài)規(guī)劃的方法解決。狀態(tài)轉(zhuǎn)移方程為：MaxTIS= 炸

10、彈I炸不到S S-1 炸彈I炸得到S MaxTIS+1MaxTIm+1=m求MaxT的時間復雜度為O(N2)。具體實現(xiàn)方法： 考慮二分圖右邊的n個結(jié)點（n顆炸彈），如果結(jié)點I沒有被匹配，I被認為可以使用。如果結(jié)點I已經(jīng)被匹配，如果從任何一個沒有匹配的結(jié)點出發(fā)存在一條到達I，而且I為外點的交錯路，I也被認為可以使用。所以MaxL=Max(MaxTIS | I可以使用)；具體實現(xiàn)方法：計算所有從沒有匹配點出發(fā)的交錯路（沒有匹配點I出發(fā)的交錯路沒有被匹配點I一定為外點）所能到達的匹配的結(jié)點，只要從每一個沒有匹配的結(jié)點出發(fā)，寬度優(yōu)先搜索，只要O(N2)的時間。注意判斷重復（如果一個已經(jīng)匹配的結(jié)點已經(jīng)被

11、確定為可以使用，那么不需要對它再擴展一次，因為當把這個已經(jīng)匹配的結(jié)點確定為可以使用的結(jié)點的時候，已經(jīng)從這個結(jié)點擴展過，如果再擴展必將產(chǎn)生無謂的重復）如果已經(jīng)求出了MaxL，可以先求一組長度為MaxL的匹配A，這樣對于所有長度在1-MaxL范圍內(nèi)的劃分，A都是一組可行匹配。擴展一次增廣路的復雜度為O(n2)。這樣大大節(jié)省了優(yōu)化二的時間。性能分析（3）：通過以上的優(yōu)化，所有數(shù)據(jù)都是瞬間出解，并且所有結(jié)果都是最優(yōu)解。甚至對n=200的隨機數(shù)據(jù)，也可以在瞬間出解，可見程序的效率有了很大的提高。最簡單的搜索 優(yōu)化的搜索 進一步優(yōu)化的搜索 10.000.010.0120.000.010.0130.500.

12、100.024TimeOverTimeOver0.0350.650.210.006TimeOver0.260.027TimeOverTimeOver0.028TimeOver0.260.019TimeOver0.100.0210TimeOver0.400.02總結(jié)：本文中的兩個例子都可以應用部分搜索匹配的方法高效解決。它們在思想上有著明顯的相同點。一般的思維過程如下：一般的優(yōu)化包括：(1)提前通過匹配判斷，避免多余的搜索(2)判斷時盡可能充分利用以前的結(jié)果，減少匹配的重復運算。 部分搜索同樣可以和解方程、 貪心、 動態(tài)規(guī)劃等高效算法結(jié)合。部分搜索匹配算法體現(xiàn)了搜索與其他方法的有機結(jié)合，充分發(fā)揮兩者的長處，相互彌補對方的不足，這就是其高