匹配算法在搜索問(wèn)題中的巧用

1、匹配算法在搜索問(wèn)題中的巧用,浙江省杭州第十四中學(xué) 樓天城loutiancheng@sina.com,很多的題目，如果我們可以建立數(shù)學(xué)模型，應(yīng)該盡量用解析法來(lái)處理，因?yàn)楹?jiǎn)單的模型更清晰地反映了事物之間的關(guān)系。　　但是，并不是所有的題目都可以建立簡(jiǎn)單的數(shù)學(xué)模型。我們這時(shí)必須使用搜索的方法，也就是枚舉所有可能情況來(lái)尋找可行解或最優(yōu)解。,前言,由于搜索一般建立在枚舉之上，所以搜索常常和低效是分不開(kāi)的。　　有時(shí)搜索的運(yùn)算量實(shí)在太大，實(shí)

2、在是一件痛苦的事情。,于是我們需要利用很多技巧來(lái)提高效率：　　可行性剪枝， 最優(yōu)性剪枝， 調(diào)整搜索順序， 等方法都很有用，在它們的幫助下，我們可以大大提高搜索的效率。,而有些題目，這些常規(guī)的優(yōu)化方法很難有用武之地。這是我們必須使用一些非常規(guī)的搜索方法?！　”疚闹形覀儗⒂懻摲浅Ｒ?guī)搜索中的一種　　　　　　　　　——部分搜索+匹配算法,引題：　　N個(gè)物品與N個(gè)位置，給定每個(gè)物品的可能放的

3、位置集合，要求尋找一一對(duì)應(yīng)的關(guān)系?！　〉€給出物品位置之間的限制（例如：如果1放在3則2不能放在1）?！　∏笠唤M可行解，或給每一種對(duì)應(yīng)關(guān)系一個(gè)權(quán)，求滿(mǎn)足條件的最優(yōu)解。,由于事物之間的限制關(guān)系非常復(fù)雜，很難建立簡(jiǎn)單的二分圖關(guān)系，或者用網(wǎng)絡(luò)流來(lái)解決。　　面對(duì)這一系列類(lèi)似的問(wèn)題，我們一般只有搜索，如何搜索又如何優(yōu)化呢？,簡(jiǎn)單分析：　　如果我們枚舉每一個(gè)物品的位置，然后判斷。這樣的時(shí)間復(fù)雜度為O(N!)。好像似乎也只能這樣。,進(jìn)一步分析

4、：我們看一個(gè)例子，N=6：其它限制有4條(a,b,c,d)表示如果a放在b則c不能放在d1 3 5 62 2 5 33 1 4 13 2 6 2　　我們發(fā)現(xiàn)，如果我們一旦確定了3和5的位置，其它4個(gè)物品的位置之間已經(jīng)沒(méi)有限制關(guān)系了，這樣其它4個(gè)物品的位置可以通過(guò)匹配來(lái)解決。,這時(shí)我們發(fā)現(xiàn)一個(gè)新的搜索方法：部分搜索+匹配。,1 3 5 62 2 5 33 1 4 13 2 6 2,部分搜索+匹配： 搜索

5、一部分變量，使得余下的變量之間的關(guān)系簡(jiǎn)化，然后通過(guò)一些高效算法（匹配）完成余下問(wèn)題。,就本題而言就是：先搜索一定數(shù)量（而不是全部）的物品的位置，使問(wèn)題內(nèi)其它物品的關(guān)系簡(jiǎn)化為二分圖關(guān)系，用二分圖匹配來(lái)解決余下的物品。,通過(guò)部分搜索為匹配算法提供條件（例如上面的例子創(chuàng)造二分圖關(guān)系），而匹配算法代替搜索，高效地完成余下的任務(wù)?！　〔糠炙阉?匹配的方法充分發(fā)揮了搜索和匹配算法的雙重優(yōu)勢(shì)。搜索的優(yōu)勢(shì)在于應(yīng)用性廣，可以克服復(fù)雜的情況，匹配算法的優(yōu)

6、勢(shì)在于效率高。兩者相互促進(jìn)，同時(shí)也彌補(bǔ)對(duì)方的不足。這也是這個(gè)方法的成功的關(guān)鍵。,例如上面的例子，如果我們先知道了3和5的位置后，不用匹配，其實(shí)我們是在用搜索來(lái)求匹配，效率當(dāng)然不會(huì)高。,部分搜索+匹配的方法已經(jīng)在很多題目中得到了應(yīng)用。,一個(gè)部分搜索+匹配算法的經(jīng)典例子。,智破連環(huán)陣,題目簡(jiǎn)述(NOI2003二試第三題)　　B國(guó)的連環(huán)陣由M個(gè)武器組成。最初，1號(hào)武器處于攻擊狀態(tài)，其他武器都處在無(wú)敵自衛(wèi)狀態(tài)。以后，一旦第i（1 ? i<

7、;M）號(hào)武器被消滅，1秒鐘以后第i+1號(hào)武器就自動(dòng)從無(wú)敵自衛(wèi)狀態(tài)變成攻擊狀態(tài)。 　　A國(guó)有N個(gè)炸彈，每個(gè)炸彈的作用半徑均為k，且會(huì)持續(xù)爆炸5分鐘。在這5分鐘內(nèi)，瞬間消滅離它直線(xiàn)距離不超過(guò)k的、處在攻擊狀態(tài)的B國(guó)武器，不會(huì)炸毀本國(guó)炸彈。,任務(wù)：　　決定一個(gè)序列a1、a2、a3…使得在第ax號(hào)炸彈引爆的時(shí)間內(nèi)連環(huán)陣被摧毀。這里的x應(yīng)當(dāng)盡量小。輸入：　　N,M及武器和炸彈的坐標(biāo)。測(cè)試數(shù)據(jù)中的坐標(biāo)是隨機(jī)生成的。,初步分析：　　A

8、國(guó)炸彈I可以炸到B國(guó)武器J的條件： (u[I]-x[J])2+(v[I]-y[J])2<=R2,結(jié)論：很難找到求最優(yōu)解的多項(xiàng)式算法。面對(duì)此類(lèi)問(wèn)題，一般只有搜索策略。,進(jìn)一步分析：　　每一顆炸彈必定炸掉B國(guó)武器中編號(hào)連續(xù)的一段?！　?分鐘只是表明每一顆炸彈可以炸掉任意多個(gè)編號(hào)連續(xù)的B國(guó)武器。,普通的搜索方法：　　每次尋找一個(gè)編號(hào)最小的沒(méi)有被炸掉的B國(guó)武器，選擇一顆沒(méi)有使用過(guò)并能炸到此武器的A國(guó)炸彈，然后使

9、用這顆炸彈炸掉B國(guó)武器連續(xù)的一段，繼續(xù)深度優(yōu)先搜索下一顆炸彈的編號(hào)，如果發(fā)現(xiàn)B國(guó)武器已經(jīng)全部炸毀就可以回溯。　　搜索的時(shí)間復(fù)雜度為O(n!)。即使加上優(yōu)化，程序效率也不是很高。,部分搜索：　　此題使用部分搜索的算法需要一些轉(zhuǎn)化：如果已經(jīng)將B國(guó)武器根據(jù)編號(hào)分為x段，其中第I段為[Si,Ti] (S1=1,Ti>=Si,Ti+1=Si+1)?！　∪缓蟮娜蝿?wù)就是判斷是否可以從A國(guó)的N顆炸彈中選出x顆，分別可以炸掉其中的一段。,其

10、實(shí)我們把搜索分為了兩部分，?。ǎ保國(guó)武器根據(jù)編號(hào)分為x段?！。ǎ玻┡袛嗍欠窨梢詮腁國(guó)的N顆炸彈中選出x顆，分別可以炸掉其中的一段。,其實(shí)第二部分可以用匹配來(lái)解決。,建圖：C[S][T][I] 表示A國(guó)炸彈I是否可以炸到B國(guó)武器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] (

11、S<T)求C的時(shí)間復(fù)雜度為O(N3)。,建圖：左邊x個(gè)點(diǎn)，表示B國(guó)武器根據(jù)編號(hào)分為的x段，右邊N個(gè)點(diǎn)，表示A國(guó)的N顆炸彈。左邊第i個(gè)點(diǎn)到右邊第j個(gè)點(diǎn)有邊的條件即：C[Si][Ti][j]?！　∠旅嫒蝿?wù)就是將B國(guó)武器根據(jù)編號(hào)劃分為若干段+二分圖匹配判斷。,樣例1：4 3 60 6 6 6 6 0 0 01 5 0 3 1 1,性能分析（1）：　　搜索的基本框架已經(jīng)建立，雖然數(shù)據(jù)是隨機(jī)生成的，但是m個(gè)B國(guó)武器的劃

12、分方案還是非常多的，有時(shí)可能高達(dá)2m。時(shí)間上很難承受，如果使用卡時(shí)，正確性受到影響，效果不會(huì)很好?！　≈挥?個(gè)數(shù)據(jù)可以在時(shí)限內(nèi)出解，另外6個(gè)如果卡時(shí)，有2個(gè)也可以得到最優(yōu)解。,優(yōu)化： 優(yōu)化可以通過(guò)可行性和最優(yōu)性?xún)煞矫娣治觥?優(yōu)化一（最優(yōu)性）：如果A國(guó)炸彈可以重復(fù)使用，設(shè)：Dist[I]=炸掉B國(guó)武器I－m的最少使用炸彈數(shù)?！】梢杂脛?dòng)態(tài)規(guī)劃計(jì)算Dist值，狀態(tài)轉(zhuǎn)移方程如下：Dist[m+1]=0。Dist[I]=Min

13、(Dist[J]+1 | Can[I][J-1][K](1<=K<=n)) (1<=I<=N) (I<J<=N+1)求Dist的時(shí)間復(fù)雜度為O(N3)。,從而產(chǎn)生了一個(gè)最優(yōu)性剪枝條件：if (當(dāng)前已經(jīng)使用的炸彈數(shù)+Dist[當(dāng)前已經(jīng)炸掉的B國(guó)武器數(shù)+1]>=當(dāng)前找到的最優(yōu)解)then 剪枝；,優(yōu)化二（可行性）：　　部分搜索＋匹配的方法一般都可以用兩個(gè)效果很好的可行性?xún)?yōu)化：(1)提前判

14、斷是否可以匹配成功，避免多余的搜索。(2)每次匹配可以從以前的匹配開(kāi)始擴(kuò)展，不需要重新開(kāi)始。,如果當(dāng)前的劃分方法已經(jīng)無(wú)法匹配成功，就沒(méi)有搜索下去的必要了，只要每搜索新的一段時(shí)立即通過(guò)匹配判斷即可?！　∶看吻笃ヅ渲灰獜脑瓉?lái)的基礎(chǔ)上擴(kuò)展就可以了。沒(méi)有必要從頭開(kāi)始。,性能分析（2）：　　通過(guò)上述兩個(gè)優(yōu)化，程序的效率有了很大的提高?！　?10個(gè)測(cè)試數(shù)據(jù)中有8個(gè)可以在時(shí)限內(nèi)出解，另外2個(gè)如果卡時(shí)，也可以得到最優(yōu)解。,,進(jìn)一步優(yōu)化：

15、　　優(yōu)化二雖然排除了許多不必要的劃分，但是在判斷時(shí)浪費(fèi)了不少時(shí)間?！　∫虼耍诿杜e劃分長(zhǎng)度時(shí)，可以通過(guò)以前的劃分和匹配情況（被匹配的邊），用O(n2)的時(shí)間復(fù)雜度的寬度優(yōu)先搜索計(jì)算出下一個(gè)劃分的最大長(zhǎng)度maxL，顯然下一個(gè)劃分的長(zhǎng)度在[1，maxL]都一定可以找到可行的匹配。　　這樣既節(jié)省了判斷的時(shí)間，又可以使每次劃分長(zhǎng)度從長(zhǎng)到短枚舉，使程序盡快逼近最優(yōu)解，從而同時(shí)增強(qiáng)剪枝條件一的效果。,這一部分的實(shí)現(xiàn)，首先需要求MaxT。Max

16、T[I][S]=炸彈I，從S開(kāi)始炸，可以炸到的最大編號(hào)。 如果，炸彈I炸不到S，則MaxT[I][S]=S-1。求MaxT[I][S]可以用動(dòng)態(tài)規(guī)劃的方法解決。狀態(tài)轉(zhuǎn)移方程為：MaxT[I][S]= 炸彈I炸不到S S-1 　　炸彈I炸得到S MaxT[I][S+1]MaxT[I][m+1]=m求MaxT的時(shí)間復(fù)雜度為O(N2)。,具體實(shí)現(xiàn)方法： 考慮二分圖右邊

17、的n個(gè)結(jié)點(diǎn)（n顆炸彈），　　如果結(jié)點(diǎn)I沒(méi)有被匹配，I被認(rèn)為可以使用?！　∪绻Y(jié)點(diǎn)I已經(jīng)被匹配，如果從任何一個(gè)沒(méi)有匹配的結(jié)點(diǎn)出發(fā)存在一條到達(dá)I，而且I為外點(diǎn)的交錯(cuò)路，I也被認(rèn)為可以使用?！　∷訫axL=Max(MaxT[I][S] | I可以使用)；,具體實(shí)現(xiàn)方法：　　計(jì)算所有從沒(méi)有匹配點(diǎn)出發(fā)的交錯(cuò)路（沒(méi)有匹配點(diǎn)I出發(fā)的交錯(cuò)路沒(méi)有被匹配點(diǎn)I一定為外點(diǎn)）所能到達(dá)的匹配的結(jié)點(diǎn)，只要從每一個(gè)沒(méi)有匹配的結(jié)點(diǎn)出發(fā)，寬度優(yōu)先搜索，只要O(

18、N2)的時(shí)間?！　∽⒁馀袛嘀貜?fù)（如果一個(gè)已經(jīng)匹配的結(jié)點(diǎn)已經(jīng)被確定為可以使用，那么不需要對(duì)它再擴(kuò)展一次，因?yàn)楫?dāng)把這個(gè)已經(jīng)匹配的結(jié)點(diǎn)確定為可以使用的結(jié)點(diǎn)的時(shí)候，已經(jīng)從這個(gè)結(jié)點(diǎn)擴(kuò)展過(guò)，如果再擴(kuò)展必將產(chǎn)生無(wú)謂的重復(fù)）,如果已經(jīng)求出了MaxL，可以先求一組長(zhǎng)度為MaxL的匹配A，這樣對(duì)于所有長(zhǎng)度在1-MaxL范圍內(nèi)的劃分，A都是一組可行匹配。擴(kuò)展一次增廣路的復(fù)雜度為O(n2)?！　∵@樣大大節(jié)省了優(yōu)化二的時(shí)間。,性能分析（3）：　　通過(guò)以上的

19、優(yōu)化，所有數(shù)據(jù)都是瞬間出解，并且所有結(jié)果都是最優(yōu)解?！　∩踔翆?duì)n=200的隨機(jī)數(shù)據(jù)，也可以在瞬間出解，可見(jiàn)程序的效率有了很大的提高。,總結(jié)：本文中的兩個(gè)例子都可以應(yīng)用部分搜索＋匹配的方法高效解決。　　它們?cè)谒枷肷嫌兄黠@的相同點(diǎn)。一般的思維過(guò)程如下：,,一般的優(yōu)化包括：(1)提前通過(guò)匹配判斷，避免多余的搜索(2)判斷時(shí)盡可能充分利用以前的結(jié)果，減少匹配的重復(fù)運(yùn)算。,部分搜索同樣可以和解方程、

20、 貪心、 動(dòng)態(tài)規(guī)劃等高效算法結(jié)合。,部分搜索＋匹配算法體現(xiàn)了搜索與其他方法的有機(jī)結(jié)合，充分發(fā)揮兩者的長(zhǎng)處，相互彌補(bǔ)對(duì)方的不足，這就是其高效的主要原因所在?！　∫虼耍谒阉鲉?wèn)題中靈活地應(yīng)用部分搜索的方法，往往可以創(chuàng)造出奇效?！　≈档米⒁獾氖牵糠炙阉鱽?lái)解決搜索問(wèn)題作為一種非常規(guī)的搜索方法。雖然在本文的例子中，部分搜索有著很多的過(guò)人